Other Topics – Optimization Online

Probabilistically Exact Convexification of Mixed-Integer Quadratic Optimization with Indicators

Published: 2026/11/11

We study the convexification of mixed-integer quadratic optimization with indicator variables. The problem remains NP-hard even when the quadratic matrix has bandwidth two, posing a fundamental obstacle to tractable exact convexification. To overcome this challenge in realistic settings, we introduce probabilistically exact (inner) convexification, a framework that relaxes the requirement of exactness for every objective … Read more

Exact Equilibrium Analysis of Sparse Network Games in Subexponential Time

Published: 2026/11/07

Zeyang (Patton) Wang

Bilevel Optimization, Combinatorial Optimization, Game Theory capacity procurement, counting complexity, exponential time hypothesis, graphical games, price of anarchy, pure nash equilibrium, stackelberg games

In October 2026 two independent groups claimed deterministic algorithms that count the satisfying assignments of a k-CNF formula in time 2^{o(n)}, refuting the Exponential Time Hypothesis (ETH). We ask what these claims imply for the exact analysis of equilibria in games where each player interacts with a bounded number of others. Conditional on the claimed … Read more

String-averaging bargaining in solidarity cooperative games

Published: 2026/11/02

Applications - OR and Management Sciences, Convex Optimization, Game Theory Consortium of coalitions, cooperative game, core, Solidarity set., String-averaging algorithm

We consider the situation that the grand set of all players, in a cooperative game in characteristic function form with a nonempty core, consists of recognizable subsets of players. The underlying assumption is that the players of each subset have something in common between themselves which is not shared by the players of other subsets. … Read more

A Novel Dynamic Program and Relaxations: Dual Bounds for the Capacitated Vehicle Routing Problem

Published: 2026/10/29

Anthony Karahalios

Dynamic Programming, Integer Programming, Transportation arc flow formulation, dynamic programming, vehicle routing

State-of-the-art exact methods for solving vehicle routing problems rely on a dynamic program that enumerates the set of feasible routes and their distances. Using relaxations of the dynamic program improves these exact methods. This work is motivated by two observations. First, the dynamic program enumerates some routes with a suboptimal permutation of the locations. Second, … Read more

On the BFGS Method for Unconstrained Optimization

Published: 2026/10/26

Other Topics, Unconstrained Optimization bfgs method, line search methods, quasi-newton methods, self-scaled quasi-Newton methods, unconstrained optimization, updating matrix factorizations

Quasi-Newton methods form the basis of many effective methods for unconstrained and constrained optimization. As the iterations proceed, a quasi-Newton method incorporates new curvature information by performing a low-rank update to a matrix that serves as an approximation to a Hessian matrix of second derivatives. In the years following the publication of the Davidon-Fletcher-Powell (DFP) … Read more

On Modified Newton Methods for Unconstrained Optimization Based on Lanczos Tridiagonalization

Published: 2026/10/23

Nonlinear Optimization, Other Topics

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

Published: 2026/10/23

Bound-constrained Optimization, Control Applications, Optimization of Simulated Systems adaptive subspace technique, contact-rich robotic assembly, controller tuning, derivative-free optimization, derivative-free policy optimization, particle swarm optimization, trust-region methods

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

solving the multi-objective integer minimum cost flow problem via circulations

Published: 2026/10/18

Antonio Sedeño-Noda

Combinatorial Optimization, Multi-Criteria Optimization, Network Optimization Circulations, Multi-objective Integer Minimum Cost Flow, network optimization

The Multi-objective Integer Minimum Cost Flow Problem (MOIMCF) asks for the efficient integer flows of a capacitated network whose arcs carry vectors of conflicting costs. We present an exact algorithm that computes a minimal complete set of efficient flows, based on a characterization of efficiency by circulations in the residual network. The feasible set is … Read more

Are Single-Leader-Multi-Follower Problems Particular Cases of Bilevel Optimization?

Published: 2026/10/13, Updated: 2026/10/14

Bilevel Optimization, Game Theory, Global Optimization bilevel optimization, Complexity theory, Optimistic vs. pessimistic, Single-leader-multi-follower games

For more than 20 years, single-leader multi-follower (SLMF) problems have been treated as a more difficult class of problems in comparison to bilevel optimization. In this work we challenge this common belief, studying whether SLMF problems can be reformulated as equivalent bilevel optimization problems. We consider both optimistic and pessimistic formulations. For the optimistic case … Read more

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

Published: 2026/10/10

Constrained Nonlinear Optimization, Optimization of Simulated Systems, Optimization of Systems modeled by PDEs chance-constrained controller tuning, derivative-free line search, evolution strategy, finite-sample validation, Model Predictive Path Integral, rank uncertainty, statistical 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