Duality in SDPs - Ciallo Wiki

1 Primal Semidefinite Programs

1.1 Standard primal form

A primal semidefinite program (SDP) seeks to optimize a linear objective over the intersection of an affine set with the cone of positive semidefinite matrices. A standard form is \[ \begin{aligned} \text{minimize}\quad & \langle C, X\rangle\\ \text{subject to}\quad & \langle A_i, X\rangle = b_i,\quad i=1,\dots,m,\\ & X\succeq 0, \end{aligned} \] where \(X\) is the decision matrix (typically symmetric), \(C\) and \(A_i\) are given symmetric matrices of the same size, \(b\in\mathbb{R}^m\), and \(\langle U,V\rangle=\mathrm{trace}(U^\top V)\) denotes the matrix inner product.

1.2 Feasible sets and positive semidefinite cones

The feasible region is defined by two ingredients: linear equalities \(\langle A_i, X\rangle=b_i\) and the semidefinite constraint \(X\succeq 0\). The constraint \(X\succeq 0\) restricts \(X\) to the semidefinite cone, a convex cone consisting of all symmetric positive semidefinite matrices. This cone has a rich geometric structure (faces, exposed faces, and rank-deficient boundary points) that directly influences duality behavior.

1.3 Objective functions and constraint structure

In standard SDP form, both the objective and each constraint are linear in \(X\). Although the problem is “linear” in the decision variable, the variable itself is matrix-valued, so geometry occurs in matrix space rather than Euclidean vector space. The specific choice of constraint matrices \(A_i\) determines how the affine slice intersects the semidefinite cone, shaping feasibility, optimality conditions, and the possibility of multiple dual solutions.

1.4 Examples of common SDP models

Many standard optimization tasks can be phrased as SDPs. Typical sources include:

Quadratic optimization with linear or convex constraints, where lifting variables produces linear matrix inequalities.
Matrix inequality constraints \(F(X)\succeq 0\) that become linear in an appropriately selected decision matrix.
Semidefinite relaxations of combinatorial problems, where discrete constraints are replaced by matrix positivity and moment constraints.
Control and estimation problems, where Lyapunov inequalities, Riccati-related forms, or covariance constraints lead to SDPs.

1.5 Notation and matrix inner products

Throughout SDP duality, consistent notation is essential. Common conventions include:

Symmetric matrices \(X\succeq 0\) for primal feasibility.
Inner product \(\langle U,V\rangle = \mathrm{trace}(UV)\) for symmetric \(U,V\).
Dual variables \(y\in\mathbb{R}^m\), appearing as linear combinations \(\sum_{i} y_i A_i\).

This framework makes the primal objective \(\langle C,X\rangle\) and the dual feasibility constraints expressible through the same inner-product structure.

2 Duality Theory Fundamentals

2.1 Lagrangian formulation

Duality in SDP begins with a Lagrangian that relaxes the equality constraints using multipliers \(y\in\mathbb{R}^m\). For the primal above, define \[ L(X,y)=\langle C,X\rangle + \sum_{i=1}^m y_i\left(b_i-\langle A_i,X\rangle\right) = \langle C-\sum_{i=1}^m y_i A_i,\; X\rangle + \sum_{i=1}^m y_i b_i. \] The key step is to take the infimum over feasible \(X\succeq 0\) for fixed \(y\). This produces a condition ensuring the Lagrangian cannot decrease without bound.

2.2 Derivation of the dual problem

For fixed \(y\), consider \[ \inf_{X\succeq 0}\ \langle C-\sum_i y_i A_i,\ X\rangle + \sum_i y_i b_i. \] If the matrix \(C-\sum_i y_i A_i\) has a negative direction on the cone, the infimum becomes \(-\infty\). To avoid this, one requires \[ C-\sum_{i=1}^m y_i A_i \succeq 0. \] Under this condition, the infimum over \(X\succeq 0\) is attained at \(X=0\) and equals \(\sum_i y_i b_i\). This yields the dual SDP: \[ \begin{aligned} \text{maximize}\quad & \sum_{i=1}^m y_i b_i\\ \text{subject to}\quad & \sum_{i=1}^m y_i A_i \preceq C. \end{aligned} \] Equivalently, the dual feasibility constraint is \(C-\sum_i y_i A_i\succeq 0\).

2.3 Dual feasibility and interpretability of multipliers

Dual variables \(y_i\) can be interpreted as multipliers that weight the primal equality constraints. The feasibility condition \(\sum_i y_i A_i\preceq C\) ensures that the weighted combination of constraint matrices does not exceed the objective matrix \(C\) in the semidefinite ordering. When such a \(y\) exists, it can be used to certify an upper bound on the primal objective.

