CS Paper Radar

Input convex neural networks as surrogates in mathematical optimisation

Yu Liu, Jan Kronqvist, Fabricio Oliveira

cs.LG math.OC ·submitted 2026-08-10 15:11 UTC · v1

Abstract

Embedding trained neural networks as surrogates within optimisation problems is an established practice in operations research. The prevailing approach uses feedforward neural networks (FNNs) with ReLU activations, whose piecewise-linear structure admits an exact but computationally intensive mixed-integer programming (MIP) reformulation as the networks grow. We advocate input convex neural networks (ICNNs) as structurally superior surrogates when the underlying response is approximately convex or concave. The convex architecture offers two computational advantages. First, the ICNN-MIP formulation tends to yield a tighter linear programming (LP) relaxation than its FNN-MIP counterpart, with no integrality gap in favourable instances. Second, ICNNs uniquely admit an LP-based reformulation via epigraph representations of ReLU activations, though this embedding is not always exact. When it is not, we exploit the properties of ICNNs to construct the strongest continuous relaxation over box domains, namely, the convex hull of the ICNN's graph, bounded below by the epigraph and above by the concave envelope; this construction is tractable under input convexity but hard for general ReLU networks. On this basis, we develop a branch-and-bound algorithm that builds this relaxation at each node, branches directly on input variables rather than intermediate variables as in MIP reformulations, and terminates at the root node whenever the epigraph embedding is valid. Case studies on humanitarian food aid, oil well routing, and wine blending show that ICNN surrogates match FNN accuracy and deliver gains in solve time and scalability, supporting ICNN as the default surrogate when the underlying function is convex, concave, or well-approximated as such.

Closest papers

Nearest neighbours by meaning across the whole index.

DCEmbed: Scalable Optimization over Neural Surrogates

cs.LG math.OC ·2026-09-27 ·Akshay Sreekumar, Nicolas Christianson, Priya L. Donti, Ellen Vitercik, Ram Rajagopal
similarity 0.77
Abstract

Neural surrogates can accelerate large-scale optimization by replacing expensive or intractable model components with efficient learned approximations, but solving the resulting embedded problems can remain prohibitively costly. For instance, standard exact encodings of neural networks with ReLU activations allow the problem to be solved by mixed-integer solvers, but add large numbers of binary variables to accommodate the nonlinearity of the activations, which can render the problem computationally prohibitive. To address this, we propose DCEmbed, a heuristic for optimization problems with embedded neural surrogates that leverages the difference-of-convex (DC) representation of the network and avoids adding activation binaries. Exploiting shared structure within the DC representation of a ReLU network, we derive a reduced-size, exact formulation for its convex components that can be embedded in optimization problems using just two linear inequalities and one continuous auxiliary variable per hidden neuron. Using this, the problem is solved via an iterative penalty convex-concave procedure, where only the concave portions of the neural terms are approximated at each stage. The original objective, constraints, and any discrete decisions are retained, allowing standard convex or mixed-integer optimization solvers to optimize the host and surrogate jointly at each iteration. In experiments on quadratic programs, mixed-integer resource allocation, and neural two-stage stochastic programming, our method demonstrates much faster progress toward high-quality feasible solutions than approaches using exact mixed-integer embeddings. In particular, DCEmbed achieves $4\times$ lower normalized primal integral than the best exact baseline on the resource allocation problem, while in two-stage stochastic programming it reaches the global surrogate optimum $\sim 5\times$ faster than Gurobi ML.

0.06

Structure-Preserving Neural Approximation of Convex, Semiconvex, and Quasiconvex Functions

cs.LG math.OC ·2026-11-18 ·Yeachan Park, Yeoneung Kim
similarity 0.71
Abstract

