04. What makes this an SDP?

The previous chapter optimized the smallest PSD slice by inspection. Before returning to exam scheduling, use a three-variable problem, send it to a solver, and derive its feasible boundary exactly. The independent derivation will help us catch a wrong model or misleading numerical answer.

Correlation matrices must be PSD with unit diagonal. This is a structural requirement, not a software convention: the entries must be realizable as inner products of standardized variables. Invalid or incomplete correlation data arises in practice; nearest-correlation computations were developed in part for financial correlation matrices. Higham, 2002

We begin with completion rather than repair. Three variables have $X_{12}=0.6$ and $X_{23}=-0.2$. How small can $X_{13}$ be?

Write the unknown correlation as $x=X_{13}$:

\[ X(x)= \begin{bmatrix} 1&a&x\\ a&1&b\\ x&b&1 \end{bmatrix}, \qquad a=0.6,\quad b=-0.2. \]

A correlation matrix has ones on its diagonal because each standardized variable has variance one. It is PSD because, for any coefficients $z$, $z^TXz$ is the variance of the linear combination of those variables and cannot be negative. Thus the PSD constraint is the mathematical consistency condition linking the three pairwise correlations.

How low can the missing correlation go?

Decide whether each statement is plausible.

Every value in [-1, 1] is available for $X_{13}$.
The minimizing correlation matrix lies on the boundary of the PSD cone.
A solver reporting OPTIMAL proves that our Julia model matches the mathematical question.

What mathematical object captures the question?

We use

\[ \min_X\ \langle C,X\rangle \quad\text{s.t.}\quad \langle A_i,X\rangle=b_i,\qquad X\succeq0. \]

Here $\langle A,X\rangle=\operatorname{tr}(A^TX)$. To select the symmetric off-diagonal entry $X_{13}$, put 1/2 in positions (1,3) and (3,1) of $C$. The inner product counts both positions.

using LearnSDP
using Clarabel
using LinearAlgebra

a, b = 0.6, -0.2
problem = correlation_completion(a, b)

(objective_matrix = problem.C,
 equality_rhs = problem.b,
 number_of_equalities = length(problem.A))

(objective_matrix = [0.0 0.0 0.5; 0.0 0.0 0.0; 0.5 0.0 0.0], equality_rhs = [1.0, 1.0, 1.0, 0.6, -0.2], number_of_equalities = 5)

Before solving, check one piece of the encoding independently.

trial = [1.0 a 0.35; a 1.0 b; 0.35 b 1.0]
@assert matrix_inner(problem.C, trial) == trial[1, 3]

Is the Julia code the model?

The mathematical objects are:

one symmetric matrix decision variable $X$;
a linear objective selecting $X_{13}$;
five affine equalities fixing the diagonal and two correlations;
membership in the PSD cone.

StandardSDP stores those objects as data. solve_sdp currently translates them into JuMP and sends the result to Clarabel. Another modeling library or solver could consume the same $C$, $A_i$, and $b_i$. This separation matters: package syntax is one representation of the model, not the definition of an SDP.

JuMP also permits a direct matrix-variable formulation such as @variable(model, X[1:3, 1:3], PSD). The explicit standard-form data is more verbose here, but it makes objective coefficients, equality residuals, and dual derivation inspectable.

Go further: Julia modeling syntax

JuMP’s official semidefinite constraint documentation explains the distinction between a PSD matrix constraint and elementwise matrix inequalities. Its small SDP examples show other formulations. These are syntax references after the mathematical model is understood.

What does the solver return?

result = solve_sdp(problem, Clarabel.Optimizer)
report = audit_solution(result.model, problem, result.numerical_X)

(X = round.(result.numerical_X; digits = 6),
 status = report.termination,
 objective = report.primal_objective,
 equality_residual = report.equality_residual,
 minimum_eigenvalue = report.minimum_eigenvalue,
 relative_gap = report.relative_gap)

(X = [1.0 0.6 -0.903837; 0.6 1.0 -0.2; -0.903837 -0.2 1.0], status = MathOptInterface.OPTIMAL, objective = -0.9038367180685138, equality_residual = 0.0, minimum_eigenvalue = -3.322448306640074e-10, relative_gap = 5.7446924994764e-10)

The status reports why the solver stopped. The residuals measure the point it returned against the original matrices. Neither check substitutes for verifying that those matrices encode the intended correlations.

