Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am currently working through an old textbook Practical Optimization by Gill, Murray and Wright (c 1982) who make some derivations which seem correct, but I am unable to duplicate. In the equations below $g$ and $p$ are both vectors. $g$ is the gradient from the current iterate of a optimization procedure and $p$ is the search direction we wish to solve for.

The authors inform the reader that the minimum (over $p$) of

$\Large\frac{g'p}{||p||}$ is $p=-g$.

Alternatively, we might form a different norm for $p$ by considering a symmetric positive definite matrix $C$ in which case the minimizer of

$\Large\frac{g'p}{(p'Cp)^{1/2}}$ is $p=-C^{-1}g$.

I am having trouble deriving these statements.

My question is: Does it take more than a derivative and setting equal to zero to prove this? If so, how do I derive these formulas?

This question is similar to

Gradient Descent with constraints

but not identical. This other question deals with solutions that are unit length, not necessarily step directions which are unit length.

share|improve this question
    
Note that if $p$ is a minimizer in the above problems, then so is $\lambda p$, where $\lambda >0$. –  copper.hat Jan 28 '13 at 3:49

2 Answers 2

This is a simple application of Cauchy-Schwarz.

$(g^Tp)^2 \leq \|g\|^2 \|p\|^2.$

So, $-\|g\| \leq \frac{g^T p}{\|p\|} \leq \|g\| $ and the lower bound is attained when $ p = -g $.

Similarly, $ (g^T p)^2 = \langle C^{-1/2}g , C^{1/2} p\rangle^2 \leq (g^T C^{-1} g) \times (p^T C p) $ and the lower bound is similarly attained.

share|improve this answer

I prefer to look at the problem (which ends up being equivalent) of solving $\min \{ \langle g, h \rangle | \|h\| \leq 1 \}$. The norm is the standard $2$-norm. The reason I prefer this formulation is that it is closer in form to the original problem from which the search direction problem is derived. Also, it has a trust region flavor, which I personally find more appealing than a search direction/step length approach.

For the first problem, the Cauchy Bunyakovsky Schwartz Beiber inequality gives $|\langle g, h \rangle| \leq \|g\| \|h\|$, hence it is easy to see that the minimum is $\min \{ \langle g, h \rangle \,|\, \|h\| \leq 1 \} = - \|g\|$, and the minimizer is (it is unique with the $2$-norm) $h = -\frac{1}{\|g\|} g$. You could also derive this by noting that (if $g\neq 0$), the constraint $\|h\| \leq 1$ must be active, and use Lagrange multipliers to obtain the same result.

For the second, let $A^TA = C$ be the Cholesky decomposition of $C$. The problem is now $\min \{ \langle g, h \rangle \,|\, \|Ah\| \leq 1 \} = \min \{ \langle g, h \rangle \,|\, \|\delta\| \leq 1, \, h= A^{-1}\delta \} $. This is equivalent to $\min \{ \langle g, A^{-1}\delta \rangle \,|\, \|\delta\| \leq 1 \} = \min \{ \langle (A^{-1})^T g, \delta \rangle \,|\, \|\delta\| \leq 1 \}$, where $h = A^{-1}\delta$, and the first problem shows that the minimum is $-\|(A^{-1})^T g\|$ and the minimizer is $\delta = -\frac{1}{\|(A^{-1})^T g\|} (A^{-1})^Tg$, or in terms of the original problem $h = A^{-1}\delta = -\frac{1}{\|(A^{-1})^T g\|} A^{-1}(A^{-1})^Tg$. Since $A^TA = C$, we have $\|(A^{-1})^T g\| = \sqrt{\langle (A^{-1})^T g, (A^{-1})^T g \rangle} = \sqrt{\langle g, C^{-1} g \rangle}$, and $h = -\frac{1}{\sqrt{\langle g, C^{-1} g \rangle}} C^{-1} g$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.