Misplaced Pages

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages) The topic of this article may not meet Misplaced Pages's general notability guideline. Please help to demonstrate the notability of the topic by citing reliable secondary sources that are independent of the topic and provide significant coverage of it beyond a mere trivial mention. If notability cannot be shown, the article is likely to be merged, redirected, or deleted. Find sources: "Collinear gradients method" – news · newspapers · books · scholar · JSTOR (January 2025) (Learn how and when to remove this message) This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources. Find sources: "Collinear gradients method" – news · newspapers · books · scholar · JSTOR (January 2025) This article is written like a manual or guide. Please help rewrite this article and remove advice or instruction. (January 2025) (Learn how and when to remove this message)

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

The concept of the method

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

The next iteration of ColGM:

(1) ${\displaystyle \quad u^{k+1}=u^{k}+b^{k}d^{k},\quad k\in \left\{0,1\dots \right\},}$

where the optimal ${\displaystyle b^{k}\in \mathbb {R} }$ is found analytically from the assumption that the one-dimensional function ${\displaystyle J(u^{k}+bd^{k})}$ is quadratic:

(2) ${\displaystyle \quad b^{k}=\left(1-{\frac {\langle \nabla J(u^{k_{\ast }},d^{k}\rangle }{\langle \nabla J(u^{k}),d^{k}\rangle }}\right)^{-1},\quad \forall u^{k_{\ast }}.}$

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

For a strictly convex quadratic function ${\displaystyle J(u)}$ the ColGM step is

 ${\displaystyle b^{k}d^{k}=-H^{-1}\nabla J^{k},}$

i.e. it is a Newton's step (a second-order method with a quadratic convergence rate), where ${\displaystyle H}$ is the Hesse matrix. Such steps ensure the quadratic convergence rate for ColGM.

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

Search for collinear gradients

Collinearity of gradients is estimated by the residual of their directions, which has the form of a system of ${\displaystyle n}$ equations for search a root ${\displaystyle u=u^{k_{\ast }}}$:

(3) ${\displaystyle \quad r^{k}(u)={\frac {\nabla J(u)}{||\nabla J(u)||}}s-{\frac {\nabla J(u^{k})}{||\nabla J(u^{k})||}}=0\in \mathbb {R} ^{n},}$

where the sign ${\displaystyle s=\operatorname {sgn} \langle \nabla J(u),\nabla J(u^{k})\rangle }$, this allows us to equally evaluate the collinearity of gradients, both co-directional and oppositely directed, ${\displaystyle ||r^{k}(u)||\leq {\sqrt {2}}}$.

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

(4) ${\displaystyle \quad u^{k_{l+1}}=u^{k_{l}}+\tau ^{l}p^{l},\quad l=1,2\ldots ,}$

where vector ${\displaystyle \;p^{l}\;{\overset {\textrm {def}}{=}}\,p(u^{k_{l}})=-r^{l}+{\beta ^{l}p}^{l-1}}$, ${\displaystyle \;r^{l}\,{\overset {\textrm {def}}{=}}\,r(u^{k_{l}})}$, ${\displaystyle \;\beta ^{l}=||r^{l}||^{2}/||r^{l-1}||^{2},\ \beta ^{1,n,2n...}=0}$, ${\displaystyle \;\tau ^{l}=||r^{l}||^{2}/\langle p^{l},H^{l}p^{l}\rangle }$, the product of the Hesse matrix ${\displaystyle H^{l}}$ by ${\displaystyle p^{l}}$ is found by numerical differentiation:

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

where ${\displaystyle u^{k_{h}}=u^{k_{l}}+hp^{l}/||p^{l}||}$, ${\displaystyle h}$ is a small positive number such that ${\displaystyle \langle p^{l},H^{l}p^{l}\rangle \neq 0}$.

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

(6) ${\displaystyle \quad u_{i}^{k_{1}}=u_{i}^{k}+{\frac {\delta ^{k}}{\sqrt {n}}}\operatorname {sgn} {\ \nabla _{i}J}^{k},\quad i=1\ldots n.}$

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

(7) ${\displaystyle \quad \delta ^{k}=\max \left,\quad k>0.}$

Necessary ${\displaystyle ||u^{k_{l}}-u^{k}||\geq \delta ^{m},\;l\geq 1}$. Here, the small positive number ${\displaystyle \delta _{m}}$ is noticeably larger than the machine epsilon.

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

1. ${\displaystyle ||r^{l}||\leq c_{1}{\sqrt {2}},\quad 0\leq c_{1}<1}$ — accuracy achieved;
2. ${\displaystyle \left|{\frac {||r^{l}||-||r^{l-1}||}{||r^{l}||}}\right|\leq c_{1},\quad l>1}$ — convergence has stopped;
3. ${\displaystyle l\leq l_{max}=\operatorname {integer} \left|c_{2}\ln c_{1}\ln n\right|,\quad c_{2}\geq 1}$ — redundancy of sub-iterations.

Algorithm for choosing the minimization direction

• Parameters: ${\displaystyle c_{1},c_{2},\delta ^{0},\delta _{m}=10^{-15}\delta ^{0},h=10^{-5}}$.
• Input data: ${\displaystyle n,k=0,u^{k},J(u^{k}),\nabla J(u^{k}),\nabla J^{k}}$.

1. ${\displaystyle l=1}$. If ${\displaystyle k>0}$ then set ${\displaystyle \delta ^{k}}$ from (7).
2. Find ${\displaystyle u^{k_{l}}}$ from (6).
3. Calculate ${\displaystyle \nabla J^{l},||\nabla J^{l}||}$. Find ${\displaystyle r^{l}}$ from (3) when ${\displaystyle u=u^{k_{l}}}$.
4. If ${\displaystyle ||r^{l}||\leq c_{1}{\sqrt {2}}\,}$ or ${\displaystyle l\geq l_{max}}$ or ${\displaystyle ||u^{k_{l}}-u^{k}||<\delta _{m}}$ or {${\displaystyle \,l>1}$ and ${\displaystyle \left|{\frac {||r^{l}||-||r^{l-1}||}{||r^{l}||}}\right|\leq c_{1}}$} then set {${\displaystyle u^{k_{\ast }}=u^{k_{l}}}$, return ${\displaystyle \nabla J\left(u^{k_{\ast }}\right)}$ and ${\displaystyle d^{k}={(u^{k_{\ast }}-u}^{k})}$, stop}.
5. If ${\displaystyle l\neq 1,n,2n,3n\ldots }$ then set ${\displaystyle \beta ^{l}=||r^{l}||^{2}/||r^{l-1}||^{2}}$ else ${\displaystyle \beta ^{l}=0}$.
6. Find ${\displaystyle p^{l}=-r^{l}+\beta ^{l}p^{l-1}}$.
7. Searching for ${\displaystyle \tau ^{l}}$:
   1. Memorize ${\displaystyle u^{k_{l}}}$, ${\displaystyle \nabla J^{l}}$, ${\displaystyle ||\nabla J^{l}||}$, ${\displaystyle r^{l}}$, ${\displaystyle ||r^{l}||}$;
   2. Find ${\displaystyle u^{k_{h}}=u^{k_{l}}+hp^{l}/||p^{l}||}$. Calculate ${\displaystyle \nabla J(u^{k_{h}})}$ and ${\displaystyle r\left(u^{k_{h}}\right)}$. Find ${\displaystyle H^{l}p^{l}}$ from (5) and assign ${\displaystyle w\leftarrow \langle p^{l},H^{l}p^{l}\rangle }$;
   3. If ${\displaystyle w=0}$ then ${\displaystyle h\leftarrow 10h}$ and return to step 7.2;
   4. Restore ${\displaystyle u^{k_{l}}}$, ${\displaystyle \nabla J^{l}}$, ${\displaystyle ||\nabla J^{l}||}$, ${\displaystyle r^{l}}$, ${\displaystyle ||r^{l}||}$;
   5. Set ${\displaystyle \tau ^{l}=||r^{l}||^{2}/w}$.
8. Perform sub-iteration ${\displaystyle u^{k_{l+1}}}$ from (4).
9. ${\displaystyle l\leftarrow l+1}$, Go to step 3

The parameter ${\displaystyle c_{2}=3\div 5}$. For functions without saddle points, we recommend ${\displaystyle c_{1}\approx 10^{-8}}$, ${\displaystyle \delta \approx {10}^{-5}}$. To "bypass" saddle points, we recommend ${\displaystyle c_{1}\approx 0.1}$, ${\displaystyle \delta \approx 0.1}$.

The described algorithm allows us to approximately find collinear gradients from the system of equations (3). Therefore, the resulting direction ${\displaystyle b^{k}d^{k}}$ for the ColGM algorithm (1) will be approximate Newton direction (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:

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

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

For ${\displaystyle {\color {red}n=1000}}$ (parameter ${\displaystyle \delta ^{0}={10}^{-5}}$) with the starting point ${\displaystyle u^{0}=(-1...1)}$ ColGM achieved ${\displaystyle u_{\ast }}$ with an accuracy of 1% in 3 iterations and 754 calculations ${\displaystyle J}$ and ${\displaystyle \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 of the second order — 1 iteration.

As the dimension ${\displaystyle \color {red}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.

Test function Rosenbrock

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

Parameters ${\displaystyle c_{1}=10^{-8}}$, ${\displaystyle c_{2}=4}$, ${\displaystyle \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 ${\displaystyle u^{0}=\left(-0.8;-1.2\right)}$, and the red one is ${\displaystyle u_{\ast }}$. Unit vector of the gradient are drawn at each point ${\displaystyle u^{k}}$.

Test function Himmelblau function

${\displaystyle J(u)=(u_{1}^{2}+u_{2}-11)^{2}+(u_{1}+u_{2}^{2}-7)^{2}.}$

Parameters ${\displaystyle c_{1}=0.1}$, ${\displaystyle c_{2}=4}$, ${\displaystyle \delta ^{0}=0.05}$.

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

v t e Optimization: Algorithms, methods, and heuristics
Unconstrained nonlinear Functions Golden-section search Powell's method Line search Nelder–Mead method Successive parabolic interpolation Gradients Convergence Trust region Wolfe conditions Quasi–Newton Berndt–Hall–Hall–Hausman Broyden–Fletcher–Goldfarb–Shanno and L-BFGS Davidon–Fletcher–Powell Symmetric rank-one (SR1) Other methods Collinear gradients method Conjugate gradient Gauss–Newton Gradient Mirror Levenberg–Marquardt Powell's dog leg method Truncated Newton Hessians Newton's method
Constrained nonlinear General Barrier methods Penalty methods Differentiable Augmented Lagrangian methods Sequential quadratic programming Successive linear programming
Convex optimization Convex minimization Cutting-plane method Reduced gradient (Frank–Wolfe) Subgradient method Linear and quadratic Interior point Affine scaling Ellipsoid algorithm of Khachiyan Projective algorithm of Karmarkar Basis-exchange Simplex algorithm of Dantzig Revised simplex algorithm Criss-cross algorithm Principal pivoting algorithm of Lemke Active-set method
Combinatorial Paradigms Approximation algorithm Dynamic programming Greedy algorithm Integer programming Branch and bound/cut Graph algorithms Minimum spanning tree Borůvka Prim Kruskal Shortest path Bellman–Ford SPFA Dijkstra Floyd–Warshall Network flows Dinic Edmonds–Karp Ford–Fulkerson Push–relabel maximum flow
Metaheuristics Evolutionary algorithm Hill climbing Local search Parallel metaheuristics Simulated annealing Spiral optimization algorithm Tabu search
Software

References

1. Tolstykh V.K. Collinear Gradients Method for Minimizing Smooth Functions // Oper. Res. Forum. — 2023. — Vol. 4. — No. 20. — doi: s43069-023-00193-9
2. Tolstykh V.K. Free demo Windows application Optimization

• Optimization algorithms and methods