arxiv: 2605.04891 · v1 · submitted 2026-05-06 · 📡 eess.SY · cs.SY

Recognition: unknown

ADMM-based decomposed DNN+RLT Relaxations for Completely Positive Models in Electricity Market Clearing

Jan Kronqvist, Mohammad Reza Hesamzadeh, Mohammad Reza Karimi Gharigh, Shudian Zhao

Pith reviewed 2026-05-08 16:45 UTC · model grok-4.3

classification 📡 eess.SY cs.SY

keywords electricity market clearingcompletely positive programmingdoubly nonnegative relaxationreformulation-linearization techniquealternating direction method of multipliersADMMmarket optimization

0 comments

The pith

The proposed ADMM-based decomposed DNN+RLT relaxations of completely positive programs provide tighter lower bounds and faster solutions for electricity market clearing than standard LP relaxations.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The authors reformulate a mixed-integer linear program for day-ahead electricity market clearing with elementary, block, and flexible orders into an equivalent completely positive program. They create relaxed CPP variants and doubly nonnegative relaxations that decompose the problem into smaller positive semidefinite matrices while adding tailored reformulation-linearization inequalities. An alternating direction method of multipliers with adaptive penalty updates solves the resulting large-scale problems and supplies certified dual lower bounds that support early termination. A sympathetic reader would care because exact MILP solutions become intractable at scale and ordinary LP relaxations often yield weak bounds that hinder reliable market clearing decisions.

Core claim

Starting from a compact MILP formulation of welfare-maximizing market clearing, the paper derives an equivalent completely positive programming reformulation via matrix lifting. Relaxed CPP variants are introduced to reduce modeling burden while preserving strong bounds, followed by decomposed doubly nonnegative relaxations strengthened by RLT inequalities. These are solved using an ADMM scheme with adaptive penalties that yields rigorous dual lower bounds for certified early termination.

What carries the argument

The decomposed doubly nonnegative (DNN) relaxations of the completely positive programs, augmented with problem-specific RLT inequalities and solved by ADMM with adaptive penalty updates.

If this is right

Substantially tighter lower bounds on optimal market welfare than the LP relaxation of the MILP.
Significant reduction in computational effort for large instances through decomposition into smaller matrices and first-order optimization.
Certified solution quality via dual lower bounds that justify early algorithm termination.
Scalable handling of nonconvex order types in welfare-maximizing market clearing without solving the full MILP.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The decomposition strategy could be adapted to other block-structured nonconvex problems in energy system optimization.
Embedding the relaxations inside a branch-and-bound tree might produce practical exact solvers for medium-scale instances.
Testing the method on historical clearing data from real exchanges would reveal whether the synthetic-instance gains carry over to operational use.

Load-bearing premise

The relaxed CPP variants and decomposed DNN+RLT formulations maintain strong dual bounds without significant loss of tightness relative to the original MILP.

What would settle it

On a large synthetic market instance the obtained dual bound from the DNN+RLT model is no tighter than the LP relaxation bound of the original MILP, or the ADMM algorithm fails to produce a certified bound faster than a standard MILP solver.

read the original abstract

The day-ahead electricity market clearing with nonconvex order types can be formulated as a mixed-integer linear program (MILP), but its LP relaxation may provide weak bounds, and exact solutions can become computationally intractable in large-scale or extended market settings. We study a welfare-maximizing clearing model with elementary hourly orders, block orders with logical acceptance constraints, and flexible hourly orders. Starting from a compact MILP formulation, we derive an equivalent completely positive programming (CPP) reformulation via matrix lifting and propose relaxed CPP variants that further reduce the modeling burden while maintaining strong bounds. We then develop tractable doubly nonnegative (DNN) relaxations, including decomposed formulations that exploit the problem structure by using smaller positive semidefinite matrices. To further strengthen these bounds, we introduce reformulation-linearization technique (RLT) inequalities tailored to the decomposed structure. To tackle the challenge of large-scale DNNs, we design an alternating direction method of multipliers (ADMM) with adaptive penalty updates and rigorous dual lower bounds, enabling certified early termination. Computational experiments on synthetic instances show that the proposed DNN+RLT relaxations substantially tighten LP bounds, while decomposition and first-order methods significantly reduce computational effort.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper builds a decomposed DNN+RLT relaxation solved by ADMM for tightening bounds on nonconvex electricity market clearing, but the decomposition step risks weakening the dual bounds relative to the full DNN.

