Draft:Collinear gradients method

Collinear gradients method (ColGM)  is an iterative method of directional search for the local extremum of a smooth multivariate function $J(u):{ℝ}^n\to ℝ$, which do moving towards the extremum along the vector $d\in {ℝ}^n$ such that the gradients $\mathrm{\nabla }J(u)\parallel \mathrm{\nabla }J(u+d)$, i.e. they are collinear vectors. This is a first-order method (it uses only the first derivatives $\mathrm{\nabla }J$) with a quadratic convergence rate. It can be applied to functions of high dimension $n$ with several local extremes. GolGM can be attributed to the Truncated Newton method family.

Collinear vectors $\mathrm{\nabla }J(u^k)$ and $\mathrm{\nabla }J(u^{k\ast })$ with the direction of minimization $d^k$ for a convex function, $n=2$

The concept of the method

For a smooth function $J(u)$ in a relatively large vicinity of a point $u^k$, there is a point $u^{k_{\ast }}$, where the gradients $\mathrm{\nabla }{J}^k\stackrel{\text{def}}{=}\mathrm{\nabla }J(u^k)$ and $\mathrm{\nabla }{J}^{k_{\ast }}\stackrel{\text{def}}{=}\mathrm{\nabla }J(u^{k_{\ast }})$ are collinear vectors. The direction to the extremum $u_{\ast }$ from the point $u^k$ will be the direction $d^k={(u^{k_{\ast }}-u}^k)$. The vector $d^k$ points to the maximum or minimum, depending on the position of the point $u^{k_{\ast }}$. It can be in front or behind of $u^k$ relative to the direction to $u_{\ast }$ (see the picture). Next, we will consider minimization.

The next Template:Font color: (1) $u^{k+1}=u^k+b^k{d}^k,k\in \{0,1\dots \},$ where the optimal $b^k\in ℝ$ is found analytically from the assumption of a quadratic one-dimensional function $J(u^k+b{d}^k)$:

