Constraint Learning by Optimizing over Trained Neural Networks: A Pragmatic Tutorial

Constraint learning is an emerging paradigm of modeling optimization problems with the help of machine learning. In this paradigm, trained machine learning models are embedded into the optimization model. For example, we can learn constraints empirically from available data, or we can avoid using a nonlinear objective function by learning a simpler approximation for it. … Read more

Mixed-Integer Linear Reformulations of Pessimistic Bilinear Bilevel Infima

We study pessimistic bilevel optimization with bilinear objectives and linear constraints. Assuming a compact polyhedral leader domain, nonempty follower solution sets, and a finite pessimistic infimum, we derive mixed-integer linear optimization formulations that attain this infimum, even when the original problem has no optimal solution. This setting has applications such as pricing, security, and decision-focused … Read more

On Modified Newton Methods for Unconstrained Optimization Based on Lanczos Tridiagonalization

For a strongly convex unconstrained minimization problem, Newton’s method with a line search offers rapid convergence to a minimizer by incorporating second-order infor- mation. However, for a general unconstrained problem the Hessian need not be positive definite, which can lead to the inability to find a search direction or to search directions that fail to … Read more

A particle swarm optimization with a reduced-subspace trust-region safeguard for contact-rich controller tuning

Contact-rich robotic insertion is challenging because uncertainty in alignment, friction, and contact conditions can lead to unsuccessful assembly, excessive contact forces,  and jamming. Designing a reliable controller therefore requires balancing insertion performance, robustness, and recovery from unexpected contact. In this paper, we propose PSO+TR, a derivative-free optimization (DFO) method that combines the exploratory search of … Read more

From Mixing to Tearing: Graph Decomposition in Decentralized Optimization via Message Passing

We study decentralized minimization of sums of smooth strongly convex functions, one per agent, with communication restricted to neighbors in a graph. Existing decentralized algorithms typically emulate a {\it centralized} method; {\it the network serves only to exchange information}, from which agents approximate the global quantities that the method needs. This paper breaks with this … Read more

Distributional Lifting for Discrete Optimization

We introduce a framework that transforms discrete optimization into continuous optimization over parameterized probability distributions. The framework reveals a common distributional structure behind several methods that have largely developed independently, including continuous reformulations for multilinear binary optimization, Markov decision processes and reinforcement learning, the cross-entropy method, mean-field variational optimization, and the quantum approximate optimization algorithm. … Read more

Box-Cone Representations of Bound-Factor RLT Constraints in Semidefinite Relaxations

Linear inequalities can generate large constraint systems in semidefinite relaxations of binary quadratic programs, making the quadratic subproblems of splitting methods expensive to solve. We develop a box-cone representation of bound-factor reformulation-linearization technique (RLT) constraints in semidefinite relaxations of binary quadratic programs. These constraints arise by multiplying each original linear inequality by every binary variable … Read more

Risk-Constrained MPPI Tuning with Update-Aware MA-ES Racing

We formulate offline tuning of Model Predictive Path Integral (MPPI) controllers as a chance-constrained black-box optimization problem and develop an update-aware framework based on Matrix Adaptation Evolution Strategy (MA-ES). We use statistical information from noisy controller evaluations to determine when the evolutionary update is sufficiently reliable. When the recombination direction is certified, a derivative-free nonmonotone … Read more

Breaking the Odd Cycle: Regularization and First-Order Optimization for the Maximum s-Plex Problem

Building on a new regularized continuous formulation which avoids spurious solutions of the maximum s-plex problem, we develop a tailored block-coordinate first-order method that combines away-step Frank-Wolfe updates on the standard simplex with linear optimization over the fractional b-matching polytope. We establish finite stabilization of the auxiliary variables, convergence to stationary points, and finite support … Read more

Linearizable Instances of the Quadratic Minimum Spanning Tree Problem on 3-Connected Graphs

An instance of the quadratic minimum spanning tree problem (QMSTP) is called linearizable if it can be rewritten as an instance of the linear minimum spanning tree problem in such a way that the objective function value is preserved at all feasible solutions. Previous work has shown that a sufficient condition for linearizability is that … Read more