2.4 Weak duality

Weak duality states that for any primal feasible \(X\succeq 0\) and any dual feasible \(y\), \[ \langle C,X\rangle \ge \sum_{i=1}^m y_i b_i. \] A concise proof uses complementary substitution: \[ \langle C,X\rangle = \left\langle C-\sum_i y_i A_i,\ X\right\rangle + \sum_i y_i \langle A_i,X\rangle = \left\langle C-\sum_i y_i A_i,\ X\right\rangle + \sum_i y_i b_i, \] and the first term is nonnegative because both \(X\succeq 0\) and \(C-\sum_i y_i A_i\succeq 0\) lie in the semidefinite cone. Therefore, the dual objective cannot exceed the primal objective.

2.5 Strong duality and its significance

Strong duality means that the primal and dual optimal values coincide: \[ \inf(P)=\sup(D). \] When strong duality holds, solving either side provides the same optimal objective value, and dual solutions can serve as exact certificates of optimality rather than only bounds. Strong duality is not automatic in general; it depends on the structure of the feasible sets and, in particular, on interior-point-type constraint qualifications.

3 Constraint Qualifications and Optimality Conditions

3.1 Slater’s condition (interior-point feasibility)

A central sufficient condition for strong duality in SDP is Slater’s condition. In equality-constrained standard form, one version is:

There exists a matrix \(X\succ 0\) such that \(\langle A_i,X\rangle=b_i\) for all \(i\).

This “strict feasibility” places the affine slice in the interior relative to the semidefinite cone. Under such conditions, the duality gap typically disappears and optimal solutions can be characterized via KKT conditions.

3.2 When strong duality holds

Strong duality holds under appropriate constraint qualifications, including variants of Slater’s condition for both primal and dual problems (e.g., existence of a strictly feasible point on at least one side, or regularity conditions related to closedness of certain sets). Conceptually, these requirements ensure that the dual problem is not “too weak” to capture the primal geometry, and that optimal values are stable under perturbations.

3.3 Complementary slackness in SDPs

Complementary slackness connects primal and dual optimal solutions through the product of primal feasibility residuals and dual slackness. In matrix form, if \(X^\star\) is primal optimal and \(y^\star\) is dual optimal with slack matrix \[ S^\star = C-\sum_i y_i^\star A_i \succeq 0, \] then complementary slackness implies \[ \langle S^\star, X^\star\rangle = 0. \] Because both matrices are positive semidefinite, this scalar equality forces a stronger structural relation: the ranges of \(X^\star\) and \(S^\star\) are orthogonal, which often manifests as rank interactions.

3.4 KKT conditions for SDPs

The Karush–Kuhn–Tucker conditions provide a complete set of optimality relationships when strong duality and regularity assumptions hold. For the standard primal/dual pair, KKT conditions typically consist of:

Primal feasibility: \(\langle A_i,X^\star\rangle=b_i\) and \(X^\star\succeq 0\).
Dual feasibility: \(\sum_i y_i^\star A_i \preceq C\) (equivalently \(S^\star\succeq 0\)).
Complementary slackness: \(\langle S^\star, X^\star\rangle=0\).

Together, these conditions can be used both for theoretical derivations and as stopping criteria in numerical methods.

3.5 Degeneracy and duality gaps

Degeneracy occurs when constraint gradients or multipliers are not uniquely determined, or when the problem lies on “flat” faces of the cone such that multiple primal or dual solutions share the same objective value. In such situations, numerical solvers may return solutions that satisfy feasibility approximately while the underlying optimal face is nontrivial. While strong duality may still hold, degeneracy increases sensitivity and can make recovery of exact ranks or certificates difficult. When constraint qualifications fail, a duality gap can remain, meaning \(\inf(P)>\sup(D)\).

4 Geometry of SDP Duality

4.1 Cones and faces of the semidefinite cone

Geometric intuition helps explain why semidefinite duality is so effective for certification. The semidefinite cone is convex and has faces determined by nullspaces. If \(X^\star\) is rank-deficient, it lies in a lower-dimensional face, and the dual slack \(S^\star\) aligns with the orthogonal complement face. Thus, complementary slackness can be read as a face-to-face matching: primal optimal solutions live on one face while dual slack lives on a complementary face.

4.2 Separating hyperplanes viewpoint

Duality is closely tied to separation theorems. In many treatments, the dual feasible set can be viewed through the lens of hyperplanes that separate an affine image of the feasible region from infeasible points. When separation is exact (under regularity), the separating hyperplane corresponds to a dual multiplier \(y^\star\) that certifies optimality. This perspective underlies the deep link between convex analysis and SDP duality.