read the letter

The core contribution is a pipeline that starts from a compact MILP for day-ahead clearing with elementary, block, and flexible orders, lifts it to a completely positive program, relaxes to a doubly nonnegative form, decomposes the PSD blocks to exploit structure, adds tailored RLT cuts, and solves the result with ADMM plus adaptive penalties that supply certified dual lower bounds for early termination. On synthetic instances the authors report tighter LP bounds and lower runtimes than the plain relaxation or the non-decomposed version. That combination of lifting, structured decomposition, and first-order method with rigorous termination is the new piece for this domain. The formulation choices around the order types and the ADMM penalty update look standard but are applied cleanly to the market model. The dual-bound mechanism is a practical addition that lets the solver stop with a guarantee rather than an arbitrary iteration limit. The main soft spot is the decomposition itself. Splitting the lifted matrix into smaller PSD blocks enlarges the feasible set compared with the full DNN unless the coupling constraints and extreme rays are recovered exactly; the abstract claims no significant loss of tightness, yet the stress-test concern is live until the paper shows either a proof that the blocks preserve the same bound or numerical gaps between decomposed and full DNN on the same instances. The experiments are synthetic only, and the abstract gives no instance sizes, gap percentages, or baseline tables, so the size of the claimed improvement is still unclear. This work is aimed at people who already work on conic relaxations or market-design optimization and need a scalable way to get better dual bounds than LP without solving the full MILP. A reader who cares about ADMM on structured PSD problems or about electricity-market clearing will find the details worth reading. It is coherent on its own terms and engages the relevant lifting and decomposition literature, so it deserves a serious referee even if the tightness claim needs more evidence in revision.

Referee Report

2 major / 2 minor

Summary. The paper derives an equivalent CPP reformulation of a compact MILP for day-ahead electricity market clearing (with elementary, block, and flexible hourly orders) via matrix lifting, then introduces relaxed CPP variants and tractable DNN relaxations that include decomposed formulations exploiting problem structure with smaller PSD matrices. RLT inequalities are added to strengthen the decomposed DNNs, and an ADMM algorithm with adaptive penalty updates is developed to solve the resulting large-scale problems while supplying certified dual lower bounds for early termination. Computational experiments on synthetic instances are reported to show that the DNN+RLT relaxations substantially tighten LP bounds and that decomposition plus first-order methods reduce computational effort.

Significance. If the decomposed DNN+RLT formulations preserve tightness close to the full DNN (as claimed), the work provides a practical, scalable route to stronger dual bounds for nonconvex market-clearing problems that are otherwise intractable at scale. The combination of CPP lifting, structure-exploiting decomposition, tailored RLT cuts, and ADMM with rigorous dual bounds is a concrete methodological contribution to optimization in energy systems; the emphasis on certified bounds and early termination is particularly useful for real-time or large-scale applications.

major comments (2)

[Abstract and §4] Abstract and §4 (decomposed DNN+RLT): the claim that the decomposed formulations 'maintain strong dual bounds without significant loss of tightness' relative to the full DNN or original MILP is load-bearing for the headline result of substantial bound improvement. Block decomposition into smaller PSD matrices (even with coupling constraints and RLT cuts) enlarges the feasible set unless the paper proves that the extreme rays or the lifted matrix cone are recovered exactly; no such equivalence or gap bound is evident from the abstract description, and the skeptic concern on further relaxation therefore applies directly.
[§5] §5 (ADMM scheme): the 'rigorous dual lower bounds' supplied by the adaptive-penalty ADMM must be shown to be valid lower bounds on the decomposed DNN+RLT problem and, crucially, how any gap between the decomposed and full DNN propagates to these bounds. Without this, the justification for certified early termination and the assertion that the method still delivers substantially tighter bounds than the LP relaxation cannot be verified.

