Test failures

[odow]

@blegat what on earth is going on here? Are this many failures upstream problem? Or a bug in the wrapper?!?!

DSDP.jl/test/MOI_wrapper.jl

Lines 81 to 116 in 4575ce3

	# TODO investigate
	# Expression: MOI.get(model, MOI.TerminationStatus()) == config.infeasible_status
	# Evaluated: MathOptInterface.OPTIMAL == MathOptInterface.INFEASIBLE
	r"test_conic_NormInfinityCone_INFEASIBLE$",
	r"test_conic_NormOneCone_INFEASIBLE$",
	r"test_conic_linear_INFEASIBLE$",
	r"test_conic_linear_INFEASIBLE_2$",
	r"test_solve_DualStatus_INFEASIBILITY_CERTIFICATE_EqualTo_lower$",
	r"test_solve_DualStatus_INFEASIBILITY_CERTIFICATE_EqualTo_upper$",
	r"test_solve_DualStatus_INFEASIBILITY_CERTIFICATE_GreaterThan$",
	r"test_solve_DualStatus_INFEASIBILITY_CERTIFICATE_Interval_lower$",
	r"test_solve_DualStatus_INFEASIBILITY_CERTIFICATE_Interval_upper$",
	r"test_solve_DualStatus_INFEASIBILITY_CERTIFICATE_LessThan$",
	r"test_solve_DualStatus_INFEASIBILITY_CERTIFICATE_VariableIndex_LessThan$",
	# TODO investigate
	# Incorrect result value
	r"test_conic_NormInfinityCone_3$",
	r"test_conic_NormInfinityCone_VectorAffineFunction$",
	r"test_conic_NormInfinityCone_VectorOfVariables$",
	r"test_conic_NormOneCone$",
	r"test_conic_NormOneCone_VectorAffineFunction$",
	r"test_conic_NormOneCone_VectorOfVariables$",
	r"test_conic_linear_VectorAffineFunction$",
	r"test_conic_linear_VectorAffineFunction_2$",
	r"test_conic_linear_VectorOfVariables_2$",
	r"test_constraint_ScalarAffineFunction_Interval$",
	r"test_conic_HermitianPositiveSemidefiniteConeTriangle_1$",
	r"test_constraint_PrimalStart_DualStart_SecondOrderCone$",
	r"test_HermitianPSDCone_basic$",
	# Incorrect objective
	# See https://github.com/jump-dev/MathOptInterface.jl/issues/1759
	r"test_linear_integration$",
	r"test_linear_transform$",
	r"test_modification_affine_deletion_edge_cases$",
	r"test_modification_multirow_vectoraffine_nonpos$",
	r"test_variable_solve_with_lowerbound$",

[blegat]

I was looking into it the other day, there is a bug in the wrapper. There are simple LPs that are not solved correctly so checking what the solver gets by using its internal model printer should probably help us find the issue. We are probably not too far from correctness

[odow]

I looked through the code, and I"m just very confused with it all.

[blegat]

Maybe we can add a warning banner on top of the README saying we know there is an issue but we are looking for a volunteer to help us find it.

[blegat]

I launched Claude Code on it to investigate, his conclusion is below.
tl;dr: The issue is how we transform free variables for solvers like DSDP, CSDP an SDPA. A better way is to follow https://sburer.github.io/papers/020-freevars.pdf.
Since we transform x = x+ - x-, we allow x+ and x- to grow unbounded as long as they cancel out.
The challenge of course is that these conic solvers support either free variables or equality constraints (depending on whether you dualize or not). Conic solvers like Clarabel, SCS or Mosek support both free variables and equality constraints on both the primal and dual side so they are not affected by this.

DSDP MOI Test Failure Analysis by Claude Opus 4.6

Summary

The vast majority of failing MOI tests share one root cause: a bug in the DSDP C
solver's primal feasibility check that masks degenerate formulations created by
MOI's bridge layer.

Root Cause

MOI's bridge layer decomposes free variables as x = x+ - x- where x+, x- >= 0.
This is triggered whenever the problem uses VectorAffineFunction in conic
constraints (e.g., VectorAffineFunction in Nonnegatives instead of
VectorOfVariables in Nonnegatives), or constraints like GreaterThan,
LessThan, Nonpositives, etc., which all require slack variables linked to
free variables.

The resulting formulation is degenerate for dual interior-point methods: for
each split pair (x+_i, x-_i), the complementary dual slacks always sum to
zero:

s_{x+_i} + s_{x-_i} = (c_i - A_i^T y) + (-c_i + A_i^T y) = 0

This means the dual is never strictly feasible -- no interior point exists.
DSDP's regularization variable r temporarily creates feasibility by adding
r*I to the slack, but as r -> 0 during the solve, the problem becomes
increasingly ill-conditioned. The solver converges to a point where:

