Implement Optimal Line Search Algorithm for Quadratic Form Objective Function

Question

I have the function $f(x)=\frac {1}{2} \mathbf x^T Q \mathbf x$.

I want to use the steepest descent algorithm where $Q$ is the diagonal matrix $\begin{bmatrix}1 & 0\\0 & 20\end{bmatrix}$ and $\mathbf x = \begin{bmatrix}0.7\\-0.2\end{bmatrix}$.

I want to implement the ideal line search algorithm: for a starting $\mathbf x$ and direction $\mathbf d$ choose $\alpha > 0$ so that $\mathbf d ^T\nabla f (\mathbf x + \alpha \mathbf d)=0$.

I have the hint that I can find $\alpha$ by substituting the formula for $\nabla f(\mathbf z)$ and then solving for $\alpha$.

I am to carry out 50 steps of the steepest descent method.

Is this something that I just need to Matlab for? I would appreciate any guidance of what I should do!

Answer 1

One does typically implement numerical algorithms in some computing environment. Matlab or Python or Mathematica will do fine, whatever you have available, or even a raw programming language without the mathy surroundings :-), like C or C++.

You describe the algorithm pretty well. At each step,

1. Determine the correct direction $\vec{d}$.
2. Execute the line search to get the $\alpha$.
3. Iterate $\vec{x}_{n+1} = \vec{x}_n + \alpha \vec{d}$.

Start with $\vec{x}_0 = [0.7, -0.2]^T$ and perform $50$ steps.

Hint #2

The most optimal guess for the direction of motion at $\vec{x}_{n}$ is $-\nabla f \left(\vec{x}_n\right)$, so we set $\vec{d} = -\nabla f \left(\vec{x}_n\right)$.

The remaining job is to define $\alpha$. You can use the hint you were given to do that.

Answer 2

You can solve it by seeing that $ d = -Q x $ namely the gradient descent.

Solving you equation will yield:

$$ \alpha = \frac{ {x}^{T} {Q}^{T} Q x }{ 2 {x}^{T} {Q}^{T} Q Q x } $$