Articles of numerical optimization

Remez algorithm for best degree-0ne reduced polynomials with same endpoints

Given a function $f(x)$ on [-1,1], the Remez algorithm can find the degree (at most) $n$ polynomial $P_n(x)$ that minimizes the maximum error between $P_n(x)$ and $f(x)$ on that interval. It is an iterative algorithm that finds $n+2$ nodes in the interval with extremal errors of equal magnitude and alternating signs. Is there a variant […]

Jacobian of exponential mapping in SO3/SE3

Following this post Jacobian matrix of the Rodrigues' formula (exponential map) What if I really need the Jacobian of the exponential mapping function in $\omega \neq 0$? Basically, I want to optimize $argmin_{\mathbf T} \sum_i \mathbf{e}_i(\mathbf{T}), i = 0..N $ with $\mathbf{T} \in SE(3)$ $\mathbf{e}_i(\mathbf{T}) = exp(a_i log(\mathbf{T}))\cdot P_i – P^*_i $ $a_i \in [0,1]$ […]

Calculating sin and cos based on combination of exponentiation and power series?

Taylor series for $\sin(x)$ and $\cos(x)$ around $0$ are well known and usually exercised in beginner calculus courses. However as we know Taylor series are very localized, ultimately fitting only one point and a series of limits of that one point (differentials of integer orders): $$\begin{align}\sin(x) &= \sum_{k=0}^\infty \frac{(-1)^kx^{2k+1}}{(2k+1)!} \\\cos(x) &= \sum_{k=0}^\infty \frac{(-1)^kx^{2k}}{(2k)!}\end{align}$$ We also […]

Good Textbook in Numerical PDEs?

I am currently taking a course on Numerical PDE. The course covers the following topics listed below. Chapter 1: Solutions to Partial Dierential Equations: Chapter 2: Introduction to Finite Elements:

What is the time complexity of conjugate gradient method?

I have been trying to figure out the time complexity of the conjugate gradient method. I have to solve a system of linear equations given by $$Ax=b$$ where $A$ is a sparse, symmetric, positive definite matrix. What would be the time complexity of the conjugate gradient method?

Intuition for gradient descent with Nesterov momentum

A clear article on Nesterov’s Accelerated Gradient Descent (S. Bubeck, April 2013) says The intuition behind the algorithm is quite difficult to grasp, and unfortunately the analysis will not be very enlightening either. This seems odd, for such a powerful method (“you do not really understand something unless you can explain it to your grandmother”). […]

Monotonic Function Optimization on Convex Constraint Region

So I have the following function, which I want to maximize: $$f(x_1,…,x_n) = \sum_{i=1}^n\alpha_i\sqrt{x_i}$$ (where all $\alpha_i$ are positive), subjected to the following equality and inequality constraints: $$\sum_{i=1}^nx_i = B$$ $$l_i \leq x_i \leq u_i$$ for $l_i,u_i,B$ all positive. I want to say that there’s a nice geometric way to think about this. In particular, […]

Why do we need to check both primal and dual feasibility in LP programs?

In in interior point method (and in fact in many practical optimization methods), a large part of the algorithm for finding the minimum is to follow a path called the central path while minimizing a potential function. Usually this is called the path finding algorithm or predictor-corrector method. In the explanations of this algorithm, we […]

What is the difference between projected gradient descent and ordinary gradient descent?

I just read about projected gradient descent but I did not see the intuition to use Projected one instead of normal gradient descent. Would you tell me the reason and preferable situations of projected gradient descent? What does that projection contribute?

Gradient descent with constraints

In order to find the local minima of a scalar function $p(x), x\in \mathbb{R}^3$, I know we can use the gradient descent method: $$x_{k+1}=x_k-\alpha_k \nabla_xp(x)$$ where $\alpha_k$ is the step size and $\nabla_xp(x)$ is the gradient of $p(x)$. My question is: what if $x$ must be constrained on a sphere, i.e., $\|x_k\|=1$? Then we are […]