Numerical Optimization

Step length

Convergence Theory

Zoutendijk Theorem: If the Wolfe conditions hold, then we must have $$\cos^2 \theta_k \|\nabla f_k\|^2 \rightarrow 0 \quad \cos \theta_k = \frac{-\nabla f_k^\intercal p_k}{\|\nabla f_k\| \|p_k\|}$$

If the angle is bounded amway from $90^\circ$, then $\|\nabla f_k\| \rightarrow 0$. (globally convergent)

Consider Newton-like method: $$x_{k+1} = x_k + \alpha_k p_k; \quad p_k = -B_k^{-1} \nabla f_k$$ $B_k$ is bounded and uniformly positive definite: $$\|B_k\| \|B_k^{-1}\| \leq M$$ Then $\cos \theta_k \geq 1/M$ and $\|\nabla f_k\| \rightarrow 0$.

Rate of convergence

Newton’s Methos with Hessian Modification

If the problem is not convex, far away from the solution, Newton’s direction is not necessarity a descent direction.

General framework:

Modified Symmetric Indefinite Factorization

$$PAP^\intercal = LBL^\intercal$$ A symmetric, L unit lower triangular, B bloack diagonal with blocks of dim 1 or 2, P permutation matrix. B has same number of positive and negative eigenvalues as A.

Modified version: $P(A + E)P^\intercal = L(B+F)L^\intercal$, where $E = P^\intercal LFL^\intercal P.$

Exact solution

$p^\star$ statisfies $$(B + \lambda I) p^\star = -g \quad \text{ for some } \lambda \geq 0$$

Find $\lambda > 0$ s.t. $$p(\lambda) = -(B + \lambda I)^{-1} g \quad \|p(\lambda)\| = \Delta$$ Using eigendecomposition of $B = Q\Lambda Q^\intercal$ ($\lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$), we have $$p(\lambda) = -\sum_{j=1}^n \frac{q_j^\intercal g}{\lambda_j + \lambda} q_j, \quad \|p(\lambda)\|^2 = \sum_{j=1}^n \frac{(q_j^\intercal g)^2}{(\lambda_j + \lambda)^2}$$ Note that: $\lim_{\lambda \rightarrow\infty} \|p(\lambda)\| = 0$. Good case: $q_j^\intercal g \neq 0$, then $\lim_{\lambda \rightarrow -\lambda_j} \|p(\lambda)\| = \infty$, so there must be a solution. The practical algorithm: It needs to with large enough $\lambda$.

Hard case: $q_j^\intercal g = 0$

$\lambda = -\lambda_1$, $p = -\sum_{j: \lambda_j \neq \lambda_1}^n \frac{q_j^\intercal g}{\lambda_j + \lambda} q_j$. We set $$p(\tau) = -\sum_{j: \lambda_j \neq \lambda_1}^n \frac{q_j^\intercal g}{\lambda_j + \lambda} q_j + \tau q_1.$$ There always exist $\tau$ s.t. $\|p(\tau)\| = \Delta$.

Approximate solution

1. Cauchy point

It’s easier to solve linear model: $l(p) = f + g^\intercal p$. Solve TR linear model $$p^s = \arg \min_{\|p\|\leq \Delta} f + g^\intercal p \Rightarrow p^s = -\frac{\Delta}{\|g\|}g.$$ The Cauchy point, $\tau = \arg \min_{\|\tau p^s\| \leq \Delta} m(\tau p^s)$.

2. Dogleg method (B positive definite) $p^U$ is the Cauchy point, $$p^U = -\frac{g^\intercal g}{g^\intercal B g} g.$$ $p^B$ is the Newton’s direction, $$p^B = - B^{-1} g$$

3. Two-dimensional subspace minimization

Use the linear combination of $g$ and $B^{-1}g$, $$\min_p m(p) = f + g^\intercal p + \frac{1}{2}p^\intercal B p \quad s.t. \|p\|\leq \Delta, p \in span[g, B^{-1}g]$$ If B is indefinite, we can find $\alpha$ s.t. $B + \alpha I$ is pd. If $\|(B+\alpha I )^{-1}g\| \leq \Delta$, $p = -(B+\alpha I)^{-1} g + v$, s.t. $v^\intercal (B+\alpha I)^{-1} g \leq 0$. Otherwise, $p \in span[g, (B+\alpha I )^{-1}g]$

Convergence

Algorithmic requirement : improvement in the MODEL is bounded below by some coercive function of the gradient. $$m(0) - m(p) \geq c_1 \|g\| \min(\Delta, \frac{\|g\|}{\|B\|}), c_1 \in (0,1]$$

When $\eta = 0$, $\lim \inf_{k \rightarrow \infty} \|g_k\| = 0$.

When $\eta > 0$, $\lim_{k \rightarrow \infty} g_k = 0$.

Enhancements

1. Bad scaled problem – elliptical TR:

$$\min m(p) = f + g^\intercal p + \frac{1}{2} p^\intercal B p \quad \|Dp\| \leq \Delta$$ $D$ is a diagonal matrix with positive diagonal elements.

2. Other norms: $\|p\|_1 \leq \Delta$ or $\|p\|_\infty \leq \Delta$.

This is useful in bound constrained optimization: $$\min f(x), \quad s.t. x\geq 0$$ $$\min m(p) = f + g^\intercal p + \frac{1}{2} p^\intercal B p \quad s.t. x+p\geq 0, \|p\| \leq \Delta$$ When the $\infty$-norm is used, the feasible resion is simply the rectangular box $$x + p \geq 0, \quad p \geq -\Delta 1, \quad p \leq \Delta 1$$

Linear Conjugate Gradient Method

Conjugate gradient method is an iterative method for solving a linear system of equations $$Ax = b, A \text{ is } n \times n \text{ symmetric positive definite }.$$ This is equivalent as $$\min \phi(x) = \frac{1}{2} x^\intercal A x - b^\intercal x.$$ The gradient of $\phi$ is the residual of the linear system, $$\nabla \phi(x) = Ax - b = r(x)$$

Definition: nonzero vectors $\{p_0, p_1, \cdots, p_l\}$ is conjugate with respect to the synnetric positive definite matrix A if $$p_i^\intercal A p_j = 0, i\neq j,$$ which also implies linearly independent.

1. Conjugate direction method

Given a starting point $x_0 \in \mathbb{R}^n$ and a set of conjugate directions $S = \{p_0, p_1,\cdots, p_{n-1}\}$, $$x_{k+1} = x_{k} + \alpha_k p_k,$$ where $\alpha_k$ is teh one-dimensional minimizer of $\phi$ along $x_k + \alpha p_k$, $$\alpha_k = -\frac{r_k^\intercal p_k}{p_k^\intercal A p_k}$$

2. Conjugate gradient method

The space of the search directions should coincide with the space of the residuuals. $S_k = \{r_0, r_1, \cdots, r_{k-1}\}$.

If A has only $r$ distinct eigenvalues, then the CG iteration will terminate at the solution in at most $r$ iterations.

Preconditioning

Transform the linear system to improve the eigenvalue distribution of A. $$\hat{x} = C x$$ The problem becomes $$(C^{-\intercal} A C^{-1}) \hat{x} = C^{-\intercal} b.$$

Non-Linear Conjugate Gradient Methods

The Fletcher-Reeves Method