PaperlayerView exact revision on arXiv

Source-linked AI summary

DC3: A learning method for optimization with hard constraints

Priya L. Donti, David Rolnick, J. Zico Kolter

arXiv:2104.12225v1cs.LGmath.OCstat.ML

TL;DR

Large constrained optimization problems motivate fast neural approximators, but naive deep learning can produce infeasible outputs when hard constraints must hold. DC3 uses differentiable completion for equality constraints and gradient-based correction for inequality constraints, yielding solutions with significantly better feasibility and objective value than approximate deep-learning solvers on convex and non-convex tasks. Its procedure is broadly applicable, although completion and correction costs vary by setting.

  • Problem

    Large optimization problems need faster alternatives to expensive classical solvers, yet neural approaches often fail to satisfy hard constraints at test time.

  • Method

    DC3 outputs partial variables, differentiably completes them to satisfy equalities, and applies gradient-based correction to address inequality violations.

  • Results

    DC3 yields solutions with significantly better feasibility and objective value than other approximate deep-learning solvers on convex and non-convex optimization tasks.

  • Takeaways & Limitations

    The framework supports fast approximate solutions for optimization problems with hard constraints, including AC optimal power flow on electrical grids.

  • Takeaways & Limitations

    The expense of DC3’s completion and correction procedures varies with the setting, and gradient descent may converge more or less easily.

Abstract

from arXiv · show

Large optimization problems with hard constraints arise in many settings, yet classical solvers are often prohibitively slow, motivating the use of deep networks as cheap "approximate solvers." Unfortunately, naive deep learning approaches typically cannot enforce the hard constraints of such problems, leading to infeasible solutions. In this work, we present Deep Constraint Completion and Correction (DC3), an algorithm to address this challenge. Specifically, this method enforces feasibility via a differentiable procedure, which implicitly completes partial solutions to satisfy equality constraints and unrolls gradient-based corrections to satisfy inequality constraints. We demonstrate the effectiveness of DC3 in both synthetic optimization tasks and the real-world setting of AC optimal power flow, where hard constraints encode the physics of the electrical grid. In both cases, DC3 achieves near-optimal objective values while preserving feasibility.

1 INTRODUCTION

DC3 is introduced as a differentiable framework for applying deep learning to optimization with hard constraints. It combines equality completion and inequality correction to produce feasible approximate solutions while retaining near-optimal objectives.

  • The neural network outputs a partial variable assignment, which a differentiable completion procedure expands into a solution satisfying the equality constraints.Completion can be implemented explicitly or through the implicit function theorem.
  • A differentiable correction procedure addresses inequality violations while maintaining the equality constraints.The correction uses gradient-based steps along the manifold defined by the equalities.
  • DC3 is a general framework for incorporating potentially non-convex equality and inequality constraints into deep-learning optimization algorithms.
  • DC3 produces approximate solutions with significantly better feasibility than other deep-learning approaches while maintaining near-optimal solution quality.
  • AC optimal power flow provides a real-world application where the framework improves upon general-purpose deep-learning methods for a difficult non-convex grid optimization task.The task must be solved at scale and is critical for renewable energy adoption.

2 RELATED WORK

The work connects fast optimization methods with deep-learning approaches that approximate optimization, incorporate constraints, and use implicit layers to define structured input-output relationships.

  • Relationship to prior work: The approach draws inspiration from fast optimization, implicit layers, and incorporating constraints into neural networks.These areas are described as related strands of prior literature.
  • Fast optimization methods: Classical fast optimization methods include constraint and variable elimination, along with problem-specific techniques such as KKT factorization for convex quadratic programs.These methods target practical efficiency in solving optimization problems.
  • Fast optimization methods: Deep-learning approaches to speeding up optimization models have been organized into two main classes in prior reviews.The passage situates these approaches within work on combinatorial optimization, optimal power flow, and surrogate modeling.
  • Constraints in neural networks: Neural-network procedures can encode constraints through softmax layers, sigmoids, ReLUs, and convolutional layers.These examples represent simplex constraints, bounds, positive-orthant projections, and translational equivariance, respectively.
  • Implicit layers: Implicit layers define implicit relationships between neural-network inputs and outputs across applications including SAT solving, differential equations, games, rigid-body physics, and sequence modeling.The passage presents these layers as structured neural-network components.

