1
$\begingroup$

I am new to convex optimization and have a lot of questions about convex algorithm. Here is what I am confused when reading Prof. Boyd's book (chapter III - Algorithms): enter image description here

In the book, gradient descent method and steepest descent method are different types. As seen in the figure, the direction of negative gradient and the steepest descent direction are different.

However, what I have known before is that negative gradient points in the steepest descent direction of a level set. Thus, I thought negative gradient $-\nabla f(x)$ must be $-\nabla f(x) = c \Delta x$ where $c$ is a constant. According to the figure as well as the context of the book, $-\nabla f(x)$ does not lies in the same direction of $\Delta x$ in general. Could you please explain that?

$\endgroup$
  • $\begingroup$ From what it seems to me, gradient is the classical gradient, where as you are trying to find the steepest descent direction for a different measure of norm (Because ball of unit norm is a ellipsoid, not a sphere) $\endgroup$ – Meet Taraviya Apr 26 '17 at 9:12
  • $\begingroup$ @MeetTaraviya What do you mean by saying classical gradient? I think the concept of gradient is consistent and the same for all cases. $\endgroup$ – pej Apr 26 '17 at 9:32
3
$\begingroup$

A steepest descent direction is always associated to some norm, not necessarily the (standard) Euclidean norm (i.e. $\ell_2$). E.g. steepest descent w.r.t the $\ell_2$ norm is different than steepest descent w.r.t the $\ell_1$ norm (or every other norms).

Keep in mind that:

gradient descent = steepest descent with respect to the $\ell_2$ norm

In the above figure, the steepest descent direction is w.r.t the quadratic norm, which is different than the steepest descent direction w.r.t the $\ell_2$ norm (which is $-\nabla f(x)$).

$\endgroup$
  • $\begingroup$ Could you please illustrate the steepest descent direction with several cases of norm (with figures or some derivations)? $\endgroup$ – pej Apr 27 '17 at 14:29
  • $\begingroup$ @pej Examples are already given in the book (figures 9.9 - 9.15). $\endgroup$ – Khue Apr 27 '17 at 14:34
  • $\begingroup$ Thanks, I'll look into it. I have another question relating to this topic. For some other kinds of norm (not $l_2$ norm), the steepest descent direction seems not to be perpendicular to tangent plane, so that it may be difficult to find its direction. Can you help out to suggest any way/method/book to find the steepest descent direction? $\endgroup$ – pej Apr 27 '17 at 14:42
  • 1
    $\begingroup$ @pej The steepest descent direction is given by: $\Delta x = \arg\min_{v} \{ \nabla f(x)^\top v \ | \ ||v||\le 1 \}$, which is easy to find for $\ell_1,\ell_2$ or quadratic norms. The solutions are already given in the book (sections 9.4.1 and 9.4.2). More in-depth discussion on the choice of the norm can be found in section 9.4.4. Just read those sections and if you encounter any problems, post a new question ;) $\endgroup$ – Khue Apr 27 '17 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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