Convex Optimization · Problem 9.28

Equality constrained minimization — Boyd & Vandenberghe

Mathematics — Optimization · analytic-center-quadratic-inequalities

Problem

Analytic center of quadratic inequalities. Describe an efficient method for computing the Newton step of the function

f(x) = -\sum_{i=1}^m \log(-x^T A_i x - b_i^T x - c_i),

with

\mathbf{dom}\, f = \{x \mid x^T A_i x + b_i^T x + c_i < 0,\ i = 1, \ldots, m\}

. Assume that the matrices

A_i \in \mathbf{S}_{++}^n

are large and sparse, and

m \ll n

. Hint. The Hessian and gradient of

f

x

are given by

H = \sum_{i=1}^m (2\alpha_i A_i + \alpha_i^2 (2A_i x + b_i)(2A_i x + b_i)^T), \qquad g = \sum_{i=1}^m \alpha_i(2A_i x + b_i),

where

\alpha_i = 1/(-x^T A_i x - b_i^T x - c_i)