Input convex neural networks provide a natural way to enforce convexity globally through architectural constraints. We study how this structure-preserving approximation framework extends to semiconvex, quasiconvex, and convex transformable functions. For $C^{1,1}$ convex functions on compact convex domains, we establish the sharp $W^{1,p}$ minimax rate $m^{-1/d}$ under max-affine approximation with $m$ affine pieces, and show that every max-affine function admits an exact bounded-width ICNN representation with complexity linear in $m$. The same $W^{1,p}$ approximation rate extends to semiconvex functions through quadratic lifting and to convex transformable functions through monotone composition. For general Lipschitz quasiconvex functions, we develop a quantitative finite-probe approximation theory based on monotone responses to affine projections and obtain a structure-preserving IqCNN with an $L^\infty$ approximation guarantee. We further show that these approximation results extend to ReLU-transferable smooth activations, including Softplus and ELU. Numerical experiments on PDE-based approximation problems compare the proposed architectures with parameter-matched MLPs and validation-tuned shape penalties, demonstrating global structural validity without penalty tuning while maintaining competitive approximation accuracy. Overall, the results identify recoverable convex latent structure as the key mechanism enabling gradient-level structure-preserving approximation beyond convexity.

0.29

Certified Robustness via Sparse Second-Order Cone Relaxations

cs.LG ·2026-10-12 ·Mohammadreza Maleki, Daniel Sadig, Rushendra Sidibomma, Mahyar Fazlyab, Arman Adibi +1 more
benchmark similarity 0.69
Abstract

Certified robustness is critical for deploying neural networks in safety-sensitive settings, but computing exact certificates typically requires solving nonconvex optimization problems. Practical verifiers use convex relaxations: linear programming (LP) relaxations are scalable but often too conservative, whereas semidefinite programming (SDP) relaxations can be substantially tighter but are computationally expensive. We introduce a hierarchy of second-order cone programming (SOCP) relaxations that provide stronger certificates than LP while avoiding the cost of global positive-semidefinite constraints. Our construction combines convex-hull relaxations of ReLU activations, selective McCormick lifting over certified variable bounds, and second-order cone constraints induced by 2-by-2 principal minors. Adding these constraints progressively yields a monotone hierarchy of increasingly tight bounds with a controllable computation-tightness trade-off. On fully connected and convolutional networks on MNIST and CIFAR-10, SOCP-based verification improves certified robust accuracy over LP-based verification and is competitive with alpha,beta-CROWN, while remaining orders of magnitude faster than SDP-based verification. These results position selective second-order constraints as a practical middle ground between scalable LP-based and tight SDP-based certification. Finally, we introduce class-optimized robust evaluation (CORE), which applies tighter relaxations only to target classes not certified by cheaper ones. On the fully connected MNIST benchmark, CORE variants match SDP-cert's certified robust accuracy while reducing average verification time by up to 86.30%.

0.11

Universal neural network approximation of symmetric polyconvex energies and envelopes

cs.CE math.NAcs.LG ·2026-10-23 ·Florian Gammer
theory similarity 0.69
Abstract

Symmetric polyconvexity provides a sufficient condition for weak lower semicontinuity in small-strain elasticity and a tractable lower bound for the relaxation of non-(quasi)convex energies. Since classical algorithms for computing such functions can be computationally expensive, neural network approximations have recently emerged as an alternative. A central difficulty with establishing such neural network based approaches for symmetric polyconvexity is the additional monotonicity property. As we show, the corresponding weight restrictions on ReLU-based input-convex networks do not yield universal approximation of the lifted representers. Here, we introduce symmetric polyconvex neural networks (SPCNNs) for constitutive modeling and approximation of symmetric polyconvex envelopes. The deep architecture combines convexity with the monotonicity required of a representer in the space of minors. We prove a universal approximation theorem for symmetric polyconvex energies, without requiring isotropy, and quantify the number of affine pieces attainable by the lifted network and derive reduced architectures for isotropic energies. Numerical examples illustrate stress-based regression and approximation of the symmetric polyconvex envelope of a double-well potential. Symmetric polyconvexity is guaranteed by construction, while the accuracy of the fitted energies and envelopes is assessed numerically.

0.21

Taming Nonconvexity with Epigraph Lifting

cs.LG math.OC ·2026-10-12 ·Clara Lage, Hok Shing Wong, Matthias Ehrhardt
similarity 0.66
Abstract