minor comments (2)

[Abstract] The abstract states that experiments demonstrate 'substantial' tightening and 'significant' reduction in effort but supplies no quantitative metrics, instance sizes, or comparison tables; these should be summarized with specific numbers (bound gaps, CPU times, number of instances) already in the abstract or introduction.
[§4] Notation for the decomposed PSD blocks and the coupling constraints should be made fully explicit (e.g., define the block sizes and the linking equalities) to allow readers to reproduce the decomposition.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive and detailed comments, which help clarify the presentation of our contributions on decomposed DNN+RLT relaxations and the ADMM solver. We address each major comment below and indicate planned revisions.

read point-by-point responses

Referee: [Abstract and §4] Abstract and §4 (decomposed DNN+RLT): the claim that the decomposed formulations 'maintain strong dual bounds without significant loss of tightness' relative to the full DNN or original MILP is load-bearing for the headline result of substantial bound improvement. Block decomposition into smaller PSD matrices (even with coupling constraints and RLT cuts) enlarges the feasible set unless the paper proves that the extreme rays or the lifted matrix cone are recovered exactly; no such equivalence or gap bound is evident from the abstract description, and the skeptic concern on further relaxation therefore applies directly.

Authors: We agree that the decomposition enlarges the feasible set in general and that an explicit analysis of the resulting relaxation gap is required to substantiate the claim of maintained tightness. The manuscript currently motivates the decomposition via problem structure (block and flexible orders leading to block-diagonal structure in the lifted matrix) and strengthens it with tailored RLT inequalities, with computational results on synthetic instances demonstrating that the obtained bounds remain substantially tighter than the LP relaxation. However, no formal gap bound or equivalence proof between the decomposed and full DNN cones is provided. In the revision we will add a dedicated paragraph or subsection in §4 that either derives a theoretical bound on the gap (e.g., via comparison of the extreme rays or via the coupling constraints) or explicitly quantifies the worst-case loss of tightness; we will also update the abstract to reflect this added analysis. revision: yes
Referee: [§5] §5 (ADMM scheme): the 'rigorous dual lower bounds' supplied by the adaptive-penalty ADMM must be shown to be valid lower bounds on the decomposed DNN+RLT problem and, crucially, how any gap between the decomposed and full DNN propagates to these bounds. Without this, the justification for certified early termination and the assertion that the method still delivers substantially tighter bounds than the LP relaxation cannot be verified.

Authors: The ADMM iterates are performed on the decomposed DNN+RLT formulation; the dual lower bounds are obtained from the dual of the augmented Lagrangian (with the adaptive penalty ensuring convergence properties) and are therefore valid lower bounds for the decomposed problem by standard ADMM duality arguments. Because the decomposed formulation is itself a relaxation of the full DNN (larger feasible set), any dual bound obtained for the decomposed problem is also a valid (though possibly weaker) lower bound for the full DNN and hence for the original CPP/MILP. We will revise §5 to include an explicit derivation of these dual bounds, a short paragraph explaining the propagation of the decomposition gap, and a statement that the resulting certified bounds remain strictly stronger than the LP relaxation whenever the RLT cuts are active (as confirmed by the experiments). This will also clarify the justification for early termination. revision: yes

Circularity Check

0 steps flagged

No circularity: standard matrix-lifting and relaxation pipeline with independent validation

full rationale

The derivation begins with an explicit MILP formulation of the market-clearing problem, applies matrix lifting to obtain an equivalent CPP model, then constructs DNN relaxations (including decomposed variants) and adds RLT cuts. These steps follow well-established conic-optimization techniques without any equation reducing a claimed bound or performance metric to a fitted parameter or self-referential definition. The ADMM solver with adaptive penalties is presented as a standard first-order method supplying certified dual bounds; no load-bearing self-citation or uniqueness theorem imported from the authors' prior work is invoked to force the result. Computational experiments on synthetic instances serve as external validation rather than part of the derivation chain itself. Consequently the central claims remain independent of their own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no explicit free parameters, axioms, or invented entities are stated. Standard ADMM penalty adaptation and matrix-lifting steps are assumed but not detailed.

