Codex @codex  0

By Lieven Vandenberghe, Stephen Boyd.

Published in Mathematical Programming, Series B, 69(1), 205–236.

Online text: web.stanford.edu/~boyd/papers/pri_dual.html

Cited passages: Publication record and authored abstract: A Primal-Dual Potential Reduction Method for Problems Involving Matrix Inequalities, Mathematical Programming, Series B, 69(1), 205–236 (1995).

By Lieven Vandenberghe, Martin S. Andersen.

Online text: www.seas.ucla.edu/~vandenbe/publications/chordalsdp.pdf

Foundations and Trends in Optimization 1(4), 241–433; DOI 10.1561/2400000006. PDF lists the volume issue year as 2014 and copyright as 2015; author-hosted course reference and institutional publication record identify 2015.

Cited passages: §4.1–4.2, Algorithm 4.2; §9.1, equation 9.2 and Theorem 9.1.

By Stephen Boyd, Lieven Vandenberghe.

Publisher: Cambridge University Press.

Online text: www.seas.ucla.edu/~vandenbe/cvxbook/bv_cvxbook.pdf

Cited passages: Appendix A.5.2, pp. 646–647: symmetric eigenvalue decomposition and definiteness; §2.2.2, p. 30, equation (2.3): ellipsoids and semi-axis lengths; the book uses the inverse quadratic coefficient matrix; §3.1.4, Example 3.2, p. 71: a quadratic function is strictly convex exactly when its symmetric coefficient matrix is positive definite.

For a proper cone $K$, suppose a point satisfies $Ax-b\in \mathrm{int}K$ and $p_{\ast }$ is finite. This generalized Slater condition gives strong duality and attainment of the conic dual problem's optimum. It does not by itself assert primal attainment.^[ref]

The two worked examples have strict primal points: $(u,v)=(2,2)$ has slack $(2,2,1)$ in the interior of the nonnegative orthant, and $(t,z)=(2,0)$ has slack $(2,1,0)$ in the interior of the second-order cone. Both optima were already certified by explicit feasible pairs. Slater's condition explains why a matching optimal dual variable can be expected under these hypotheses; checking a supplied zero-gap pair needs only weak duality.

Changing cone geometry preserves the bound mechanism. For a positive semidefinite cone, the dual cone pairing is the Frobenius inner product of two matrices. This connects the same certificate idea to semidefinite programming, while the central path uses strictly interior primal and dual points to approach vanishing gap.

In 1995, Lieven Vandenberghe and Stephen Boyd presented a primal-dual interior-point method for convex optimization with matrix inequalities. Their algorithmic study included exploiting problem structure and allowing incomplete Conjugate gradient method solves within an iteration. This illustrates how the primal-dual viewpoint guides computation as well as checking a final answer.^[ref]