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
A stochastic proximal-gradient method is proposed and analyzed for solving regularized optimization problems subject to nonlinear equality constraints and nonnegativity bounds. The objective function’s values and gradients are available only through inexact stochastic oracles. The method decomposes each trial step into one component that reduces linearized infeasibility and a second component that seeks optimality while … Read more
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
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
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
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
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
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
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
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