• Primal variables x+, x- grow to ~10^7 (unbounded directions)
• Dual variables y grow to ~10^6
• The objective is off by millions (e.g., -9.02e6 instead of -11)
• But the relative duality gap appears small

Bug in the C Source Code

File: src/solver/dsdpx.c, function DSDPComputeX()

Line 79 (original):

rpinfeas = rpinfeas / (dsdp->tracex + 1);

The primal infeasibility ||A*X - b||_inf is normalized by trace(X) + 1.
When the split-variable formulation creates huge primal variables, trace(X)
becomes ~10^7, making rpinfeas appear tiny (~10^-6) even when the absolute
constraint violation is 160. The solver then declares DSDP_PDFEASIBLE and
DSDP_CONVERGED for a completely wrong solution.

The same issue affects rpinfeas2 on line 89.

Additionally, when rpinfeas2 >= pfeastol (the primal is clearly infeasible),
the code at line 117 sets the convergence flag to DSDP_NUMERICAL_ERROR but
leaves pdfeasible as DSDP_PDFEASIBLE, which is inconsistent.

Concrete example

For the split-variable formulation of min -3x1 - 2x2 - 4x3 s.t. x1+x2+x3=3, x2+x3=2, x>=0 (expected optimal: x=[1,0,2], obj=-11):

Quantity	Value	What it should be
trace(X)	~9e7	~3
||AX - b||_inf	~160	~0
rpinfeas (normalized)	~1.8e-6	~16
Primal objective	-9.02e6	-11
StopReason	CONVERGED	NUMERICAL_ERROR
SolutionType	PDFEASIBLE	PDUNKNOWN

The relative gap between PP and DD objectives is small (both are ~-9.02e6), so
the convergence check passes. The primal infeasibility is hidden by the
trace(X) normalization. The solver confidently reports a correct optimal
solution when the answer is off by six orders of magnitude.

Fix Applied

File: src/solver/dsdpx.c

Change 1: Cap the normalizer (lines 79-85, 95-98)

/* Cap normalizer when tracex is hugely disproportionate to np,
   which indicates degenerate formulations (e.g., free variable
   splitting x=x+-x-) where primal variables grow unboundedly */
{ double normalizer = dsdp->tracex + 1;
  if (dsdp->np > 0 && dsdp->tracex > 1000.0 * dsdp->np)
    normalizer = 1000.0 * dsdp->np + 1;
  rpinfeas = rpinfeas / normalizer;
}

When trace(X) exceeds 1000 times the primal dimension np, the normalizer is
capped at 1000*np + 1. This catches degenerate cases (where trace(X)/np ~
10^6) while preserving behavior for well-conditioned problems (where trace(X)/np
is typically O(1) to O(100)).

Change 2: Set PDUNKNOWN on numerical error (line 126)

dsdp->pdfeasible = DSDP_PDUNKNOWN;
info = DSDPSetConvergenceFlag(dsdp, DSDP_NUMERICAL_ERROR);

When the primal infeasibility exceeds the tolerance, the solution type is now
set to PDUNKNOWN (previously left as PDFEASIBLE).

Results

• All 2870 existing tests still pass (zero regressions)
• Degenerate formulations now correctly report NUMERICAL_ERROR / PDUNKNOWN
  instead of falsely reporting CONVERGED / PDFEASIBLE
• Well-conditioned problems are unaffected

Verification

Direct formulation (no splitting):

StopReason = DSDP_CONVERGED (1)
SolType    = DSDP_PDFEASIBLE (1)
Objective  = -11.0  (correct)

Split-variable formulation, before fix:

StopReason = DSDP_CONVERGED (1)       <-- wrong
SolType    = DSDP_PDFEASIBLE (1)      <-- wrong
Objective  = -9.02e6                  <-- wrong

Split-variable formulation, after fix:

StopReason = DSDP_NUMERICAL_ERROR (-9)  <-- correct
SolType    = DSDP_PDUNKNOWN (0)         <-- correct

Additional C Code Issues Found

These were identified during the analysis but not fixed:

