Optimize with positive-semidefinite matrix constraints

Try

Choose a symmetric matrix X=[[1,z],[z,9]] that is positive semidefinite, abbreviated PSD. The condition means vᵀXv≥0 for every real vector v. In this two-by-two case, nonnegative diagonal entries and determinant 9−z²≥0 give −3≤z≤3. Thus maximizing z has optimum three, attained by the rank-one matrix (1,3)(1,3)ᵀ. A matrix inequality has encoded a coupled constraint on its entries, not separate nonnegativity of each entry.

Predict

Predict whether a PSD matrix may have negative off-diagonal entries. The same example permits z=−3, so yes. Predict whether the product of two PSD matrices is always symmetric PSD. It need not be symmetric unless the matrices commute. Nevertheless, their trace inner product is nonnegative, and this weaker fact is exactly what SDP weak duality needs. Using an unjustified product-order claim would obscure the correct certificate.

Experiment

Minimize trace(CX) with C=diag(1,4), X PSD and trace X=1. Consider several diagonal feasible matrices and a dual scalar price.

Matrix X	Objective	Feasible?
diag(1,0)	1	Yes
diag(1/2,1/2)	5/2	Yes
diag(0,1)	4	Yes

The dual choice y=1 has slack S=C−yI=diag(0,3), which is PSD. Thus trace(CX)≥y·trace X=1 for every feasible X, and the first row attains that bound. Check trace(SX)=0 there. This proves optimality for all feasible matrices, including those with nonzero off-diagonal entries, not just the three displayed candidates.

Understand

The symmetric PSD cone is convex: a nonnegative combination of PSD quadratic forms remains nonnegative. It is closed because a limit preserves vᵀXv≥0 for every v. With trace inner product ⟨S,X⟩=trace(SX), the cone is self-dual. If X=RRᵀ, then trace(SX)=trace(RᵀSR), a sum of nonnegative quadratic forms for PSD S. Conversely, testing against every rank-one X=vvᵀ recovers vᵀSv≥0, hence PSD of symmetric S.

An equality-form SDP minimizes trace(CX) subject to trace(AᵢX)=bᵢ and X PSD, with symmetric data. Use L=trace(CX)+Σyᵢ(bᵢ−trace(AᵢX)). If S=C−ΣyᵢAᵢ is PSD, the infimum over PSD X is bᵀy, attained at X=0 for that unconstrained Lagrangian minimization. If S has a negative quadratic direction, scaling its rank-one matrix makes the infimum negative infinity. The dual therefore maximizes bᵀy subject to S PSD. For feasible pairs, the gap is trace(SX)≥0; zero gap certifies both optima. Strong duality and attainment require qualification, such as appropriate strict feasibility and finiteness, rather than holding automatically for every SDP.

Apply

Quadratic vector problems can be lifted by writing X=xxᵀ, since xᵀCx=trace(CX). The lifted matrix is PSD and rank one. Dropping the rank condition enlarges the feasible set, creating an SDP relaxation and a lower bound for minimization. A higher-rank optimum may have no vector producing it exactly. Rounding or extracting a vector requires an additional feasibility and objective check in the original model. The convex relaxation is useful precisely because it can be easier, not because the omitted rank restriction was redundant.

The interior of the PSD cone consists of positive-definite matrices, where −log det X is a barrier. Singular PSD optima lie on its boundary. A numerical eigenvalue slightly below zero must be assessed relative to scaling and tolerances; an unchecked nearly PSD matrix is not an exact certificate. Small two-by-two examples permit determinant checks, while higher-dimensional cases require full spectral or factorization reasoning.

Continue

Keep matrix symmetry, PSD feasibility, trace constraints and the gap visible in an SDP report. Continue to Projected and proximal methods for algorithms that enforce simple convex geometry directly. These methods complement interior-point techniques; choosing between them depends on structure and workload, not a claim that one algorithm universally solves every convex model most efficiently.