Convex Optimization · Problem 10.12

Interior-point methods — Boyd & Vandenberghe

Mathematics — Optimization · newton-step-trace-inverse

Problem

Describe an efficient way to compute the Newton step for the problem

\begin{array}{ll} \text{minimize} & \mathbf{tr}(X^{-1}) \\ \text{subject to} & \mathbf{tr}(A_i X) = b_i, \quad i = 1, \ldots, p \end{array}

with domain

\mathbf{S}^n_{++}

, assuming

p

and

n

have the same order of magnitude. Also derive the Lagrange dual problem and give the complexity of finding the Newton step for the dual problem.