Problem

Show the one dimensional minimizer of a strong convex quadrative function

Solution:

1. State the quadractic function:

$$f(x) = \frac{1}{2}x^TQx - b^Tx$$

1. We know the minimizer is along the descent direction of a given point thus we are searching along the path $$x_k + \alpha p_k$$
   
   
   

2. Plug (2) into the function:

$$f(x) = \frac{1}{2}x^TQx - b^Tx$$

$$f(x) = \frac{1}{2}(x_k + \alpha p_k)^TQ(x_k + \alpha p_k) - b^T(x_k + \alpha p_k)$$

1. Simplify: $$f(x) = \frac{1}{2}(x_k Q + \alpha p_k Q)^T(x_k + \alpha p_k) - b^T x_k + \alpha b^T p_k)$$
   
   
   $$f(x) = \frac{1}{2}((x_k^T Q x_k) + (x_k^T Q \alpha p_k) + (\alpha p_k^T Q x_k) + (\alpha p_k Q \alpha p_k)) - b^T x_k + \alpha b^T p_k)$$
   
   
   $$f(x) = \frac{1}{2} ((x_k^T Q x_k) + (\alpha x_k^T Q p_k) + (\alpha p_k^T Q x_k) + (\alpha^2 p_k Q p_k)) - b^T x_k + \alpha b^T p_k)$$
   
   
   

$$f(x) = \frac{1}{2}(x_k^T Q x_k) + \alpha x_k^T Q p_k + (\frac{\alpha^2}{2} p_k Q p_k)) - b^T x_k + \alpha b^T p_k)$$

1. Calculate the $\frac{\delta F}{\delta x}(x_k + \alpha p_k)$

$$ x_k^T Q p_k + \alpha p_k Q p_k - b^T p_k$$

1. Set equal to 0 and solve for $\alpha$

$$ x_k^T Q p_k + \alpha p_k Q p_k - b^T p_k = 0 $$

$$ \alpha p_k Q p_k = b^T p_k - x_k^T Q p_k $$

$$ \alpha = \frac{b^T p_k - x_k^T Q p_k}{p_k Q p_k} $$

$$ \alpha = \frac{- x_k^T Q p_k + b^T p_k}{p_k Q p_k} $$

$$ \alpha = \frac{- x_k^T Q p_k + b^T p_k}{p_k Q p_k} $$

1. subsitute $\nabla f(x) = Q x_k - b$

$$ \alpha = \frac{- x_k^T \nabla f_k p_k}{p_k Q p_k} $$