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