> For the complete documentation index, see [llms.txt](https://muhans-notebook.gitbook.io/computational-optimization/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://muhans-notebook.gitbook.io/computational-optimization/scaled-descent.md).

# Scaled Descent

* Scaled Descent
* Gauss-Newton Method
* Newton’s Method
* Diagonal Scaling

### Computing descend direction

$$x\_0$$ given; $$\varepsilon > 0$$ convergence tolerance

for $$k = 0,1,2,…$$

* choose $$d\_k$$ such that $$f(x\_k+\alpha d\_k)< f(x\_k)$$ for some small $$\alpha > 0$$ (descent direction)
* line search: choose $$\alpha\_k$$ for some small $$\alpha > 0$$ to enforce (descent)
* $$x\_{k+1}=x\_k+\alpha\_k d\_k$$
* check convergence: Exit if $$\lVert \nabla f(x\_{k+1})\rVert < \varepsilon \cdot \lVert \nabla f(x\_k)\rVert$$, e.g., $$\varepsilon=10^{-6}$$

### Scaled Descent

$$(P)$$$$\min\_{x \in \mathbb{R}^n} f(x)$$ $$f:\mathbb{R}^n \to \mathbb{R}$$ continuous differentiable

Make a change of variables:

$$x:=Sy$$ or $$y=S^{-1}x$$

where $$S$$ is ***non-singular*** and ***squares***

**Ex:**

$$\begin{bmatrix} s\_1 & & & &\ \&s\_2&&&\ & \&s\_3&& \ & & & \ddots & \ &&&\&s\_n \end{bmatrix}$$

$$Sw=0$$ iff $$w=0$$

$$S^Tv = 0$$ iff $$v=0$$

$$x=\begin{bmatrix}s\_1 & & \ & \ddots & \\&\&s\_n\end{bmatrix}\begin{bmatrix}y\_1 \ \vdots \ y\_n\end{bmatrix}$$⇒ $$x\_i=s\_iy\_i$$

$$(P\_{scaled})$$ $$\min\_{y\in \mathbb{R}^n} g(y):=f(Sy)$$

Apply gradient descent to $$(P\_{scaled})$$:

$$y\_{k+1}=y\_k-\alpha\_k \nabla g(y\_k)=y\_k-\alpha\_kS^T\nabla f(Sy\_k)$$

$$\nabla g(y) = \nabla\_y f(Sy) = S^T\nabla f(Sy)$$

application of chain rule and $$\nabla\_x (a^Tx)=a$$

“Move” to the “x-space” by pre-multiple by $$S$$:

$$Sy\_{k+1}=Sy\_k-\alpha\_kSS^T\nabla f(Sy\_k)$$

$$x\_{k+1}=x\_k-\alpha\_kSS^T\nabla f(x\_k)$$

let $$D:=SS^T$$

$$D\nabla f(x)$$ is the “scaled” gradient of $$x$$

Is $$d = -D\nabla f(x)$$ a descent direction?

$$\begin{aligned}0> \nabla f(x)^Td & =\nabla f(x)^T(-D\nabla f(x)) \ &= -\nabla f(x)^TD\nabla f(x) \ &=-\nabla f(x)SS^T\nabla f(x) \ &= -(S^T\nabla f(x))^T(S^T \nabla f(x))\ &=-\lVert S^T\nabla f(x)\rVert^2\end{aligned}$$

If $$S$$ orthogonal ⇒ $$SS^T=I$$

Scaled descent ↔ unscaled descent

$$-D\nabla f(x)$$ descent direction if $$\nabla f(x)\ne 0$$ (i.e., not stationary)

![](https://596692103-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FuVC1Ieh2j1XfxqLWFoSa%2Fuploads%2FBn4Yr4c8n0226HIvXxg9%2Fimage.png?alt=media\&token=def4fca1-a6c4-4740-a93c-527d976fabd8)![](https://596692103-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FuVC1Ieh2j1XfxqLWFoSa%2Fuploads%2FsACd1uPpqwu4gF9LWtla%2Fimage.png?alt=media\&token=859a16e8-d42f-4f69-9d49-2a68ea0ab73f)

“Perfect” quadratic function:

$$f(x)=\frac{1}{2}x^Tx=\frac{1}{2}\lVert x\rVert^2$$

$$\nabla f(x)=x$$

$$\nabla\_2 f(x)=I$$

$$\lambda\_i(I)=1$$

$$cond(A)=\frac{\lambda\_{max}(A)}{\lambda\_{min}(A)}\ge 1$$

$$g(y)=f(Sy)$$

$$\nabla g(y)=S^T\nabla f(Sy)$$

$$\nabla^2g(y)=S^T\nabla^2f(Sy)\cdot S$$

where $$\nabla^2g(y)$$ is Hessian Symmetric ⇒ $$n\times n$$

⇒ choose $$S$$ to make $$\nabla^2 g(y)=S^T\nabla^2f(x)S$$ be “well-condition”, i.e., all eigenvalues are approximately the same

### Newton’s Method

Choose $$S$$ as $$S=(\nabla^2f(x))^{-\frac{1}{2}}$$

⇒

$$\begin{aligned}SS^T &=\nabla^2 f(x)^{-\frac{1}{2}}(\nabla^2 f(x)^{-\frac{1}{2}})^T \ &=\nabla^2 f(x)^{-\frac{1}{2}} \cdot \nabla^2 f(x)^{-\frac{1}{2}} \ &= \nabla^2 f(x)^{-1}\end{aligned}$$

If $$\nabla^2 f(x)$$ is pos-def, then $$\nabla^2 f(x)=D^{-\frac{1}{2}}\cdot D^{-\frac{1}{2}}$$ for some $$D$$ non-singular

$$\begin{aligned}\nabla^2 g(y)=S^T\nabla^2f(x)S &= \nabla^2 f(x)^{-\frac{1}{2}}\nabla^2 f(x)\nabla^2 f(x)^{-\frac{1}{2}} \ &=\nabla^2 f(x)^{-\frac{1}{2}}(\nabla^2 f(x)^{\frac{1}{2}} \cdot \nabla^2 f(x)^{\frac{1}{2}})\nabla^2 f(x)^{-\frac{1}{2}}\ &=I\end{aligned}$$

### Newton’s direction at $$x$$

$$\begin{aligned}d\_N &= -SS^T\nabla f(x)\ &=-\nabla^2f(x)^{-1}\cdot \nabla f(x)\end{aligned}$$

i.e., Newton direction $$d\_N$$ is the solution of the pos-def system (linear)

Newton Equation: $$\nabla^2 f(x)\cdot d=-\nabla f(x)$$

### Newton’s Method Steps

$$x\_0$$ given; $$\varepsilon > 0$$

for $$k = 0,1,2,…$$

* $$d\_N$$ solves $$\nabla^2f(x\_k)d=-\nabla f(x\_k)$$
* line search on $$\alpha$$
* $$x\_{k+1}=x\_k+\alpha\_k d\_k$$
* check convergence, $$\lVert \nabla f(x\_k)\rVert$$ small

work $$O(n^3)$$

$$\begin{aligned}\nabla^2 f(x) & = U \Lambda U^T \text{ eigen decompose} \ &=(U\Lambda^{\frac{1}{2}})(U\Lambda^{\frac{1}{2}})^T\end{aligned}$$

Set $$S=(U\Lambda^{\frac{1}{2}})^{-T}=(\Lambda^{-\frac{1}{2}}U^{-1})^T=U^{-T}\Lambda^{-\frac{1}{2}}=U\Lambda^{-\frac{1}{2}}$$

$$\begin{aligned} \nabla^2 g(y) &= S^T\nabla^2 f(x)S\ &= (\Lambda^{-\frac{1}{2}}U^T)(U\Lambda U^T)(U\Lambda^{-\frac{1}{2}})\ &= \Lambda^{-\frac{1}{2}}\cdot \Lambda \cdot \Lambda^{-\frac{1}{2}} \ &=I\end{aligned}$$

### Gauss-Newton

$$\min\_{x\in \mathbb{R}^n} f(x):=\frac{1}{2}\lVert r(x)\rVert^2$$

$$r(x)=\begin{bmatrix}r\_1(x)\ \vdots \ r\_m(x)\end{bmatrix}$$, where $$r\_i: \mathbb{R}^n \to \mathbb{R}$$

$$\nabla f(x) = J(x)r(x)$$

**G-N iteration:**

$$\begin{aligned}x\_{k+1} &=\argmin\_x \frac{1}{2}\lVert \underbrace{r(x\_k)+J(x\_k)^T(x-x\_k)}\_{\text{linearization of r at }x\_k}\rVert^2\ &= \argmin\_x \frac{1}{2} \lVert J\_k^Tx-(J\_k^Tx\_k-r\_k)\rVert^2\ &=(J\_kJ\_k^T)^{-1}J\_k(J\_k^Tx\_k-r\_k)\ &=x\_k-(J\_kJ\_k^T)^{-1}J\_kr\_k\ &=x\_k-(J\_kJ\_k^T)^{-1}\nabla f(x\_k)\end{aligned}$$

(normal equation: $$\frac{1}{2}\lVert Ax-b\rVert^2$$⇒$$x=(A^TA)^{-1}A^Tb$$)