Problem to find exact solution with steepest descent

Question

I have a problem that is formulated as this: $$\begin{matrix}\min\\x \in \mathbb{R}^2\end{matrix} f(\mathbf{x}) := (2 x_1^2 - x_2^2)^2 + 3x_1^2-x_2$$ The task is: Perform one iteration using the steepest descent algorithm when $\mathbf{x}_0 = (1/2, 5/4)^T$.

And I get the solution to be: $\mathbf{x}_1 = (1/2, 3/4)^T$

but it should be: $\mathbf{x}_1 = (1/2, 1)^T$

This is how I solved it:

1. $\mathbf{p}_k = -\nabla f(\mathbf{x}_k)$
2. $\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \cdot \mathbf{p}_k$ Since nothing is said about choosing $\alpha$ I set it to $\alpha = 1$.

$\nabla f(\mathbf{x}) = (8x_1(2x_1^2-x_2) + 6x_1, -2(2x_1^2-x_2)-1)^T = (16x_1^3 - 8x_1x_2 + 6x_1, -4x_1^2+2x_2-1)^T$

$\nabla f(\mathbf{x}_0) = (0, 1/2)^T, \mathbf{p}_k = (0, -1/2)^T$

$\mathbf{x}_1 = \mathbf{x}_0 + 1 \cdot (0, -1/2)^T = (1/2, 3/4)$

I think it depends on that I picked my $\alpha$ to be 1 but it gets correct when it's 1/2. So why should $\alpha = 1/2$? Should I use Armijo step rule to find out, or how?

Answer 1

Let $x_1=x$ and $x_2=y$ and $y^2\leq\frac{3}{4}$.

Thus, by AM-GM $$(2x^2-y^2)^2+3x^2-y=4x^4-4x^2y^2+3x^2+y^4-y=$$ $$\geq x^2(4x^2+3-4y^2)+y^4-y\geq y^4-y=$$ $$=y^4+\frac{3}{4\sqrt[3]4}-y-\frac{3}{4\sqrt[3]4}\geq4\sqrt[4]{y^4\left(\frac{1}{4\sqrt[3]4}\right)^3}-y-\frac{3}{4\sqrt[3]4}=$$ $$=|y|-y-\frac{3}{4\sqrt[3]4}\geq-\frac{3}{4\sqrt[3]4}.$$ The equality occurs for $x=0$ and $y=\frac{1}{\sqrt[3]4}.$

Now, let $y^2\geq\frac{3}{4}$.

Thus, $$(2x^2-y^2)^2+3x^2-y=$$ $$=4x^4-(4y^2-3)x^2+\left(y^2-\frac{3}{4}\right)^2+y^4-\left(y^2-\frac{3}{4}\right)^2-y\geq$$ $$\geq y^4-\left(y^2-\frac{3}{4}\right)^2-y=\frac{3}{2}y^2-y-\frac{9}{16}\geq\frac{3}{4}+\frac{1}{2}y^2-y-\frac{9}{16}\geq$$ $$\geq\frac{3}{4}-\frac{1}{2}-\frac{9}{16}=-\frac{5}{16}>-\frac{3}{4\sqrt[3]4},$$ which says that $-\frac{3}{4\sqrt[3]4}$ it's a minimal value.

Answer 2

David K You were right about the $\alpha$ so I looked again and I managed to find my error. The thing I forgot was that I need to minimize $\alpha$ using: $$\begin{matrix} min \\ \alpha \ge 0 \end{matrix} \varphi(\alpha) = f(\mathbf{x}_k - \alpha \nabla f(\mathbf{x}_k))$$ Which we do by finding the stationary points as: $\varphi'(\alpha) = 0$

$\varphi'(\alpha) = \nabla f(\mathbf{x}_k - \alpha f(\mathbf{x}_k))^T(-\nabla f(\mathbf{x}_k))$

$\varphi'(\alpha) = -\nabla f(\mathbf{x}_0 - \alpha f(\mathbf{x}_0))^T \cdot \nabla f(\mathbf{x}_0)$

$\nabla f(\mathbf{x}) = (16x_1^3 - 8x_1x_2 + 6x_1, -4x_1^2+2x_2-1)^T$

Using this with $\mathbf{x}_0 = ( \frac{1}{2}, \frac{5}{4} )^T$

I get: $\nabla f(\mathbf{x}_0) = (0, \frac{1}{2})^T$ so

$\varphi'(\alpha) = - 0 \cdot \nabla f_1 - \frac{1}{2} \nabla f_2 = -\frac{1}{2} \nabla f_2 = 0$ where $\nabla f_2 = -4x_1^2+2x_2-1$. Plugging in values gives: $-\frac{1}{2} \nabla f_2((\frac{1}{2}, \frac{5}{4})^T - \alpha (0, \frac{1}{2})^T) = -\frac{1}{2}(-4 (\frac{1}{2})^2+2(\frac{5}{4} - \frac{1}{2}\alpha)-1) = 0 \iff (\frac{5}{2} - \alpha) = 2 \iff \alpha = \frac{1}{2}$ and $\alpha > 0$ so solution is ok. Then plugging in this $\alpha$ in the original post solves the problem.