(2) $b^k={(1-\frac{⟨\mathrm{\nabla }J(u^{k_{\ast }},d^k⟩}{⟨\mathrm{\nabla }J(u^k),d^k⟩})}^{-1},\mathrm{\forall }{u}^{k_{\ast }}.$

Angle brackets are an inner product space in the Euclidean space ${ℝ}^n$. If $J(u)$ is a convex function in the vicinity of $u^k$, then for the front point $u^{k_{\ast }}$ we get the number $b^k>0$, for the back $b^k<0$. In any case, we follow step (1).

For a strictly convex quadratic function $J(u)$ the Template:Font color is $b^k{d}^k=-H^{-1}\mathrm{\nabla }{J}^k,$ i.e. Template:Font color (a second-order method with a quadratic convergence rate), where $H$ is the Hesse matrix. Such steps ensure the quadratic convergence rate for ColGM.

In general, if $J(u)$ has a variable convexity and saddle points are possible, then the minimization direction should be checked by the angle $\gamma$ between the vectors $\mathrm{\nabla }{J}^k$ and $d^k$. If $\cos (\gamma )=\frac{⟨\mathrm{\nabla }{J}^k,d^k⟩}{||\mathrm{\nabla }J(u^k)||||d^k||}\ge 0$, then $d^k$ is the direction of maximization, and in (1) we should take $b^k$ with the opposite sign.

Search for collinear gradients

Template:Font color is estimated by the residual of their directions, which has the form of a system of $n$ equations for search a root $u=u^{k_{\ast }}$: (3) $r^k(u)=\frac{\mathrm{\nabla }J(u)}{||\mathrm{\nabla }J(u)||}s-\frac{\mathrm{\nabla }J(u^k)}{||\mathrm{\nabla }J(u^k)||}=0\in {ℝ}^n,$ where the sign $s=\mathrm{sgn}⟨\mathrm{\nabla }J(u),\mathrm{\nabla }J(u^k)⟩$, this allows us to equally evaluate the collinearity of gradients, both co-directional and oppositely directed, $||r^k(u)||\le \sqrt{2}$.

System (3) is solved iteratively (sub-iterations $l$) by the conjugate gradient method, assuming that the system is linear in the $u^k$-vicinity:

(4) $u^{k_{l+1}}=u^{k_l}+{\tau }^l{p}^l,l=1,2\dots ,$

where vector $p^l\stackrel{\text{def}}{=}p(u^{k_l})=-r^l+{{\beta }^{l}p}^{l-1}$, $r^l\stackrel{\text{def}}{=}r(u^{k_l})$, ${\beta }^l=||r^l|{|}^2/||r^{l-1}|{|}^2,{\beta }^{1,n,2n...}=0$, ${\tau }^l=||r^l|{|}^2/⟨p^l,H^l{p}^l⟩$, the product of the Hesse matrix $H^l$ by $p^l$ is found by numerical differentiation:

(5) $H^l{p}^l\approx \frac{r(u^{k_h})-r(u^{k_l})}{h/||p^l||},$

where $u^{k_h}=u^{k_l}+h{p}^l/||p^l||$, $h$ is a small positive number such that $⟨p^l,H^l{p}^l⟩\ne 0$.

The initial approximation is set at 45° to all coordinate axes and ${\delta }^k$-length:

(6) $u_i^{k_1}=u_i^k+\frac{{\delta }^k}{\sqrt{n}}\mathrm{sgn}{{\mathrm{\nabla }}_{i}J}^k,i=1\dots n.$

The initial radius ${\delta }^k$ is the vicinity of the point $u^k$ and it is modifid:

(7) ${\delta }^k=\max [\min ({\delta }^{k-1}\frac{||\mathrm{\nabla }J(u^k)||}{||\mathrm{\nabla }J(u^{k-1})||},{\delta }^0),{\delta }_m],k>0.$

Necessary $||u^{k_l}-u^k||\ge {\delta }^m,l\ge 1$. Here, the small positive number ${\delta }_m$ is noticeably larger than the machine epsilon.

Sub-iterations $l$ terminate when at least one of the conditions is met:

1. $||r^l||\le c_1\sqrt{2},0\le c_1<1$ — accuracy achieved;
2. $\left|\frac{||r^l||-||r^{l-1}||}{||r^l||}\right|\le c_1,l>1$ — convergence has stopped;
3. $l\le l_{max}=\mathrm{integer}|c_2\ln c_1\ln n|,c_2\ge 1$ — redundancy of sub-iterations.

Algorithm for choosing the minimization direction

• Parameters: $c_1,c_2,{\delta }^0,{\delta }_m=10^{-15}{\delta }^0,h=10^{-5}$.
• Input data: $n,k=0,u^k,J(u^k),\mathrm{\nabla }J(u^k),\mathrm{\nabla }{J}^k$.

1. $l=1$. If $k>0$ then set ${\delta }^k$ from (7).
2. Find $u^{k_l}$ from (6).
3. Calculate $\mathrm{\nabla }{J}^l,||\mathrm{\nabla }{J}^l||$. Find $r^l$ from (3) for $u=u^{k_l}$.
4. If $||r^l||\le c_1\sqrt{2}$ or $l\ge l_{max}$ or $||u^{k_l}-u^k||<{\delta }_m$ or {$l>1$ and $\left|\frac{||r^l||-||r^{l-1}||}{||r^l||}\right|\le c_1$} then set $u^{k_{\ast }}=u^{k_l}$, return $\mathrm{\nabla }J\left(u^{k_{\ast }}\right)$, $d^k={(u^{k_{\ast }}-u}^k)$, Template:Font color.
5. If $l\ne 1,n,2n,3n\dots$ then set ${\beta }^l=||r^l|{|}^2/||r^{l-1}|{|}^2$ else ${\beta }^l=0$.
6. Find $p^l=-r^l+{\beta }^l{p}^{l-1}$.
7. Searching for ${\tau }^l$:
   1. Memorize $u^{k_l}$, $\mathrm{\nabla }{J}^l$, $||\mathrm{\nabla }{J}^l||$, $r^l$, $||r^l||$;
   2. Find $u^{k_h}=u^{k_l}+h{p}^l/||p^l||$. Calculate $\mathrm{\nabla }J(u^{k_h})$ and $r\left(u^{k_h}\right)$. Find $H^l{p}^l$ from (5) and assign $w\leftarrow ⟨p^l,H^l{p}^l⟩$;
   3. If $w=0$ then $h\leftarrow 10h$ and return to step 7.2;
   4. Restore $u^{k_l}$, $\mathrm{\nabla }{J}^l$, $||\mathrm{\nabla }{J}^l||$, $r^l$, $||r^l||$;
   5. Set ${\tau }^l=||r^l|{|}^2/w$.
8. Perform sub-iteration $u^{k_{l+1}}$ from (4).
9. $l\leftarrow l+1$, Go to step 3

The parameter $c_2=3÷5$. For functions without saddle points, we recommend $c_1\approx 10^{-8}$, $\delta \approx {10}^{-5}$. To "bypass" saddle points, we recommend $c_1\approx 0.1$, $\delta \approx 0.1$.

The described algorithm allows us to approximately find collinear gradients from the system of equations (3). The resulting direction $b^k{d}^k$ for the ColGM algorithm (1) will be Template:Font color (truncated Newton method).

Demonstrations

In all the demonstrations, ColGM shows convergence no worse and sometimes even better (for functions of variable convexity) than Newton's method.

The "rotated ellipsoid" test function

A strictly convex quadratic function:

ColGM minimization, $n=2$

$J(u)=\sum _{i=1}^n{\left(\sum _{j=1}^i{u}_j\right)}^2,u_{\ast }=(0...0).$

In the drawing, three black starting points $u^0$ are set for $n=2$. The gray dots are sub-iterations of $u^{0_l}$ with ${\delta }^0=0.5$ (shown as a dotted line, inflated for demonstration). Parameters $c_1=10^{-8}$, $c_2=4$. It took one iteration for all $u^0$ and no more than two sub-iterations $l$.

For $n=1000$ (parameter ${\delta }^0={10}^{-5}$) with the starting point $u^0=(-1...1)$ ColGM achieved $u_{\ast }$ with an accuracy of 1% in 3 iterations and 754 calculations $J$ and $\mathrm{\nabla }J$. Other first-order methods: Quasi-Newtonian BFGS (working with matrices) required 66 iterations and 788 calculations; conjugate gradients (Fletcher—Reeves) - 274 iterations and 2236 calculations; Newton's finite difference method — 1 iteration and 1001 calculations. Newton's method second order — 1 iteration.

As the dimension of $n$ increases, computational errors in the implementation of the collinearity condition (3) may increase markedly. Because of this, the ColGM, in comparison with the Newton's method, in the considered example required more than one iteration.

ColGM minimization: 3 iterations and 16 calculations $J$ and $\mathrm{\nabla }J$

Test function Rosenbrock

$J(u)=100(u_1^2-u_2{)}^2+(u_1-1{)}^2,u_{\ast }=(1,1).$

The parameters are the same, except ${\delta }^0={10}^{-5}$. The descent trajectory of the ColGM completely coincides with the Newton's method. In the drawing, the blue starting point is $u^0=(-0.8;-1.2)$, and the red one is $u_{\ast }$. Unit vector of the gradient are drawn at each point $u^k$.

Test function Himmelblau function

$J(u)=(u_1^2+u_2-11{)}^2+(u_1+u_2^2-7{)}^2.$

Parameters $c_1=0.1$, $\delta =0.05$.

ColGM minimization: 7 iterations and 22 calculations $J$ and $\mathrm{\nabla }J$. The red lines are $\cos \gamma \ge 0$.	| Minimization by Newton's method: 9 iterations ($b^k=1$)
Minimization by conjugate gradient method (Fletcher-Reeves): 9 iterations and 62 calculations $J$ and $\mathrm{\nabla }J$	| Minimization by quasi-Newton BFGS: 6 iterations and 55 calculations $J$ and $\mathrm{\nabla }J$. Red line (violation of the curvature condition) — steepest descent method.

Template:Font color in terms of the number of calculations $J$ and $\mathrm{\nabla }J$. Due to formula (2), it does not require expensive calculations of the step multiplier $b^k$ by linear search (for example, golden-section search, etc.).