Can we check the answer without the solver?

For a $3\times3$ symmetric matrix, PSD requires every principal minor to be nonnegative. The one-by-one minors are already one, and the fixed correlations $a$ and $b$ already satisfy $|a|,|b|\le1$. The remaining determinant is

\[ \begin{aligned} \det X(x) &=1+2abx-a^2-b^2-x^2\\ &=(1-a^2)(1-b^2)-(x-ab)^2. \end{aligned} \]

Therefore $\det X(x)\ge0$ exactly when

\[ ab-\sqrt{(1-a^2)(1-b^2)} \le x\le ab+\sqrt{(1-a^2)(1-b^2)}. \]

So the three opening predictions can now be resolved:

The unknown correlation cannot use all of $[-1,1]$; the two fixed correlations narrow its interval.
Minimizing $x$ reaches the lower endpoint, where $\det X(x)=0$, so the optimizer lies on the PSD boundary.
An OPTIMAL status supports the model the solver received. The determinant derivation is an independent check that we encoded the intended question.

analytic_minimum = a * b - sqrt((1 - a^2) * (1 - b^2))

@assert report.primal_objective ≈ analytic_minimum atol = 2e-6
@assert abs(det(result.numerical_X)) <= 3e-6

(analytic_minimum,
 computed_minimum = report.primal_objective,
 determinant = det(result.numerical_X))

(analytic_minimum = -0.9038367176906169, computed_minimum = -0.9038367180685138, determinant = -5.924188428707567e-10)

The optimizer is singular because minimizing a linear function pushes it to the boundary of this feasible slice. The near-zero eigenvalue and determinant are numerical observations, not exact zeros.

Why will this geometry return?

A correlation matrix is a Gram matrix of unit vectors. In Chapter 06 the Max-Cut relaxation will impose exactly the same two conditions:

\[ X\succeq0,\qquad X_{ii}=1. \]

The interpretation will change—from correlations to relaxed binary signs—but the geometry will be the same.

Try it yourself

Build the five equality matrices by hand instead of calling correlation_completion.
Predict and then compute how the feasible interval changes when a = 0.9.
Give an example of individually plausible pairwise correlations that cannot form a valid correlation matrix.
Complete learner/04_first_sdp.jl, including a one-paragraph audit statement.

