Dual Lagrangian Learning for Conic Optimization
Authors: Mathieu Tanneau
Pascal Van Hentenryck
Venue: NeurIPS 2024 poster (2024)
Keywords: Conic optimization
optimization proxies
duality
self-supervised learning
Primary area: optimization
TL;DR: This paper presents a principled methodology for learning dual conic optimization proxies with dual feasibility guarantees.

Abstract: This paper presents Dual Lagrangian Learning (DLL), a principled learning methodology for dual conic optimization proxies.
DLL leverages conic duality and the representation power of ML models to provide high-duality, dual-feasible solutions, and therefore valid Lagrangian dual bounds, for linear and nonlinear conic optimization problems.
The paper introduces a systematic dual completion procedure, differentiable conic projection layers, and a self-supervised learning framework based on Lagrangian duality.
It also provides closed-form dual completion formulae for broad classes of conic problems, which eliminate the need for costly implicit layers.
The effectiveness of DLL is demonstrated on linear and nonlinear conic optimization problems.
The proposed methodology significantly outperforms a state-of-the-art learning-based method, and achieves 1000x speedups over commercial interior-point solvers with optimality gaps under 0.5\% on average.

Dual Lagrangian Learning for Conic Optimization
Mathieu Tanneau, Pascal Van Hentenryck
H. Milton Steward School of Industrial and Systems Engineering
NSF AI Institute for Advances in Optimization Georgia Institute of Technology
(mathieu. Fanneau,pascal. ot Bisye gatech. edu
Abstract
This paper presents Dual Lagrangian Learning (DLL), a principled learning method- ology for dual conic optimization proxies. DLL leverages conic duality and the representation power of ML models to provide high-duality, dual-feasible solutions, and therefore valid Lagrangian dual bounds, for linear and nonlinear conic opti- mization problems. The paper introduces systematic dual completion procedure, differentiable conic projection layers, and self-supervised learning framework based on Lagrangian duality. It also provides closed-form dual completion for- mulae for broad classes of conic problems, which eliminate the need for costly implicit layers. The effectiveness of DLL is demonstrated on linear and nonlinear conic optimization problems. The proposed methodology significantly outper- forms a tate-of-theeart learning-based method, and achieves 1000x speedups over commercial interior-point solvers with optimality gaps under 0.5% on average.
Introduction
From power systems and manufacturing to supply chain management, logistics and healthcare, optimization technology underlies most aspects of the economy and society. Over recent years, the substantial achievements of Machine Learning (MI. have spurred significant interest in combining the two methodologies. This integration has led to the development of new optimization algorithms (and the revival of old ones) taylored to ML problems, well as new ML techniques for improving the resolution of hard optimization problems [.. This paper focuses on the latter (ML for optimiza- tion), specifically, the development of so-called optimization proxies, i.c., ML models that provide approximate solutions to parametric optimization problems, see e.g., (2).
In that context, considerable progress has been made in learning primal solutions for broad range of problems, from linear to discrete and nonlinear, non-convex optimization problems. State-of-the-as methods can now predict high-quality. feasible
solutions for various applications 2] This paper complements these methods by learning dual solutions which, in turn, certify the (sub)optimality of learned primal solutions. Despite the fundamental role of duality in optimization, there is no dedicated framework for dual optimization proxies, which have seldom received any attention in the literature. The paper addresses this gap by proposing, for the first time, principled learning methodology that combines conic duality theory with Machine Learning. As a result, it becomes possible, for large class of optimization problems, design primal proxy to deliver high-quality primal solution and an associated dual proxy to obtain a quality certificate.
1.1 Contributions and outline
The core contribution of the paper is the Dual Lagrangian Learning (DLL) methodology for learning dual-feasible solutions for parametric conic optimization problems. DLL leverages conic duality to design a self-supervised Lagrangian loss for training dual conic optimization proxies. addition, the
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

paper proposes general dual conic completion using differential conic projections and implicit layers to guarantee dual feasibility, which yields stronger guarantees than existing methods for constrained optimization learning. Furthermore, it presents closed-form analytical solutions for conic projections, and for dual conic completion across broad classes of problems. This eliminates the need for implicit layers in practice. Finally, numerical results on linear and nonlinear conic problems demonstrate the effectiveness of DLL, which a outperforms state-of-the-ar learning baseline, and yields significant speedups over interior-point solvers.
The rest of the paper is organized as follows. Section presents the relevant literature. Section introduces notations and background material. Section 4 presents the DLL methodology. which comprises the Lagrangian loss, dual completion strategy, and conic projections. Section S reports numerical results. Section discusses possible the limitations of DLL and possible extensions, and Section concludes the paper.
2
Related works
Constrained Optimization Learning The vast majority of cxisting works on optimization proxies focuses on learning primal solutions and, especially, ensuring their feasibility. This includes, for
instance, physics-inffnee informeed training loss B 4 5) mimicking the steps of an optimization algorithm
6 7 8
using masking operations [9] 10]. or designing custom projections and feasibility layers
The reader is referred to [2 for an extensive survey of constrained optimization learning.
Only handful of methods offer feasibility guarantees, and only for convex constraints; this latter point is to expected since satisfying non-convex constraints is NP-hard in general. Implicit layers [3] have high computational cost, and are therefore impractical unless closed-form solutions are available. DC3 (5) uses equality completion and inequality correction, and is only guaranteed to converge for convex constraints and given enough correction steps. LOOP-LC [14] uses gauge mapping to ensure feasibility for bounded polyhedral domains. RAYEN 12] and the similar work in
[5] use line search-based projection mechanism handle convex constraints. All above methods assume knowledge a strictly feasible
employ equality completion, and the latter three [14 12 15 point, which is not always available.
Dual Optimization Learning To the authors' knowledge, dual predictions have received very little attention, with most works using them to warm-start an optimization algorithm. In [16), primal-dual prediction is used to warm-start an ADMM algorithm, while These works consider specific applications, and do not provide dual fcasibility guarantees. More recently, [6 g attempt to mimic the (dual) steps of augmented Lagrangian method, however with the goal of obtaining high-quality primal solutions.
In the mixed- integer programming (MIP) setting, [17] and [8 use a dual prediction as warm-start in column-generation
a column generation algorithm, for outting-stock and unit-commitment problems, respectively. In similar fashion, [19] consider a (combinatorial) Lagrangian relaxation of Traveling Salesperson Problem (TSP) Most recently, 20 consider learning Lagrangian multipliers for mixed-integer linear programs. Therein, a machine learning model predicts Lagrange multipliers, and a Lagrangian sub- problem is solved obtained Lagrangian dual bound. This approach only supports linear constraints for the Lagrangian, and it requires an external combinatorial solver to solve the subproblem, which may be NP-hard in general.
The first work to explicitly consider dual proxies in the context of conic optimization, and to offer dual feasibility guarantees, is (1], which learns a dual proxy for second-orde cone relaxation of the AC Optimal Power Flow. Klamkin et al. [22] later introduce a dual interior-point learning algorithm to speed-up the training of dual proxies for bounded linear programming problems. In contrast, this paper proposes general methodology for conic optimization problems, thus generalizing the approach (21, and provides more extensive theoretical results. The dual completion procedure used in 22 Lemma 1] is special case of the one proposed in this paper.

---

3 Background
This section introduces relevant notations and standard results on conic optimization and duality, which lay the basis for the proposed learning methodology. The reader is referred to 23 for thorough overview of conic optimization.
3.1 Notations
Unless specified otherwise, the Euclidean norm of a vector x E R is denoted by ||]||| = vx x. The positive and negative part of E R are denoted by x max(0, x)) and max(0, -x). The identity matrix of order is denoted by In, and e denotes the vector of all ones. The smallest eigenvalue of real symmetric matrix X is Amin (X)..
Given a set X' C R", the interior and closure of are denoted by int X' and by X, respectively. The Euclidean projection onto convex set C is denoted by IIc, where
He i = arg min SEC
| æ||².
(1)
The set K R is cone if x X 0 Ar K. The dual cone of K. is
K = fy E
0, Vx EC),
(2)
whose negative K. = KC* is the polar cone K. A cone I. is self-dual if K= and it pointed if IC (-XC) {0}. All cones considered in the paper proper cones, i.e., closed, convex, pointed cones with non-empty interior. A proper cone defines conic inequalities Ex and >x as
V(x, v) E R XR" KK y e - a-yEK,
(3a)
v(z, v) E R AKY
E int K.
(3b)
3.2 Conic optimization
Consider (convex) conic optimization problem of the form
min SF
{c
Ar >x 6}
where A E mR bexxxbbbe DE Rmm ce "
and K. is a proper cone. All convex optimization problems can be formulated in conic form. A desirable property of conic formulations is that is enables the use of principled conic duality theory [23]. Namely, the conic dual problem reads
max
{ y-yyeyy
(5)
The dual problem (5) is a conic problem, and the dual of (5) is (4. Weak conic duality always holds, i.e., any dual-feasible solution provides a valid lower bound on the optimal value of (4), and vice-versa. When strong conic duality holds, e.g., under Slater's condition, both primal/dual problems have the same optimal value and a primal-dual optimal solution exists [23]
Conic optimization encompasses broad classes of problems such linear and semi-definite program- ming. Most real-life convex optimization problems can be represented in conic form using only a small number of cones (24) which are supported by off-the-shelf solvers such Mosek, ECOS, SCS. These so-called "standard" cones comprise the non-negative orthant R,,, the second-order cone Q and rotated second-order cone 2,, the positive semi-definite cone S4, the power cone P and the exponential cone E; see Appendix B for algebraic definitions.
4 Dual Lagrangian Learning (DLL)
This section presents the Dual Lagrangian Learning (DLL) methodology. illustrated in Figure I for learning dual solutions for conic optimization problems. DLL combines the representation power of artificial neural networks (or, more generally, any differentiable program), with conic duality theory, thus providing valid Lagrangian dual bounds for general conic optimization problems. To the best of the authors' knowledge, this paper is the first to propose a principled self-supervvsed framework with dual guarantees for general conic optimization problems.

---

Artificial Neural Network
Conic Projection
Dual Completion
E nng max, T
A
al M2-- A
B
ZEC
h
Lagrangian Dual Bound
C(s) b
Gradient step
V.C(9)
Figure 1: Illustration of the proposed DLL scheme. Given imput data (A, b, H, h, c). a neural network first predicts y R". Next, conic projection layer computes vonic-feasible ÿ E K"', which is then completed into a full dual-fcasible solution (g. 8). The model is trained in a selff-uperrvsed fashion, by updating the weights 0 to maximize the Lagrangian dual bound L(ÿ)-
DLL exploits three fundamental building blocks: (1) dual conic completion procedure that provides dual-feasible solutions and, hence, valid Lagrangian dual bounds; (2) fast and differentiable conic projection layers; and (3) self-supervised learning algorithm that emulates the steps of a dual Lagrangian ascent algorithm.
4.1 Dual Conic Completion
Consider a conic optimization problem in primal-dual form
min cTx
(6a)
max U.5
bT y + hT
(7a)
s.t. Ax xx b. Hr Cc h,
(6b)
s.L.
A y H c,
(7b)
(6c)
E
(7c)
where y K and E C* the dual variables associated constraints (6b) and (6c), respectively. The proposed dual conic completion, outlined in Theorems [ and below, takes as input j K and recovers & E C* such that (ú, 2) is feasible for (7). The initial assumption that ğ E K can be enforced through a projection step, which will be described in Section 4.2
Theorem (Dual conic completion). Assume that Vÿ E K 3x : HE c h and the problem
min (cTx + (b- Ar) T Hx Ze h]
(8)
is bounded. Then, Vù E "8EC" A H 2= iee. (0.2) is feasible for 7
Theorem 2 (Optimal dual completion). Let K", and let be dual- optimall for g
Then, L(u, 2) 6 ÿ + h 2 is valid dual bound on the optimal value of (6) and L(ū 2) is the strongest dual bound that can be obtained after fixing y = 9 in 7
It is important to note the theoretical differences between the proposed dual completion, and applying a generic method, e.g.. DC3 [ LOOP-LC [44 or RAYEN [2]. to the dual problem (7). First,
LOOP-LC is not applicable here, because it only handles linear constraints and requires a compact feasible set, which not the case in general for 7 Second, unlike RAYEN, Theorem I does not require an explicit characterization of the affine hull of the (dual) feasible set, nor does it assume knowledge strictly feasible point. fact, Theorem T appllee even if the feasible set of 7 has an empty interior. Third, the proposed dual completion enforces both linear equality constraints (7b) and conic constraints (7c). In contrast, the equality completion schemes used in DC3 and RAYEN enforce equality constraints but need an additional mechanism to handle incquality constraints. Fourth, the optimal completion outlined in Theorem 2 provides guarantees on the strength of the Lagrangian dual bound C(j, 2). This is major difference with DC3 and RAYEN, whose correction mechanism does not provide any guarantee of solution quality. Overall, the fundamental difference between generic methods and the proposed optimal dual completion, is that the former only exploit dual feasibility constraints (7b) 77c) whereas DLL also exploits (dual) optimality conditions, thus providing additional guarantees.
Another desirable property of the proposed dual completion procedure, is that does not require the user to formulate the dual problem (7) explicitly, would be the case for DC3 or RAYEN, Instead,

---

the user only needs to identify set of primal constraints that satisfy the conditions of Theorem I For instance, it suffices identify constraints that bound the set of primalefeasible solutions. This is advantageous because practitioners typically work with primal problems rather than their dual. The optimal dual completion can then be implemented via an implicit optimization layer. Thereby, in forward pass, is computed by solving the primal-dual pair (8) (27 and, in backward pass, gradient information is obtained via the implicit function theorem
The main limitations of implicit layers are their numerical instability and their computational cost, both in the forward and backward passes. To eliminate these issues, closed-form analytical solutions are presented next for broad classes of conic optimization problems; other examples are presented in the numerical experiments of S5ction[5]
Example (Bounded variables). Consider a conic optimization problem with bounded vuriables
min
|z bx
(9)
where < u are finite lower and upper bounds on all variables æ. The dual problem is
yb u=²" A + 2" = c.ye 2' 2 2" 203 min M.a",a" 2M
(10)
and the optimal dual completion is 2º = A 01+
= 1= A AT
The assumption in Example T that all variables have finite bounds holds in most -ff not all- real-life settings, where decision variables are physical quantities (e.g. budgets or production levels) that are naturally bounded. The resulting completion procedure is generalization of that used in 22 for linear programming (L.) problems.
Example 2 (Trust region). Consider the trust region problem [26]
min
{c x Ar >x ||||||| rr
(11)
where r20, ||:Il is a norm, and | (r, [C EC {(t, |2||=11 The dual problem is
{ y A c, K (zo, 2) e c**
(12)
B-50.2
where ||-11+ the dual norm and C ((t, +2) (27]. The optimal dual completion is 2 ==c A j. 2g ||
Example 3 (Convex quadratic objective). Consider the convex quadratic conic problem
min (1/2 x x Qx + c. x Ax >x b}.
(13)
where Q FT
F is positive definite. The problem can be formulated the conic problem
min {a+ oq Ax xx b. (1, Fx) E 02tmm
(14)
whose dual is
max 8.
TT 20
A + FT 2 (1, 2) E @2+m].
(15)
The optimal dual completion is = F-T(T-- A ú). 20 1/2|
4.2
Conic Projections
The second building block of DLL are differentiable conic projection layers. Note that DLL only requires valid projection onto IC,, which need not be the Euclidean projection IIg. Indeed, the latter may be computationally expensive and cumbersome to differentiate. For completeness, the paper presents Fuclidean and non-Fuclidean projection operators, where the latter are simple to implement, computationally fast, and differentiable almost everywhere. Closed-form formulae are presented for each standard cone in Appendix B and an overview is presented in Table I
5

---

Table 1: Overview of conic projections for standard cones
Cone
Definition
Euclidean projection
Radial projection
R
Appendix
B.
350
35
Appendix
8
S
Appendix
B.3
(41b
42
Appendix
no closed form
(45)
and
P Appendix
B
no closed form
50
4.2.1 Euclidean projection
Let K. be proper cone, and E E R". By Moreau's decomposition (28).
(x) + 1Ix (T),
(16)
which is reformulation of the KKT conditions of the projection problem ( i...
I - p 4. PEK, GEK,, p=q=0.
(17)
It then follows that 1x- (z) -Ilx- (-I), by invariance of Moreau's decomposition under orthogo- transformations. Thus, it sufficient to know how to project onto to able to project onto K and KC Furthermore, (T6) shows that II is identically zero the polar cone 1C In a machine learning context, this may cause gradient vanishing issues and slow down training.
4.2.2 Radial projection
Given an interior ray p x O, the radial projection operator IT is defined
I (T)
Ap
where A min () E + Ap K.). X20
(18)
The name stems from the fact that II traces ray p from until KC is reached. Unlike the Euclidean projection, it requires interior ray. which however only needs to be determined once per cone. The radial projection can then be computed, in general, via a line search on À or via an implicit layer. Closed-fome formulae for standard cones and their duals are presented in Appendix
4.3 Self-Supervised Dual Lagrangian Training
The third building block of DLL is a self-supervised learning framework for training dual conic optimization proxies. In all that follows, let { = (A, b. H, h, c) denote the data of an instance (6) and assume distribution of instances
E. Next, let Ma be a differentiable program parametrized by 6, e.g., an artificial neural network, which takes as input & and outputs dual-feasible solution (ú, E). Recall that dual feasibility of (ú, 2) can be enforced by combining the dual conic projection presented in Section 4.2 and the optimal dual completion outlined in Theorem 2
The proposed self-supervised dual lagrangian training is formulated
max E (C. {)
(19a)
s.t. (0.)) = Me(E).
(19b)
where L(j, E(), =T 2 is the Lagrangian dual bound obtained from (j.2) by weak duality. Thereby, the training problem (19) seeks the value of & that maximizes the expected Lagrangian dual bound over the distribution of instances effectively mimicking the steps of (sub)gradient algorithm. Note that, instead of updating (ý, 2) directly, the training procedure computes a (sub)gradient Og 2, to update 0, and then obtains new prediction (ý, E) through Mo. Also note that formulation (19) does not required labeled data, i.e., it does not require pre-computed dual-optimal solutions. Furthermore, applics to any architecture that guarantees dual feasibility of (j, 2). i.c., does not assume any specific projection completion procedure.
5 Numerical experiments
This section presents numerical experiments on linear and nonlinear optimization problems; detailed problem formulations, model architectures, and other experiment settings, reported in Appendix

---

Table 2: Comparison of optimality gaps on linear programming instances.
DC3
DLL
m
71
Opt val*
avg.
std
max
avg.
std
max
100
14811.9
19.58
1.86
41.42
0.36
0.20
1.36
200
29660.4
20.58
49.47
0.18
0.10
0.84
500
74267.0
33.70
1.29
41.54
0.07
0.04
0.30
10
100
14675.8
41.85
2.51
69.58
0.68
0.25
2.15
200
29450.7
36.88
2.28
100.90
0.34
0.13
0.96
500
73777.5
100.04
3.38
104.00
0.14
0.06
0.46
30
100
14441.5
159.49
5.54
166.31
1.93
0.37
3.31
200
29156.1
255.24
8.42
259.25
0.96
0.20
1.83
500
73314.3
274.78
7.91
277.40
0.38
0.09
0.75
All gaps are in best values are bold. "Mean optimal value on test set; obtained with Gurobi.
The code used for experiments is available under an open-source license The proposed DLL methodology is evaluated against applying DC3 to the dual problem (7) as baseline. Thereby, linear equality constraints (7b) and conic inequality constraints (7c) are handled by DC3's equality completion and inequality correction mechanisms, respectively. The two approaches (DLL and DC3) are evaluated in terms of dual optimality gap and training/inference time. The dual optimality gap defined (L* ()) C*, where L is the optimal value obtained from a state-of-the-art interior-point solver.
5.1
Linear Programming Problems
5.1.1
Problem formulation and dual completion
The first set of experiments considers continuous relaxations of multi-dimensional knapsack problems 30,, which are of the form
29
min
{-p Wa S b, [0, 1]"}
(20)
where p RT. W E RRT and b E TR The dual problem reads
max D.s 2n
(b y e Tzz W y -. 0,
0, 0.}
(21)
where E I.mh and 2', " E R², Since variables x is bounded, the closed-form completion presented in Example applies. Namely, 2l l 0 and -1-p- W where ø R
5.1.2 Numerical results
Table 2 reports, for each combination of m, n: the average optimal value obtained by Gurobi (Opt val), well as the average (avg), standard-deviation (std) and maximum (max) optimality gaps achieved by DC3 and DLL on the test set. First, DLL significantly outperforms DC3, with average gaps ranging from 0.07% 1.93%, compared with -9.8%%-274.78% for DC3, an improvement of about two orders of magnitude. A similar behavior is observed for maximum optimality gaps. The rest of the analysis thus focuses on DLL. Second, an interesting trend can identified: optimality gaps tend to increase with and decrease with n. This effect may be explained by the fact that increasing m increases the output dimension of the FCNN; larger output dimensions are typically harder to predict. In addition, a larger n likely provides a smoothing effect on the dual, whose solution becomes easier to predict. The reader referred to for probabilistic results on properties of multi-knapsack problems.
Next, Table 3 reports computing time statistics for Gurobi, DC3 and DLL. Namely, the table reports, for each combination of m, the time it takes to execute each method on all instances in the test set. First, DLL 3-10x faster than DC3, which caused by DC3's larger output dimension (m-+n, compared to m for DLL), and its correction steps. Furthermore, unsurprisingly, both DC3 and DLL.

---

Table 3: Computing time statistics for linear programming instances
Gurobit
DC3#
DLL
5
100
2.8 CPU.s
2.1 GPU.ms
0.3 GPU.ms
200
4.1 CPU.s
4.0 GPU.ms
0.7 GPU.ms
500
6.6 CPU.s
13.2 GPU.ms
3,0 GPU.ms
10
100
3.7 CPU.s
2.3 GPU.ms
0,4 GPU.ms
200
6.1 CPU.s
4,9 GPU.ms
1.1 GPU.ms
500
CPU.s
17.2 GPU.ms
4.7 GPU.ms
30
100
14.0 CPU.s
4.6 GPU.ms
0.9 GPU.ms
200
21.3 CPU.s
10.4 GPU.ms
2.5 GPU.ms
500
40.0 CPU.s
39.5 GPU.ms
13.6 GPU.ms
Time solve instances in the test set, using one CPU core. *Time run inference on instances in the test set, using one V100 GPU.
yield substantial speedups compared to Gurobi, of about 3 orders of magnitude. Note however that Gurobi's 's timings could be improved given additional CPU cores, although both ML-based methods remain significantly faster using single GPU.
5.2
Nonlinear Production and Inventory Planning Problems
5.2.1
Problem formulation and dual completion
The second set of experiments considers the nonlinear resource-constrained production and inventory planning problem [31 32). In primal-dual form, the problem reads
min m:6
d_ x f
(22a)
max U:
by V2el
(23a)
5b
(22b)
s.t.
ry + π = d, 7 = f,
(23b)
(I,,t,, /2) 2¹, j=1, (22c)
(23c)
y S 0,
(23d)
(T,, Ti, o;) E O j=1,..,,
(23c)
where f R" are positive vectors, and b 0. Primal variables
t E F" and the dual variables associated to constraints (22b) and (22c) are y E IR. and n, o, T E R", respectively.
Note that (2cc) implies t 2 0. Next, let y S 0 be fixed, and consider the problem
min z,t
(rd f by 22c
(24)
Problem 24 is immediately strictly feasible, and bounded since (d yr). f f> and x, 22 0. Hence, Theorems and apply, and there exists dual-optimal completion to recover ı, 0, T. A closed-form completion is then achieved as follows. First, constraints (23b) and (23c) yield π = d- and T = f. Next, note that only appears in constraint (23e) and has negative objective coefficient. Further noting that (2ee can written as o3 < TT it follows that oj = -2 /2TTTT at the optimum.
5.2.2 Numerical Results
Table 4 reports optimality gap statistics for DC3 and DL.., Similar to the linear programming setting, DLL substantially outperforms DC3, with average optimality gaps ranging from 0.23% 1.03%. compared with 70.76%-87.01 % for DC3. In addition, DLL exhibits smaller standard deviation and maximum optimality gaps than DC3. These results can be explained by several factors. First, the neural network architecture used in DC3 has output size n, compared to for DLL; this is because DLL leverages a more efficient dual completion procedure. Second, closer examination of DC3's output reveals that it often fails to satisfy the (conic) inequality constraints (23d) and (23e). More generally, DC3 was found to have much slower convergence than DLL during training. While performance of DC3 may benefit from more exhaustive hypertuning, doing comes at significant computational and environmental cost. This further highlights the benefits of DLL,, which requires minimal tuning and is efficient to train.

---

Table 4: Comparison of optimality gaps on production planning instances.
DC3
DLL
Y2
Opt vall
avg.
std
max
avg.
max
10
3441.8
70.76
9.42
90.23
0.23
0.57
17.05
6988.2
78.52
6.67
92.31
0.41
0.69
9.04
50
17667.4
81.70
5.41
92.69
1.03
1.69
21.68
100
35400.2
83.25
4.78
93.31
0.37
0.57
6.69
200
70889.5
84.06
4.20
93.44
0.29
0.46
4.81
500
177060.0
86.74
3.80
93.74
0.46
0.73
9.92
1000
354037.5
87.01
3.71
93.80
0.36
0.48
4.44
All gaps are in %; best values are in bold. "Mean optimal value on test set; obtained with Mosek, Table Computing time statisties for nonlinear instances
Mosek
DC31
DLL
10
73.5 CPU.s
2.7 GPU.ms
0.2 GPU.ms
20
75.3 CPU.s
2.7 GPU.ms
0.2 GPU.ms
50
15.4 CPU.s
2.7 GPU.ms
0.2 GPU.ms
100
24.9 CPU.s
2.7 GPU.ms
0.4 GPU.ms
200
49.9 CPU.s
5.1 GPU.ms
1.0 GPU.ms
500
98.8 CPU.s
GPU.ms
5.1 GPU.ms
1000
203.0 CPU.s
41.5 GPU.ms
19.0 GPU.ms
Time solve all instances in the test set, using one CPU core. 'Time run inference on all instances in the test set, using one V100 GPU.
Finally, Table 5 reports computing time statistics for Mosek, a state-of-the-ard conic interior-poin prrino solver, DC3 and DLL. Abnormally high times are observed for Mosek and n=10, 20. These are most likely caused by congestion on the computing nodes used in the experiments, and are discarded in the analysis. Again, DC3 and DLL outperform Mosek by about three orders of magnitude. Furthermore, DLL is about 10x faster than DC3 for smaller instances (n51000, and about 2x faster for the largest instances 1000...). This caused by DC3's larger output dimension and correction steps.
Discussion
6.1
Mixed-Integer Nonlinear Programming Setting
The proposed Dual Lagrangian Learning framework directly extends to the mixed-integer nonlinear programming (MINLP) setting. Consider general MINLP problem of the form
min FEX
{f(x)
h(x)) = O, g(x) 2 0},
(25)
where X' C "R" denotes possibly discrete domain. Given Lagrange multipliers X E Th and μ R. associated to equality and inequality constraints, the corresponding Lagrangian dual bound is
(4).4) = min zEX
f(x) - (T)())) - g()).
(26)
Note that 26 is the MINLP counterpart of in the conic setting.
The dual Lagrangian function ((), (u) is concave, non-smooth, and admits sub-differentials of the form C, (.), O, = -[ where 7 is an optimal solution of (26). The self-supervised learning framework of Section 4.3 can then be applied out of the box, wherein an ML model predicting (X, ()) is trained in a self-supervised fashion by maximizing the dual bound C(X, 11). This approach is followed in, c.g., [20] for mixed-integer linear problems, and [6] for nonlinear problems.
Despite natural similarities between the (convex) conic and MINLP settings, several intrinsic limi- tations appear in the latter. First, although the domain of (), ER" m R. is simple, and can be enforced via, e.g., ReLU activations, evaluating C(X, (1) is not. Indeed, this requires solving the MINLP problem (26) to optimality, which NP-hard in general. contrast, the proposed dual conic completion can be performed efficiently, and closed-fort solutions are available for broad classes of problems. Second, (sub)gradient information AL obtained from an optimal solution of (26), which poses obvious limitations if 26) is solved approximately. Third, arbitrary values of X, ş may result in

---

(26 being unbounded, yielding a dual bound of -oo and no usable gradient information. In contrast, the conic setting. [eeoremm[prooide sufficient conditions under which dual completion is always possible. Finally, an intrinsic limitation in the MINLP setting is the absence, in general, of strong duality. Therefore, even predicting a dual-optimal (A, (u) may insufficient to prove optimality, thus requiring additional computation such as branching. In contrast, the strong conic duality theorem [23] offers robust foundation to obtain high-quality dual bounds efficiently.
6.2
Limitations
The main theoretical limitation of the paper is that it considers convex conic optimization problems, and therefore does not consider discrete decisions nor general non-convex constraints. Since convex relaxations are typically used to solve non-convex problems to global optimality, the proposed approach nonetheless still useful in non-convex settings. Furthermore, as pointed out Section 6.1 the DLL framework extends naturally to the MINLP setting, by leveraging Lagrangian duality for discrete and/or nonlinear problems. However, this approach suffers from several theoretical and computational limitations.
On the practical side, the optimal dual completion presented in Section requires, in general, the use of an implicit layer, which is typically not tractable for large-scale problems. In the absence of a known closed-fore optimal dual completion, may still be possible to design efficient completion strategies that at least ensure dual feasibility. One such strategy is to introduce artificial large bounds on all primal variables, and use the completion outlined Example [ Finally, all neural network architectures considered in the experiments are fully-connected neural networks. Thus, a separate model is trained for each input dimension. Nevertheless, the DLL methodology applicable to graph neural network architectures, which would support arbitrary problem size. The use of GNN models the DLL context is promising avenue for future research.
Conclusion
The paper has proposed Dual Lagrangian Learning (DLL), principled methodology for learning dual conic optimization proxies. Thereby, a systematic dual conic completion, differentiable conic projection layers, and self-supervised dual Lagrangian training framework have been proposed. The effectiveness of DLL has been demonstrated on numerical experiments that consider linear and nonlinear conie problems, where DLL significantly outperforms DC3 (5), and achieves 1000x speedups over commercial interior-point solvers.
One of the main advantages of DLL is its simplicity. The proposed dual completion can be stated only in terms of primal constraints, thus relieving users from the need to explicitly write the dual problem. DLL introduces very few good performance. This results in simpler models and improved performance, thus delivering computational and environmental benefits.
and requires minimal tuning to achieve
DLL opens the door to multiple avenues for future research, at the intersection of MI. and optimization. The availability of high-quality dual-feasible solutions naturally calls for the integration of DLLI in existing optimization algorithms, either as warm-start, or to obtain good dual bounds fast. Multiple optimization algorithms have been proposed optimize Lagrangian functions, which may yield more efficient training algorithms in DLL. Finally, given the importance of conic optimization in numerous real-life applications, DLL can provide useful complement to existing primal proxies.
Acknowledgments
This research was partially supported by NSF awards 2007 164 and 21 12533, and ARPA-E PERFORM award DE-AR0001280.
10

---

References
[1] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: A methodological tour d' d'horizon. European Journal of Operational Research, 290(2):405-421, 2021. ISSN 0377-2217. doi: https:://doi.or//100 101..000.0.......0200...00 .063.
[2] James Kotary, Ferdinando Fioretto, Pascal Van Hentenryck, and Bryan Wilder. constrained optimization learning: A survey. In Zhi-Hua Zhou, editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pages 4475-448) 4482. International Joint Conferences on Artificial Intelligence Organization, 8 2021. doi: 10.24963/ ijcai.2021/610 URL httts:://dott http///oooorr//////// 10. 24963/ ijcai 2021/610 Survey Track.
[3] Ferdinando Fioretto, Terrence WK Mak, and Pascal Van Hentenryck. Predicting AC Optimal Power Flows: Combining deep learning and lagrangian dual methods. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 630-637, 2020. URL https
//doi.org// 10. 1609/ aaai v34101,1111111 5403
[4] Xiang Pan, Tianyu Zhao, Minghua Chen, and Shengyu Zhang. DeepOPF: A deep neural network approach for security- DC optimal power flow. IEEE Transactions on Power Systems, 36(3): 1725)):725-17333 2020.
[5] Priya L. Donti, David Rolnick, and J. Zico Kolter. DC3: A learning method for optimization with hard constraints. In 9th International Conference Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021, 2021. URL http/ttts///clr.cco http:///c....c/viruuaa///////// poster/2868
[6] Seonho Park and Pascal Van Hentenryck. Self-supervised primal-dual learning for constrained optimization. Proceedings the AAAI Conference on Artificial Intelligence, 37(4):4052 40600 2023. doi: 10. 20.1669/aai..v2 v37.4.25522 URL https://ojs aaai. org/
wwt//idex..../oooooooooooooe iindxx,dxx,//// php/AAAT
article/view 25520
[7] Chendi Qian, Didier Chételat, and Christopher Morris. Exploring the power of graph neural networks in solving linear optimization problems. In Sanjoy Dasgupta, Stephan Mandt, and Yingzhen Li, editors, Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pages 1432-1440. PMLR, 02-04 May 2024. URL URLtttts:: http:::t///rrreee https://ppoceeeddngs mlr. wttp://sw.....meeeeeeeeeeeeeeeee v238//233////
v238/qian24s qian24a..aaaaa/aa html
[8] James Kotary and Ferdinando Fioretto. Learning constrained optimization with deep augmented lagrangian methods, 2024.
[9] Irwan Bello, Hieu Pham, Quoc Le, Mohammad Norouzi, and Samy Bengio. Neural combi- natorial optimization with reinforcement learning. In Sth International Conference Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Workshop Track Proceedings. OpenReview.net, 2017. URL htttps://openreviiie http:////pppaeeeeeeeeeee///re/re wwtp://oooooiiddeeeemeeee
[10] Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30, 2017.
[11] Wenbo Chen, Mathieu Tanneau, and Pascal Van Hentenryck. End-to-End Feasible Optimization Proxies for Large-Scale Economic Dispatch. IEEE Transactions on Power Systems, pages 1-12, 2023. doi: 10. 20009/22
[12] Jesus Tordesillas, Jonathan P How, and Marco Hutter. Rayen: Imposition of hard convex constraints on neural networks, 2023.
[13] Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond, and J. Zico Kolter. Differentiable convex optimization layers. In Wallach, H. Larochelle, A. Beygelzimer, F. L'Alché-Buc, F. Fox, and R. Garnett, editors, Advances in Neurul Information Processing Sys- tems, volume 32, Curran Associates, Inc., 2019. URL https //tp newteeeeiddiinn...e.......e..... cc/ / bagpreac...iaaoooooggooeeeeeeeea

---

[14] Meiyi Li, Soheil Kolouri, and Javad Mobammadi. Learning to Solve Optimization Problems With Hard Linear Constraints. IEEE Access, 11:59995-60004 2023. doi: 10.110/SS. 2023.3285199.
[15] Andrei V Konstantinov and Lev V Utkin. A new computationally simple approach for imple- menting neural networks with output hard constraints. In Doklady Mathematics, pages 1-9. Springer, 2024.
[16] Terrence W.K. Mak, Minas Chatzos, Mathieu Tanneau, and Pascal Van Hentenryck. Learning regionally decentralized ac optimal power flows with admm. IEEE Transactions on Smart Grid, 14(6):4863-455 2023.
[17] Sebastian Kraul, Markus Seizinger, and Jens O. Brunner. Machine -upported prediction of dual variables for the cutting stock problem with an application in stabilized column genera- tion. INFORMS Journal on Computing, 35(3):692-709, 2023. doi: 10. 287/
[18] Nagisa Sugishita, Andreas Grothey, and Ken McKinnon. Use of machine learning models to warmstart column generation for unit commitment. INFORMS Journal on Computing, 2024. doi: 10. 0111188//joc222221140
[19] Augustin Parjadis, Quentin Cappart, Bistra Dilkina, Aaron Ferber, and Louis- Martin Rousseau. Learning Lagrangian Multipliers for the Travelling Salesman Problem, 2023.
[20] Francesco Demelas, Joseph Le Roux, Mathieu Lacroix, and Axel Parmentier. Predicting lagrangian multipliers for mixed integer linear programs. Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 10368-10388 PMLR, 21-27 Jul 2024. URL htttps:/pproceedingg mlr. prwss/ v235 /etps//dmeela22225. html
[21] Guancheng Qiu, Mathieu Tanneau, and Pascal Van Hentenryck. Dual Conic Proxies for AC Optimal Power Flow. In Power Systems Computations Conference, 2024.
[22] Michael Klamkin, Mathieu Tanneau, and Pascal Van Hentenryck. Dual interior-point optimiza- tion learning, 2024.
[23] Aharon Ben-Tal Tal and Arkadi Nemirovski. Lectures on modern convex optimization: analysis, algorithms, and engineering applications. SIAM, 2001.
[24] M. Lubin, E. Yamangil, R. Bent, and J. P. Vielma. Extended Formulations in Mixed-Integer Convex Programming. In Q. Louveaux and M. Skutella, editors, Proceedings of the 18th Conference on Integer Programming and Combinatorial Optimization (IPCO 2016), volume 9682 of Lecture Notes in Computer Science, pages 102-113, 13, 2016.
[25] Akshay Agrawal, Shane Barratt, Stephen Boyd, Enzo Busseti, and Walaa M. Moursi. Differenti- ating through a Cone Program. Journal of Applied and Numerical Optimization, 1()):107-115, August 2019.
[26] Jorge Nocedal and Stephen J Wright. Numerical optimization. Springer, 1999.
[27] Stephen P Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[28] Neal Parikh, Stephen Boyd, et al. Proximal algorithms. Foundations and trends@ in Optimiza- tion, 1(3):127-239, 2014.
[29] Arnaud Freville and Gérard Plateau. An efficient preprocessing procedure for the multidimen- sional 0-1 knapsack problem. Discrete Applied Mathematics. 49(1):1892112 1994. ISSN 0166-218X. doi: 10. 11111000666-11889999000000 tion.
Special Volume Viewpoints on Optimiza-
[30] Arnaud Freville. The multidimensional 0-1 knapsack problem: An overview. European Journal of Operational Research, 155(1):1-21, 2004. ISSN 0377-2217. doi: 10.1016/50337-22117033
00274-1.
12

---

[31] Hans Ziegler. Solving certain singly constrained convex optimization problems in production
planning. Operations Research Letters, 1(6):246 1982. ISSN 0167-6377. doi: 10.1016/ 0167-6377(82)90000-xX
[32] MOSEK Aps. The MOSEK Modeling Cookbook, 2023. URL https://doce. htw.::/:://occccoo..e... com/
bodelingg-cookboo//nndde html
13

---

A
Proofs for Section (Dual Lagrangian Learning (DLL))
Theorem 1 (Dual conic completion). Assume that Vğ K", Fr Hr > h and the problem
min {cTx x + (b-Ar) 9 HE Ze h
(8)
bounded. Then, Vg E K", a A g+ H = c, i.e. () is feasible for 7
Proof. Let i E K", and recall that ( is bounded and strictly feasible. By strong duality, its dual
max
{ Th + bJg 0 H
A g. E C*}
(27)
Therefore, there exists a feasible solution 2 for 27 By construction, & E and A + H c, hence (Ú, 2) is feasible for 7
solvable BTNOT
C*
Theorem 2 (Optimal dual completion). Let K", and let be dual for (8)
Then, Cly. 2) DJ ý + h & valid dual bound on the optimal value of (6 and L(j, 2) the strongest dual bound that can be oblained after fixing y ÿ in
Proof. First, recall that exists by strong conic duality; see proof of Theorem Furthermore, (0. feasible for 7 by construction. Thus, by weak duality, the Lagrangian bound L(ğ) bt 5 h is a valid dual bound on the optimal value of (6). Finally, fixing = ÿ in 7 yields
max
y 9)
(28)
which is equivalent to (27). Hence, its optimal value is bT g+hh = L(0. 2) by definition of a. Example (Bounded variables). Consider a conic optimization problem with bounded variables
min
{cTxz x Ax łx b, 1 x < u
where < u are finite lower and upper bounds on all variables æ. The dual problem is
min W,2l,e"
(b y - TT nd A + - = E x' 2 0, 2" 2 0}
(10)
and the optimal dual completion is 2 = lc ø) nth
Proof. Let ÿ E K be fixed. Fixing in the dual problem yields
max =1,2
1 z - u T
(29)
s.t. - = - A
(30)
212²" 20 0.
(31)
Eliminating 2 === =" (c- ATo), the problem becomes
max (1 (1- 4) 2" + (c A 4)
(32)
s.t. 2² (c A
(33)
z²0 0.
(34)
Since < i.e., the objective coefficient of z" is negative, and the problem is maximization problem, follows that z" must as small as possible in any optimal solution. Hence, at the optimum, 2" max(0, - (c A AT)) |c A o_ and Et = A gl+
Example 2 (Trust region). Consider the trust region problem [NW99)
min {c Ar žx b, ||=||| rr)
(11)
where r20, ||:|| is a norm, and || + (r, EC= [(t, x) ||
). The dual problem is
max 8-20.2
yby-rzz A ATy+2 = c, K (zo, E c**
(12)
where ||-11+ is the dual norm and C* {(t, x)) | 1 | BV04y. The optimal dual completion is 2 A T g. &o ||
14

---

Proof. The relation & = c- A immediate from the dual equality constraint A y Next, observe that 2g appears only in the constraint (Zo, 2) C*, and has negative objective coeffient. Hence, 20 must be as small possible in any optimal solution. This yields &n ||
Example 3 (Convex quadratic objective). Consider the convex quadratic conic problem
min (1/2 x x Qu + x Ax >x
(13)
where Q = F F is positive definite. The problem can be formulated as the conic problem
min
{a+ cxx Ax xx b. (1, Fx) E 2
(14)
whose dual is
max 2.20.2
{b 20
A FT, c. (1, 10, 2) E 2
(15)
The optimal dual completion is 2 F T (c A Ø). 2u 1/21
Proof.
The proof uses the same argument the proof of Example 2 Namely, 8 == F A) is immediate from the dual equality constraint A A + + _
Note that F is non-singular because Q is positive definite. Finally, 2g has negative objective coefficient, and only appears the conic constraint (1, 20, 2) O,- Therefore, at the optimum, one must have 28 2 which concludes the proof.
B Standard cones
This section presents standard cones and their duals, as well as corresponding Euclidean and radial projections. The reader is referred to [CKV22] for more exhaustive list of non-standard cones, and to [PB 14 Sec. 6.3] for an overview of Fuclidean projections onto standard cones.
B.1 Non-negative orthant
The non-newe nog-negative orthant is defined R7 {x R" 0}. It is self-dual cone, and forms the basis of linear programming [TOOT]
Euclidean projection The Fuclidean projection on R is
11 Ugg (j) max(0, ÿ) ReLU(g),
(35)
where the max and ReLU operations are performed dlement-wise.
The radial projection with ray applied coordinate-wise, is equivalent to the Euclidean projection.
Radial projection
B.2
Conic quadratic cones
Conic quadratic cones include the second-order cone (SOC)
nh {ir IR. x1 2
+
(36)
and the rotated second-order cone (RSOC)
2" = {x ER" :2r 2 1
X1, 2 0).
(37)
Both cones are self-dual, i.e., Q Q and O e. The RSOC is the main building block of conic optimization problems.
formulations of convex quadratically-constrii
Euclidean projection
The Euclidean projection on Q" is given by
T
if o E Q
I (z)
if i - otherwise
(38)
2,+6 25
(8, 32 Fn)
where 8 (( 22)
15

---

Radial projection Given interior ray (1,0, ..., 0) > Q" 0, the radial projection is
1 (8) (+1, 22, ... 1n),
G max(@1, ( ... Tx. 2l))))
(39)
Note that, in the worst case, computing ( requires (2n) operations, and modifies all coordi- nates of ž. In contrast, computing 11g (3) requires only (nn) operations, and only modifies the first coordinate of x.
Closed-form formulae for Euclidean and radial projections onto O are derived from and (39).
B.3 Positive
cone
The cone of positive semi-definite (PSD) matrices of order defined as
S =X R=== X X Amin (X) 0).
(40)
Note that all matrices in S are symmetric, hence all their eigenvalues are real. The PSD cone is self-dual, and generalizes the non-negative orthant and SOC cones (BV04).
Euclidean projection The Euclidean projection onto S is given by
Tsş (X)
Σ max(0, A:)o,u,"
(41)
where X E R is symmetric with eigenvalue decomposition X = E, Aaveo Note that the Euclidean projection onto the PSD code thus requires full eigenvalue decomposition, which has complexity O(n²).
Radial projection The radial projection considered in the paper uses p In inl(()). This yields the closed-form projection
I (X) X min(0, (X)))
(42)
Note that the radial projection only requires computing the smallest eigenvalue of X, which is typically much faster than full eigenvalue decomposition, and only modifies the diagonal of X.
B.4 Exponential Cone
The 3-dimensional exponential cone is a non-symmetric cone defined as
E E x R
2
xye
//=2 22 0)
(43)
whose dual cone
m = cl yER'
91 y3
2
2
1/ 0. 00030000 <
(44)
The exponential cone is useful to model exponential and logarithmic terms, which occur in, e.g.. relative entropy, logistic regression, or logarithmic utility functions.
To the best of the authors' knowledge, there is no closed-fone foomm analytical formula for evaluating IIg nor Ig.,, which instead require numerical method, see, e.g., [PB 14 and Fr233 for completeness.
Euclidean projection
Radial projection To avoid any root-finding operation, the paper leverages the fact that J1. 22 > 0, V(21, F2,
x2) 23)) E E. Note that one can enforce TT, 32 > via, e.g., softplus activation.
radial projection is then obtained using p (0, 0, 1), which yields
11 (T 22, Ra) = F 32, min (Za, T2 log
(45)
T2
This approach does not require any root-finding, and is therefore more amenable to automatic differentiation. The validity of Eq. (45) is immediate from the representation
- fl E R3
Ø1 I3 log
1 22 > 0}.
(46)
22
222
Similarly, assuming 51 > 0 and Øs < O, the radial projection onto m- reads
11 11.. (z Z2 T3) = V1. max (3z, T3 03
03
(47)
Ta
16

---

B.5 Power Cone
Given 0 0< <a<<< the 3-dimensional power cone is defined as
Pa = f E E 2 2 21, 2
(48)
Power cones are non non-symmetric cones, which allow to express power other than 2. e.g., p-norms with
p 2 1. Note that Py/a scaled version of the rotated second-order cone 2. The 3-dimensional power cone Pa is sufficient to express more general, high- high-dimensional power cones. The dual power cone
=a= -
1/2 ( a'1-a
EPa
(49)
Euclidean projection
The Euclidean projection onto the power cone Pa is described in Hiel5
Similar to the exponential cone, it requires a root- noot-finding operation.
The proposed radial projection is similar to the one proposed for E. Assuming T2 F3 > 0, and using p (1,0,00 0), the radial projection reads
Radial projection
11 (I1, T2,
max (11. 22 [3g 82.
(50)
A similar approach is done to recover y E P after scaling the first two coordinates of This technique can be extended to the more general power cones.
C Experiment Details
C.1 Common experiment settings
All experiments are conducted on the Phoenix cluster [AC17] with Intel Xeon Gold 6226@2.70GH. + Tesla V100 GPU nodes; each job was allocated GPU, 12 CPU cores and 64GB of RAM. All ML models are formulated and trained using Flux IIF+ 18 unless specified otherwise, all (sub)gradien) are computed using the auto-differentiation backend Zygote [In18]] All linear problems are solved with Gurobi v10 GOI8. All nonlinear conic problems are solved with Mosek [MOS23])
All neural network architectures considered here are fully-connected neural networks (FCNNs). Thus, separate model is trained for each input dimension. Note that the proposed DLL methodology is applicable to graph neural network architectures, which would support arbitrary problem size. The use GNN models in the DLL context is a promising avenue for future research; a systematic comparison of the performance of GNN and FCNN architectures is, however, beyond the scope of this work.
All ML models are trained in a self-supervised fashion following the training scheme outlined in Section and training is performed using the Adam optimizer [B155 The training scheme patience mechanism where the learning rate is decreased by a factor if the validation loss does improve for more than N, epochs. The initial learning rate 17 = 10-4, Training is stopped maximum Nm.. epochs is reached. Every ML.
if either the learning rate reaches Muiia 10-7 model considered in the experiments was trained in under an hour.
A limited, manual, hypertuning was performed by the authors during preliminary experiments. It was found that DLL models require very little hypertuning, if any, to achieve satisfactory performance. In contrast, DC3 was found to require very careful hypertuning, even just to ensure its numerical stability. is also important to note that DC3 introduces multiple additional hyperparameters, such the number of correction steps, learning rate for the correction steps, penalty coefficient for the soft penalty loss, etc. These additional hy hyprpaarameters complicate the hypertuning task, and result in additional computational needs. Given the corresponding economical and environmental costs, only limited hypertuning of DC3 was performed.
Finally, it was observed that DC3 often fail to output dual-feasible solutions, which therefore do not valid dual bounds. Therefore, to ensure fair comparison, the dual solution produced by DC3 fed to the dual optimal completion of DLI., thus ensuring dual feasibility and valid dual bound. This is only performed at test time, with a negligible overhead since the dual completion uses closed-form formula. All optimality gaps for DC3 reported for this valid dual bound.
17

---

C.2 Linear programming problems
C.2.1 Problem formulation
The first set of experiments considers the continuous relaxation of multi-dimensional knapsack problems [FP94] Fre04] which of the form
min {-p Wx S b, 2 E [0,
(51)
where n denotes the number of items, denotes the number of resources, p I& is the value of each item, by is the amount of resource i, and Wiy denotes the amount of resource i used by item The dual problem reads
max 2.2
(b'y-c W y V u+ 2" = P. p. 0, 0, 2 20.
(52)
C.2.2 Data generation
For each number of items n (100, 200, 500) and number resources m E (5. 10. (0.00.._000000 total of 16384 instances generated using the same procedure as the MIPLearn library (SXQG+23 23). Each instance is solved with Gurobi, and the optimal dual solution is recorded for evaluation purposes. This dataset is split in training, validation and testing sets, which contain 8192, 4096 and 4096 instances, respectively.
C.2.3 DLL implementation
The DLL architecture considered here fully-connected neural network (FCNN); a separate model is trained for each combination (m, nt). The FCNN model takes as input the flatted problem data (b, p, W) E *R-++ and outputs y E R.. The FCNN has two hidden layers of size 2(m + n) and sigmoid activation; the output layer completion procedure follows Example
negated softplus activation ensure 0. The dual
Hyperparameters epochs is N max 1024.
The patience parameter is N, =32 and the maximum number of training
C.2.4 DC3 implementation
The DC3 architecture consists of initial FCNN which takes input (b, p, W), and outputs z Then, z" is recovered by equality completion as 2" = -p+ + W + z/. The correction then applies gradient steps (y, 2*) + (y. <Voly, 2') where
ply 2 max(0, 1) + min 2 2 =I"
The corresponding gradients Vøly, =1) were computed analytically. After applying corrections, the dual equality completion is applied one more time to recover 2", and the final soft loss is
b 2
6(y.2))
(53)
which considers both the dual objective value, and the violation of inequality constraints. Note that the dual objective 6T - e 2" is not a valid dual bound in general, because x', z" may not be dual-feasible.
Hyperparameters The maximum number of correction steps is 10, the learning rate for correction is 7 10-1 The soft penalty weight is set to p 10; this parameter was found to have a high impact on the numerical stability of training. The patience parameter N,, = 32, and the maximum number of training epochs is Nuxx 1024.
18

---

C.3 Nonlinear Production and Inventory Planning Problems
C.3.1
Problem formulation
The original presentation of the resource-constrainee production and inventory planning problem Zie82 uses the nonlinear convex formulation
min
Edjas + f3
Sim Dij
(54a)
3
8.l. xTx S, x x2 0,
(54b)
(54c)
where is the number of items to be produced, amount, and > 0 denotes the resource consumption rate of item j. The objective function captures production and inventory costs. Namely, d J and f, = D where c > and Dj > denote per-unit holding cost, rate of holding cost, ordering cost, and total demand for item j. respectively.
R R denotes the available resource
The problem is reformulated in conic form MOS23a as
min x,t
d fx
(55a)
s.l. 5b
(55b)
(1 V2) E O₂,,
Vj I.
(55c)
whose dual problem is
max
by /2e jj
(56a)
9,3,5,0
ry + d,
(56b)
7 T= fz
(56c)
y SSO. 0,
(56d)
(Tg, Ty) E O =j= L...n
(56c)
Note that the dual problem contains + 3n variables, 2n equality constraints, 1 línear inequality constraints, and n conic inequality constraints. Therefore, DC3 must predict n + 1 dual variables, then recover 2n variables by equality completion, and correct for n + 1 inequality constraints. In contrast, by exploiting dual optimality conditions, DLL eliminates 3n dual variables, thus reducing the output dimension of the initial prediction from n + 1 to 1, and eliminates the need for correction.
C.3.2 Data generation
For each n E (10, 20, 50, 100, 200, 500, 1000). 16384 instances are generated using the procedure of [Zie82]. First, D, is sampled from uniform distribution U[1, 100), df, is sampled from U11, 10), and of sampled from (0.05, 0.2). Then, ef ayd; and ry B,c where a, B are sampled from U 1.5) and (0,,1, 2], respectively. Finally, the right-hand side is = Σ, r where 7) is sampled from U(0.25, 0.75).
Each instance is solved with Mosek, and its solution is recorded for evaluation purposes. The dataset split into training, validation and testing sets comprising 8192, 4096 and 4096 instances. respectively.
C.3.3 DLL implementation
The DLL architecture consists of an initial FCNN that takes as input (d, f, E R1+3n and output E R. The FCNNs have two hidden layers of size max(128, 4n) and sigmoid activation. For the output layer, negated softplus activation ensures y S The dual completion outlined Section 5.2 then recovers (T, T).
19

---

Hyperparameters The patience parameter is Mp = 128, and the maximum number of training epochs is Nmx 4096. The patience mechanism deactivated for the first 1024 epochs; this latter setting has little impact of the performance of DLI, and was introduced to avoid premature termination for DC3.
C.3.4 DC3 implementation
The DLL architecture consists of an initial FCNN that takes as input (d, f.r, E IR-++ and outputs y. a R. The FCNNs have two hidden layers of size max 4n) and sigmoid activation, and the output layer has linear activation.
The equality completion step recovers π d ry and f. The correction step then apply gradient steps to minimize the violations u o) - (v, σ) + 2n (v,, o)) + o, σ), where
(y σ)) max (0, y)²
(57)
(1, min(0, T))
(58)
(1) = max -
(59)
Note that, to express da (y, o), conic constraints 23e are converted to their nonlinear programming equality, because DC3 does not handle conic constraints. Gradients for é are computed analytically, and implemented directly the inequality correction procedure. The final soft loss then
by /2e oj po(y.o).
(60)
Hyperparameters The maximum number of correction steps is 10, the learning rate for correction is y= 10-50 and the soft loss penalty parameter is p 10. The patience parameter is Np 128, and the maximum number of training epochs is NMma = 4096. The patience mechanism deactivated for the first 1024 epochs; this latter setting has little impact of the performance of DLL, and was introduced to avoid premature termination for DC3.
Overall, DC3 was found to experience substantial numerical instability, and failed to produce dual- feasible solutions on a majority of instances. Increasing the number of correction steps helps alleviate this issue, at the cost of more expensive inference and back-propagatte rate for correction (7) was also found to yield smaller violations, yet resulted in degraded numerical stability. Finally, increasing the number of correction steps also increases GPU memory requirements, which can further affect training performance.
Increasing the learning
C.3.5 Convergence plots
Figures and shoow the progress of the Lagrangian dual bound obtained by DLL and DC3 throughout training. The figures report the average Lagrangian dual bound on the training and validation set, as function of the number of epochs (Figure 2) and training time (Figure 3. The difference in training times, for a same number of epochs, is explained by the longer inference and back pack-propagation times for DC3 (see also Table 5).
Both figures show that DLL exhibits a faster convergence, with performance plateau-ing after about 1,000 training epochs. The performance of DC3 degrades as the instances become larger (from 10
500): the plots exhibit more erratic behavior, especially in the first 500 training epochs. On the smallest instances (n=10 and n=20), the behavior stabilizes after about 500 epochs, yet progress remains slow compared DLL.
20

---

1200
Figure 2: Production planning instances: convergence plots of average Lagrangian dual bound on training and validation sets for DLL and DC3 models, as function of the number of training epochs.
4.1
40
1000
100
200
n=000
n-0
130.1/
km
4.0"""
10007
Figure 3: Production planning instances: convergence plots of average Lagrangian dual bound on training and validation sets for DLL and DC3 models, function of training time.
21

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The abstract mentions the 3 building blocks of the proposed methodology. which are described in Section 4 The numerical results that are mentioned in the abstract reflect the results presented in Section
Justification:
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Theoretical and practical limitations are discussed in Section 6.2
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Assumptions are stated in the paper and in theorem, and proof's are provided in Appendix.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification: Experiment details provided in Appendix C These include:
Computing resourees used for experiments (CPU and GPU models)
Problem formulations and data-generation procedures
Neural architecture used in the experiments
Detailed training scheme
Hyper-parameter used for the final results
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All the data used in the experiments is publicly available and/or synthetically generated. We have cited sources whenever using data- eetaa-enerationn procedure proposed elsewhere. We intend to release our code upon acceptance of the paper.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: Experimental details are provided in Appendix
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
22

---

When reporting optimality gaps in Section S (Tables and 4 we report averages, standard deviations, and maximum across the test set. Computing times reported in Tables 3 and were evaluated over multiple runs.
Justification:
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: Compute resources and training time are reported in Appendix C
9. Code Of Ethies
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httppp////eeerisss.cccpbbbbb/eec
Answer: [Yes]
Justification: We have reviewed the code of ethics, and do not see any deviation to report.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Broader impact is discussed in Section (Limitations) and Section (Conclu- sion).
Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: Not applicable.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All prior codes / methods have been cited.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: [NA]
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: [NA]
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
23

---

Answer: [NA]
Justification: [NA]
References for the Appendix
[BTNOI] Aharon Ben-Tal and Arkadi Nemirovski. Lectures on modern convex optimization: analysis, algorithms, and engineering applications. SIAM, 2001.
[BV04] Stephen P Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[CKV22] Chris Coey, Lea Kapelevich, and Juan Pablo Vielma. Solving natural conic formulations with hypatia.jl. INFORMS Journal on Computing. 34(5):2686-2699, 2022.
[FP94] Arnaud Freville and Gérard Plateau. An efficient preprocessing procedure for the multidimensional 0-1 knapsack problem. Discrete Applied Mathematics, 1994. Special Volume Viewpoints on Optimization.
[Fre04] Amaud Freville. The multidimensional 0-1 knapsack problem: An overview. European Journal of Operational Research, 155(1):1-21, 2004.
[Fri23] Henrik A. Friberg. Projection onto the exponential problem. Optimization Methods and Software, 38(3):457-473, 2023.
univariate root-finding
[GO18] LLC Gurobi Optimization. Gurobi optimizer reference manual, 2018.
[Hie15] Le Thi Khanh Hien. Differential properties of euclidean projection onto power cone. Mathematical Methods of Operations Research, 82:265-284, 2015.
[Inn18] Michael Innes. Don't unroll adjoint: Differentiating ssa-form programs.
CoRR,
abs/1810.07951, 2018.
[IF+ 18] Michael Innes, Elliot Saba, Keno Fischer, Dhairya Gandhi, Marco Concetto Rudilosso, Neethu Mariya Joy, Tejan Karmali, Avik Pal, and Viral Shah. Fashionable modelling with flux. CoRR,
2018
[KB15] Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
[MOS23a] MOSEK Aps. The MOSEK Modeling Cookbook, 2023.
[MOS23b] MOSEK Aps. The MOSEK optimization toolbox for Julia manual. Version 10.1.23., 2023.
[NW99] Jorge Nocedal and Stephen Wright. Numerical optimization. Springer, 1999.
[PACI7] PACE. Partnership for an Advanced Computing Environment (PACE), 2017.
[PB+ 14] Neal Parikh, Stephen Boyd, et al. Proximal algorithms. Foundations and trends@ in Optimization, 127-232,- 2014.
[SXQG+ 23] Alinson Santos Xavier, Feng Qiu, Xiaoyi Gu, Berkay Becu, and Santanu S. Dey. MIPLeam: An Extensible Framework for Learning- Enhanced Optimization, June 2023.
[Zie82] Hans Ziegler.
Solving certain singly constrained production planning. Operations Research Letters, 1(6):246-25 252, 1982.
optimization problems in
24


Reviews:
[{"review_id": "qrVskeqrB7", "reviewer": "Reviewer_yA4S", "summary": "The paper introduces Dual Lagrangian Learning (DLL), a machine learning framework designed for dual conic optimization problems. DLL utilizes conic duality and machine learning models to produce high-quality, dual-feasible solutions and corresponding Lagrangian dual bounds for both linear and nonlinear conic optimization problems. It introduces techniques like a systematic dual completion procedure, differentiable conic projection layers, and a self-supervised learning framework based on Lagrangian duality. The methodology is demonstrated to significantly outperform existing state-of-the-art methods and provides a faster alternative to traditional interior-point methods used in commercial solvers.", "questions": "Justification for Focus on Continuous Problems: Can the authors provide a stronger rationale for focusing predominantly on continuous problems given the prevalent interest and necessity for solving MIP in real-world applications?\nComparison with Existing Methods: How does DLL compare in performance and applicability with existing methods that combine ML with Lagrangian relaxation specifically for MIP problems?\nScalability and Practical Applicability: Could the authors elaborate on the potential scalability of DLL? Are there plans to test the methodology on larger-scale problems, particularly those involving discrete decisions common in industrial applications?", "limitations": "The limitations are provided in the paper, but in the view of the above review, they appear to be rather restrictive.", "rating": 3, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper introduces Dual Lagrangian Learning (DLL), which combines machine learning (ML) techniques with dual conic optimization to enhance the computation of dual feasible solutions and corresponding Lagrangian bounds. This integration addresses both linear and nonlinear conic optimization problems, aiming at providing a new approach as compared to a traditional methods. The methodology applies differentiable programming to optimization, thus enabling gradient-based optimization methods to refine dual solutions directly. The paper is well-structured and articulates complex ideas with clarity.", "weaknesses": "Despite its strengths, the paper has several areas that could be improved:\n\nScope of Application: The focus on continuous problems seems a step back considering the current trend and necessity of addressing mixed-integer programming (MIP) in real-world important applications like power systems and manufacturing, which authors rightfully point out in the beginning. The utility of DLL in these contexts remains unclear, especially without addressing the discrete aspects of such problems.\nIncremental Nature: The contributions, while innovative in combining ML with dual conic optimization, appear incremental when compared to existing research integrating ML with Lagrangian relaxation for MIP. More distinction or comparison with these methods could help in highlighting the unique advantages of DLL.\nNumerical Validation: The experiments provided are based on relatively small problem instances. This limitation might raise concerns about the scalability and practical applicability of DLL. Even by the standards of MIP applications, the sizes of the problems tested appear to be rather small. Extending these experiments to larger, more complex problem instances could enhance the paper's impact and relevance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed feedback and their appreciation of our work.\nPlease refer to our general rebuttal for a detailed discussion of how DLL can be used in the non-convex and discrete setting.\nDetailed answers to the reviewer's questions follow.\n\n## Comparison with Lagrangian decomposition for MIP problems\n\nWe agree with the referee that MIP problems are of utmost importance in real-life applications.\nWe would nevertheless like to point out that many real-life problems are posed as conic optimization problems, e.g., portfolio optimization problems in finance, model predictive control, day-ahead and real-time electricity market-clearing, etc.\n\nMore importantly, convex optimization is at the heart of most algorithms for mixed-integer optimization, e.g., branch-and-cut or outer approximation. Hence, by providing highly efficient tools for convex conic optimization, DLL makes a first step towards scalable learning-based methods for mixed-integer optimization.\n\nIn addition, while LD-MIP and DLL both leverage Lagrangian duality, DLL introduces tools that handle nonlinear conic constraints, whereas, to our knowledge, existing work on LD-MIP only considers the dualization of linear constraints.\nFinally, while obtaining a valid dual bound in LD-MIP requires solving a combinatorial problem, which may be NP-hard, DLL obtains valid bounds using efficient (polynomial-time), closed-form formulae for a very broad class of problems.\n\n## Scalability\n\n(this answer is repeated in our response to reviewer `H5sy`)\n\nThe scalability of our proposed framework is supported by several key ingredients:\n* Efficient conic projection layers: DLL does not require any external solver, nor the resolution of NP-hard problems (when considering the standard cones presented in the paper). We also introduce non-Euclidean conic projection with better complexity. For instance, for the PSD cone, the Euclidean projection has complexity $O(n^{3})$, compared to $O(n^{2})$ for the proposed radial projection.\n* Closed-form dual conic completion: we showcase several efficient dual completion layers for broad classes of problems (See Examples 1--3 and numerical experiments)\n* Self-supervised learning: this removes the need for offline data-generation using standard optimization solvers. This greatly accelerates training, and we have found this approach to often yield improved performance compared to supervised learning settings.\n\nFinally, DLL-based proxies are expected to offer similar computational burden and benefits as primal optimization proxies, which have been shown in various works to be scalable for large-scale real-life problems.", "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": "", "extra_scores": {}}, {"review_id": "nXF7O9oiSe", "reviewer": "Reviewer_9KhZ", "summary": "This paper presents the Dual Lagrangian Learning (DLL) framework that utilizes a fully-connected neural network (FCNN) to provide high-quality dual-feasible solutions that can be used to generate valid Lagrangian dual bounds for linear and nonlinear conic optimization problems without the use of costly implicit layers. This FCNN provides a candidate dual feasible point that is passed through a conic projection step to produce a dual feasible point, then dual completion subproblem is solved to get a complete dual feasible pair $(\\hat{z}, \\hat{y}) which is then used to get a valid Lagrangian dual bound. The subgradient of the Lagrangian at the dual feasible point is used to update the FCNN network weights to provide better candidate points. The dual completion subproblem is solved for a variety of conic optimization problems. The experimental evaluation is done on both linear and nonlinear conic optimization problems and it is shown to outperform the state-of-art method DC3.", "questions": "1. On Line 515-6, there seems to be a typo. \"do not valid bounds\" should be replaced with \"do not output valid bounds\"\n2. How was the limited tuning of DC3 done? While DC3 has many parameters and is difficult to tune, it is possible that DC3 maybe better with more extensive tuning. It is important to show that a reasonable effort was made to tune DC3 before claiming that its performance is worse than DLL.\n3. How does the quality of the candidates provided by DLL change over time? It would be interesting to see how the Lagrangian dual bound changes with each iteration of DLL. \n4. What considerations did you use when designing the FCNN for DLL? Have you tried other NN architectures other than GNNs?", "limitations": "The authors acknowledge the limitations of their work, which include lack of consideration for general non-convex constraints and suggest Graph Neural Networks (GNNs) as a promising future avenue of research.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The strength of the paper is the simplicity and effectiveness of the DLL framework compared to DC3 and commercial interior point solvers. While previous work used dual feasible points as a warm-start, this work shows how dual feasible points can be used to get valid Lagrangian dual bounds.", "weaknesses": "The main weakness of the paper is lack of consideration for general non-convex constraints. A minor weakness of the paper is lack of detail about how DC3 was tuned. The authors claim that DC3 was difficult to tune and only limited tuning was done with DC3 due to this. However, on the positive side, they do provide adequate detail of how the hyperparameters for DC3 were set for easy reproducibility.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time reviewing our paper, and for their insightful comments.\nPlease see our general rebuttal regarding how DLL can be used in non-convex and discrete settings.\nDetailed responses to the reviewer's questions follow.\n\n## Non-convex constraints\n\nPlease see our general rebuttal.\nIn a nutshell:\n* Most algorithms for global non-convex optimization leverage convex relaxations. DLL can therefore provide high-quality surrogate models for these convex relaxations, and/or accelerate their resolution.\n* DLL can be extended to handle non-convex and discrete constraints by leverage similar Lagrangian duality. However, obtaining valid Lagrangian bounds then requires solving typically NP-hard problems, instead of polynomial-time closed-form formulae in the conic setting.\n\n## Model architecture and tuning\n\nAs the reviewer pointed out, DC3 has multiple hyper-parameters, which makes its tuning difficult and resource-intensive.\n\nWe ran initial experiments on small datasets to evaluate the sensitivity of DC3's performance with respect to 1) number and size of hidden layers, 2) overall learning rate, 3) number of inequality corrections, 4) learning rate for correction mechanism. These experiments led us to select the hyper-parameters reported in the paper.\n\nWe decided not to run systematic hyper-tuning for each size of problems because of the associated financial and environmental cost.\nIndeed, for production planning instances, even on the smallest instances, each DC3 training run would typically hit its 1-hour time limit on a V100 GPU (at a cost of about \\\\$1/hr). Even testing just 15 hyper-parameter combinations would require a computing budget of \\\\$100 to produce the results of Table 4.\n\nTo ensure a fair comparison with DLL, we nevertheless implemented the following improvements, which mostly catered to DC3:\n* we implemented batched, analytical gradients to DC3's correction mechanism, to alleviate the use of AD tools;\n* we implemented a learning rate scheduler to reduce the need for tuned learning rate. We also added a patience mechanism to avoid DC3 getting stuck in a local optimum early on;\n* we increased the limits for training to 4000 epochs and one hour. In contrast, DLL models typically reached 99.9% of their final performance in at most 5min and a couple hundred epochs.\n\nWe agree with the reviewer that there might exist a configuration of DC3 whose performance is greatly improved compared to results presented in the paper. However, our experience suggests that this comes at a heavy price tag compared to DLL, be it developer's time, cloud computing budget, or environmental cost.\n\nFinally, while we did not consider GNN architecture in this work, it is a very natural avenue which we intend to explore in future work.\n\n## Performance of DLL\n\nAs we briefly mention above, the training of DLL models is typically completed in at most 200 epochs and under a few minutes.\nWe recorded a relative improvement of the average Lagrangian bound of less that 0.1% between 5min and 1hr of training time.\n\nWe will include a figure comparing the evolution of the DLL and DC3 bound during training in the final version of the paper.", "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": "", "extra_scores": {}}, {"review_id": "rQKy73QJEo", "reviewer": "Reviewer_vMXP", "summary": "This paper addresses the broad category of machine learning (ML) for optimization, where ML-based approaches are used to obtain solutions or bounds on the solutions of optimization problems. In particular, the paper addresses a particular subclass of problem - conic problems, and even more specifically, the dual solution of these problems.\n\nMost \"ML-for-optimization\" frameworks have thus far focused on finding the solution to primal problems, which is intuitive because the variables in primal problems are typically the variables of interest for most real-world problems. However, learning dual solutions can help certify or bound the primal solution, and in some cases, one may be interested in the dual solution directly (for example, when learning shadow prices in economic optimization problems). This paper uses a conic projection layer in addition to the dual completion step to ensure dual feasibility.\n\nThe paper compares the method (DLL) to other existing methods in terms of their ability to learn solutions to dual problems and shows superiority, mostly due to the fact that DLL includes dual optimality conditions in addition to dual feasibility constraints. An alternative to Euclidean projection is also provided (Radial projection), for the projection layer, which allows for computation once per cone and attempts to avoid gradient vanishing issues during training.", "questions": "It would be interesting to also see indications of whether or not strong duality holds in the test cases, if this is not too challenging to check. If so, the optimality gaps reported also should hold in the primal. The authors may also want to come up with some examples of why learning dual solutions directly may be a contribution on its own, outside of just providing a bound on a primal solution.\n\nI would also want to see more of a discussion about the comparison with reference [19], specifically, is [19] already generalizable but the authors only applied it to the AC OPF problem in the paper?\n\nRegarding the use of implicit layers, a discussion (or even better, experiments if time allows) on their computational limitations and how this slows down inference as problem size grows", "limitations": "The authors have sufficiently addressed the limitations of the method. I don't see any potential negative societal impacts of the work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper claims that the model can guarantee dual feasibility, which is significant for yielding bounds on the primal solution. In addition, the authors show a closed-form, analytical solution for conic projections and for dual conic completion, outside of the ML model development.\n\nThe proposed DLL framework doesn't require an explicit formulation of the dual problem; instead, the user must only have to provide a set of primal constraints that satisfy a certain set of conditions. This is convenient but not a main contribution (if the primal conic problem is known, the dual should be relatively easy to find).\n\nEven though the most challenging and time consuming optimization problems in practice are nonconvex optimization problems, many of these problems can be cast as conic problems, and thus the method can be applied to solve quite a large array of problems that may occur in practice.\n\nVersus other methods, the DLL framework requires far less hyperparameter tuning and iterative procedures, which contributes to the ease of training and increased computational speed.", "weaknesses": "One limitation of the method, if a known closed-form optimal dual completion cannot be achieved, is its use of implicit layers. It would be interesting to see how the speedups diminish with very large problems where the implicit layer becomes a bottleneck. \n\nThe comparison with existing approaches is fair since those are the state of the art for learning primal solutions, but it's slightly unfair because those methods were not specifically designed to learn dual solutions. I think this is fine since there are not existing ML-for-optimization methods tailored towards dual solutions in particular, but just to note.\n\nThe work in this paper does seem like a more generalized and extended version of the work in reference [19], where reference [19] was the first to provide a dual proxy for a second-order cone relaxation of the AC optimal power flow (OPF) problem. However, in reading [19], it does not seem to be necessarily limited to the AC OPF problem, although those authors only apply it to such. The approach in the present paper is generalized to a broader class of problems, but is not the first to provide dual feasibility guarantees as determined by a learning model.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful reading of our paper, and their valuable feedback.\nPlease see our general rebuttal for comments regarding how DLL can be used in discrete and non-convex settings.\nDetailed responses to the reviewer's questions follow.\n\n## Implicit layers\n\nWe agree with the referee that implicit layers can quickly become a computational bottleneck for large problems.\nIn our experience, this typically happens when dealing with implicit layers for problems with $>10^{3}$ variables and constraints.\n\nNevertheless, we would like to point out the following:\n* We have never encountered any problem for which we were not able to design a closed-form completion procedure. Indeed, most real-life problems are naturally bounded, which allows to use the completion presented in Example 1. In many cases, finite bounds can be derived for all variables using the problem's structure. Furthermore, Problem (8) (see Theorem 1) can often be decomposed in smaller problems that can be solved in parallel.\n\n   While this is obviously only a computational conjecture, it should also be noted that even a partial dual completion can help reduce the size of the problem that eventually may need to be solved via an implicit layer.\n\n* As we pointed out in the general rebuttal, subgradients of the Dual Lagrangian Loss in Eq. (19a) are of the form $b - Ax$, where $x$ solves Problem (8). Therefore, it suffices to use a primal-dual solver to solve Problem (8), and use the dual (resp. primal) solution for the forward (resp. backward) pass. This would further reduce the computational burden of implicit layers.\n\n    \nWe will include this discussion (and explicit formulae for gradient computation) in the paper's final version.\n\n##  Strong duality\n\nStrong duality does hold for all instances considered in the numerical experiments, i.e., the primal and dual problems have same optimal values. Indeed, note that Slater's constraint qualification condition holds for all considered problems.\n\nThe reviewer is thus correct that the gaps reported in Tables 2 and 4 apply w.r.t to the primal optimal value, whose (average) value is reported in the second column of each table.\n\nThe most common example of dual solutions being valuable on their own is in market-clearing applications, where dual variables represent clearing prices. In that context, DLL can provide highly-accurate price predictions that are guaranteed to satisfy dual feasibility constraints.\n\n## Relation to Ref. [19]\n\nIn reference [19], _Dual Conic Proxies for AC Optimal Power Flow_, the authors learn dual solutions for a second-order cone relaxation of nonlinear, non-convex AC Optimal Power Flow (OPF) problems. While Ref [19] does utilize a dual completion procedure, its approach is specific to the SOC-OPF problem, and does not generalize to arbitrary conic settings.\nFor instance, Ref [19] utilizes the fact that some primal variables can never be zero to eliminate dual variables, a property that does not hold in general. In addition, the authors use domain knowledge to design input features for their models, which cannot be replicated for arbitrary problems.\n\nIn contrast, in this paper proposes theoretical and computational tools for general conic optimization problems.\nIn particular, Theorem 1 offers a much stronger foundation for dual completion procedures than the setting of Ref [19].\nFurthermore, the paper presents closed-form completion procedures for broader classes of problems, and conic projection layers for all standard cones and their duals. This includes the PSD, exponential and power cones, which were not considered in Ref [19].", "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": "", "extra_scores": {}}, {"review_id": "qCrOdC7a3R", "reviewer": "Reviewer_H5sy", "summary": "The authors propose Dual Langrangian Learning for learning dual conic optimization problems. Dual conic completion, differentiable conic projection layers, and a self supervised Lagrangian training framework are discussed.", "questions": "- It is unclear how the utility of this framework can be tested for problem-solving in the real world. While DC3 has been selected as a comparable technique, it remains to be seen whether dual optimization is always beneficial -- for e.g. assuming a problem can be solved both in the primal and dual, are there necessary computational benefits to solving in the dual? How scalable are the proposed algorithmic frameworks?", "limitations": "No.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- Presents a unique framework for the dual optimization. No dedicated framework for dual optimization proxies are known to date\n-Extensive theoretical formulations", "weaknesses": "- The practical use of the framework is unclear especially with regard to scalability and computational costs involved", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback and their appreciation of our work.\n\n## Benefits of dual optimization\n\nWhile the paper outlines the theoretical and computational building blocks of DLL, this methodology is meant to be used in tandem with primal techniques, e.g., primal optimization proxies that produce candidate primal solutions.\nThe dual proxies trained with DLL then provide valid dual bounds to certify the quality (i.e. optimality) of primal solutions.\n\nAccurate dual solutions can also be used to speedup primal algorithms, e.g., by identifying inactive constraints (whose associated dual variable will be zero), which can be safely removed from the problem.\n\nThere are also cases where dual solutions are valuable in their own right.\nThis is the case for instance instance in market-clearing applications, where primal variables are cleared quantities, and dual variables are prices. In that context, DLL can offer higher accuracy and guarantees of dual feasibility.\n\n## Scalability\n\nThe scalability of our proposed framework leverages several key ingredients:\n* Efficient conic projection layers: DLL does not require any external solver, nor the resolution of NP-hard problems (when considering the standard cones presented in the paper). We also introduce non-Euclidean conic projection with better complexity. For instance, for the PSD cone, the Euclidean projection has complexity $O(n^{3})$, compared to $O(n^{2})$ for the proposed radial projection.\n* Closed-form dual conic completion: we showcase several efficient dual completion layers for broad classes of problems (See Examples 1--3 and numerical experiments)\n* Self-supervised learning: this removes the need for offline data-generation using standard optimization solvers. This greatly accelerates training, and we have found this approach to often yield improved performance compared to supervised learning settings.\n\nFinally, DLL-based proxies are expected to offer similar computational burden and benefits as primal optimization proxies, which have been shown in various works to be scalable for large-scale real-life problems.", "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": "", "extra_scores": {}}]

Author rebuttal:
# General rebuttal

We express our gratitude to the area chairs and reviewers for their careful reading of our manuscript, their appreciation of our work, and their valuable feedback. In this general rebuttal, we comment on the applicability of the proposed framework to mixed-integer and non-convex problems.

We would also like to report that the paper's main author was sick with Covid during the past week, and was therefore unable to run additional experiments for this rebuttal. We nevertheless discuss, in individual rebuttals, what such experiments would have looked like and what results we would have expected. We hope to include them in the final version of the paper.

## How DLL can be used for discrete / non-convex problems

First, we would like to point out that convex optimization is the workhorse that underlies virtually all global optimization methods for discrete and non-convex problems. This includes, for instance, branch-and-cut algorithms for MIL(N)P, Outer-Approximation algorithms for convex MINLP, and spatial branch-and-bound for non-convex continuous optimization. Namely, **all these algorithms employ convex relaxations to obtain valid dual bounds and eventually prove optimality**.

Hence, by establishing the theoretical fundamentals of a principled learning framework for (convex) conic optimization, this paper marks a first step towards hybrid frameworks for non-convex optimization, wherein learning-based methods are used to solve (or accelerate the solution of) convex relaxations.

## Relation between DLL and Lagrangian decomposition for MIP

More generally, it is important to note that Lagrangian duality is a fundamental principle in constrained optimization, which is applicable to convex, discrete and non-convex problems alike.
Formally, consider a problem $\min_{x} \lbrace c^{\top}x | A x \geq b, x \in X \rbrace$ and the Lagrangian relaxation $L(y) = \min_{x} \lbrace c^{\top}x + y^{\top}(b - Ax) | x \in X \rbrace$. It is always the case that
* $L$ is concave w.r.t $y$, even if $X$ is non-convex or discrete, 
* $L(y)$ is a valid dual (lower) bound,
* if $x$ is an optimal solution of the Lagrangian subproblem, then $b - Ax$ is a subgradient of $L$ at $y$.

In our paper, $X$ is described by conic constraints. In Lagrangian decomposition for MIP problems (LD-MIP), e.g., [this paper](https://openreview.net/forum?id=aZnZOqUOHq), $X$ is a discrete set.
The two approaches then differ as follows:

1. Existing work on LD-MIP only considers the dualization of linear constraints of the form $Ax \geq b$, which yields a simple dual set $y \geq 0$. In contrast, we consider general conic constraints $Ax \succeq_{K} b$, with associated multipler $y \in K^{\*}$. **Extending LD-MIP to support general conic constraints would require the conic projection layers proposed in our paper** to ensure $y \in K^{*}$.

2. **Obtaining a _valid_ Lagrangian bound in LD-MIP requires solving typically NP-hard discrete problems** and requires an external solver. In contrast, in the conic setting, dual bounds are typically obtained via efficient (i.e. polynomial$^{\dagger}$) formulae.

    This is thanks to the elegant conic duality theory, whereby the dual of a conic problem is a conic problem. On the other hand, there is no tractable duality theory for non-convex or discrete problems.

Therefore, DLL and LD-MIP both leverage Lagrangian duality in a learning context.
**DLL introduces key ingredients that support the dualization of nonlinear conic constraints**, compared to linear constraints in existing works on LD-MIP.
In addition, its extension to the non-convex or discrete setting is straightforward.
The key computational difference is that, in the non-convex / discrete settings, computing a valid Lagrangian bound requires solving typically NP-hard non-convex / discrete problem.
In contrast, **DLL offers scalable, polynomial-time formulae$^{\dagger}$.**

___

$^{\dagger}$ The polynomial-time result applies to all standard cones considered in the paper. However, some classes of conic programs, e.g. copositive programming, are NP-hard to solve.

Meta-review: This paper leverages conic duality to learn to predict dual-feasible solutions and therefore valid Lagrangian dual bounds, for linear and nonlinear conic optimization problems. The paper is well-written and technically sound. Experiments showed that it compares favorably to baselines such as Mosek and DC3.
Decision: Accept (poster)