Convex Optimization · Problem 9.26

Equality constrained minimization — Boyd & Vandenberghe

Mathematics — Optimization · newton-equations-linear-structure

Problem

Newton equations with linear structure. Consider the problem of minimizing a function of the form

f(x) = \sum_{i=1}^N \psi_i(A_i x + b_i) \tag{9.63}

where

A_i \in \mathbf{R}^{m_i \times n}

b_i \in \mathbf{R}^{m_i}

, and the functions

\psi_i : \mathbf{R}^{m_i} \to \mathbf{R}

are twice differentiable and convex. The Hessian

H

and gradient

g

f

x

are given by

H = \sum_{i=1}^N A_i^T H_i A_i, \qquad g = \sum_{i=1}^N A_i^T g_i. \tag{9.64}

where

H_i = \nabla^2 \psi_i(A_i x + b_i)

and

g_i = \nabla \psi_i(A_i x + b_i)

. Describe how you would implement Newton's method for minimizing

f

. Assume that

n \gg m_i

, the matrices

A_i

are very sparse, but the Hessian

H

is dense.