Convex Optimization · Problem 9.7

Unconstrained minimization — Boyd & Vandenberghe

Mathematics — Optimization · steepest-descent-dual-norm

Problem

Let

\|\cdot\|

be any norm on

\mathbf{R}^n

with dual norm

\|\cdot\|_*

, and let

\Delta x_{\mathrm{nsd}}

be the normalized steepest descent direction defined by

\Delta x_{\mathrm{nsd}} = \operatorname{argmin}\{\nabla f(x)^T v \mid \|v\| = 1\}.

The steepest descent step is

\Delta x_{\mathrm{sd}} = \|\nabla f(x)\|_* \Delta x_{\mathrm{nsd}}

. Show that

\nabla f(x)^T \Delta x_{\mathrm{sd}} = -\|\nabla f(x)\|_*^2.