06. What if signs became vectors?

Return to the exam-conflict graph from Chapter 00. Give each vertex a sign $s_i\in\{-1,1\}$. An edge crosses the cut exactly when its signs differ, so

\[ \operatorname{cut}(s) =\frac14\sum_{i<j}W_{ij}(s_i-s_j)^2 =\frac14s^TLs, \]

where $L=\operatorname{Diag}(W\mathbf1)-W$ is the weighted graph Laplacian. The sum uses each undirected edge once. If it were written over all ordered pairs $(i,j)$, the coefficient would be $1/8$ because every edge would appear twice.

Can one matrix hold every sign product?

Set $X=ss^T$. Then

\[ s^TLs=\langle L,X\rangle, \]

and $X$ has three properties:

\[ X\succeq0,\qquad X_{ii}=1,\qquad \operatorname{rank}(X)=1. \]

Conversely, every PSD rank-one matrix with unit diagonal represents a cut. Indeed, rank one and PSD give $X=ss^T$ for some vector $s$, while $X_{ii}=s_i^2=1$ forces every $s_i$ to equal $1$ or $-1$.

The rank-one requirement is the part that prevents this from already being an SDP. It is not preserved by averaging: the average of two different rank-one cut matrices is PSD and still has unit diagonal, but generally has rank greater than one. Thus the exact cut matrices form a nonconvex subset inside the convex set of PSD matrices with unit diagonal.

using LearnSDP
using Clarabel
using LinearAlgebra

W = course_graph()
exact = exact_maxcut(W)
L = Diagonal(W * ones(size(W, 1))) - W
Xcut = exact.signs * exact.signs'

@assert cut_weight(W, exact.signs) ≈ dot(L, Xcut) / 4
(cut_weight = exact.weight,
 diagonal = diag(Xcut),
 rank = rank(Xcut))

(cut_weight = 23.0, diagonal = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], rank = 1)

Exact enumeration is acceptable here only because the teaching graph has ten vertices. The number of distinct cuts doubles with every additional vertex.

Which condition makes the problem hard?

The SDP relaxation drops rank(X) == 1:

\[ \begin{aligned} \max_X\quad &\frac14\langle L,X\rangle\\ \text{s.t.}\quad &X_{ii}=1 &&i=1,\ldots,n,\\ &X\succeq0. \end{aligned} \]

Every cut matrix remains feasible, but the SDP also admits Gram matrices of unit vectors pointing in more than two directions. Maximizing over a larger set can only increase the value. Therefore the SDP optimum is an upper bound on the maximum cut.

LearnSDP.maxcut_problem stores an equivalent minimization with objective $-\langle L,X\rangle/4$.

problem = maxcut_problem(W)
result = solve_sdp(problem, Clarabel.Optimizer)
report = audit_solution(result.model, problem, result.numerical_X)
upper_bound = -report.primal_objective

(best_cut_by_enumeration = exact.weight,
 sdp_upper_bound = upper_bound,
 relaxation_gap = upper_bound - exact.weight,
 numerical_rank = count(>(1e-7), eigvals(Symmetric(result.numerical_X))))

(best_cut_by_enumeration = 23.0, sdp_upper_bound = 23.583132070108665, relaxation_gap = 0.5831320701086646, numerical_rank = 3)

The SDP matrix has rank greater than one, so it does not directly describe a cut. That is why Chapter 10 needs a rounding algorithm.

What did rank one prevent?

Because $X$ is PSD with unit diagonal, write $X_{ij}=v_i^Tv_j$ with unit vectors. The objective becomes

\[ \frac14\sum_{i,j}W_{ij}\lVert v_i-v_j\rVert_2^2. \]

The discrete problem permits only two antipodal vectors. The relaxation lets the vectors use any directions that satisfy one globally consistent Gram matrix. The matrix geometry from Chapters 02–03 is now doing algorithmic work.

What can we reuse beyond Max-Cut?

This construction illustrates a reusable modeling move:

encode products of original variables in a matrix;
identify necessary PSD, affine, and rank conditions;
locate the condition that causes nonconvexity;
remove or weaken that condition;
prove whether the relaxed optimum is an upper or lower bound;
design a map from the relaxed solution back to an original feasible point.

Dropping rank is useful far beyond Max-Cut, including relaxations of quadratic optimization, control, and polynomial problems. The details differ, and a relaxation is valuable only when its bound and recovery procedure answer the original question.

Go further: SDP relaxations

The Vandenberghe–Boyd survey contains examples from eigenvalue optimization, control, and combinatorial optimization. MIT’s Algebraic Techniques and Semidefinite Optimization provides a longer set of freely available graduate notes. Both are optional routes outward from this rank-relaxation pattern.

The relaxation argument proves that the SDP value is an upper bound. But the number still came from the same solve as the matrix. Can a separate mathematical object certify a bound without trusting that primal output?

Try it yourself

Verify the cut identity for five randomly generated sign vectors.
Explain precisely why dropping rank gives an upper rather than a lower bound.
Add an isolated vertex and predict which parts of the SDP solution become nonunique.
Complete learner/06_signs_to_vectors.jl without calling maxcut_problem.