--- title: "04. What makes this an SDP?" engine: julia julia: exeflags: ["--project=@."] --- The previous chapter optimized the smallest PSD slice by inspection. Before returning to exam scheduling, use a three-variable problem, send it to a solver, and derive its feasible boundary exactly. The independent derivation will help us catch a wrong model or misleading numerical answer. Correlation matrices must be PSD with unit diagonal. This is a structural requirement, not a software convention: the entries must be realizable as inner products of standardized variables. Invalid or incomplete correlation data arises in practice; nearest-correlation computations were developed in part for financial correlation matrices. [Higham, 2002](https://eprints.maths.manchester.ac.uk/232/) We begin with completion rather than repair. Three variables have $X_{12}=0.6$ and $X_{23}=-0.2$. How small can $X_{13}$ be? Write the unknown correlation as $x=X_{13}$: $$ X(x)= \begin{bmatrix} 1&a&x\\ a&1&b\\ x&b&1 \end{bmatrix}, \qquad a=0.6,\quad b=-0.2. $$ A correlation matrix has ones on its diagonal because each standardized variable has variance one. It is PSD because, for any coefficients $z$, $z^TXz$ is the variance of the linear combination of those variables and cannot be negative. Thus the PSD constraint is the mathematical consistency condition linking the three pairwise correlations. ## How low can the missing correlation go? Decide whether each statement is plausible. 1. Every value in `[-1, 1]` is available for $X_{13}$. 2. The minimizing correlation matrix lies on the boundary of the PSD cone. 3. A solver reporting `OPTIMAL` proves that our Julia model matches the mathematical question. ## What mathematical object captures the question? We use $$ \min_X\ \langle C,X\rangle \quad\text{s.t.}\quad \langle A_i,X\rangle=b_i,\qquad X\succeq0. $$ Here $\langle A,X\rangle=\operatorname{tr}(A^TX)$. To select the symmetric off-diagonal entry $X_{13}$, put `1/2` in positions `(1,3)` and `(3,1)` of $C$. The inner product counts both positions. ```{julia} #| label: inspect-standard-form using LearnSDP using Clarabel using LinearAlgebra a, b = 0.6, -0.2 problem = correlation_completion(a, b) (objective_matrix = problem.C, equality_rhs = problem.b, number_of_equalities = length(problem.A)) ``` Before solving, check one piece of the encoding independently. ```{julia} #| label: objective-encoding trial = [1.0 a 0.35; a 1.0 b; 0.35 b 1.0] @assert matrix_inner(problem.C, trial) == trial[1, 3] ``` ## Is the Julia code the model? The mathematical objects are: - one symmetric matrix decision variable $X$; - a linear objective selecting $X_{13}$; - five affine equalities fixing the diagonal and two correlations; - membership in the PSD cone. `StandardSDP` stores those objects as data. `solve_sdp` currently translates them into JuMP and sends the result to Clarabel. Another modeling library or solver could consume the same $C$, $A_i$, and $b_i$. This separation matters: package syntax is one representation of the model, not the definition of an SDP. JuMP also permits a direct matrix-variable formulation such as `@variable(model, X[1:3, 1:3], PSD)`. The explicit standard-form data is more verbose here, but it makes objective coefficients, equality residuals, and dual derivation inspectable. ::: {.callout-note title="Go further: Julia modeling syntax"} JuMP's official [semidefinite constraint documentation](https://jump.dev/JuMP.jl/stable/manual/constraints/#Semidefinite-constraints) explains the distinction between a PSD matrix constraint and elementwise matrix inequalities. Its [small SDP examples](https://jump.dev/JuMP.jl/stable/tutorials/conic/simple_examples/) show other formulations. These are syntax references after the mathematical model is understood. ::: ## What does the solver return? ```{julia} #| label: solve-correlation result = solve_sdp(problem, Clarabel.Optimizer) report = audit_solution(result.model, problem, result.numerical_X) (X = round.(result.numerical_X; digits = 6), status = report.termination, objective = report.primal_objective, equality_residual = report.equality_residual, minimum_eigenvalue = report.minimum_eigenvalue, relative_gap = report.relative_gap) ``` The status reports why the solver stopped. The residuals measure the point it returned against the original matrices. Neither check substitutes for verifying that those matrices encode the intended correlations. ## Can we check the answer without the solver? For a $3\times3$ symmetric matrix, PSD requires every principal minor to be nonnegative. The one-by-one minors are already one, and the fixed correlations $a$ and $b$ already satisfy $|a|,|b|\le1$. The remaining determinant is $$ \begin{aligned} \det X(x) &=1+2abx-a^2-b^2-x^2\\ &=(1-a^2)(1-b^2)-(x-ab)^2. \end{aligned} $$ Therefore $\det X(x)\ge0$ exactly when $$ ab-\sqrt{(1-a^2)(1-b^2)} \le x\le ab+\sqrt{(1-a^2)(1-b^2)}. $$ So the three opening predictions can now be resolved: 1. The unknown correlation cannot use all of $[-1,1]$; the two fixed correlations narrow its interval. 2. Minimizing $x$ reaches the lower endpoint, where $\det X(x)=0$, so the optimizer lies on the PSD boundary. 3. An OPTIMAL status supports the model the solver received. The determinant derivation is an independent check that we encoded the intended question. ```{julia} #| label: analytic-boundary analytic_minimum = a * b - sqrt((1 - a^2) * (1 - b^2)) @assert report.primal_objective ≈ analytic_minimum atol = 2e-6 @assert abs(det(result.numerical_X)) <= 3e-6 (analytic_minimum, computed_minimum = report.primal_objective, determinant = det(result.numerical_X)) ``` The optimizer is singular because minimizing a linear function pushes it to the boundary of this feasible slice. The near-zero eigenvalue and determinant are numerical observations, not exact zeros. ## Why will this geometry return? A correlation matrix is a Gram matrix of unit vectors. In Chapter 06 the Max-Cut relaxation will impose exactly the same two conditions: $$ X\succeq0,\qquad X_{ii}=1. $$ The interpretation will change—from correlations to relaxed binary signs—but the geometry will be the same. ## Try it yourself 1. Build the five equality matrices by hand instead of calling `correlation_completion`. 2. Predict and then compute how the feasible interval changes when `a = 0.9`. 3. Give an example of individually plausible pairwise correlations that cannot form a valid correlation matrix. 4. Complete `learner/04_first_sdp.jl`, including a one-paragraph audit statement.