We consider inverse problems regularized by a trained neural network with \emph{convex activations} and \emph{unrestricted weights}. The resulting optimization problem is generally nonconvex, and gradient-based methods may converge to poor local minima. We introduce a \emph{penalized epigraph lifting} of the network and show that the lifted problem admits a \emph{difference-of-convex (DC) decomposition}. For Lipschitz continuous activations, we establish \emph{finite exactness}: the original objective is recovered exactly at a finite and explicitly computable penalty threshold $\barρ$. Building on this structure, we propose \emph{H-DC} (Homotopic DC), a homotopic scheme that solves a sequence of DC subproblems with increasing $ρ$, warm-starting each level from the previous solution. Numerical experiments on synthetic problems, a manifold denoiser regularizer, and image inpainting with a learned Mumford--Shah regularizer show that H-DC consistently escapes poor local minima and reaches solutions with lower objective values than gradient-based methods from the same initialization.

0.14

Mathematical Programming in Machine Learning and Artificial Intelligence: A Unified Taxonomy of Models and Applications

cs.AI math.OC ·2026-09-07 ·Chaosheng Dong
similarity 0.66
Abstract

Mathematical programming provides a common language for many decisions embedded in modern machine-learning (ML) and artificial-intelligence (AI) systems: selecting retrieval context, routing tokens, allocating inference compute, fitting structured predictors, protecting against distribution shift, and balancing competing objectives. However, the relevant literature is fragmented across optimization, information retrieval, recommendation, natural-language processing, computer vision, and learning theory. This paper organizes various applications under common mathematical programming paradigms: linear, quadratic, binary and mixed-integer, conic, bilevel, multi-objective, inverse, distributionally robust, submodular, and min--max optimization. We normalize the models with a mostly unified notation and, for every application, identify inputs, decision variables, a principal formulation, structural properties, solution strategies, and limitations. Across paradigms, we compare tractability, relaxation quality, decomposition, approximation guarantees, and scalability bottlenecks. The paper shows that mathematical programming is most useful not as a claim that all learning is LP or MIP, but as a disciplined interface between predictions and constrained decisions.

0.12

Reformulation-Contrastive Learning for Mixed Integer Programs

cs.LG ·2026-09-30 ·Ousema Bouaneni, Mathis Le Bail, Clément Elliker, Maël Jenny, Sonia Vanier
similarity 0.65
Abstract

Mixed-integer linear programs (MILP) model many real-world decision problems, motivating machine-learning methods that exploit recurring structure to accelerate MILP solving. MILPs can admit many equivalent formulations: integrality-preserving changes of variables and the addition of redundant constraints can alter their formulations while preserving the optimization problem. We leverage these reformulations as a source of self-supervision for learning general-purpose representations of MILP variables and constraints. We characterize the affine reformulations that are valid for every input instance, and distinguish re-descriptions, which leave variables unchanged, from substitutions, which transform them predictably. Building on equivariant self-supervised learning, we introduce ReMILP (reformulation-contrastive MILP representation learning), which jointly trains a graph neural network and a hypernetwork to predict how variable embeddings transform under changes of variables. Without solver-derived labels, ReMILP learns representations that exhibit the intended invariance and equivariance on unseen problem classes. Across binary solution, constraint activity and integrality gap prediction, these representations carry task-relevant information when frozen and provide a useful initialization for fine-tuning.

0.25

Learning to Solve Mixed-Integer Nonlinear Programming with Neural Networks and Sequential Quadratic Programming Refinement

eess.SY math.OC ·2026-10-05 ·Viet-Anh Le, Rahul Mangharam
similarity 0.65
Abstract · 8 pages, submitted to ACC 2027

We propose a learning-to-optimize framework for solving parametric mixed-integer nonlinear programs arising in model predictive control and trajectory optimization. The proposed method combines neural network prediction with a sequential quadratic programming (SQP) refinement layer. First, neural networks are trained using a combination of supervised and self-supervised losses to predict integer solutions together with compatible continuous warm starts. To account for prediction inaccuracies, the trained predictor generates multiple candidate integer solutions, each paired with a continuous initialization. The integer solutions are then fixed, and a differentiable SQP layer refines the associated continuous variables over a prescribed number of iterations. The SQP-layer parameters, including the curvature regularization and step size, are trained to improve both feasibility and objective value after every iteration. By separating integer prediction from continuous optimization-based refinement, the proposed framework improves robustness to imperfect neural predictions while maintaining a predictable computational budget. We demonstrate the proposed framework on contact and trajectory optimization for a planar box-pushing example.

0.20