--- title: "06. What if signs became vectors?" engine: julia julia: exeflags: ["--project=@."] --- Return to the exam-conflict graph from Chapter 00. Give each vertex a sign $s_i\in\{-1,1\}$. An edge crosses the cut exactly when its signs differ, so $$ \operatorname{cut}(s) =\frac14\sum_{i<j}W_{ij}(s_i-s_j)^2 =\frac14s^TLs, $$ where $L=\operatorname{Diag}(W\mathbf1)-W$ is the weighted graph Laplacian. The sum uses each undirected edge once. If it were written over all ordered pairs $(i,j)$, the coefficient would be $1/8$ because every edge would appear twice. ## Can one matrix hold every sign product? Set $X=ss^T$. Then $$ s^TLs=\langle L,X\rangle, $$ and $X$ has three properties: $$ X\succeq0,\qquad X_{ii}=1,\qquad \operatorname{rank}(X)=1. $$ Conversely, every PSD rank-one matrix with unit diagonal represents a cut. Indeed, rank one and PSD give $X=ss^T$ for some vector $s$, while $X_{ii}=s_i^2=1$ forces every $s_i$ to equal $1$ or $-1$. The rank-one requirement is the part that prevents this from already being an SDP. It is not preserved by averaging: the average of two different rank-one cut matrices is PSD and still has unit diagonal, but generally has rank greater than one. Thus the exact cut matrices form a nonconvex subset inside the convex set of PSD matrices with unit diagonal. ```{julia} #| label: verify-cut-identity using LearnSDP using Clarabel using LinearAlgebra W = course_graph() exact = exact_maxcut(W) L = Diagonal(W * ones(size(W, 1))) - W Xcut = exact.signs * exact.signs' @assert cut_weight(W, exact.signs) ≈ dot(L, Xcut) / 4 (cut_weight = exact.weight, diagonal = diag(Xcut), rank = rank(Xcut)) ``` Exact enumeration is acceptable here only because the teaching graph has ten vertices. The number of distinct cuts doubles with every additional vertex. ## Which condition makes the problem hard? The SDP relaxation drops `rank(X) == 1`: $$ \begin{aligned} \max_X\quad &\frac14\langle L,X\rangle\\ \text{s.t.}\quad &X_{ii}=1 &&i=1,\ldots,n,\\ &X\succeq0. \end{aligned} $$ Every cut matrix remains feasible, but the SDP also admits Gram matrices of unit vectors pointing in more than two directions. Maximizing over a larger set can only increase the value. Therefore the SDP optimum is an **upper bound** on the maximum cut. `LearnSDP.maxcut_problem` stores an equivalent minimization with objective $-\langle L,X\rangle/4$. ```{julia} #| label: solve-relaxation problem = maxcut_problem(W) result = solve_sdp(problem, Clarabel.Optimizer) report = audit_solution(result.model, problem, result.numerical_X) upper_bound = -report.primal_objective (best_cut_by_enumeration = exact.weight, sdp_upper_bound = upper_bound, relaxation_gap = upper_bound - exact.weight, numerical_rank = count(>(1e-7), eigvals(Symmetric(result.numerical_X)))) ``` The SDP matrix has rank greater than one, so it does not directly describe a cut. That is why Chapter 10 needs a rounding algorithm. ## What did rank one prevent? Because $X$ is PSD with unit diagonal, write $X_{ij}=v_i^Tv_j$ with unit vectors. The objective becomes $$ \frac14\sum_{i,j}W_{ij}\lVert v_i-v_j\rVert_2^2. $$ The discrete problem permits only two antipodal vectors. The relaxation lets the vectors use any directions that satisfy one globally consistent Gram matrix. The matrix geometry from Chapters 02–03 is now doing algorithmic work. ## What can we reuse beyond Max-Cut? This construction illustrates a reusable modeling move: 1. encode products of original variables in a matrix; 2. identify necessary PSD, affine, and rank conditions; 3. locate the condition that causes nonconvexity; 4. remove or weaken that condition; 5. prove whether the relaxed optimum is an upper or lower bound; 6. design a map from the relaxed solution back to an original feasible point. Dropping rank is useful far beyond Max-Cut, including relaxations of quadratic optimization, control, and polynomial problems. The details differ, and a relaxation is valuable only when its bound and recovery procedure answer the original question. ::: {.callout-note title="Go further: SDP relaxations"} The [Vandenberghe–Boyd survey](https://web.stanford.edu/~boyd/papers/sdp.html) contains examples from eigenvalue optimization, control, and combinatorial optimization. MIT's [Algebraic Techniques and Semidefinite Optimization](https://ocw.mit.edu/courses/6-972-algebraic-techniques-and-semidefinite-optimization-spring-2006/resources/lecture-notes/) provides a longer set of freely available graduate notes. Both are optional routes outward from this rank-relaxation pattern. ::: The relaxation argument proves that the SDP value is an upper bound. But the number still came from the same solve as the matrix. Can a separate mathematical object certify a bound without trusting that primal output? ## Try it yourself 1. Verify the cut identity for five randomly generated sign vectors. 2. Explain precisely why dropping rank gives an upper rather than a lower bound. 3. Add an isolated vertex and predict which parts of the SDP solution become nonunique. 4. Complete `learner/06_signs_to_vectors.jl` without calling `maxcut_problem`.