07. How can we bound every unseen schedule?

The relaxation argument already tells us the SDP value bounds every cut. But a reported optimal value still comes from a numerical solver. Duality gives a second object whose feasibility can be checked independently.

Can another feasible object bound every schedule?

Write $Q=L/4$. The primal relaxation is

\[ \begin{aligned} \text{maximize}\quad &\langle Q,X\rangle\\ \text{subject to}\quad &X_{ii}=1, \qquad i=1,\ldots,n,\\ &X\succeq0. \end{aligned} \]

We want a number that is guaranteed to sit above this objective for every feasible $X$. Choose numbers $y_1,\ldots,y_n$. Because every feasible matrix has $X_{ii}=1$,

\[ \sum_i y_i =\sum_i y_iX_{ii} =\langle\operatorname{Diag}(y),X\rangle. \]

Subtract the primal objective:

\[ \sum_i y_i-\langle Q,X\rangle =\left\langle\operatorname{Diag}(y)-Q,X\right\rangle. \]

Define the dual slack matrix

\[ S=\operatorname{Diag}(y)-Q. \]

If we choose $y$ so that $S\succeq0$, then both $S$ and every primal-feasible $X$ are PSD. Their inner product cannot be negative. To see why, write $S=AA^T$ and $X=BB^T$:

\[ \langle S,X\rangle =\operatorname{tr}(AA^TBB^T) =\lVert A^TB\rVert_F^2 \ge0. \]

It follows that

\[ \langle Q,X\rangle\le\sum_i y_i \]

for every primal-feasible $X$. Since every exact cut matrix is also primal-feasible, one such $y$ bounds the SDP relaxation and every unseen schedule at once.

Different dual-feasible vectors $y$ give different upper bounds. The dual problem asks for the smallest one:

\[ \begin{aligned} \text{minimize}\quad &\sum_i y_i\\ \text{subject to}\quad &S=\operatorname{Diag}(y)-Q\succeq0. \end{aligned} \]

When do the two bounds meet?

The inequality above is weak duality. It requires only primal and dual feasibility, so it remains useful when either point is suboptimal.

Equality of optimal values is strong duality and needs regularity. A common sufficient condition for an SDP is Slater’s condition: a strictly feasible primal point $X\succ0$ or a strictly feasible dual slack $S\succ0$, together with the usual finite-value assumptions. Here $X=I$ satisfies the diagonal equalities and is positive definite. Choosing all $y_i$ sufficiently large makes the dual slack positive definite. The pair is therefore well behaved.

Strong duality does not say a floating-point solver returns exact equal objectives. It says the mathematical optimal values agree. Numerically we look for a small gap relative to problem scale.

Go further: conic duality

MIT’s complete convex-analysis notes state SDP duality and Slater conditions in a broader conic setting. For Julia’s sign and cone conventions, consult the official MathOptInterface duality background. The first is mathematical context; the second explains software conventions.

Do the bounds meet numerically?

using LearnSDP
using Clarabel
using JuMP
using LinearAlgebra

W = course_graph()
n = size(W, 1)
L = Diagonal(W * ones(n)) - W
Q = Matrix(L / 4)

primal_problem = maxcut_problem(W)
primal = solve_sdp(primal_problem, Clarabel.Optimizer)
X̂ = primal.numerical_X
primal_value = dot(Q, X̂)

dual_model = Model(Clarabel.Optimizer)
set_silent(dual_model)
set_optimizer_attribute(dual_model, "chordal_decomposition_enable", false)
@variable(dual_model, y[1:n])
S = [y[i] * (i == j) - Q[i, j] for i in 1:n, j in 1:n]
@constraint(dual_model, Symmetric(S) in PSDCone())
@objective(dual_model, Min, sum(y))
optimize!(dual_model)

ŷ = value.(y)
Ŝ = Matrix(Diagonal(ŷ) - Q)
dual_value = sum(ŷ)

(primal_value,
 dual_value,
 gap = dual_value - primal_value,
 minimum_slack_eigenvalue = eigmin(Symmetric(Ŝ)))

(primal_value = 23.583132070108665, dual_value = 23.583132127646522, gap = 5.753785714546211e-8, minimum_slack_eigenvalue = -1.5506888998230167e-8)

What must an optimality claim check?

For any feasible primal-dual pair, the objective gap is exactly

\[ \sum_i y_i-\langle Q,X\rangle=\langle S,X\rangle. \]

Under strong duality, an optimal pair has zero gap, so $\langle S,X\rangle=0$. This is complementarity: the primal matrix and dual slack meet without leaving any unused objective gap.

