Regularized SDPs#

Regularization adds a spectral penalty to the primal SDP. The unregularized problem is

\[\min_X \quad \langle C, X\rangle \quad \text{s.t.} \quad \mathcal{A}X = b,\quad X \succeq 0.\]

Write the eigendecomposition of the primal as

\[X = V \operatorname{diag}(\lambda) V^\dagger.\]

A scalar convex \(\varphi\) is applied to \(X\) spectrally, so the penalty is a sum over eigenvalues,

\[\operatorname{Tr}[\varphi(X)] = \sum_i \varphi(\lambda_i),\]

and the regularized primal objective at strength \(\varepsilon > 0\) is

\[P_\varepsilon(X) = \langle C, X\rangle + \varepsilon \operatorname{Tr}[\varphi(X)].\]

Dual-side view#

Write the dual slack as

\[S = \mathcal{A}^\dagger y - C, \qquad S = W \operatorname{diag}(s) W^\dagger.\]

The regularized dual is unconstrained and differentiable,

\[D_\varepsilon(y) = \langle b, y\rangle - \varepsilon \operatorname{Tr}\!\left[\psi\!\left(\frac{S}{\varepsilon}\right)\right], \qquad \psi(s) = \sup_t \{s t - \varphi(t)\},\]

where \(\psi\) is the Legendre transform of \(\varphi\). The map primal_from_dual inverts the first-order relation in the eigenbasis of \(S\),

\[\lambda_i(X) = \psi'\!\left(\frac{s_i}{\varepsilon}\right).\]

Built-in regularizers#

`sdplab.regularization.EntropyReg`	Entropy regularizer, \(\varphi(t) = t(\log t - 1)\).
`sdplab.regularization.QuadraticReg`	Quadratic spectral regularizer on nonnegative spectra.

Entropy regularization uses

\[\begin{split}\varphi(t) = \begin{cases} t(\log t - 1), & t > 0,\\ 0, & t = 0,\\ +\infty, & t < 0, \end{cases} \qquad \psi(s) = \exp(s).\end{split}\]

Quadratic regularization uses

\[\varphi(t) = \frac{t^2}{2} + \iota_{[0,\infty)}(t), \qquad \psi(s) = \frac{\max(s, 0)^2}{2}.\]

In both cases, the scalar formulas are lifted to matrices through the eigenvalues of Hermitian matrices.

Fixed-trace recovery#

Every method that recovers a primal takes normalized. It selects the fixed-trace conjugate – the supremum taken over unit-trace primals only – rather than the free one, so it changes the objective and not merely the reported \(X\):

\[F(S) = \sup_{X \succeq 0,\ \operatorname{Tr}[X] = 1} \ \langle S, X\rangle - \varepsilon \operatorname{Tr}[\varphi(X)].\]

The trace constraint carries a multiplier that enters additively in the argument, \(X = \psi'((S - \theta)/\varepsilon)\) with \(\theta\) fixed by \(\sum_i \psi'((s_i - \theta)/\varepsilon) = 1\). Dividing \(\psi'(S/\varepsilon)\) by its trace is not the same operation: a division preserves the ratios \(\lambda_i/\lambda_j\) and the zero pattern, while the shift changes both. For entropy the two coincide – a shift rescales \(\exp\) globally, so the answer is \(\operatorname{softmax}(S/\varepsilon)\), the Gibbs state. For the quadratic penalty the shift moves the clip point instead, so the answer is the projection onto the simplex and is genuinely low rank.

Solving#

Couple a problem to a regularizer, bind \(\varepsilon\), and hand the result to the solver. bind returns a standard single-argument spacecore.Functional, so the spacecore.optimize drivers consume it directly.

from sdplab import EntropyReg, RegularizedSDPDualFunctional, run_regularized_solver
from sdplab.examples import generate_max_cut

problem = generate_max_cut(8, seed=0, unit_trace=True)
dual = RegularizedSDPDualFunctional(problem, EntropyReg(problem.dom))

result = run_regularized_solver(dual.bind(0.1), verbose=0)
X = dual.primal_from_dual(result.dual, 0.1)

problem.primal_objective(X)     # -5.0859, against -5.0990 from CVXPY

\(\varepsilon\) is supplied per call rather than stored, so a continuation schedule can lower it without rebuilding the functional. The instance is built with unit_trace=True because primal_from_dual normalizes to \(\operatorname{Tr}[X] = 1\): on a problem whose feasible set has a different trace the recovered \(X\) would not be feasible for it.