4.3 Complementary subspaces and ranks

Complementary slackness implies that \(X^\star S^\star=0\) in an appropriate sense for positive semidefinite matrices (often stated as \(X^\star S^\star=0\) when matrices commute in a suitable basis, or as orthogonality of ranges). As a consequence, ranks often satisfy relationships such as \[ \mathrm{rank}(X^\star)+\mathrm{rank}(S^\star) \le n, \] in dimension \(n\) for \(n\times n\) matrices. This rank geometry is exploited in rank reduction heuristics and in understanding why certain SDP relaxations admit exact solutions.

4.4 Extreme points and dual solutions

Extreme points and extreme rays of convex sets correspond to “corner” solutions and can control the complexity of optimal certificates. In SDP, dual optimal solutions may concentrate on extreme directions in the dual feasible region, influencing sparsity of multipliers and the structure of \(S^\star\). However, due to cone geometry, optimal solutions may also lie on edges or higher-dimensional faces, yielding non-unique multipliers.

5 Computational Aspects of Duality

5.1 Solving primal vs. solving dual

In practice, SDP solvers typically operate on either the primal, the dual, or a primal–dual combination. Solving the dual can be advantageous when it has fewer or more stable constraints, or when dual feasibility corresponds more naturally to an application’s quantities. Conversely, primal solving is often more direct when the decision matrix \(X\) has an interpretable physical or statistical meaning.

5.2 Recovering primal/dual solutions from solvers

Most interior-point solvers compute approximate primal and dual iterates and then refine feasibility. After termination, it is common to post-process:

Verify constraint satisfaction \(\langle A_i,X\rangle\approx b_i\).
Check semidefiniteness \(X\succeq 0\) and \(S=C-\sum_i y_iA_i\succeq 0\) numerically.
Use complementary slackness residuals \(\langle S,X\rangle\approx 0\) to gauge closeness to optimality.

Because numerical errors can blur strict feasibility, recovering exact certificates may require tolerance adjustments.

5.3 Dual bounds as certificates

Even when full optimality is hard to certify exactly, any dual feasible point \(y\) provides a rigorous certificate of an upper bound (for minimization problems) on the primal objective. In tandem with primal feasible solutions producing lower bounds, one can compute a bound interval: \[ \text{lower bound from primal} \le \text{upper bound from dual}. \] As iterations progress, this interval tightens, reflecting improved optimality.

5.4 Numerical considerations and scaling

Duality computations depend on inner products and semidefinite ordering, both of which can be sensitive to scaling of data matrices \(A_i\) and \(C\). Poor conditioning can lead to slow convergence or inaccurate residuals. Common strategies include rescaling constraint data, normalizing matrix norms, and careful selection of tolerances for feasibility and complementarity.

5.5 Detecting infeasibility via dual information

While the primal might be infeasible, the dual can still provide evidence. Under strong duality-type regularity conditions, if the primal is infeasible, the dual may become unbounded or exhibit patterns that indicate inconsistency. Conversely, a dual infeasibility witness can indicate primal infeasibility. In practical solvers, this often appears through failure of feasibility measures and diagnostic signals tied to residual growth or unbounded dual objectives.

6 Algorithms Using Primal–Dual Structure

6.1 Interior-point methods in primal–dual form

Interior-point methods exploit primal–dual relationships by maintaining iterates that are strictly feasible with respect to a barrier term, often using a central path toward optimality. For SDPs, this involves simultaneous updates to \(X\), \(y\), and the dual slack \(S\), with equations enforcing both primal/dual feasibility residuals and a barrier-driven complementarity condition. The barrier prevents the iterates from touching the boundary of the cone too early.

6.2 Predictor–corrector and central path intuition

The central path is the set of solutions to perturbed KKT conditions for a sequence of barrier parameters. Predictor–corrector schemes take a step along an approximate direction (predictor) and then adjust to restore the correct perturbed conditions (corrector). This provides a mechanism to balance progress with numerical stability, especially when the optimal solution lies on a low-rank face.

6.3 Stopping criteria tied to primal/dual residuals

Algorithmic stopping typically uses measures such as:

- Primal residuals: \(\\|\langle A_i,X\rangle-b_i\\|\).
- Dual residuals: \(\\|S - (C-\sum_i y_iA_i)\\|\) or equivalent formulations.

Complementarity gap: \(\langle S,X\rangle\) normalized appropriately.

Stopping when these residuals fall below tolerance aims to ensure approximate satisfaction of KKT conditions and thus approximate optimality, assuming constraint qualifications.

6.4 Regularization and rank-reduction heuristics