3 DC3: DEEP CONSTRAINT COMPLETION AND CORRECTION

DC3 trains neural networks for constrained optimization by completing partial outputs to satisfy equalities and correcting inequality violations through differentiable procedures. It targets feasible, near-optimal approximate solutions without requiring supervised optimal-solution datasets.

  • DC3 trains directly from problem specifications rather than supervised datasets requiring known optimal solutions.This addresses the difficulty or expense of constructing training data with an exact solver.
  • Completion and correction are differentiable, allowing the neural network to account for constraint satisfaction during training and remain agnostic to network architecture.The framework backpropagates through explicit or implicit completion and unrolled correction procedures.
  • Specialized techniques may be more efficient for constraints with exploitable structure, while DC3 targets more general settings such as non-convex AC optimal power flow.The paper illustrates linear settings but motivates DC3 for non-convex problems lacking specialized structure.
  • Equality completion: The network outputs m variables, then an equality-completion procedure infers the remaining n−m variables to produce a full equality-feasible solution.Completion may be explicit or use implicit equations differentiated through the implicit function theorem.
  • Inequality correction: A gradient-based correction procedure moves completed points toward the inequality-feasible region while remaining on the equality-constraint manifold.The correction operates through gradient steps in the partial variables z.
  • Inequality correction: For general problems, gradient-based correction may not converge globally, whereas linear-constraint correction is mathematically guaranteed to converge.The procedure is expected to work in practice when initialized close to inequality feasibility.

4 EXPERIMENTS

DC3 is evaluated on convex quadratic programs, a simple non-convex task, and AC optimal power flow using optimality, feasibility, and speed criteria. Across these settings, DC3 preserves hard-constraint feasibility while achieving near-optimal objectives and substantially faster runtimes than classical or differentiable solvers.

  • 4.1 CONVEX QUADRATIC PROGRAMS: DC3 preserves both equality- and inequality-constraint feasibility while achieving a 10.59% average per-instance optimality gap on the convex QP task.Every baseline deep learning method significantly violates either equality or inequality constraints.
  • METHOD AND ABLATIONS: DC3 combines completion of partial network outputs with gradient-based correction, while ablations reveal that removing completion or correction violates the corresponding constraints.Completion is used for equality constraints, while correction addresses inequality constraints during training and inference.
  • 4.2 SIMPLE NON-CONVEX OPTIMIZATION: DC3 achieves an 8.02% per-instance optimality gap while maintaining feasibility on the simple non-convex task, and runs about 10× faster than IPOPT.Other evaluated deep learning methods violate constraints significantly.
  • 4.3 AC OPTIMAL POWER FLOW: DC3 achieves comparable objective values to the optimizer and preserves both equality- and inequality-constraint feasibility on ACOPF.Baseline deep learning methods and DC3 ablations show constraint violations.
  • 4.3 AC OPTIMAL POWER FLOW: 10× faster than PYPOWER, DC3 remains near-optimal on ACOPF, with a 0.22% per-instance optimality gap across 97 of 100 test instances.Three instances produced lower-than-optimal objective values reflecting slight constraint violations.

5 CONCLUSION

DC3 combines differentiable equality completion with inequality correction to produce fast approximate solutions that improve feasibility and objective value across convex and non-convex tasks. Its computational cost varies with the problem setting.

  • 5 CONCLUSION: DC3 outputs partial variables, differentiably completes equality-constrained solutions, and corrects inequality violations.The completion fills remaining variables according to equality constraints, while correction fixes inequality violations.
  • 5 CONCLUSION: DC3 yields significantly better feasibility and objective value than other approximate deep learning-based solvers on convex and non-convex optimization tasks.
  • 5 CONCLUSION: Completion and correction costs vary by setting, with implicit solutions potentially more time-consuming and gradient descent potentially converging more or less easily.

A ADDITIONAL QP TASK RESULTS

The additional QP results compare DC3 with other methods while varying the number of equality and inequality constraints for 100-variable problems.

  • A ADDITIONAL QP TASK RESULTS: Performance is compared on convex QPs with 100 variables as equality and inequality constraint counts vary.Equality-constraint counts are reported in Table A.1, while inequality-constraint counts are reported in Table A.2.

