Skip to content

Extract PSD cones from unrestricted matrix variables - #3510

Draft
PTNobel wants to merge 11 commits into
masterfrom
codex/extract-unrestricted-psd
Draft

PTNobel wants to merge 11 commits into
masterfrom
codex/extract-unrestricted-psd

Conversation

@PTNobel

@PTNobel PTNobel commented Sep 5, 2026

Copy link
Copy Markdown
Collaborator

Description

For X = cp.Variable((n, n)), X >> 0 constrains the symmetric part of X. This PR recognizes the two-entry off-diagonal rows produced by symmetrization and extracts their PSD cone directly. A sparse change of coordinates separates the symmetric and skew components, transforms the objective and remaining constraints, and restores the full nonsymmetric primal solution and PSD dual. Batched matrices and DPP parameter updates are covered.

Extraction reserves both entries of each coordinate pair. Parameter-dependent, overlapping, and nonmatching blocks remain on the slack side. Pair extraction also stays disabled for native coordinate bounds or integrality; Moreau's bounds are already lowered to ordinary constraints. Other scaled PSD expressions are outside this follow-up's scope.

Type of change

  • New feature (backwards compatible)
  • New feature (breaking API changes)
  • Bug fix
  • Other (Documentation, CI, ...)

Contribution checklist

  • Add our license to new files. (No new files; existing headers retained.)
  • Check that your code adheres to our coding style.
  • Write unittests.
  • Run the unittests and check that they are passing.
  • Run the benchmarks to make sure your change does not introduce a regression.

Stack created with GitHub Stacks CLIGive Feedback 💬