When optimal solutions are expected to be low rank, the raw SDP can be computationally demanding. Regularization can improve numerical behavior, while rank-reduction heuristics attempt to identify structure in \(X\) and adjust formulations or post-process solutions. These methods are closely related to geometry: the algorithm effectively steers iterates toward the face where complementary slackness forces the correct nullspace structure.

6.5 Warm-starting and model updating using duals

Warm-starting uses previous solutions to initialize an SDP solve when data changes slightly, such as in iterative model refinement. Dual variables can be particularly useful: they indicate which constraints are “active” through the magnitude patterns in \(y\) and the structure of \(S\). When updating models, keeping dual information helps maintain proximity to the relevant optimal face and can reduce computation time.

7 Sensitivity and Parameter Dependence

7.1 Perturbation of objective coefficients

If the objective matrix \(C\) is perturbed by a small amount, the corresponding optimal value changes in a manner related to the primal optimal matrix and the dual slack structure. In smooth settings, first-order sensitivities often express how \(\langle C,X^\star\rangle\) varies with \(C\) through \(X^\star\). Thus, the primal optimizer acts as a sensitivity object for objective perturbations.

7.2 Perturbation of constraint data

If the right-hand side vector \(b\) changes, dual multipliers \(y^\star\) often provide the leading-order effect on the optimal value. Since the dual objective is \(\sum_i y_i b_i\), small changes in \(b\) directly scale through the multipliers. This makes dual solutions valuable for sensitivity analysis, especially in engineering contexts where constraints correspond to resource allocations or calibration parameters.

7.3 Dual variables as sensitivity multipliers

The interpretation of \(y_i^\star\) as sensitivity multipliers is a core practical consequence of SDP duality. When strong duality and regularity conditions hold, dual multipliers quantify the marginal effect of changing each equality constraint. In matrix terms, the dual feasibility condition also reflects how much “slack” remains in the semidefinite ordering, influencing robustness of the solution.

7.4 Interpreting dual solutions under uncertainty

In applications, \(A_i\), \(b_i\), or even \(C\) may be uncertain or measured with noise. Dual solutions can be used to assess which constraints most strongly influence the objective and how conservative or tight the corresponding certificate may be. While exact sensitivity claims require assumptions, the qualitative story remains: multipliers highlight directions in data space to which the optimal value is most sensitive.

7.5 Lipschitz-style stability intuition (high level)

At a high level, convex optimization under regularity often yields stability of the optimal value with respect to data perturbations, sometimes captured by Lipschitz-type bounds. Duality contributes to this intuition because dual feasible multipliers create upper bounds that move predictably with perturbed right-hand sides or objective matrices. The precise constants depend on conditioning, geometry of feasible faces, and whether interior points exist.

8 Applications and Modeling Patterns

8.1 Quadratic forms and matrix inequalities

Quadratic forms such as \(x^\top Qx\) can often be rewritten or bounded using matrix inequalities by introducing a lifted variable \(X=xx^\top\). Constraints on \(x\) that are quadratic or linear can lead to linear constraints in \(X\), turning the problem into an SDP. Duality then yields certificate matrices that prove bounds on the original quadratic objective.

8.2 Robust optimization formulations

Robust optimization considers uncertainty in data and seeks solutions that remain feasible across a set of perturbations. Many robust constraints can be converted into SDPs via worst-case analysis and semidefinite bounds. In such settings, duality interprets dual variables as describing the “worst-case” weighting of constraints or scenarios, and the resulting SDP dual certificate can certify robust objective performance.

8.3 Sum-of-squares (SOS) as an SDP duality pipeline

Sum-of-squares techniques provide a systematic method to certify nonnegativity of polynomials by representing them as sums of squares of other polynomials. This representation corresponds to the existence of a positive semidefinite Gram matrix, which leads to an SDP. Duality then translates the existence of such a representation into certificate structure: infeasibility of an SOS relaxation or existence of a separating dual can imply polynomial nonnegativity or nonnegativity bounds depending on the formulation.

8.4 Control and signal processing motivations

In control, stability and performance constraints are frequently expressed through matrix inequalities such as Lyapunov inequalities, which can be cast as SDPs. In signal processing, covariance estimation, filter design, and power or energy constraints similarly lead to semidefinite formulations. Dual solutions often correspond to interpretable weights on constraint channels, providing insight into which performance requirements are most binding.

Distance minimization and norm-related problems can be expressed using semidefinite constraints, especially when norms arise from covariance matrices or when one requires bounds on Euclidean distances through Gram matrices. SDPs can also encode constraints on covariance structure, such as ensuring a matrix remains positive semidefinite while matching measured moments. In these models, duality provides certificates that validate feasibility and bound optimal values, often reflecting tightness of the covariance constraints.