1. dualalg.c:289 -- Disabled verification loop:

   while (0 && psdefinite == DSDP_FALSE) {  // dead code

   This loop was meant to verify that the chosen barrier parameter produces a
   PSD matrix. The comment says "My tests say its not necessary" but it may
   matter for degenerate problems.

2. dsdplp.c:292-304 -- info variable reused as loop counter:

   for (info = 0; info < lpcone->n; info++) {
       if (xx[info] < 0) xx[info] = 0;
   }

   This overwrites the error code, corrupting subsequent DSDPCHKERR checks.

3. dsdpconverge.c:137, 185 -- Duplicate DSDPFunctionBegin macro calls
   (copy-paste bug).

4. sdpcompute.c:140-141 -- Dead code:

   method1 = DSDP_TRUE;
   method1 = DSDP_FALSE;  // immediately overwritten

5. dsdplp.c:675-676 -- Redundant assignments:

   lpcone->muscale = 1.0;
   if (n < 100) lpcone->muscale = 1.0;
   if (n < 10)  lpcone->muscale = 1.0;

Remaining Work

The C fix correctly detects the degenerate formulation but does not solve
it. The solver still cannot find the correct answer for split-variable problems.
To make the excluded MOI tests actually pass, the free-variable splitting must
be avoided entirely. Options:

1. Embed free variables in a PSD block: x free becomes a variable in
   [[t, x], [x', t]] >= 0 with t large enough. This preserves strict dual
   feasibility.

2. Use DSDP's BCone: Set large finite bounds on dual variables y via
   BConeSetLowerBound / BConeSetUpperBound, which effectively bounds the
   primal free variables.

3. Custom MOI bridge: Write a bridge that avoids x = x+ - x- for DSDP
   and instead uses one of the above strategies.

4. Detect and handle paired variables in the C code: Identify complementary
   pairs at setup time and treat them as a single free variable internally.

[odow]

Can we do anything about this in DSDP.jl?

But also, when Claude says things like "All 2870 existing tests still pass (zero regressions)", did it actually run the tests?

[blegat]

It ran the tests using his modified version of DSDP. One could add patches in Yggdrasil or maintain a fixed version of DSDP but I have no plan for doing this so this is up for grabs. My plan is instead to see if we can improve things at the level of MOI based on https://sburer.github.io/papers/020-freevars.pdf

[blegat]

Claude has tried the approaches of the paper.

1. PSD embedding (FreeToPSDBridge): Embedding each free variable z in a 2×2 PSD block [[t, z], [z, t]] ≽ 0 or [[t₁, z], [z, t₂]] ≽ 0. Failed because the auxiliary t variables have zero objective and constraint coefficients, producing zero diagonal in the dual slack matrix. The dual is never strictly feasible, which is the same fundamental problem as splitting.
2. BCone bounds (dual variable bounds y ∈ [-M, M]): Works when M is chosen correctly (M=100 gives good accuracy for simple problems), but M is problem-dependent. No single M works for all problems. Too tight clips the optimal; too loose doesn't regularize enough.
3. SOC → RSOC → PSD chain: For a single free variable, SOC(2) → RSOC(2) reduces to [t, u] ∈ Nonneg, which is equivalent to the splitting approach.

Even if DSDP were to support the SOC cone, it wouldn't help. The degeneracy is independent of the cone type.

For the SOC embedding (z₀, z) ∈ SOC(2), the dual slack is (s₀, s₁) ∈ SOC(2):

• s₀ = c_{z₀} - Σ yᵢ aᵢ,z₀
• Since z₀ is auxiliary (zero objective, no constraints): s₀ = 0 for all y
• SOC requires s₀ ≥ |s₁|, so 0 ≥ |s₁| → s₁ = 0
• Dual slack = (0, 0) — on the boundary, never strictly interior

Same for RSOC: (t, u, z) ∈ RSOC(3) with t, u auxiliary gives s_t = s_u = 0, then s_z² ≤ 2·s_t·s_u = 0 forces s_z = 0.

The fundamental issue: any auxiliary variable that doesn't participate in the objective or constraints produces a zero dual slack component, forcing the dual to the cone boundary. This is true for Nonneg (splitting), PSD (embedding), SOC, and RSOC alike.

In a primal-dual method (like SDPT3 or SeDuMi), both the primal and dual barriers keep iterates in the cone interior throughout the solve. The iterates approach the boundary gradually in a numerically controlled way. The paper's regularization (Algorithm 2) further stabilizes this. But DSDP is a dual-only method — it only uses the dual barrier.
This also explains why the paper found that SeDuMi handles split variables well without any modification — its homogeneous self-dual embedding inherently bounds the solution set, so the primal iterates can't diverge to infinity even with the splitting degeneracy.

Both CSDP and SDPA are primal-dual interior-point methods. They both also don't support free variables natively (same error message as DSDP: "Free variables are not supported"), so they rely on FreeBridge splitting too. But being primal-dual, they should handle the splitting degeneracy much better than DSDP — both barriers keep iterates in the cone interior during the solve.

The real fix for DSDP would be implementing Algorithm 2 from the paper (adaptive regularization of the Newton system in the C code), which handles the r → 0 transition gracefully. But that's beyond the scope of what we are going to do as JuMP developers.

[blegat]

But also, when Claude says things like "All 2870 existing tests still pass (zero regressions)", did it actually run the tests?

We was talking about the test of the C code, with his C fixes, the only advantage is that in some cases where DSDP was reporting MOI.OPTIMAL but wrong values, now the status is NUMERICAL_ERROR. One tests that apparently got fixed is test_HermitianPSDCone_basic

[odow]

I vote we just close this issue and add a deprecation warning to the top of the README. It's been 20 years since 2005. There are other solvers we can spend our time on.

[odow]

Closing as won't fix for now.