For this pair, the Karush–Kuhn–Tucker (KKT) conditions collect everything an exact optimum must satisfy:

primal feasibility: $\operatorname{diag}(X)=\mathbf1$ and $X\succeq0$;
dual feasibility: $S=\operatorname{Diag}(y)-Q\succeq0$;
complementarity: $\langle S,X\rangle=0$.

A numerical solution replaces each equality or inequality by a residual that must be interpreted at a stated tolerance.

certificate = (
    primal_equality = maximum(abs.(diag(X̂) .- 1)),
    primal_psd_violation = max(0.0, -eigmin(Symmetric(X̂))),
    dual_psd_violation = max(0.0, -eigmin(Symmetric(Ŝ))),
    objective_gap = dual_value - primal_value,
    scaled_complementarity = abs(dot(Ŝ, X̂)) / max(1.0, norm(Ŝ) * norm(X̂)),
)

@assert maximum(abs, values(certificate)) <= 2e-6
certificate

(primal_equality = 0.0, primal_psd_violation = 0.0, dual_psd_violation = 1.5506888998230167e-8, objective_gap = 5.753785714546211e-8, scaled_complementarity = 2.1556765373849575e-9)

Small residuals make this a numerical certificate at the displayed scale. They do not make $X̂$, $ŷ$, or $Ŝ$ exact symbolic objects.

Must a certificate be optimal?

Choose $y_i=\lambda_{\max}(Q)$ for every $i$. Then $\operatorname{Diag}(y)-Q\succeq0$, so $n\lambda_{\max}(Q)$ is an immediately checkable upper bound. It is generally weaker than the optimized dual bound.

simple_y = fill(eigmax(Symmetric(Q)), n)
simple_slack = Diagonal(simple_y) - Q

@assert eigmin(Symmetric(simple_slack)) >= -1e-10
(simple_bound = sum(simple_y), optimized_bound = dual_value)

(simple_bound = 25.52659374420293, optimized_bound = 23.583132127646522)

Try it yourself

Derive the dual from the Lagrangian, including the sign of the slack matrix.
Perturb one component of ŷ downward until dual feasibility fails.
Explain why a dual-feasible point remains useful even when its objective does not match the primal objective.
Complete learner/07_bounds_from_duality.jl.