B DETAILS ON HYPERPARAMETER TUNING

The experiments fix several neural-network hyperparameters and tune remaining parameters using coordinate search, prioritizing feasibility before objective value and speed.

  • B DETAILS ON HYPERPARAMETER TUNING: Hidden layers use size 200, and the correction procedure uses momentum 0.5 across neural-network methods.
  • B DETAILS ON HYPERPARAMETER TUNING: Final timing experiments run all test datapoints in one batch, although training uses a different batch size.
  • B DETAILS ON HYPERPARAMETER TUNING: Table A.2 varies the number of inequality constraints from 10 to 90 for QPs with 100 variables and 50 equality constraints.
  • B DETAILS ON HYPERPARAMETER TUNING: Coordinate-search tuning prioritizes feasibility, followed by objective value and speed.Feasibility is assessed using mean and maximum equality and inequality violations.

B.1 CONVEX QUADRATIC PROGRAMS

For the convex QP experiments, DC3 hyperparameters were reused for two ablated variants rather than tuned separately, with correction learning rate ρx fixed at 10^-7.

  • B.1 CONVEX QUADRATIC PROGRAMS: DC3 hyperparameters are reused for “DC3,̸ ≤train” and “DC3, no soft loss” to reduce tuning.
  • B.1 CONVEX QUADRATIC PROGRAMS: The gradient-based correction procedure uses learning rate ρx = 10^-7 for all methods in these experiments.

B.2 SIMPLE NON-CONVEX OPTIMIZATION

The simple non-convex optimization experiments retained the hyperparameter settings selected for the convex QP task. This choice relied on the designed similarity between the tasks.

  • All hyperparameters were kept at the settings chosen for the convex QP task.
  • The selected settings were reused rather than retuned for the simple non-convex experiments.
  • This reuse was justified by the tasks being similar by design.

B.3 AC OPTIMAL POWER FLOW

The AC optimal power flow experiments report hyperparameter search ranges alongside central coordinate-search values and final parameter choices. To reduce tuning, DC3 settings were reused for two ablated variants.

  • Hyperparameter ranges were listed for each method, with central coordinate-search values italicized and final values bolded.
  • DC3 hyperparameters were reused for “DC3,̸ ≤train” and “DC3, no soft loss” instead of tuning those methods separately.
  • The reuse of DC3 settings was intended to minimize the amount of tuning.

C.1 PROBLEM SETTING

The problem setting defines ACOPF over buses partitioned into demand, reference, and remaining generator buses, then expresses voltage and power-flow constraints in rewritten form.

  • ACOPF is formulated as the optimization problem considered in Section 4.3.
  • Buses are partitioned into demand buses D, reference buses R, and remaining generator buses G = B \ (D ∪ R).Demand buses have zero active and reactive generation; reference buses have known voltage angle; remaining generator-bus angles are unknown.
  • The rewritten formulation includes voltage-magnitude bounds and a fixed reference-bus voltage angle.
  • It also imposes zero generation at demand buses and real and reactive power-flow equalities.
  • The voltage variables are represented through vr = |v| cos(∠v) and vi = |v| sin(∠v).
  • Some constraints, including (C.1b), (C.1c), and (C.1f), can be condensed in practice.

C.2 OVERALL APPROACH

DC3 predicts a partial variable set, completes it using equality constraints, and applies differentiable gradient-based correction for inequalities. In ACOPF, completion combines Newton updates with closed-form recovery of remaining variables.

  • Given pd, qd, (pg)G, and |v|B\D, the remaining ACOPF variables can be recovered from the power-flow equations.
  • The implementation outputs bounded partial variables α and β using sigmoid activations.
  • The completion procedure solves the equality constraints for remaining quantities, then a gradient-based correction enforces inequality feasibility.
  • The training loop computes the loss, backpropagates through the procedures, updates network parameters, and repeats until convergence.
  • In ACOPF, the network outputs (pg)G and |v|B\D, which serve as inputs to completion.The full-variable solve is split because Newton’s method for all variables can be unstable.
  • Step 1 uses Newton’s method for |v|D and (∠v)B\R, while Step 2 computes (pg)R and (qg)B\D from remaining equality constraints.Together, the two steps complete all decision variables.
Loading 2104.12225v1…