pith-pipeline@v0.9.0 · 5526 in / 1106 out tokens · 52220 ms · 2026-05-08T16:45:59.918324+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

13 extracted references

[1]

PhD thesis, University of California, Los Angeles, 2011

Martin Skovgaard Andersen.Chordal sparsity in interior-point methods for conic optimization. PhD thesis, University of California, Los Angeles, 2011. 17

2011
[2]

On the copositive representation of binary and continuous nonconvex quadratic programs.Mathematical Programming, 120(2):479–495, 2009

Samuel Burer. On the copositive representation of binary and continuous nonconvex quadratic programs.Mathematical Programming, 120(2):479–495, 2009

2009
[3]

Chatzigiannis, Grigoris A

Dimitris I. Chatzigiannis, Grigoris A. Dourbois, Pandelis N. Biskas, and Anasta- sios G. Bakirtzis. European day-ahead electricity market clearing model.Electric Power Systems Research, 140:225–239, 2016

2016
[4]

Drew and Charles R

John H. Drew and Charles R. Johnson. The completely positive and doubly nonnegative completion problems.Linear and Multilinear Algebra, 44(1):85–92, 1998

1998
[5]

Conic relaxations of the unit commitment problem.Energy, 134:1079–1095, 2017

Salar Fattahi, Morteza Ashraphijuo, Javad Lavaei, and Alper Atamt¨ urk. Conic relaxations of the unit commitment problem.Energy, 134:1079–1095, 2017

2017
[6]

Johnson, Eduardo M

Robert Grone, Charles R. Johnson, Eduardo M. S´ a, and Henry Wolkowicz. Pos- itive definite completions of partial hermitian matrices.Linear algebra and its applications, 58:109–124, 1984

1984
[7]

Copositive duality for discrete energy markets.Available at SSRN 4964985, 2024

Cheng Guo, Merve Bodur, and Joshua Taylor. Copositive duality for discrete energy markets.Available at SSRN 4964985, 2024

2024
[8]

Non-stationary douglas–rachford and al- ternating direction method of multipliers: adaptive step-sizes and convergence

Dirk A Lorenz and Quoc Tran-Dinh. Non-stationary douglas–rachford and al- ternating direction method of multipliers: adaptive step-sizes and convergence. Computational Optimization and Applications, 74(1):67–92, 2019

2019
[9]

Non-convexities in european day-ahead electricity markets: Belgium as a case study

Mehdi Madani, Mathieu Van Vyve, Alain Marien, Marijn Maenhoudt, Patrick Luickx, and Andreas Tirez. Non-convexities in european day-ahead electricity markets: Belgium as a case study. In2016 13th International Conference on the European Energy Market (EEM), pages 1–5, 2016

2016
[10]

Admm for the sdp relaxation of the qap.Mathematical Programming Computation, 10(4):631–658, 2018

Danilo Elias Oliveira, Henry Wolkowicz, and Yangyang Xu. Admm for the sdp relaxation of the qap.Mathematical Programming Computation, 10(4):631–658, 2018

2018
[11]

A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique

Hanif D Sherali and Cihan H Tuncbilek. A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique. Journal of Global Optimization, 2(1):101–112, 1992

1992
[12]

Ryohei Yokoyama, Yuji Shinano, Syusuke Taniguchi, Masashi Ohkura, and Tet- suya Wakui. Optimization of energy supply systems by milp branch and bound method in consideration of hierarchical relationship between design and operation.Energy conversion and management, 92:92–104, 2015

2015
[13]

Chordal decomposition in operator-splitting methods for sparse semidefinite programs.Mathematical Programming, 180(1):489–532, 2020

Yang Zheng, Giovanni Fantuzzi, Antonis Papachristodoulou, Paul Goulart, and Andrew Wynn. Chordal decomposition in operator-splitting methods for sparse semidefinite programs.Mathematical Programming, 180(1):489–532, 2020. 18

2020