Draft:Collinear gradients method

Submission declined on 29 December 2024 by KylieTastic (talk). This submission is not adequately supported by reliable sources. Reliable sources are required so that information can be verified. If you need help with referencing, please see Referencing for beginners and Citing sources. This draft's references do not show that the subject qualifies for a Wikipedia article. In summary, the draft needs multiple published sources that are: in-depth (not just passing mentions about the subject) reliable secondary independent of the subject Make sure you add references that meet these criteria before resubmitting. Learn about mistakes to avoid when addressing this issue. If no additional references exist, the subject is not suitable for Wikipedia. If you would like to continue working on the submission, click on the "Edit" tab at the top of the window. If you have not resolved the issues listed above, your draft will be declined again and potentially deleted. If you need extra help, please ask us a question at the AfC Help Desk or get live help from experienced editors. Please do not remove reviewer comments or this notice until the submission is accepted. Where to get help If you need help editing or submitting your draft, please ask us a question at the AfC Help Desk or get live help from experienced editors. These venues are only for help with editing and the submission process, not to get reviews. If you need feedback on your draft, or if the review is taking a lot of time, you can try asking for help on the talk page of a relevant WikiProject. Some WikiProjects are more active than others so a speedy reply is not guaranteed. How to improve a draft Wikipedia:Contributing to Wikipedia – a basic overview on how to edit Wikipedia. Help:Wikitext – how to use the markup Help:Referencing for beginners – how to include references Wikipedia:Article development – how to develop your article Wikipedia:Writing better articles – how to improve your article Wikipedia:Verifiability – make sure your article includes reliable third-party sources You can also browse Wikipedia:Featured articles and Wikipedia:Good articles to find examples of Wikipedia's best writing on topics similar to your proposed article. Improving your odds of a speedy review To improve your odds of a faster review, tag your draft with relevant WikiProject tags using the button below. This will let reviewers know a new draft has been submitted in their area of interest. For instance, if you wrote about a female astronomer, you would want to add the Biography, Astronomy, and Women scientists tags. Add tags to your draft Editor resources Easy tools: Citation bot (help) | Advanced: Fix bare URLs Declined by KylieTastic 7 months ago. Last edited by TakuyaMurata 2 months ago. Reviewer: Inform author. Resubmit Please note that if the issues are not fixed, the draft will be declined again.

In mathematics, Collinear gradients method (ColGM)^[1]  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 method family.

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

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 of a quadratic one-dimensional function ${\displaystyle J(u^{k}+bd^{k})}$:

(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 space 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 (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 ${\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[\min \left(\delta ^{k-1}{\frac {||\nabla J(u^{k})||}{||\nabla J(u^{k-1})||}},\delta ^{0}\right),\delta _{m}\right],\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) for ${\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)}$ , ${\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). 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:

 

ColGM minimization, ${\displaystyle n=2}$ 

${\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 second order — 1 iteration.

As the dimension of ${\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.

 

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

Test function Rosenbrock

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

The parameters are the same, except ${\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 \delta =0.05}$ .

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

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.).

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