Convex Optimization · Problem 9.11

Equality constrained minimization — Boyd & Vandenberghe

Mathematics — Optimization · gradient-newton-methods-composition

Problem

Gradient and Newton methods for composition functions. Suppose

\phi : \mathbf{R} \to \mathbf{R}

is increasing and convex, and

f : \mathbf{R}^n \to \mathbf{R}

is convex, so

g(x) = \phi(f(x))

is convex. (We assume that

f

and

g

are twice differentiable.) The problems of minimizing

f

and minimizing

g

are clearly equivalent. Compare the gradient method and Newton's method, applied to

f

and

g

. How are the search directions related? How are the methods related if an exact line search is used? Hint. Use the matrix inversion lemma (see \S C.4.3).

Related theory

Gradient Boosting As Functional Gradient Descent

Browse the problem library