# Gradient direction vs Steepest direction

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):

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?

• 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) – Meet Taraviya Apr 26 '17 at 9:12
• @MeetTaraviya What do you mean by saying classical gradient? I think the concept of gradient is consistent and the same for all cases. – pej Apr 26 '17 at 9:32

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).
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)$).
• 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? – pej Apr 27 '17 at 14:42
• @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 ;) – Khue Apr 27 '17 at 14:52