Optimisation algorithms typically assume oracle access to objectives and constraints, yet in many applications these functions are available only through data. To recover them, a common approach learns a surrogate for each function and optimises over it, but this can be unnecessarily expensive and may fail to preserve the structure required by the optimisation algorithm. We study this problem for monotone optimisation, a class of non-convex problems which can be solved globally using the Polyblock Outer Approximation (POA) algorithm. Our key observation is that POA does not require the constraint functions themselves, but only a scalar quantity we call the radial inverse. Learning this quantity directly replaces POA's inner bisection loop over a learned constraint with a single radial inverse evaluation. We characterise exactly which maps arise as radial inverses of monotone constraints, and relate their approximation error to perturbations of the feasible set and optimal objective value. Building on these results, we introduce Homogeneous-Monotone Radial Inverse (HM-RI) networks, structured min-max models that enforce the monotonicity and positive-homogeneity of radial inverses by construction. Across synthetic monotone optimisation problems and a cellular transmit-power application, HM-RI improves solution quality over direct constraint surrogates and local optimisation baselines by up to 58.6 percentage points relative to the Oracle reference objective, while achieving a 3.0-4.7x speed-up over bisection-based POA with learned constraint surrogates, with the largest solution-quality gains occurring in data-limited and piecewise-constant settings.
Figures & tables
Figure 1: Illustration of the construction of V0={b} , V1={V11,V21} , and V2={V12,V22,V32} of POA in 2D with mh=0 , i.e., H=R+2 . Points are colour-coded by iteration. Vertices are indexed by subscripts.
Figure 2: Objective as a percentage of the Oracle ’s, for each method and problem at n=4 . Each method is shown at both data regimes, connected by a bar, so that both the level attained and its sensitivity to training-data size are visible. Horizontal ticks are errors over three training seeds.
Figure 3: Objective at the returned point (as a percentage of the Oracle ’s) against its total constraint violation, per method and problem family at n=4 in the limited-data regime. The four radial-inverse variants are shown in colour while the remaining methods (M-Net and the two local solvers) share a single grey and are distinguished by marker shape. The grey regions are those dominated by some method at both metrics. Runtimes are in Table 2 .
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
Type
Method
P-Obj. (% of Oracle)
Power
Monotone
HM-RI
75.4 ± 0.8
2.75
M-RI
79.2 ± 0.5
2.53
H-RI
74.9 ± 0.5
2.77
RI
74.0 ± 1.9
2.82
M-Net
41.0 ± 3.0
4.69
Local
SLSQP
39.8 ± 0.8
4.75
Appendix
Table 1: Transmit power optimisation ( n=7 cells, Limited data regime, 50 instances, three seeds). P-Obj. is the projected objective as a percentage of the Oracle ’s; Power is the corresponding total transmit power ∑ipi (lower is better), for which the Oracle attains 1.35 . Random is a uniformly random point, included as a reference baseline; both local solvers and the direct surrogate score below it.
Type
Method
Quadratic
Multiplicative
Monotone nets
Step
POA
HM-RI
0.20
0.41
0.38
0.15
M-RI
0.20
0.25
0.35
0.15
H-RI
0.16
0.09
0.05
0.08
RI
0.07
0.07
0.08
0.07
M-Net
0.81
1.30
1.12
0.68
Local
SLSQP
0.03
0.02
0.05
0.36
Appendix
Table 2: Mean wall-clock time per solve, in seconds, for each method and problem family at n=4 in the limited-data regime, averaged over the 50 shared instances and three training seeds.
σ
HM-RI
M-RI
H-RI
RI
0
72.6± 0.5
68.2± 0.8
61.1± 1.5
65.2± 1.2
0.05
72.8± 0.6
68.2± 0.8
60.4± 1.3
61.1± 1.1
0.1
72.9± 0.6
67.1± 0.6
59.7± 1.1
61.1± 1.2
0.2
71.7± 0.6
64.0± 0.4
58.4± 1.5
60.7± 1.2
0.4
68.2± 0.5
53.8± 0.7
57.0± 1.1
59.1± 0.9
0.8
56.3± 0.9
36.7± 0.6
54.6± 1.3
53.5± 1.1
Appendix
Table 3: Projected objective as a percentage of Oracle ’s under noisy training data, multiplicative problems at n=4 with 512 samples. σ is the standard deviation of the log-normal multiplicative noise. The lost row is the drop from the noiseless model to σ=0.8 , in points of oracle objective. Readings are means over ten training seeds with standard errors. The Random reference for this setting is 21.7% .
Family
N
M-RI
H-RI
RI
M-Net
SLSQP
COBYLA
Quadratic
512
+0.5
+6.1 ∗
+18.5 ∗
+23.3 ∗
+24.0 ∗
+23.9 ∗
8192
−0.3
+1.2 ∗
+0.7
+23.4 ∗
+23.3 ∗
+23.4 ∗
Multiplicative
512
+6.5 ∗
+9.7 ∗
+11.2 ∗
+13.6 ∗
+14.1 ∗
+13.9 ∗
8192
+9.8 ∗
−4.1 ∗
−0.1
+16.4 ∗
+16.8 ∗
+16.9 ∗
Monotone nets
512
−0.7
+8.9 ∗
+1.2
+0.3
+2.3
+1.9
8192
+10.8 ∗
+9.0 ∗
+9.2 ∗
+2.1
+2.3
+3.4
Appendix
Table 4: HM-RI minus each method, paired over the 50 shared instances after averaging across training seeds, in percentage points relative to the oracle objective. Entries marked ∗ have a 95% bootstrap confidence interval which excludes zero.
Family
Method
MSE
Recon. err.
x -viol.
y -viol.
Hom. err.
Quadratic
HM-RI
0.0016
0.030
0
0
2⋅10−7
M-RI
0.0018
0.030
0
0
2⋅10−1
H-RI
0.0020
0.037
2⋅10−6
0
1⋅10−7
RI
0.0019
0.030
4⋅10−6
0
2⋅10−1
Multiplicative
HM-RI
0.0113
0.120
0
0
2⋅10−7
M-RI
0.0122
0.121
0
0
8⋅10−1
Appendix
Table 5: Structural-property ablations at n=4 , averaged over three training repetitions. Unlike Figure 2 , these models are trained on freshly drawn samples rather than a finite buffer, since the question here is what each property costs and guarantees rather than sample efficiency. Violation columns measure the property that the corresponding variant drops; enforced properties hold exactly, up to floating-point precision. Note that monotonicity is very nearly satisfied even by the variants that do not enforce it, whereas homogeneity is not: see the discussion below.
P-Obj. (% of Oracle )
Solve time (s)
Method
n=4
n=5
n=6
n=7
n=4
n=5
n=6
n=7
HM-RI
96.4± 0.6
96.5± 0.5
91.7± 0.9
85.5± 0.9
0.19
0.35
0.52
2.07
M-RI
96.3± 0.5
95.9± 0.5
90.7± 0.9
86.3± 0.9
0.20
0.36
0.54
2.25
H-RI
95.4± 0.6
94.4± 0.6
89.4± 0.9
84.3± 1.0
0.18
0.34
0.52
2.43
RI
95.4± 0.5
94.7± 0.6
86.6± 0.9
82.9± 1.1
0.18
0.33
0.50
2.24
M-Net
71.9± 2.9
70.4± 2.9
62.6± 2.9
63.3± 2.5
0.81
1.29
1.54
4.88
Appendix
Table 6: Solution quality and cost against problem dimension, quadratic family, large-data regime (50 instances per dimension, three training seeds). P-Obj. is the projected objective as a percentage of the Oracle ’s, scored per instance and then averaged; uncertainties are standard errors over instances, which dominate those over seeds several-fold. Solve times are means over instances and seeds. Random solves nothing, so no time is reported for it. The Oracle successfully solves all instances up to n=6 and all but six at n=7 , which were excluded from all comparisons.
Method
Quadratic
Multiplicative
Monotone nets
Step
512
8192
512
8192
512
8192
512
8192
HM-RI
0.0028
0.0013
0.0153
0.0110
0.0917
0.0385
0.0055
0.0036
M-RI
0.0029
0.0015
0.0166
0.0129
0.0925
0.0217
0.0051
0.0034
H-RI
0.0096
0.0021
0.0495
0.0101
0.0737
0.0363
0.0315
0.0041
RI
0.0350
0.0024
0.0399
0.0087
0.0647
0.0223
0.0279
0.0037
Appendix
Table 7: Held-out test loss (mean squared error of the scale regression) for radial-inverse variants under both data regimes, at n=4 , measured on freshly drawn samples rather than the finite training buffer. Lowest loss per column in bold.
This paper presents a novel learning-based approach to construct a surrogate problem that approximates a given parametric nonconvex optimization problem. The surrogate function is designed to be the minimum of a finite set of functions, given by the composition of convex and monotonic terms, so that the surrogate problem can be solved directly through parallel convex optimization. As a proof of concept, numerical experiments on a nonconvex path tracking problem confirm the approximation quality of the proposed method.
Renzi Wang, Panagiotis Patrinos, Alberto Bemporad
IMT School for Advanced Studies, Lucca, Italy. · Department of Electrical Engineering ESAT-STADIUS, KU Leuven, Leuven, Belgium.
Constrained end-to-end learning trains neural networks whose outputs must satisfy feasibility constraints, such as resource, budget, or operational limits. While projection and optimization layers guarantee constraint satisfaction, boundary-based projections can introduce unfavorable optimization geometry: regions of the unconstrained output space are mapped to the same active face of the feasible set. This makes the resulting map locally rank-deficient, suppressing gradients in constrained directions and potentially impairing optimization - a bottleneck known as gradient saturation. We propose Soft-Radial Projection (SRP), a differentiable reparameterization layer that maps unconstrained network outputs into the relative interior of a convex feasible set by smoothly rescaling rays from a strictly feasible anchor point. Unlike hard radial or orthogonal projections, the resulting map is one-to-one and has a full-rank Jacobian almost everywhere, while guaranteeing strict feasibility. We prove that constrained networks equipped with SRP retain universal approximation guarantees. For polytopes and balls, the layer admits a closed-form forward pass, while for general convex sets, the ray-boundary intersection reduces to a one-dimensional search. Experiments on decision-focused learning benchmarks demonstrate strong solution quality at low computational cost, with particularly favorable results in portfolio optimization and substantially lower inference latency than differentiable optimization layers in the evaluated settings.
Surrogates provide a cheap solution evaluation and offer significant leverage for optimizing computationally expensive problems. Usually, surrogates only approximate the original function. Recently, the perfect linear surrogates were proposed that ideally represent the original function. These surrogates do not mimic the original function. In fact, they are another (correct) representation of it and enable a wide range of possibilities, e.g., discovering the optimized function for problems where the direct transformation of the encoded solution into its evaluation is not available. However, many real-world problems can not be represented by linear models, making the aforementioned surrogates inapplicable. Therefore, we propose the Limited Monotonical Perfect Surrogate (LyMPuS), which overcomes this difficulty and enables the comparison of two solutions that differ by a single variable. Our proposition is suitable for limiting the cost of expensive local search procedures. The proposed surrogate is parameterless and can be trained on the fly without any separate surrogate-building step. It uses only the necessary fitness evaluations, and the already-paid costs are not wasted when the model is updated. Finally, it offers low-cost missing-linkage detection and low-cost linkage discovery, guaranteed to find a missing dependency in no more than 2⌈log2(n)⌉ steps.
M. W. Przewozniczek, F. Chicano, R. Tinós +1
Wroclaw Univ. of Science and Techn. Wroclaw, Poland · ITIS Software, University of Málaga Málaga, Spain · University of São Paulo Ribeirão Preto, Brazil