--- title: "07. How can we bound every unseen schedule?" engine: julia julia: exeflags: ["--project=@."] --- The relaxation argument already tells us the SDP value bounds every cut. But a reported optimal value still comes from a numerical solver. Duality gives a second object whose feasibility can be checked independently. ## Can another feasible object bound every schedule? Write $Q=L/4$. The primal relaxation is $$ \begin{aligned} \text{maximize}\quad &\langle Q,X\rangle\\ \text{subject to}\quad &X_{ii}=1, \qquad i=1,\ldots,n,\\ &X\succeq0. \end{aligned} $$ We want a number that is guaranteed to sit above this objective for every feasible $X$. Choose numbers $y_1,\ldots,y_n$. Because every feasible matrix has $X_{ii}=1$, $$ \sum_i y_i =\sum_i y_iX_{ii} =\langle\operatorname{Diag}(y),X\rangle. $$ Subtract the primal objective: $$ \sum_i y_i-\langle Q,X\rangle =\left\langle\operatorname{Diag}(y)-Q,X\right\rangle. $$ Define the **dual slack matrix** $$ S=\operatorname{Diag}(y)-Q. $$ If we choose $y$ so that $S\succeq0$, then both $S$ and every primal-feasible $X$ are PSD. Their inner product cannot be negative. To see why, write $S=AA^T$ and $X=BB^T$: $$ \langle S,X\rangle =\operatorname{tr}(AA^TBB^T) =\lVert A^TB\rVert_F^2 \ge0. $$ It follows that $$ \langle Q,X\rangle\le\sum_i y_i $$ for every primal-feasible $X$. Since every exact cut matrix is also primal-feasible, one such $y$ bounds the SDP relaxation and every unseen schedule at once. Different dual-feasible vectors $y$ give different upper bounds. The **dual problem** asks for the smallest one: $$ \begin{aligned} \text{minimize}\quad &\sum_i y_i\\ \text{subject to}\quad &S=\operatorname{Diag}(y)-Q\succeq0. \end{aligned} $$ ## When do the two bounds meet? The inequality above is **weak duality**. It requires only primal and dual feasibility, so it remains useful when either point is suboptimal. Equality of optimal values is **strong duality** and needs regularity. A common sufficient condition for an SDP is Slater's condition: a strictly feasible primal point $X\succ0$ or a strictly feasible dual slack $S\succ0$, together with the usual finite-value assumptions. Here $X=I$ satisfies the diagonal equalities and is positive definite. Choosing all $y_i$ sufficiently large makes the dual slack positive definite. The pair is therefore well behaved. Strong duality does not say a floating-point solver returns exact equal objectives. It says the mathematical optimal values agree. Numerically we look for a small gap relative to problem scale. ::: {.callout-note title="Go further: conic duality"} MIT's [complete convex-analysis notes](https://ocw.mit.edu/courses/6-253-convex-analysis-and-optimization-spring-2012/resources/lecture-notes/) state SDP duality and Slater conditions in a broader conic setting. For Julia's sign and cone conventions, consult the official MathOptInterface [duality background](https://jump.dev/JuMP.jl/stable/moi/background/duality/). The first is mathematical context; the second explains software conventions. ::: ## Do the bounds meet numerically? ```{julia} #| label: primal-and-dual using LearnSDP using Clarabel using JuMP using LinearAlgebra W = course_graph() n = size(W, 1) L = Diagonal(W * ones(n)) - W Q = Matrix(L / 4) primal_problem = maxcut_problem(W) primal = solve_sdp(primal_problem, Clarabel.Optimizer) X̂ = primal.numerical_X primal_value = dot(Q, X̂) dual_model = Model(Clarabel.Optimizer) set_silent(dual_model) set_optimizer_attribute(dual_model, "chordal_decomposition_enable", false) @variable(dual_model, y[1:n]) S = [y[i] * (i == j) - Q[i, j] for i in 1:n, j in 1:n] @constraint(dual_model, Symmetric(S) in PSDCone()) @objective(dual_model, Min, sum(y)) optimize!(dual_model) ŷ = value.(y) Ŝ = Matrix(Diagonal(ŷ) - Q) dual_value = sum(ŷ) (primal_value, dual_value, gap = dual_value - primal_value, minimum_slack_eigenvalue = eigmin(Symmetric(Ŝ))) ``` ## What must an optimality claim check? For any feasible primal-dual pair, the objective gap is exactly $$ \sum_i y_i-\langle Q,X\rangle=\langle S,X\rangle. $$ Under strong duality, an optimal pair has zero gap, so $\langle S,X\rangle=0$. This is **complementarity**: the primal matrix and dual slack meet without leaving any unused objective gap. For this pair, the Karush--Kuhn--Tucker (KKT) conditions collect everything an exact optimum must satisfy: - **primal feasibility:** $\operatorname{diag}(X)=\mathbf1$ and $X\succeq0$; - **dual feasibility:** $S=\operatorname{Diag}(y)-Q\succeq0$; - **complementarity:** $\langle S,X\rangle=0$. A numerical solution replaces each equality or inequality by a residual that must be interpreted at a stated tolerance. ```{julia} #| label: certificate-audit certificate = ( primal_equality = maximum(abs.(diag(X̂) .- 1)), primal_psd_violation = max(0.0, -eigmin(Symmetric(X̂))), dual_psd_violation = max(0.0, -eigmin(Symmetric(Ŝ))), objective_gap = dual_value - primal_value, scaled_complementarity = abs(dot(Ŝ, X̂)) / max(1.0, norm(Ŝ) * norm(X̂)), ) @assert maximum(abs, values(certificate)) <= 2e-6 certificate ``` Small residuals make this a numerical certificate at the displayed scale. They do not make $X̂$, $ŷ$, or $Ŝ$ exact symbolic objects. ## Must a certificate be optimal? Choose $y_i=\lambda_{\max}(Q)$ for every $i$. Then $\operatorname{Diag}(y)-Q\succeq0$, so $n\lambda_{\max}(Q)$ is an immediately checkable upper bound. It is generally weaker than the optimized dual bound. ```{julia} #| label: loose-certificate simple_y = fill(eigmax(Symmetric(Q)), n) simple_slack = Diagonal(simple_y) - Q @assert eigmin(Symmetric(simple_slack)) >= -1e-10 (simple_bound = sum(simple_y), optimized_bound = dual_value) ``` ## Try it yourself 1. Derive the dual from the Lagrangian, including the sign of the slack matrix. 2. Perturb one component of `ŷ` downward until dual feasibility fails. 3. Explain why a dual-feasible point remains useful even when its objective does not match the primal objective. 4. Complete `learner/07_bounds_from_duality.jl`.