DC3: A learning method for optimization with hard constraints
Authors: Priya L. Donti
David Rolnick
J Zico Kolter
Venue: ICLR 2021 Poster (2021)
Keywords: approximate constrained optimization
implicit differentiation
optimal power flow
surrogate models

Abstract: 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.

Published as a conference paper at ICLR 2021
DC3: A LEARNING METHOD FOR OPTIMIZATION WITH HARD CONSTRAINTS
Priya L. Dontil. David Rolnick**, J. Zico Kolter
Carnegie Mellon University, MMcGill University and Mila, Bossh Center for Al pdont fecst cmu. edu, drolnickécs megill.ca, zxolterêcs cmu edu
ABSTRACT
Large optimization problems with hard constraints arise in many settings, yet clas- sical solvers are often prohibitively slow, motivating the use of deep networks as cheap "approximate solvers." Unfortunately, naive deep learning approaches typ- ically cannot enforce the hard constraints of such problems, leading to infeasible solutions. In this work, present Deep Constraint Completion and Correction (DC3), an algorithm to address this challenge. Specifically, this method enforces feasibility via differentiable procedure, which implicitly completes partial so- lutions 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.
INTRODUCTION
Traditional approaches constrained optimization are often expensive run for large problems, necessitating the use of function approximators. Neural networks are highly expressive and fast to run, making them ideal as function approximators. However, while deep learning has proven its power for unconstrained problem settings, it has struggled to perform well in domains where it necessary to satisfy hard constraints at test time. For example, in power systems, weather and climate models, materials science, and many other areas, data follows well-known physical laws, and violation these laws can lead to answers that are unhelpful or even nonsensical. There is thus need for fast neural network approximators that can operate in settings where traditional optimizers are slow (such as non-convex optimization), yet where strict feasibility criteria must be satisfied.
In this work, introduce Deep Constraint Completion and Correction (DC3), framework for applying deep learning to optimization problems with hard constraints. Our approach embeds dif- ferentiable operations into the training of the neural network ensure feasibility. Specifically, the network outputs a partial set of variables with codimension equal to the number of equality con- straints, and "completes" this partial set into a full solution. This completion process guarantees feasibility with respect to the equality constraints and is differentiable (cither explicitly, or via the implicit function theorem). We then fix any violations of the inequality constraints via differ- entiable correction procedure based on gradient descent. Together, this process of completion and correction enables feasibility with respect to all constraints. Further, this process is fully differen- tiable and can be incorporated into standard deep learning methods.
Our key contributions are:
Framework for incorporating hard constraints. We describe general framework, DC3, for incorporating (potentially non-convex) equality and inequality constraints into deep- learning-based optimization algorithms.
Practical demonstration feasibility. We implement the DC3 algorithm in both convex and non-conved optimization settings. We demonstrate the success of the algorithm in pro- ducing approximate solutions with significantly better feasibility than other deep learning approaches, while maintaining near-optimality of the solution.
"These authors contributed equally.

---