PTNobel and others added 11 commits April 25, 2026 01:00
Solvers that expose an x_cone path (Moreau's XConeSpec) currently see
identity-pattern cone constraints (e.g. Variable(nonneg=True),
cp.SOC(t, x) on bare variables) routed through the slack side: a row of
Ax + s = b plus a cone on s. For those rows the slack is just a
renaming of x, so the equality is redundant and the cone can sit
directly on a subvector of the primal variable.

ExtractIdentityCones (cvxpy/reductions/cone2cone/) walks each NonNeg /
SOC constraint after ConeMatrixStuffing, checks the parameter tensor
for a structural -e_j^T pattern with zero offset (DPP-correct: the
check inspects problem.A directly, not a value snapshot), drops the
matching rows, and records (kind, x_indices, constr_id) on a new
problem.x_cones field. Solvers consume that list alongside the
reduced cone_dims; the dual for an extracted block falls out of the
KKT residual q + A.T z at the x indices.

Solvers opt in via Solver.x_cone_kinds() (default empty, so the chain
never inserts the reduction otherwise). MOREAU advertises
{nonneg, soc} when the installed Moreau exposes XConeSpec.

Perf on a randomly generated SOCP: ExtractIdentityCones runs in
about 9% of ConeMatrixStuffing time at n=800, m=300, d=80, and that
fraction shrinks as problems grow.

Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
Moreau now exposes a psd_triangle XConeSpec, so identity-pattern
SvecPSD constraints (e.g. cp.Variable((k,k), PSD=True) with no further
expression on top) can ride the x_cone path alongside nonneg / SOC.

The materialised A block for an SvecPSD constraint isn't pure
identity — entries take +1 on diagonal positions and +sqrt(2) on
off-diagonals (CVXPY's upper-triangle column-major svec convention,
matched to Moreau's svec_to_mat).  ExtractIdentityCones now
pre-populates an "expected value" per row of each candidate block
(1 for nonneg/soc/psd-diagonal, sqrt(2) for psd-off-diagonal) and
checks the materialised value against that, so the same vectorised
validity pass works for all three kinds.

MOREAU advertises:
  - SUPPORTED_CONSTRAINTS += SvecPSD
  - PSD_TRIANGLE_KIND = TriangleKind.UPPER, PSD_SQRT2_SCALING = True
  - x_cone_kinds() += 'psd_triangle'

Multi-cone SvecPSD (num_cones > 1) is left for slack-side handling
for now — it would need one XConeSpec per cone with a shared
constraint id.

Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
dims_to_solver_cones used to raise "Moreau does not support PSD cones"
the moment cone_dims.psd was non-empty.  That fires for any SvecPSD
constraint that ExtractIdentityCones can't take (multi-cone, e.g.
Variable((b, k, k), PSD=True), or non-identity A-block) since
ConeDims aggregates both PSD and SvecPSD constraints into psd_dims.

Moreau accepts psd_dims=[k_1, k_2, ...] on its Cones type for slack-
side PSD cones, so the right thing is to pass the dims through and let
the solver handle them — extraction still pulls the identity-pattern
single-cone case onto a psd_triangle x_cone.

Adds test_moreau_multicone_psd_via_slacks to lock in the slack-side
path against CLARABEL.

Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
Drops the bogus num_cones() == 1 guard on SvecPSD extraction, and fixes
a latent multi-cone SOC bug where the reduction was emitting one
XConeSpec covering the entire constraint instead of one per sub-cone
(Moreau would have interpreted that as a single big SOC).

Each candidate constraint now carries its per-sub-cone row sizes (and
psd_k for SvecPSD).  When the structural-pattern check passes for the
full constraint, the flat list of x indices is split into the
sub-cone chunks and one extracted tuple is emitted per cone, all under
the same constraint id.  Moreau's solve_via_data accumulates the
per-cone KKT residual slices in iteration order and concatenates them
to produce the per-constraint dual.

The expected-per-row identity value (1 on diagonal, sqrt(2) off) is
now tiled across the num_cones sub-cones of an SvecPSD so the global
validity pass works on multi-cone constraints unchanged.

Also raises explicitly on raw PSD constraints reaching the reduction
— expand_cones is supposed to convert them to SvecPSD upstream, so
seeing one is a chain-level contract violation.

Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
Generalises per-sub-cone metadata to a kwargs dict so extras like
alpha (PowCone3D) and alphas+dim2 (PowConeND) ride alongside psd_k
into Moreau's XConeSpec.  Formats SOC/Exp/Pow rows into the
cone-interleaved layout before scanning.

Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
## Description

Stacked on #3499. This follow-up can be deferred independently of the parent PR.

For `X = cp.Variable((n, n))`, `X >> 0` constrains the symmetric part of X. This PR recognizes the two-entry off-diagonal rows produced by symmetrization and extracts their PSD cone directly. A sparse change of coordinates separates the symmetric and skew components, transforms the objective and remaining constraints, and restores the full nonsymmetric primal solution and PSD dual. Batched matrices and DPP parameter updates are covered.

Extraction reserves both entries of each coordinate pair. Parameter-dependent, overlapping, and nonmatching blocks remain on the slack side. Pair extraction also stays disabled for native coordinate bounds or integrality; Moreau's bounds are already lowered to ordinary constraints. Other scaled PSD expressions are outside this follow-up's scope.

Validation: 132 tests and 23 subtests pass across the extraction, parameter-program, DPP, Moreau, and CLARABEL suites using the local Moreau 0.4.0-beta.1 CPU build. Tests cover a known nonsymmetric optimum and PSD dual, batched parameter updates with active bounds and skew constraints, and structural rejection. Pre-commit and type-checking the changed production files pass. Full-repository pyright reports an existing optional-iterable error in `geo_mean.py`. CI inherits the parent's unavailable `moreau>=0.4.0` release dependency.

## Type of change
- [x] New feature (backwards compatible)
- [ ] New feature (breaking API changes)
- [ ] Bug fix
- [ ] Other (Documentation, CI, ...)

## [Contribution checklist](https://www.cvxpy.org/contributing/index.html#contribution-checklist)
- [x] Add our license to new files. (No new files; existing headers retained.)
- [x] Check that your code adheres to our coding style.
- [x] Write unittests.
- [x] Run the unittests and check that they are passing.
- [ ] Run the benchmarks to make sure your change does not introduce a regression.

@claude claude Bot left a comment

Copy link
Copy Markdown

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM

@github-actions

github-actions Bot commented Sep 5, 2026

Copy link
Copy Markdown
Contributor

Benchmarks that have stayed the same:

Change Before [eb12874] After [ff1fd51] Ratio Benchmark (Parameter)
1.34±0.08s 1.39±0s 1.03 matrix_stuffing.ParamConeMatrixStuffing.time_compile_problem
2.93±0.02s 3.01±0.01s 1.03 quantum_hilbert_matrix.QuantumHilbertMatrix.time_compile_problem
155±0.7ms 157±2ms 1.01 high_dim_convex_plasticity.ConvexPlasticity.time_compile_problem
1.80±0.05s 1.82±0.05s 1.01 simple_LP_benchmarks.SimpleScalarParametrizedLPBenchmark.time_compile_problem
12.2±0.01s 12.2±0.01s 1 finance.CVaRBenchmark.time_compile_problem
1.86±0.01s 1.86±0s 1 finance.FactorCovarianceModel.time_compile_problem
2.86±0.02s 2.85±0.02s 1 gini_portfolio.Cajas.time_compile_problem
1.27±0.01s 1.28±0.03s 1 gini_portfolio.Yitzhaki.time_compile_problem
3.88±0.01s 3.89±0.01s 1 huber_regression.HuberRegression.time_compile_problem
3.34±0.01s 3.34±0s 1 matrix_stuffing.ConeMatrixStuffingBench.time_compile_problem
3.58±0.03s 3.56±0.03s 1 matrix_stuffing.ParamSmallMatrixStuffing.time_compile_problem
2.33±0.01s 2.33±0.01s 1 matrix_stuffing.SmallMatrixStuffing.time_compile_problem
4.33±0s 4.32±0s 1 optimal_advertising.OptimalAdvertising.time_compile_problem
20.4±0.02s 20.3±0.03s 1 sdp_segfault_1132_benchmark.SDPSegfault1132Benchmark.time_compile_problem
1.69±0.01s 1.69±0.01s 1 semidefinite_programming.SemidefiniteProgramming.time_compile_problem
707±1ms 710±1ms 1 simple_LP_benchmarks.SimpleFullyParametrizedLPBenchmark.time_compile_problem
10.2±0.01s 10.2±0s 1 simple_LP_benchmarks.SimpleLPBenchmark.time_compile_problem
2.01±0s 2.01±0.01s 1 simple_QP_benchmarks.LeastSquares.time_compile_problem
2.81±0.01s 2.81±0s 1 simple_QP_benchmarks.ParametrizedQPBenchmark.time_compile_problem
4.08±0.01s 4.09±0.02s 1 simple_QP_benchmarks.SimpleQPBenchmark.time_compile_problem
2.41±0s 2.41±0.01s 1 slow_pruning_1668_benchmark.SlowPruningBenchmark.time_compile_problem
4.43±0.01s 4.42±0.01s 1 svm_l1_regularization.SVMWithL1Regularization.time_compile_problem
1.15±0.01s 1.15±0s 0.99 gini_portfolio.Murray.time_compile_problem
3.70±0.01s 3.68±0.01s 0.99 simple_QP_benchmarks.UnconstrainedQP.time_compile_problem
1.48±0.01s 1.47±0s 0.99 tv_inpainting.TvInpainting.time_compile_problem

Base automatically changed from ptn/extract-identity-cones to master September 5, 2026 23:05

This branch has not been deployed

No deployments
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant