Armijo rule intuition and implementation

Question

I am minimizing a convex function $f(x,y)$ using the steepest descent method: $$\mathbf{x}_{n+1}=\mathbf{x}_n-\gamma \nabla F(\mathbf{x}_n),\ n \ge 0$$

My function is defined over a specific domain $D = \{(x, y) \in R^2 : 2x^2+y^2 < 10\}$, if my $x_{n+1}$ goes out of bound, my method diverge. I was told to choose $\gamma$ using armijo rule to stay inbound.

Can someone explain to me the method and also describe a pseudo code for implementing it?

Answer 1

Pseudo Code for Steepest Descent using Armijo's Rule:

Given $x_k$, $maxiter$, other conditions

Compute $\nabla F(x_k)$

$objold \leftarrow 0$

Define $\sigma \ \& \beta$ [between $(0,1)$]

while $(iter < maxiter)$ && (other conditions)

$flag \leftarrow 0$

$s_k \leftarrow 1$

while $flag \neq 1$

$x_{new} = x_k-s_k \nabla F(x_k)$

if $x_{proj} \notin D$

$x_{proj}=P_D (x_{new})$ [Projection operation - here it will be the point where the line joining the $x_{new}$ and $(0,0)$ cuts the ellipse.]

end

$objnew = F(x_{proj})$

if $(objnew-objold) \leq \sigma*\nabla F(x_k)'*(x_{proj}-x_k)$

$flag \leftarrow 1$

else

$s_k \leftarrow s_k\times\beta$

end

end

$x_k \leftarrow x_{proj}$

Compute $\nabla F(x_k)$

$objold \leftarrow objnew$

end

(Point to be noted: there are various ways to implement it.)