Published as a conference paper at ICLR 2021
AC optimal power flow. We show how the general DC3 framework can be used to opti- mize power flows on the electrical grid. This difficult non-convex optimization task must be solved at scale and is especially critical for renewable energy adoption. Our results greatly improve upon the performance of general-purpose deep learning methods on this task.
RELATED WORK
Our approach is situated within the broader literature on fast optimization methods, and draws inspi- ration from literature on implicit layers and incorporating constraints into neural networks. We briefly describe each of these areas and their relationship to the present work.
Fast optimization methods. Many classical optimization methods have been proposed to improve the practical efficiency of solving optimization problems. These include general techniques such as constraint and variable elimination (i.e., the removal of non-active constraints redundant variables, respectively), as well as problem-specific techniques (e.g., KKT factorization techniques in the case of convex quadratic programs) (Nocedal & Wrightt| 2006). Our present work builds upon aspects of this literature, applying concepts from variable elimination to reduce the number of degrees of freedom associated with the optimization problems we wish to solve.
In addition to the classical optimization literature, there has been large body of literature in deep learning that has sought approximate or speed up optimization models. As described in reviews on topics such as combinatorial optimization (Bengio et al., 2020) and optimal power flow (Hasan ctal, ML methods to speed up optimization models have thus far taken two main approaches. The first class of approaches, akin to work on surrogate modeling (Koziel & Leifsson| 2013), has involved training machine learning models to map directly from optimization inputs to full solu- tions. However, such approaches have often struggled to produce solutions that are both feasible and (ocar-)optimal. The second class of approaches has instead focused on employing machine learning approaches alongside in the loop of optimization models, c.g., to learn warm-start points (see, e.g.. Baker (2019) and Dong et al. (2020)) or to enable constraint elimination techniques by predicting active constraints (see, e.g., MMsra al. (2018). We view work part of the for- mer set of approaches, but drawing important inspiration from the latter: that employing structural knowledge about the optimization model is paramount achieving both feasibility and optimality.
Constraints in neural networks. While deep learning is often thought of as wholly unconstrained, in reality, it quite common incorporate (simple) constraints within deep learning procedures. For instance, softmax layers encode simplex constraints, sigmoids instantiate upper and lower bounds, ReLUs encode projections onto the positive orthant, and convolutional layers enforce translational equivariance (an idea taken further in general group-equivariant networks (Cohen & Welling, 2016)). Recent work has also focused on embedding specialized kinds of constraints into neural networks, such as conservation of energy (see, e.g.. Greydanus et al. (2019) and Beucler et al. (2019), and homogeneous linear inequality constraints (Frerix et al. 2020). However, while these represent common "special cases," there has to date been little work on building more general hard constraints into deep learning models.
Implicit layers. In recent years, there has been great deal of interest in creating structured neural network layers that define implicit relationships between their inputs and outputs. For instance, such layers have been created for SAT solving (Wang et al. 2019). ordinary differential equations (Chen et al., 2018). normal and extensive-form games (Ling et al. 2018). rigid-body physics (de Avila Belbute-Peres al. 2018), sequence modeling (Bai et al. 2019). J, and various classes of optimization (] & Krause 2017: Tsschattchhe et al., (Interestingly, softmax. sigmoid, and ReLU layers can also be viewed as implicit layers (Amos 2019) though in practice it is more efficient to use their explicit form.) In principle, such approaches could be used to directly enforce constraints within neural network settings, e.g.. by projecting neural network outputs onto constraint set using quadratic programming layers (Amos & Kolter 2017) in the case of linear constraints, or convex optimization layers (Agrawal et al. 2019) in the case of general convex constraints. However, given the computational expense of such optimization layers, these projection- based approaches are likely to be inefficient. Instead, approach leverages insights from this line of work by using implicit differentiation to backpropagate through the "completion" of equality constraints in cases where these constraints cannot be solved explicitly (such as in AC optimal power flow).
problems (Amos& & Kolter 2017 Donti et al.
2018 Wilder et al. 2018 Gould al. 2019
2

---

Published as a conference paper at ICLR 2021
3 DC3: DEEP CONSTRAINT COMPLETION AND CORRECTION
In this work, we consider solving families of optimization problems for which the objectives and/or constraints vary across instances. Formally, let æ E R denote the problem data, and y E 1² denote the solution of the corresponding optimization problem (where depends on œ). For any given I, our aim is then find solving:
minimize fV), s.t. gx(2) O, h. 0, yER"
(where f. g. and h are potentially nonlinear and non-convex). Solving such a family of optimization problems be framed learning problem, where algorithm must predict optimal from the problem data x. We consider deep learning approaches to this task - that is, training a neural network Ne, parameterized by to approximate y given
naive deep learning approach to approximating such problem involves viewing the constraints as a form of regularization. That is, for training examples x0(1,, the algorithm learns to minimize a composite loss containing both the objective and two "soft loss" terms representing violations of the equality and inequality constraints (for some >g. An > 0):
(on = (0) + Agll ReLU (O)I Au (
(2)
An alternative framework (see, e.g., Zamzam & Baker (2019) is to use supervised learning on examples (z((), ()) for which an optimum y is known. this case, the loss is simply |10 (
However, both these procedures for training neural network can lead in practice to highly infeasible outputs (as we demonstrate in our experiments), because they do not strictly enforce constraints. Supervised methods also require constructing a training set (e.g., via exact solver), sometimes difficult or expensive step.
To address these challenges, introduce the method of Deep Constraint Completion and Correc- tion (DC3), which allows hard constraints to be integrated into the training of neural networks. This method is able train directly from the problem specification (instead of supervised dataset), via the following two innovations:
Equality completion. We provide mechanism to enforce equality constraints during training and testing, inspired by the literature on variable elimination. Specifically, rather than outputting the full-dimensional optimization solution directly, we first output a subset of the variables, and then infer the remaining variables via the equality constraints either explicitly, or by solving an implicit set of equations (through which we can then backpropagate via the implicit function theorem).
Inequality correction. We correct for violation of the inequality constraints by mapping infeasible points feasible points using an internal gradient descent procedure during training. This allows us to fix inequality violations while taking steps along the manifold of points satisfying the equalities, which yields an output that is feasible with respect to all constraints.
Overall, our algorithm involves training neural network Na(x) to output partial set of vari- ables z. These variables are then completed to a full set of variables ý satisfying the equal- ity constraints. In turn, is corrected to to satisfy the inequality constraints while contin- uing to satisfy the equality constraints. The overall network is trained using backpropagation (which is necessary for correction, noted below). Importantly, both the com- pletion and correction pro- cedures are differentiable ei- ther implicitly or explicitly (allowing network training to take them into account), and the overall framework is ag- nostic to the choice of neu- ral network architecture. A schematic of the DC3 frame- work is given in Figure and corresponding pseudocode is given in Algorithm]
on the soft loss described in Equation
Loss Lson (0)
ming f2(2)
9. (x) 50 (x) =
(11, 1/, Va...., .b.)
Output ú
Inputxx
correction (s)
completion
neural network
D. U2, 0. Mn)
Figure 1: A schematic of the DC3 framework.
3

---

Published as a conference paper at ICLR 2021
Algorithm Deep Constraint Completion and Correction (DC3)
1:
assume equality completion procedure fz : I - RR // to solve equality constraints
2:
3:
procedure TRAIN(X)
4: init neural network Ng: R Rm while not converged do for x E X compute partial set of variables
5:
6:
No(x)
7:
complete to full set of variables y = [x" (=(2))]² E R
8: correct to feasible (or approx. feasible) solution á = p (mm)) (ū)
9: compute constraint-regullrizzel loss (ū)
10: update using (il
11: end while
12:
end procedure
14: procedure TEST(r, No)
15: compute partial set of variables No(
16:
complete to full set of variables y 12T
Pa(2)7]²
17: correct to feasible solution p!(em) (j)
18: return '
end procedure
We note that as this procedure is somewhat general, in cases where constraints have a specialized structure, specialized techniques may be more appropriate use. For instance, while examine linearly-constrained settings in our experiments for the purposes of illustration, in practice, tech- niques such as Minkowski-Wed decomposition Cholesky factorization (see Frerix et al.) (2020), Amos & Kolter (2017)) may be more efficient in these settings. However, for more general settings without this kind of structure c.g., non-convex problems such as AC optimal power flow, which we examine in our experiments the DC3 framework can provide (differentiable) mechanism for satisfying hard constraints. We now detail the completion and correction procedures used DC3.
(see/Freri
3.1 EQUALITY COMPLETION
Assuming that the problem (I) is not overdetermined, the number of equality constraints hz(y) 0 must not exceed the dimension of the decision variable y E R": that is, the number of equality constraints equals
m for some 2 O. Then, given m of the entries of feasible point y. the other (n - m) entries are, in general, determined by the (n (n-m) m) equality constraints. We exploit this observation in our algorithm, noting that it is considerably more efficient to output point in IR' and complete it to a point E RR" such that It, (1) = 0, as compared with outputting full-dimensional points y E R and attempting to adjust all coordinates satisfy the equality constraints.
In particular, we assume that given entries of y. we either can solve for the remaining entries ex- plicitly (e.g. in linear system) or that we have access a process (e.g. Newton's 's Method) allowing us to solve any implicit equations. Formally, we assume access to function Pr. RT - IR" such that ha ([=" (=(2))]²²) 0, where [>T (=(2))]² is the concatenation of and (2).
In our algorithm, we then train our neural network No to output points 2 E R" which are completed
[2T (2)7)) R" challenge then arises as to how to backpropagate the loss during the training of No if par(2) is not readily differentiable explicit function for example, if the completion procedure uses Newton's Method. We solve this challenge by leveraging the implicit function theorem, e.g. in OptNet (Amos& & Kolter 2017) and SATNet (Wang et al. 2019). This approach allows us to express, for any training loss E, the derivatives df/ds using dF)dp=(s).
Namely, let 1h E (R( denote the Jacobian of hz(v) with respect to By the chain rule:
d hr
([e(t))
Th Th @4p((2) Jhh J. + 2h Jhh dpz(2))
0 de
dz @pp(2) Oz
Oz
(z)(2)/0z
(J.m J.mmm
4

---

Published as a conference paper at ICLR 2021
We can then backpropagate losses through the network by noting that
de de de dpp(2z) al de (J -1
J.h
J.0mm
(4)
d2 dz d2)(2) Oz Oz @pp(2)
We note that in practice, the Jacobian 0p.(=1/0= should generally not be computed explicitly due to space complexity considerations; instead, it is often desirable to form the result of the left matrix- vector product (=) directly. This process is well-described in e.g. Amos & Kolter 2017). and also in detail for the problem of AC optimal power flow in Appendix
3.2 INEQUALITY CORRECTION
While the completion procedure described above guarantees feasibility with respect to the equality constraints, it does not ensure that the inequality constraints will be satisfied. To additionally ensure feasibility with respect to the inequality constraints, our algorithm incorporates correction proce- dure that maps the outputs from the previous step into the feasible region. In particular, we employ a gradient-base based correction procedure that takes gradient steps in towards the feasible region along the manifold of points satisfying the equality constraints.
Let (3) be the operation that takes input a point y - )x(=)T]², and moves it closer to satisfying the inequality constraints by taking a step along the gradient of the inequality violation with respect to the partial variables Formally, for learning rate O, we define:
Pr ((ante)) -Lanc) ~ (x) (
for A: V. ReLU 9e ([ ((outt)))] App())=
Opp(=)
Az.
Oz
While gradient descent methods do not always converge to global (or local) optima for general optimization problems, if initialized close to an optimum, gradient descent is highly effective in practice for non-pathological settings (see e.g. Busseti et al. (2019); Lee et al. (2017)) At test time, the input to the DC3 correction procedure should already be close to feasible with respect to the inequality constraints, as it is the output of a differentiable completion process that is trained
(0) using the soft loss son Therefore, we may expect that in practice, the limit lim Ps (y) will converge to a point satisfying both inequality and equality constraints (while for problems with linear constraints in 4..2) the correction process is mathematically guaranteed to converge).
As the exact limit lim;- Pe (y) is difficult to calculate in practice, we make approximations at both training and test time. Namely, we apply p (y) to the output of the completion procedure, with t = 4mmin relatively small train time to allow backpropagation through the correction. Depending on time constraints, this same value of t may be used at test time, or larger value t = fiest Imain may be used to ensure convergence to feasible point.
4 EXPERIMENTS
We evaluate DC3 for convex quadratic programs (QPs), a simple family of non-convex optimization problems, and the real-world task of AC optimal power flow (ACOPF) In particular, we assess our method on the following criteria:
Optimality: How good is the objective value (v) achieved by the final solution?
Feasibility: How much, if at all, does the solution violate the constraints? Specifically, what are the maximum and mean feasibility violations of the inequality and equality con- max (g (v))), mean (ReLU (v))), max(h, (v)), and mean(h, (v))?
straints:
Speed: How fast is the method?
Cooee for all experiments is availahle httpp:://githbb.cmmm// ab/Dc3
5

---

Published as a conference paper at ICLR 2021
We compare DC3 against the following methods (referred to by abbreviations in our tables below):
Optimizer: A traditional optimization solver. For convex QP settings, we use OSQP (Stel-) lato et al. 2020), as well as the batched, differentiable solver qpth developed as part of OptNet (Amos & Kolter 2017). For the generic non-convex setting, we use TPOPT (Wächter & Biegler 2006). For ACOPF, we use the solver provided by PYPOWER, a Python port of MATPOWER Zimmerman et al. 1997).
NN: A simple deep learning approach trained to minimize soft loss (Equation 2
papccideepppppeedd NN, v test: The NN approach, with gradient-based correction procedure applied to the output at test time in an effort to mitigate violations of equality and inequality constraints. Unlike in DC3, correction is not used during training, and completion is not used at all.
Eq. NN: A more sophisticated approach inspired by that in Zamzam & Baker 2019), where (i) the neural network outputs a partial set of variables 2, which is completed to the full set using the equality constraints, (ii) training is performed by supervised learning on optimal pairs (x)(), 2))) with loss function || 10 not using the objective value at all.
Eq. NN, < test: The approach in Eq. NN, augmented with gradient- bbase correction at test time to mitigate violations of equality and incquality constraints.
We also attempted use the output of the NN method as a "warm start" for traditional optimizers, but found that the NN output was sufficiently far from feasibility that it did not help.
In addition, we consider weaker versions of DC3 in which components of the algorithm are ablated:
DC3, A. The DC3 algorithm with completion ablated. All variables are output by the network directly and correction is performed by taking gradient steps for both equality and inequality constraints.
DC3, & train. The DC3 algorithm with correction ablated at train time. Correction is still performed at test time.
DC3, L train/test. The DC3 algorithm with correction ablated at both train and test time.
DC3, no soft loss. The DC3 algorithm with training performed to minimize the objective value only, without auxiliary terms capturing equality and inequality violation.
As our overall framework is agnostic to the choice of neural network architecture, to facilitate com- parison, we use a fixed neural network architecture across all experiments: fully connected with two hidden layers of size 200, including ReLU activation, batch normalization, and dropout (with rate 0.2) at each hidden layer (loffe & Szegedy 2015 Srivastava et al. 2014). For our correction proce- dure, we use lrriin hest 10 for the convex QP and simple non-convex tasks and braii Lestt for ACOPF (see Appendix B). All neural networks are trained using PyTorch (Paszke et al. 2019).
To generate timing results, all neural nets and the qpth optimizer were run with full paralleliza- tion on a GeForce GTX 2080 Ti GPU. The OSQP, IPOPT, and PYP OWER optimizers were run sequentially on an Intel Xeon 2.10GHz CPU, and we report the total time divided by the number of test instances to simulate full parallelization. As our implementations are not tightly optimized, we emphasize that all timing comparisons are approximate.
4.1 CONVEX QUADRATIC PROGRAMS
As first test of the DC3 method, we consider solving convex quadratic programs with a quadratic objective function and linear constraints. Note that we examine this simple task first for illustration,
Note that this correction procedure is not exactly the same as that described in Section 3.2 as the outputs of the NN baseline do not necessarily meet the prerequisite of satisfying the equality constraints. Instead, we adjust the full set of output variables directly with respect to gradients of the inequality and equality violations. *In Zamzam & Baker (2019), the authors employ one step of an ACOPF-spe specific heuristic called PV/PQ switching to correct inequality constraint violations at test time. We do not apply this heuristic here in the spirit of presenting more general framework. As PV/PQ switching is not necessarily guaranteed to correct all inequality violations (although it can work well in practice), in principle, one could consider employing combination of PV/PQ switching and gradient-hased corrections in the context of ACOPF.

