Convex Optimization · Problem 9.27

Equality constrained minimization — Boyd & Vandenberghe

Mathematics — Optimization · analytic-center-linear-inequalities-variable-bounds

Problem

Analytic center of linear inequalities with variable bounds. Give the most efficient method for computing the Newton step of the function f(x)=−∑i=1nlog⁡(xi+1)−∑i=1nlog⁡(1−xi)−∑i=1mlog⁡(bi−aiTx),f(x) = -\sum_{i=1}^n \log(x_i + 1) - \sum_{i=1}^n \log(1 - x_i) - \sum_{i=1}^m \log(b_i - a_i^T x), with dom f={x∈Rn∣−1≺x≺1, Ax≺b}\mathbf{dom}\, f = \{x \in \mathbf{R}^n \mid -\mathbf{1} \prec x \prec \mathbf{1},\, Ax \prec b\}, where aiTa_i^T is the iith row of AA. Assume AA is dense, and distinguish two cases: m≥nm \geq n and m≤nm \leq n. (See also exercise 9.30.)
Intuitive explanation

The Newton step for this log-barrier function requires solving a linear system with the Hessian, which has a special structure: it's a sum of rank-one terms from the logarithmic barriers. The key insight is recognizing that the Hessian can be written as H=ATDA+D0H = A^T D A + D_0, where DD and D0D_0 are diagonal matrices—this allows you to use the matrix inversion lemma (Sherman–Morrison–Woodbury) to avoid explicitly forming the full Hessian. When m≥nm \geq n, solve the m×mm \times m system directly; when m≤nm \leq n, use the lemma to reduce to an m×mm \times m problem, exploiting the fact that most computational cost comes from the AA multiplications, not the diagonal terms.

Intuitive explanation

The Newton step for this log-barrier function requires solving a linear system with the Hessian, which has a special structure: it's a sum of rank-one terms from the logarithmic barriers. The key insight is recognizing that the Hessian can be written as H=ATDA+D0H = A^T D A + D_0, where DD and D0D_0 are diagonal matrices—this allows you to use the matrix inversion lemma (Sherman–Morrison–Woodbury) to avoid explicitly forming the full Hessian. When m≥nm \geq n, solve the m×mm \times m system directly; when m≤nm \leq n, use the lemma to reduce to an m×mm \times m problem, exploiting the fact that most computational cost comes from the AA multiplications, not the diagonal terms.

Related theory

Browse the problem library