---

Published as a conference paper at ICLR 2021
Obj. value
Max eq.
Mean eq.
Max ineq.
Mcan ineq.
Time (s)
Optimizer (OSQP)
-15.05 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.002 (0.000)
Optimizer (qpth)
-15.05 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
1.335 (0.012)
DC3
-13.46 (0.01)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.017 (0.001)
DC3,
-12.58 (0.04)
0.35 (0.00)
(0.00)
0.00 (0.00)
0.00 (0.00)
0.008 (0.000)
DC3, / train
-1.39 (0.97)
0.00 (0.00)
(0.00)
0.02 (0.02)
0.00 (0.00)
0.017 (0.000)
DC3, train/test
-1.23 (1.21)
0.00 (0.00)
00.000
0.09 (0.13)
0.01 (0.01)
0.001 (0.000)
DC3, no soft loss
-21.84 (0.00)
0.00
(0.00)
23.83 (0.11)
(0.01)
0.017 (0.000)
NN
-12.57 (0.01)
0.35 (0.00)
(0.00)
0.00 (0.00)
0.00 (0.00)
0.001 (0.000)
NN. S test
-12.57 (0.01)
0.35 (0.00)
(0.00)
0.00 (0.00)
0.00 (0.00)
0.008 (0,000)
Eq. NN
9.16
0.00 (0.00)
0.00 (0.00)
8.83 (0.72)
0.91 (0.09)
0,001 (0.000)
Eq. NN, I test
-14.68 (0.05)
0.00 (0.00)
0.00 (0.00)
0.89 (0.05)
0.07 (0.01)
0.018 (0.001)
Table I: Results on QP task for 100 variables, 50 equality constraints, and 50 inequality constraints. We compare the performance of DC3 and other algorithms according to the objective value and max/mean values of equalityinequality constraint violations, each averaged across test instances. We also compare the total time required to run on all 833 test instances, assuming full parallelization. (Std. deviations across 5 runs are shown in parentheses for all figures reported.) Lower values are better for all metrics. We find that methods other than DC3 and Optimizer violate feasibility (as shown in red). DC3 gives a feasible output with reasonable objective value 78x faster than qpth and only 9x slower than OSQ2, which is optimized for convex QPs.
but the general DC3 method is assuredly overkill for solving convex quadratic programs. It may not even be the most efficient deep learning-basse based method for constraint enforcement on this task, since more specialized techniques are available in such linearly constrained settings (Frerix et al. 2020).
We consider the following problem:
minimize yER"
2 + + - s.t. Ay = x,, Gy S h,
(5) Re
for constants Q E Raxn v 0. pe E ER. E Rma G E Minen X h E TRm and variable x E which varies between problem instances. We must learn to approximate the optimal y given
In our experiments, we take Q to be a diagonal matrix with all diagonal entries drawn i.i.d. from the uniform distribution on 1]. ensuring that Q is positive semi-definite. We take matrices A, G with entries drawn i.i.d. from the unit normal distribution. We assume that in each problem instance, all entries of x are in the interval [-1, 1]. In order to ensure that the problem is feasible, take h = Ej (GA+ )agl. where A is the Moore-Penrose pseudoinverse of A; namely, for this choice of h, the point y = A+ x is feasible (but not, in general, optimal), because:
AA+ ==== x,
GAtXS S
Σ (GGA)))) since |zyyl S
(6)
During training, we use examples x with entries drawn i.i.d. from the uniform distribution on [-1, 1].
Table [ compares the performance of DC3 (and various ablations of DC3) with traditional optimiz- ers and other deep leasning-based methods, for the case of n = 100 variables and Mey = Riney 50. In Appendix [A] we evaluate settings with other numbers of equality and inequality constraints. Each experiment is run 5 times for 10,000 examples x (with train/test/validation ratio 10:1:1). Hyperpa- rameters are tuned to maximize performance for each method individually (see Appendix BB.
We find that DC3 preserves feasibility with respect to both equality and inequality constraints, while achieving reasonable objective values. (The average per-instance optimality gap for DC3 over the classical optimizer is 10.59%.) For every baseline deep learning algorithm, feasibility is violated significantly for either equality or inequality constraints. As expected, "DC3 *" (completion ablated) results in violated equality constraints, while "DC3 z" (correction ablated) violates inequality constraints. Ablating the soft loss also results in violated inequality constraints, leading to objective value significantly lower than would be possible were constraints satisfied.
the other hand,
Even though we have not optimized the code of DC3 to be maximally fast, our implementation of DC3 still runs about 78x faster than the state-of-the-art differentiable QP solver hpth, and only
7

---

Published as a conference paper at ICLR 2021
Obj. value
Max eq.
Mcan eq.
Max ineq.
Mcan ineq.
Time (s)
Optimizer
-11.59 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.121 (0.000)
DC3
-10.66 (0.03)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.013 (0.000)
DC3, *
-10.04 (0.02)
0.35 (0.00)
0.13 (0.00)
0.00 (0.00)
(0.00)
0.009 (0.000)
DC3, H train
-0.29 (0.67)
0.00 (0.00)
0.00 (0.00)
0.01 (0.01)
(0.00)
0,010 (0.004)
DC3, / train/test
-0.27 (0.67)
0.00 (0.00)
0.00 (0.00)
0.03 (0.03)
(0.00)
0.001 (0.000)
DC3, no soft loss
-13.81 (0.00)
0.00 (0.00)
0.00
15.21 (0.04)
2.33 (0.01)
0.013 (0.000)
NN
-10.02 (0.01)
0.35 (0.00)
0.13 (0.00)
0.00 (0.00)
0.00 (0.00)
0.001 (0.000)
NN, S test
-10.02 (0.01)
0.35 (0.00)
0.13 (0.00)
0.00 (0.00)
(0,00)
0.009 (0.000)
Eq. NN
-3.88 (0.56)
0.00 (0.00)
0.00 (0.00)
6.87 (0.43)
(0.05)
0,001 (0.000)
Eq. NN, I test
-10.99 (0.03)
0.00 (0.00)
0.00 (0.00)
0.87 (0.04)
0.06 (0.00)
0.013 (0.000)
Table 2: Results on our simple nonconvex task for 100 variables, 50 equality constraints, and 50 inequality constraints, with details as in Table [ Since this problem is nonconvex, we use IPOPT as the classical optimizer. DC3 is differentiable and about 9x faster than IPOPT, giving a near- optimal objective value and constraint satisfaction, in contrast to baseline deep learning-based meth- ods which result in significant constraint violations.
about 9x slower than the classical optimizer OSQP, which is specifically optimized for convex QPs. Furthermore, this assumes OSQP is fully parallelized in this case, across 833 CPUs whereas standard, non-parallel implementations of ÓSQP would be orders of magnitude slower. By contrast, DC3 is easily parallelized within single GPU using standard deep learning frameworks.
4.2
SIMPLE NON-CONVEX OPTIMIZATION
We now consider a simple non-convex adaptation of the quadratic program above:
1 Qy + p" sin(y), s. t. Ay = x. Gy S h,
minimize yER" 2
where sin(y) denotes the componentwise application of the sine function to the vector y, and where all constants and variables are defined as in 5 We consider instances of this problem where all parameters are drawn randomly as in our preceding experiments in the convex setting.
In Table 2 we compare the performance of DC3 and other deep learning- based methods against the classical non-convex optimizer IPOPT We find that DC3 achieves good objective values (8. 02.0%% per-instance optimality gap), while maintaining feasibility. By contrast, all other deep learning- based methods that we consider violate constraints significantly. DC3 also runs about 10x faster than IPOP even assuming IPOPT is fully parallelized. (Even on the CPU, DC3 takes 0.030 + 0.000 seconds, about 4x faster than IPOPT.) Note that the DC3 algorithm is essentially the same between the convex QP and this non-convex task, since only the objective function is altered.
4.3 AC OPTIMAL POWER FLOW
We now show how DC3 can be applied to the problem of AC optimal power flow (ACOPF). ACOPF is a fundamental problem for the operation of the electrical grid, and is used to determine how much power must be produced by each generator on the grid in order meet demand. As the amount of renewable energy on the power grid grows, this problem must be solved more and more frequently to account for the variability of these renewable sources, and at larger scale account for an increasing number of distributed devices (Rolnick et al. 2019). However, ACOPF is a non-convex optimization problem and classical optimizers scale poorly on it. While specialized approaches to this problem have started to emerge, including using machine learning (see, e.g.. Zamzam & Baker (2019) for discussion), we here assess the ability of our more general framework to address this problem.
Formally, a power network may be considered as a graph on i nodes, representing different locations (buses) within the electrical grid, and with edges weighted by complex numbers waj E C (admit- tances) that represent how casily current can flow between the corresponding locations in the grid. Let W E Cb*b denote the graph Laplacian (or nodal admittance matrix). Then, the problem of ACOPF can be defined as follows: Given input variables pa R². qa I (representing real power
We initialize the optimizer using the feasible point y A noted in Equation
8

---

Published as a conference paper at ICLR 2021
Obj. value
Max eq.
Mcan eq.
Max incq.
Mcan ineq.
Time (8)
Optimizer
3.81 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.949 (0.002)
DC3
3.82 (0.00)
0.00 (0.00)
0.00 (0.00)
(0.00)
0.00 (0.00)
0.089 (0.000)
DC3, ,
3.67 (0.01)
0.14 (0.01)
0.02 (0.00)
(0.00)
0.00 (0.00)
0.040 (0.000)
DC3, / train
3.82 (0.00)
0.00 (0.00)
(0.00)
(0.00)
0.00 (0.00)
0.089 (0.000)
DC3, z train/test
3.82 (0.00)
0.00 (0.00)
0.00 (0.00)
0.01 (0.00)
(0.00)
0.039 (0.000)
DC3, no soft loss
3.11 (0.05)
2.60 (0.35)
0.07 (0.00)
2.33
0.03 (0.01)
0.088 (0.000)
NN
3.69 (0.02)
0.19 (0.01)
0.03 (0.00)
0.000)
(..00)
0.001 (0.000)
NN, < test
3.69 (0.02)
0.16 (0.00)
(0.00)
0.00 (0.00)
0.00 (0.00)
0.040 (0.000)
Eq. NN
3.81 (0.00)
0.00 (0.00)
0.00
0.15
0.00 (0.00)
0.039 (0.000)
Eq. NN. & test
3.81 (0.00)
0.00 (0.00)
0.00 (0.00)
0.15 (0.01)
0.00 (0.00)
0.078 (0.000)
Table 3: Results on ACOPF over 100 test instances. We compare the performance of DC3 and
other algorithms according to the metrics described in Table I. We find again that baseline methods violate feasibility (as shown in red), while DC3 gives a feasible and near-optimal output about 10x faster than the PYPOWER optimizer, even assuming that PYPOWER is fully parallelized.
and reactive power demand at the various nodes of the graph), output the variables Py E TR. 9g E TR (representing real power and reactive power generation) and e E Ch (representing real and imagi- nary voltage), according to the following optimization problem:
minimize ER*; 4, 4RER,, NECs
Pg Apg + b² Pg
subject to Pg S S Pg max min S qg S
4g
4g max min
<
|0|
S v max
(Pg - pa) + (9g qa)i = diag(v) (w)
More details about how we apply DC3 to the problem of ACOPF are given in Appendix
We assess our method on a 57-node power system test case available via the MATPOWER package. We conduct 5 runs over 1,200 input datapoints (with a train/test/validation ratio of 10:1:1). As with other tasks, hyperparameters for ACOPF were tuned to maximize performance for each method individually (see Appendix B}. Optimality, feasibility, and timing results are reported in Table 3
We find that DC3 achieves comparable objective values the optimizer, and preserves feasibility with respect to both equality and inequality constraints. Once again, for every baseline deep learning algorithm, feasibility is violated significantly for either equality or inequality constraints. Ablations of DC3 also suffer from constraint violations. though the effect is less pronounced than for the con- vex QP and simple non-convex settings, especially for ablation of the correction (perhaps because the incquality constraints here are easier to satisfy than the equality constraints). We also that DC3 rums about 10x faster than the PYPOWER optimizer, even when PYP SYPOWER is fully parallelized. (Even when running on the CPU, DC3 takes 0.906 + 0.003 seconds, slightly faster than P PYPOWER.)
Out of 100 test instances, there were 3 on which DC3 output swwer-than-optimal objective values of up to few percent (-0.30%, -.85%, -5.51%), reflecting slight constraint violations. Over the other 97 instances, the ver-instance optimality gap compared to the classical optimizer was 0.22%
CONCLUSION
We have described a method, DC3, for fast approximate solutions to optimization problems with hard constraints. Our approach includes a neural network that outputs a partial set of variables, a differentiable completion procedure that fills in remaining variables according to equality con- straints, and differentiable correction procedure that fixes inequality violations. We find that DC3 yields solutions of significantly better feasibility and objective value than other approximate deep baaming-based solvers on convex and non-convex optimization tasks.
We note that, while DC3 provides a general framework for tackling constrained optimization, de- pending the setting, the expensiveness of both the completion and correction procedures may vary (e.g., implicit solutions may be more tine-consuming, or gradient descent may converge more or less easily). We believe that, while our method stated is broadly applicable, it will be possible in future work to design further improvements tailored to specific problem instances, for example by designing problem-dependent correction procedures.
9

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGMENTS
This work was supported by the U.S. Department of Energy Computational Science Graduate Fel- lowship (DE-FG02- PGG02997ER25008) U.S. National Science Foundation (DMS-1803441 the Center for Climate and Energy Decision Making through a cooperative agreement between the National Science Foundation and Carnegie Mellon University (SES-00949710), the Computational Sustain- ability Network, and the Bosch Center for Al.
We thank Shaojie Bai, Rizal Fathony, Filippe de Avila Belbute Peres, Josh Williams, and anonymous reviewers for their feedback on this work.
REFERENCES
Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond, and Zico Kolter. Differentiable convex optimization layers. Advances in Neural Information Processing Systems (NeurIPS), 2019.
Brandon Amos. Differentiable optimization-based modeling for machine learning. PhD thesis, Carnegie Mellon University, 2019.
Brandon Amos and Zico Kolter. OptNet: Differentiable optimization as a layer in neural networks. In International Conference on Machine Learning (ICML), 2017.
Shaojie Bai, Zico Kolter, and Vladlen Koltun. Deep equilibrium models. Advances in Neural Information Processing Systems (NeurIPS), 2019.
Kyri Baker. Learning warm-start points for AC optimal power flow. In 2019 IEEE 29th International Workshop Machine Learning for Signal Processing (MLSP), pp. 1-6, 2019.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimiza- tion: methodological tour d'horizon. European Journal of Operational Research, 2020.
Tom Beucler, Stephan Rasp, Michael Pritchard, and Pierre Gentine. Achieving conservation of energy in neural network emulators for climate modeling. Preprint arXiv: 1906.06626, 2019.
Enzo Busseti, Walaa M Moursi, and Stephen Boyd. Solution refinement at regular points of conic problems. Computational Optimization and Applications, 74(3):627-643, 2019.
Ricky TQ Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud. Neural ordinary differential equations. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
Taco Cohen and Max Welling. Group equivariant convolutional networks. International Confer-
on Machine Learning (ICML), 2016.
Filipe de Avila Belbute-Peres, Kevin Smith, Kelsey Allen, Josh Tenenbaum, and Zico Kolter. End-to-end differentiable physics for learning and control. In Advances in Neural Information Processing Systems (NeurIPS), 2018
Josip Djolonga and Andreas Krause. Differentiable learning of submodular models. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
Wenqian Dong, Zhen Xie, Gokcen Kestor, and Dong Li. Smart-PGSim: Using neural network to accelerate AC-OPF power grid simulation. arXiv preprint arXiv:2008.1 //827, 2020.
Priya I. Donti, Brandon Amos, and Zico Kolter. Task-based end-to-end model learning in stochastic optimization. Preprint arXiv:1703.04522 2017.
Thomas Frerix, Matthias Nießner. and Daniel Cremers. Homogeneous linear inequality constraints for neural network activations. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pp. 748-749, 2020.
Stephen Gould, Richard Hartley, and Dylan Campbell. Deep declarative networks: A new hope. Preprint arXiv: eox::19990 1909. 099664 2019.
10

---

Published as a conference paper at ICLR 2021
Samuel Greydanus, Misko Dzamba, and Jason Yosinski. Hamiltonian neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2019. 2019.
Fouad Hasan, Amin Kargarian, and Ali Mohammadi. A survey on applications of machine learning for optimal power flow. In 2020 IEEE Texas Power and Energy Conference (TPEC), pp. 1-6. IEEE, 2020.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning (ICML), 2015.
Slawomir Koziel and Leifur Leifsson. Surrogate-based modeling and optimization. Springer, 2013.
Jason D Lee, loannis Panageas, Georgios Piliouras, Max Simchowitz, Michael Jordan, and Ben- jamin Recht. First-order methods almost always avoid saddle points. Preprint arXiv: 2017.
Chun Kai Ling, Fei Fang. and Zico Kolter. What game are we playing? End-to-end learning in normal and extensive form games. Preprint arXiv: 1805.02777, 2018.
Sidhant Misra, Line Roald, and Yeesian Ng. Learning for constrained optimization: Identifying optimal active constraint sets. Preprint arXiv:1802.09669 2018.
Jorge Nocedal and Stephen Wright. Numerical optimization. Springer Science & Business Media, 2006.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. PyTorch: imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
David Rolnick, Priya L Donti, Lynn H Kaack, Kelly Kochanski, Alexandre Lacoste, Kris Sankaran, Andrew Slavin Ross, Nikola Kilojevic-Dupont, Natasha Jaques, Anna Waldman-Brown, et al. 05433, 2019.
Tackling climate change with machine learning. Preprint
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 1929-1999- 2014.
B. Stellato, G. Banjac, P. Goulart, A. Bemporad, and S. Boyd. OSQP: an operator splitting solver for quadratic programs. Mathematical Programming Computation, 12(4))637-672, 2020.
Sebastian Tschiatschek, Aytunc Sahin, and Andreas Krause. Differentiable submodular maximiza- tion. Preprint arXiv: /rXivv/803..011 01788018...8.. 2018.
Andreas Wächter and Lorenz T Biegler. On the implementation of an interior-point filter line- search algorithm for large-scale nonlinear programming. Mathematical programming, 106(1): 25-57, 2006.
Po-Wei Wang, Priya L Donti, Bryan Wilder, and Zico Kolter. SATNet: Bridging deep learning and logical reasoning using differentiable satisfiability solver. In International Conference Machine Learning (ICML), 2019.
Bryan Wilder, Bistra Dilkina, and Milind Tambe. Melding the data-decisions pipeline: Decision- focused learning for combinatorial optimization. In AAAI Conference Artificial Intelligence, 2018.
Ahmed Zamzam and Kyri Baker. Learning optimal solutions for extremely fast AC optimal power flow. Preprint arXiv: /9100012 2019.
Ray D Zimmerman, Carlos E Murillo-Sánchez, and Deqiang Gan. MATPOWER: A MATLAB power system simulation package. Manual, Power Systems Engineering Research Center, Ithaca NY, 1, 1997.
11

---

Published as a conference paper at ICLR 2021
Obj. val.
-27.26 (0.00)
-23.13 (0.00)
-15.05 (0.00)
-14.80 (0.00)
-4.79 (0.00)
Optimizers (OSQP, qpth)
Max eq.
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
Max ineq.
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
Obj. val.
-25.79 (0.02)
-20.29 (0.20)
-1.44 (0.01)
13.73 (0.02)
-4.76 (0.00)
DC3
Max eq.
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
Max ineq.
0.00 (0.00)
(0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
Obj. val.
-22.59 (0.18)
-20.40 (0.03)
-12.58 (0.04)
-1336 (0.02)
-5.27 (0.00)
DC3, +
Max eq.
0.12 0.12 (0.01)
0.24 (0.00)
0.35 (0.00)
0.47 (0.00)
0.59 (0.00)
Max ineq.
0.00 (0.00)
(0,00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
Obj. val.
-25.75 (0.04)
-0.15)
-1.39 (0.97)
-13.71 (0.04)
-4.75 (0.00)
DC3, E train
Max eq.
0.00 (0.00)
00.000
0.00 (0.00)
0.00 (0.00)
0,00 (0.00)
Max ineq.
0.00 (0.00)
0.00
0.02 (0.02)
0.00 (0.00)
(0.00)
Ohj. val.
-25.75 (0.04)
(0.15)
-1.23 (1.21)
-13.71 (0.04)
-4.75 (0.00)
DC3, & train/test
Max eq.
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
Max ineq.
0.00 (0.00)
0.00 (0.00)
0.09 (0.13)
0.00 (0.00)
0,00 (0.00)
Ohj. val.
-66.79 (0.01)
-0.63 (0.02)
-21.84 (0.00)
-15.56 (0.02)
4.76
DC3, no soft loss
Max eq.
0.00 (0.00)
0..000
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
Max ineq.
122.52 (0.22)
50.25 (0.14)
23.83 (0.11)
5.85 (0.18)
0.00 (0.00)
Obj. val.
-22.65 (0.12)
-20.33 (0.03)
-1255 (0.01)
-13.55 (0.03)
-5.29 (0.02)
NN
Max eq.
0.11 (0.01)
0.24 (0.00)
0.35 (0.00)
0.47 (0.00)
0.59 (0.00)
Max ineq.
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
Obj. val.
-22.65 (0.12)
20.43 (0.03)
-1.57 (0.01)
-13.3 (0.03)
-5.29 (0.02)
NN, S test
Max eq.
0.11 (0.01)
0.24 (0.00)
0.35 (0.00)
0.47 (0.00)
0.59 (0.00)
Max ineq.
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
Obj. val.
-27.20 (0.02)
-22.74 (0.14)
9.16 (0.75)
14.64 (0.01)
.4.74 (0.01)
Eq. NN
Max eq.
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
Max incq.
0.43 (0.02)
1.37 (0.09)
8.83 (0.72)
0.86 (0.05)
0,00 (0.00)
Obj. val.
-27.20 (0.02)
22.76
-14.68 (0.05)
-4465 (0.01)
-4.74 (0.01)
Eq. NN, < test
Max eq.
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
Max ineq. 0.42 (0.02)
1.27 (0.09)
0.89 (0.05)
0.85 (0.05)
0.00 (0.00)
Table A.1: Results on QP task for 100 variables and 50 inequality constraints, as the number of
equality constraints varies 10, 30, 50, 70, 90. We compare the performance of DC3 and other algorithms according to objective value and maximum equality/inequaiity constraint violations av- eraged across test instances. (Standard deviations across 5 runs shown in parentheses.) We find that neural network basclines give significantly inferior performance (shown in red) across all problems.
A ADDITIONAL QP TASK RESULTS
We compare the performance of DC3 against other methods for the convex QP task with 100 vari- ables, as the number of equality constraints (Table A.1 and inequality constraints (Table A.2 varies.
B DETAILS ON HYPERPARAMETER TUNING
The following parameters were kept fixed for all neural network-based methods across exper- iments, based on small amount of informal experimentation to ensure training was stable and properly converged:
Epochs: 1000
Batch size 200
Hidden layer size: 200 (for both hidden layers)
Correction procedure stopping tolerance: 10-4
Correction procedure momentum: 0.5
While this hatch size used for training, final timing experiments were run with all test datapoints in batch.
12

---

Published as a conference paper at ICLR 2021
30
50
70
90
Obj. val.
-17.33 (0.00)
-16.33 (0.00)
-15.05 (0.00)
-14.61 (0.00)
-14.26 (0.00)
Optimizers (OSQP, qpth)
Max eq.
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
Max ineq.
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
Obj. val.
-15.18 (0.31)
-13990 (0.20)
-13.46 (0.01)
10.522 (0.93)
-11.77 (0.07)
DC3
Max eq.
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
Max ineq.
(0.00)
0.00 (0.00)
00.000.00)
0.00 (0.00)
0.00 (0.00)
Obj. val.
-15.66 (0.05)
(4.10
-12.58 (0.04)
-12110 (0.03)
-11.72 (0.03)
DC3, +
Max eq.
0.35 (0.00)
(0.00)
0.35 (0.00)
0.35 (0.00)
0.35 (0.00)
Max ineq.
0.00 (0.00)
0.00 (0.00)
0.00
0.00 (0.00)
0.00 (0.00)
Ohj. val.
-15.60 (0.30)
-13.83 (0.15)
(0.97)
-11144 (0.05)
-11.76 (0.06)
DC3, 1 train
Max eq.
0.00 (0.00)
0..0
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
Max ineq.
0.00 0.00 (0.00)
0.00
0.02 (0.02)
0.00 (0.00)
0.00 (0.00)
Ohj. val.
(0.300
-13.83 (0.15)
-1.23 (1.21)
-11.14 (0.05)
-11.76 (0.06)
DC3, 1 train/test
Max eq.
(0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00
Max ineq.
0.00 (0.00)
0.00 (0.00)
0.09 (0.13)
0.00 (0.00)
0.00 (0.00)
Ohj. val.
-21.78 (0.01)
-21722 (0.03)
-21.84 (0.00)
-21.82 (0.01)
-21.33 (0.00)
DC3, no soft loss
Max eq.
0.00 0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
Max ineq.
23.85 (0.52)
23.54 (0.23)
23.83 (0.11)
23.73 (0.09)
23.69 (0.06)
Obj. val.
-15.66 (0.03)
-14.00 (0.05)
-12.57 (0.01)
-12.12 (0.03)
-11.70 (0.02)
NN
Max eq.
0.35 (0.00)
0.35 (0.00)
0.35 (0.00)
0.35 (0.00)
0.35 (0.00)
Max incq.
0.00 (0.00)
0.00 (0.00)
(0.00)
0.00 (0.00)
0.00 (0.00)
Obj. val.
-15.66 (0.03)
-1..10 (0.05)
-12.57 (0.01)
-12.12 (0.03)
-11.70 (0.02)
NN, S test
Max eq.
0.35 (0.00)
0.35 (0.00)
0.35 (0.00)
0.35 (0.00)
0.35 (0.00)
Max incq.
(0.00)
(0.00)
(0.00)
0.00 (0.00)
0.00 (0.00)
Obj. val.
-17.07 (0.20)
-15.45 (0.09)
(0.75)
-14.2 (0.06)
-14.10 (0.
Eq. NN
Max eq.
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
Max ineq.
1.65 (0.22)
1.79 (0.10)
8.83 (0.72)
2.26 (0.04)
1,28 (0.05)
Obj. val.
-17.06 (0.20)
-15.65 (0.09)
-14.68 (0.05)
-14.31 (0.06)
-14.10 (0.10)
Eq. NN, S test
Max eq.
(0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
0.00 (0.00)
Max ineq.
1,53 (0.19)
1.58 (0.08)
0.89 (0.05)
1.92 (0.04)
1.25 (0.04)
Table A.2: Results on QP task for 100 variables and 50 equality constraints. The number of inequal- ity constraints varies as 10, 30, 50, 70, 90. Content and interpretation as in Table A.I
For all remaining parameters, we performed hyperparameter tuning via a coordinate search over relevant parameters. Central values for this coordinate search were determined via small amount of informal experimentation to ensure training was stable on that central set of parameters. Final parameters were chosen so to prioritize feasibility (as determined via the mean and max violations of equality and inequality constraints), followed by objective value and speed.
B. CONVEX QUADRATIC PROGRAMS
We list the ranges over which different hyperparameters were tuned for each method, with central values for the coordinate search in italcss, and the final parameter values in bold. In order to min- imize the amount of tuning, we employ the hyperparameters obtained for DC3 to "DC3, I train" and "DC3, no soft loss" as well (rather than tuning the latter two methods separately). For this set of experiments, we set the learning rate the gradient-based correction procedure Pa to 10 -0 for all methods, most methods went unstable for higher correction learning rates.
DC3 DC3, & train DC3, no soft loss
DC3, *
NN
Eq. NN
Lr
10
10-00-
10-4
10 10-2, 10--0 10
10-2, 10-3 10-4
10 10 10
2g
An
1,10,100
1,10,100
1,10,100
An
0.5, 0.1, 0.01
0.5, 0.9, 0.99
0.5, 0.9, 0.99
An
lest
5. 10, 50, 100, 7000
5. 10, 50, 100, 1000
5, 10, 50, 100, 1000
5, 10, 50, 100, 1000
Larin
1,2, 5, 10, 100
1,2, 5, 10, 100
13

---

Published as a conference paper at ICLR 2021
B.2 SIMPLE NON-CONVEX OPTIMIZATION
All hyperparameters in these experiments were maintained at the settings chosen for the convex QP task, since these tasks similar by design.
B.3 AC OPTIMAL POWER FLOW
We list the ranges over which different hyperparameters were tuned for each method, with central values for the coordinate search in italics, and the final parameter values in bold. As in the previous setting, in order to minimize the amount of tuning, we employ the hyperparameters obtained for DC3 "DC3, train" and "DC3, soft loss" well (rather than tuning the latter two methods separately).
DC3 DC3, & train DC3, no soft loss
DC3, +
NN
Eq. NN
Lr
10 10-2
10 10
10
10 10-3,11 10-10
10 10 10
10 10 10
Ag
1,10,100
1,10.100
1,10.100
Aa
0.5, 0.1, 0.01
0.5, 0.9, 0.99
0.5, 0.9, 0.99
An-An
test
5, 10, 50, 100
5, 10, 50, 100
5, 50, 100
5, 10, 50, 100, 200
fanin
1, 10, 100
1,2, 5, 10, 100
Lr, Pr
10-3, 10-4,10-9
10-1, 10 10-6
10 10-5, 10 10-6 10-7
10 10-5, 10-0 10
C DETAILS OF DC3 FOR ACOPF
C.I PROBLEM SETTING
We consider the problem of ACOPF defined in 14.3
Let denote the overall set buses (i.c., nodes in the power network). any instance of ACOPF there exists set D B of load (demand) buses which Py and 4g identically zero, well as a set R C B of reference (slack) buses at which Pg and (g are potentially nonzero, and where the voltage angle Lo is known. Let B (DUR) be the remaining generator buses which Pa and 4g are potentially nonzero, but where the voltage angle Lu is not known.
Then, we may rewrite Equation (7) as follows, where u = |ole and W = W. + Wii:
minimize Iv
P3 Ap
6zt Pg
(C.1a)
subject to
Pg min
Pg < Pg
max
(C.1b)
dg min
9g S 9g
(C.1c)
min
< |o| S u max
(C.1d)
(Lv)R Óstack
(C.1e)
(Dy)D = (gg)D =
(C.1f)
Pg Pa diag(e;) (W,,, W,e,)
+ W,v) 0
(C.1g)
9g qu + diag(u,) (W,r, + W,,,) - diag(u; (W,,, - W,e)) = 0 where v, |o| cos cos(Lv) and U; |o| sin
(C.1h)
(While we write the problem in this form to minimize notation, practice, some of the constraints in the above problem c.g.. (C.Ib). CC.lc). and (C.II) can be condensed.)
C.2 OVERALL APPROACH
As pointed out in Zamzam Baker 2019). given Pa, qd, (Pg)g and By, the remaining variables (py) RR. (gg B. [1] pl and (Zu)ByR B.R be recovered via the power flow equations (C.1g C.
14

---

Published as a conference paper at ICLR 2021
As such, implementation of DC3 may be outlined as follows.
Input:
[P] of] (The constant Lox is fixed across problem instances.)
Neural network: Output E [0, 1]191 and 8 [0, 1] 1|-P (applying sigmoid to the final layer of the network), and compute:
(pg)g = a(pg "g + ap g
| mim (1
B)
(In other words, output a partial set of variables, and enforce box constraints on this set of variables via sigmoids in the neural network.)
Completion procedure: Given = (wn) 1 B solve Equations (C. ChIhp
for the remaining quantities (pg)R, (gg BB |o|p, and (Lv) as described below. Out- put decision variables y = [(Pa) (4n) |0|² (Lu)²)²
Correction procedure: Correct y using the gradient-based feasibility correction procedure described in [3.2]
Backpropagate:
Compute the loss and backpropagate as described below to update neural network parameters. Repeat until convergence.
We now describe the forward and backward passes through the completion procedure, where we have introduced several "tricks" that significantly reduce the computational cost, including some that are specific to the ACOPF setting.
For ease of notation throughout, we will let E R denote the Jacobian of the equality con- straints (C.Ie))(C (C.II) with respect the complete vector y of decision variables. This matrix, which we pre-compute, will be useful throughout our computations.
C.3 SOLVING THE COMPLETION
The neural network outputs (Pylg and |,) are the inputs to the completion procedure. The- oretically, could use Newton's 's method to solve for all additional variables from the equality constraints. However, in practice we find that solving for all variables using Newton's method is sometimes unstable. Fortunately, we can divide the completion procedure into substeps, where Step 1 invokes Newton's ' method to identify some of the variables, while Step 2 solves in closed form for the others. This greatly improves the stability of the completion procedure.
Step 1. Compute |elp, (Lv)B via Newton's 's method using real power flow constraints C. at buses B RR and reactive power constraints (C.Th) at buses 'D (note that the number of equations matches the number of variables being identified). We initialize Newton's 's method by fixing variables determined by the neural network and those already determined in Step I of the completion process, and initializing [u|p. (Zv) BY at generie initial values (these are provided in the ACOPF task setup and are typically used to initialize state-of-thy art solvers). Note that the remaining variables, those determined Step of the completion process, do not actually appear in the relevant equality constraints and therefore do not need to be set.
Let JSeep1 denote the submatrix of J corresponding the equality constraints (C. and (C.Ih)p and the voltage variables julp and (Lu)BtR that we are solving this step. At the tth step of Newton's method, let Supp (t) E R | denote the vector of values on the left-hand side of the relevant equality constraints (which wish to equal identically zero), evaluated the current setting of all problem variables. Our Newton's method updates are then
|0/p
|u|p
--1 Step
1 Step (t).
(C.2)
(L))
(L))BRR
1+1
15

---

Published as a conference paper at ICLR 2021
Step 2. Compute the remaining variables (py)re and (4g (9))B)D via the remaining equality straints - that is, the real power flow equations (C.Ig) at buses R and the reactive power flow questions (C.lh) at buses in B D.
Steps 1 and 2 together allow complete all the decision variables.
C.4 BACKPROPAGATING THROUGH THE COMPLETION
Let z denote the input to the completion procedure and let 21 and 22 denote the variables respectively derived during Steps and of completion. That is:
(pg)e 1 B
10 lD (LU)
(Pg)R (9))
=
21
22
Then, we wish to backpropagate gradients of an arbitrary loss function E( 2, 21, 22). both order to train neural network and to perform gradient-based correction procedure. That is, must compute the total derivative dé/de given the partial derivatives of of/0z, 0e/Oz,, and 02/022.
Applying the chain rule through the steps of the completion procedure, we have:
df
0e
0e
0z1
0o2 Ol 022 021 de
+
(C.3)
dz
Oz
Oz
Oz
2z2
Ōz
Oz2 0z1 Oz
We now consider each of these terms in this equality, except for 0t/02, 0t/021, 0l/02o which we may assume have already been computed.
Step 2. Let J Step denote the submatrix of J corresponding to the partial derivatives of the equality constraints used in Step with respect to the voltage variables |u|?" (Zu)². Then, we have:
(Pa)t
(gn)
BVD
-J Step 2-
(C.4)
[Ju]
(Zv)z?²
As
Algyleye Ulp,1o
0, this gives us both the terms 021, Ozz/0: 0z in
Step 1.
Consider the total differential through the equality constraints C. and ChII where all terms besides W, and W; are viewed as parameters through which to differentiate. We rearrange this total differential put differentials of input quantities Step 1 side and differentials of outputs from Step on the other side:
d(lu)
d(pg) ) + d(pa)ByR
[d
Sssp
J Stop lb
(C.5)
d( d(Lv)
d(gg)
d(<L)R
where J Step is as in the forward pass of Step 1, and J S 1b denotes the submatrix of J correspond- ing the equality constraints B.. and (C.Ihop and the voltage variables ([v)) (Zu)R.
dlu|p d(Zv)
While we could compute
explicitly, we can improve efficiency by not computing and
storing a large intermediate Jacobian explicitly. Instead, we can directly compute what we need, which is the product of this Jacobian with matrices of smaller dimensions. Define
OE
O6 022
K
J Step
Oz
Ozg 0zg
Note furthermore that J-1 already computed in the forward pass, meaning that do not need perform additional matrix inver- sion.
using computation above to evaluate 0zg/ 0zz
Now, use CC.5 to derive:
16

---

Published as a conference paper at ICLR 2021
de
de d22
(1
(1-d2olove + d(pa)BiRR) d(ua)o
[(([[))B d(<u)R
)
d21 K
J step
0z1
Oz2 0z1
which gives us
0e 0æ1
de 022 021
dzi Oz
222 dz1 dz
Putting it all together. Combining our logic described above for Steps 2 and 1, we can recover all terms in C.3) and therefore identify dl/d2.
17


Reviews:
[{"review_id": "yUJk-C_Pjt", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Strength:\n+ The paper proposes a general framework to deal with constraints in optimization problems using neural networks. In my opinion this is an important problem since there exists no standard method in many existing deep neural network frameworks to deal with constraints, which are also inapplicable even if the constraints are only slightly nontrivial. The paper proposes to deal with equality and inequality constraints differently which may be often easier in large scale settings.\n+ Comparison with CVXPY indicates that the algorithm can indeed be practically useful, and applicable for a broad spectrum of problems (this is not discussed in the paper).\n\nWeakness:\n- While the related work from the recent years has been discussed to some extent, the paper fails to show how the technique proposed is better than them. The main idea of the paper has a rich history in optimization literature and is referred to as \"elimination\" of constraints. See Chapter 15 in Numerical Optimization by Nocedal & Wright (2006), and references within for more details. From my understanding, the discussion in Amos & Kolter (and their implementation) makes it clear that a reduced/partial Cholesky factorization is sufficient. This is equivalent to the completion procedure suggested here. Moreover, the correction procedure simply reduces a penalized form of constraints, and is not a projection operation. To this end, the paper does not have any discussion regarding the convergence aspects of the framework which is a crucial subject for this paper.\n- For a generic optimization framework (proposed), the paper only provides experiments on well studied optimization problems - all the experiments provided in the paper are with quadratic programming problems which are known to be easy both in theory and practice. It will be interesting to see how the framework performs in different problems. Also, it is not clear whether the experimental benefits will carry to other networks that are used in practice. Indeed, running experiments on all known network architectures is feasible but showing experiments on a few more relevant architectures can add a lot of value to the paper and readers.\nAfter response: While some of my concerns were cleared after the response, the experimental evaluations presented do not sufficiently support the claim that the method can handle nonlinear constraints. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "SIU6t2PkHYA", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### quality\nGood\n\n### clarity\nGood\n\n### originality \nCarefully combines a number of non-trivial methods from recent related work. Clever new idea for how to guarantee constraint satisfaction of the output of the network.\n\n### significance\nConcrete contribution to the field of learnable 'optimizers.' The applications are well-motivated and it appears that deploying the method for the ACOPF could have immediate impact.\n\n### Pros \nWell executed + motivated. Careful ablation analysis.\n\n### Cons \nThe results may be more impactful and interesting in an operations research venue. The gap between the learned optimizer and the exact QP solver is non-trivial for some problems. This may be a deal-breaker for deployment.\n\n## Comments\n### Satisfying inequality constraints = \n\nIt was unclear to me why the gradient descent procedure is guaranteed to converge. Is this assuming that the constraint set is convex?\n\nI was confused as to why the equality and inequality constraints are treated so differently. Why have a black box solver with implicit function theorem differentiation for equality constraints vs. back-propping through unrolled gradient descent for the inequality constraints?\n\n\nFYI, in principle, the optimization in 3.2 doesn't need to be in z space. It could be in hidden space of the neural network that outputs z. In future work this might allow local search to move better when seeking to enforce the inequality constraints.\n\n### Benchmarking \n4.1: Does making Q diagonal change the difficulty of the optimization problem? Is this a realistic setting?\n\n\n### The 'Optimizer' Baseline=\nTable 2: The gap between the exact QP optimizer and DC3 is non-trivial, with a scale that is often bigger than the gap between DC3 and some of the other deep net baselines. The claim \"we find that DC3 achieves comparable objective\" may be over-stated. Perhaps you should do a paired analysis across optimization problems. When comparing method X to method Y, on how what fraction of problems does X outperform Y?\n\nCan the 'Optimizer' baseline be warm-started? If so, how fast would it be to warm start using DC3. This might help close the speed gap between 'Optimizer' and DC3 while achieving higher quality solutions.\n\n## Minor Comments\n\nI initially found (1) confusing because I thought that part of the learning problem was to learn the dependence of the optimization problem on x. This occurs, for example, in the field of structured prediction, where we have a labeled dataset of (x, y) pairs. You should update to emphasize that this is not the case.\n\nIn algorithm 1, line 10, aren't you doing gradient descent, not stochastic gradient descent? It should be GD.\n\nIn Table 3, DC3, \\leq train matches DC3. Why do you expect this is true?\n\n\nPage 5: I would have preferred to see the discussion of the very relevant related work in the main text and not relegated to an appendix.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "H2TMNeVeUW", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "There has been an increase of works using deep neural networks to heuristically predict solutions to constrained optimization problems. However, these methods cannot generalize to arbitrary constraints.  In this paper, the authors propose a method to build neural networks that output vectors that satisfy hard equality and inequality constraints. They do this by first having the network predict the underdetermined part of the system defined by the equalities, then doing a series of gradient steps to project the solution onto the space delineated by the inequalities. They evaluate on synthetic quadratic programs and problems derived from a AC power flow application.\n\nPrior to this work I could see two ways of doing what they propose. \n\nA) If the constraints are linear, then Frerix et al. (2020) propose to compute the Minkowski-Weyl decomposition of the polyhedron of constraints, and to have the neural net output the coefficients in the resulting basis. Computing the MW decomposition is very expensive (both in theory and in practice), but once it is computed, enforcing the constraints is automatic.\n\nB) Alternatively, if the constraints are (disciplined) convex, one could use a differentiable convex layer as last layer, e.g. using the method of Agrawal et al. (2019) with a somewhat arbitrary choice of objective function. For example, it could be a quadratic program layer (as in the preceding work of Amos and Kolter (2017), where a neural net with a final QP layer is used to output soft solutions to Sudokus, which the authors do cite). In fact when constraints are convex something very similar to this paper can be done with this approach, where a neural net would predict a solution, and a final QP layer would find the point that satisfies the constraints that is the closest in L2 distance with the initial neural net guess.\n\nThe current paper discusses briefly works related to method B in the \"Implicit layers\" paragraph of Section 2, without discussing how it can accomplish what they aim to do, nor compare against it. It is a direct competitor when constraints are convex. As for method A, it is neither cited nor compared against. Against, this is a direct competitor when constraints are linear.\n\nSo in what way does the current approach compare to these previous ones? The main advantage I see is that the method can be applied to nonconvex problems. Of course, this doesn't mean it will necessarily do well - the Newton's method step for the equality constraints or the first-order projection for the inequality constraints might not converge. There is no miracle and probably this method won't be workable on nonlinear constraints that are too wild. But at least, it seems it does converge for the nonconvex \"ACOPF\" problem of the experiments, so there seems to be some use-case. I think this advantage (the method can be applied to arbitrary nonlinear constraints) should be emphasized more, and a discussion of the probable limitations should be included as well. In particular, when more assumptions are put on the constraints (e.g. linearity), there are probably better options than first-order methods.\n\nRegarding the timings in the experiments: all the machine learning methods use a GPU, so it would be interesting to compare against a baseline solver that can use a GPU when possible as well. For example, for the QP, the qpth library of Amos and Kolter (2017) has the entire QP solver implemented on CUDA - this might make a difference in speed.\n\nOverall, my opinion is that the paper does nothing groundbreaking, but has the quality of being the first method (as far as I know) to propose enforcing hard equality-inequality constraints on the output of a neural net, which is an obstacle right now in extending recent work on learning heuristics for optimization problems. The literature review definitely has to be expanded however, to explain that when constraints are linear and convex respectively, the works of Frerix et al. (2020) [method A] and Agrawal et al. (2019) [method B] are competitors. Moreover, more discussion on the advantages and inconvenients of the approach is necessary (i.e. that the method is very general, but probably inefficient on more structured problems, and yet probably can't work on constraints that are too wild). But otherwise, the core concept of the paper sounds sound to me, and the experiments, although minimal, are I think correctly made (several seeds, etc.) I also appreciate that code was provided. So I tend towards weak acceptance of the paper.\n\nIn case this paper is rejected, my recommendation to the authors would be strengthen the experimental section. First, since comparisons on QPs are presented, I would have liked to see comparisons against these methods. I think comparisons on another nonconvex problem would be a must as well. Also comparisons in a \"predict-then-optimize\" setup (e.g. see Elmachtoub and Grigas 2017, Donti et al. 2017, Wilder et al. 2019, Vlastelica et al. 2019) would be very welcome, since this is a setup where neural networks have tremendous potential. This would make for a much stronger paper.\n\n\nReferences\n\n[1] Frerix, T., Nießner, M., & Cremers, D. (2020). Homogeneous linear inequality constraints for neural network activations. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (pp. 748-749).\n\n[2] Agrawal, A., Amos, B., Barratt, S., Boyd, S., Diamond, S., & Kolter, J. Z. (2019). Differentiable convex optimization layers. In Advances in neural information processing systems (pp. 9562-9574).\n\n[3] Amos, B., & Kolter, J. Z. (2017). Optnet: Differentiable optimization as a layer in neural networks. arXiv preprint arXiv:1703.00443.\n\n[4] Elmachtoub, A. N., & Grigas, P. (2017). Smart\" predict, then optimize\". arXiv preprint arXiv:1710.08005.\n\n[5] Donti, P., Amos, B., & Kolter, J. Z. (2017). Task-based end-to-end model learning in stochastic optimization. In Advances in Neural Information Processing Systems (pp. 5484-5494).\n\n[6] Wilder, B., Ewing, E., Dilkina, B., & Tambe, M. (2019). End to end learning and optimization on graphs. In Advances in Neural Information Processing Systems (pp. 4672-4683).\n\n[7] Vlastelica, M., Paulus, A., Musil, V., Martius, G., & Rolínek, M. (2019). Differentiation of blackbox combinatorial solvers. arXiv preprint arXiv:1912.02175.\n\n---\n\nEdit after rebuttal: I am satisfied with the changes to the paper and increase my score to an accept.", "extra_scores": {}, "extra_text": {}}, {"review_id": "7H_u-x7pCz0", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a method to strictly enforce hard constraints during a neural network, without compromising differentiability. The method has two stages 1) From a smaller set of predicted variables, compute the remaining ones so that equality constraints are satisfied; 2) Take a few gradient steps (w.r.t soft constraint) in case inequality constraints are violated. They perform experiments on synthetic and also somewhat applied instances of quadratic programs. The results look very promising.\n\nWhile most of this review will focus on the negative aspect, I want to begin by stating that I like the paper very much.\n\nI think it solves an important problem (from a fundamental standpoint but with potentially large impact), it solves it with a method that is non-trivial, yet quite simple (both of which are positives) and shows performance clearly better than that of naive -- but popular -- baselines. The writeup is very nice and the experiments are sufficient.\n\nHaving said all of that, I cannot recommend acceptance of the paper in its current stage. In several places, the paper claims to have orders-of-magnitude faster runtimes than standard solvers. It is even the only claim of the paper appearing in boldface. Since the time measurement methodology is not described in the paper, I went into the code attached to the submission. Below is a list of reasons why I believe the current methodology is flawed and does not permit making strong claims from the paper.\n\n- CVXPy was never developed to be a fast solver. I checked this with the CVXPy authors and often times the solver is not even the computational bottleneck.\n- Even if other bottlenecks are factored out of CVXPy, there is an option to use an almost-SOTA QP solver on the backend with prob.solve(solver=cp.OSQP), which the authors **do not use**. For these two reasons, it would probably be better to compare against the freely available OSQP directly, without incorporating CVXPy -- (I feel, CVXPy, in general, shouldn't be promoted as a baseline for runtimes)\n- I didn't go through all the code but the time measurements I found were around large blocks of code, not the pure runtime of the solvers. This leaves a lot of room for inaccuracies.\n- The baselines optimizers do not enjoy any parallelization over the instances. On the other hand, the authors write (in a footnote on page 11) that their method was timed with *full parallelization* (all instances in one batch). **This is massively unfair to the baseline** and **may fully explain the orders of magnitude difference in runtimes**.\n- Runtime of its own is a bit of a compromised quantity due to hardware (cpu/gpu) differences, maybe FLOPS would be fairer (but I understand it might not be feasible)\n\nThere are two ways forward:\n\na) The authors remove/strongly-tone-down all claims about runtimes. In this case, I am ready to dramatically improve my evaluation as I believe the paper is safely above the acceptance threshold even without them.\n\nb) The authors insist on claims about runtime. If this is the case, the authors need to address the points made above, update the results, and add a section that demonstrates the soundness of the methodology (possibly into supplementary). In such a case, I am happy to reevaluate but I will still insist on a proper justification of the claims made in boldface.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes an approach for solving constrained optimization problems using deep learning. The key idea is to separate equality and inequality constraints and "solve" for the equality constraints separately. Empirical results are given for convex QPs and for a non-convex problem that arises in AC optimal power flow.
There was much discussion of this paper between the reviewers and the area chair. THe key question was whether the empirical evaluation is sufficient to convince that the method is more effective than existing solvers. The current experiments do not show that the method achieves better solutions than existing solvers. For the convex case this is to be expected since solvers are optimal. But in the non-convex case, it would have been nice to see that the method indeed can find better solutions.
This leaves the advantage of the method in its speedup over existing methods. However, as the authors acknowledge, it is possible that this speedup is due to better use of parallelization than the methods they compare to. It is true that deep learning is particularly easy to parallelize, but this is not impossible for other methods (e.g., for linear algebra operations etc).
Thus, taken together the empirical support for the current method is somewhat limited. The method itself does make sense, and this was indeed appreciated by the reviewers. 


Decision: Accept (Poster)