A simple effective heuristic for embedded mixed-integer quadratic programming
From MaRDI portal
Publication:5207801
DOI10.1080/00207179.2017.1316016zbMATH Open1434.90117arXiv1509.08416OpenAlexW2606482332MaRDI QIDQ5207801FDOQ5207801
Authors: Reza Takapoui, Nicholas Moehle, Stephen Boyd, A. Bemporad 
Publication date: 13 January 2020
Published in: International Journal of Control (Search for Journal in Brave)
Abstract: In this paper we propose a fast optimization algorithm for approximately minimizing convex quadratic functions over the intersection of affine and separable constraints (i.e., the Cartesian product of possibly nonconvex real sets). This problem class contains many NP-hard problems such as mixed-integer quadratic programming. Our heuristic is based on a variation of the alternating direction method of multipliers (ADMM), an algorithm for solving convex optimization problems. We discuss the favorable computational aspects of our algorithm, which allow it to run quickly even on very modest computational platforms such as embedded processors. We give several examples for which an approximate solution should be found very quickly, such as management of a hybrid-electric vehicle drivetrain and control of switched-mode power converters. Our numerical experiments suggest that our method is very effective in finding a feasible point with small objective value; indeed, we find that in many cases, it finds the global solution.
Full work available at URL: https://arxiv.org/abs/1509.08416
Recommendations
- An approximation algorithm for indefinite mixed integer quadratic programming
- Compact mixed-integer programming formulations in quadratic optimization
- Improved algorithm for mixed-integer quadratic programs and a computational study
- Heuristics for convex mixed integer nonlinear programs
- A note on solving quadratic programs using mixed-integer programming
- On approximation algorithms for concave mixed-integer quadratic programming
- On approximation algorithms for concave mixed-integer quadratic programming
- A branch and bound algorithm for general mixed-integer quadratic programs based on quadratic convex relaxation
- scientific article; zbMATH DE number 3920195
- A dual heuristic for mixed integer programming
Quadratic programming (90C20) Approximation methods and heuristics in mathematical programming (90C59) Mixed integer programming (90C11)
Cites Work
- CVXGEN: a code generator for embedded convex optimization
- Numerical Optimization
- Title not available (Why is that?)
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- A dual algorithm for the solution of nonlinear variational problems via finite element approximation
- Optimal Parameter Selection for the Alternating Direction Method of Multipliers (ADMM): Quadratic Problems
- Title not available (Why is that?)
- qpOASES: a parametric active-set algorithm for~quadratic programming
- Reducibility among combinatorial problems
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Control of systems integrating logic, dynamics, and constraints
- Local linear convergence of the alternating direction method of multipliers on quadratic or linear programs
- An alternating direction algorithm for matrix completion with nonnegative factors
- Dual coordinate step methods for linear network flow problems
- A branch-and-cut method for 0-1 mixed convex programming
- A feasibility pump heuristic for general mixed-integer problems
- Improving the feasibility pump
- The feasibility pump
- Outline of an algorithm for integer solutions to linear programs
- Title not available (Why is that?)
- Consensus in Ad Hoc WSNs With Noisy Links—Part I: Distributed Estimation of Deterministic Signals
- On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
- On the facial structure of set packing polyhedra
- Title not available (Why is that?)
- Nonconvex Splitting for Regularized Low-Rank + Sparse Decomposition
- Computational study of a family of mixed-integer quadratic programming problems
- Condition numbers and equilibration of matrices
- Branch-and-Bound Methods: A Survey
- Introduction to nonlinear optimization: theory, algorithms, and applications with MATLAB
- A universal lattice code decoder for fading channels
- On cutting-plane proofs in combinatorial optimization
- Solving propositional satisfiability problems
- A Real-Time Iteration Scheme for Nonlinear Optimization in Optimal Feedback Control
- Global convergence of splitting methods for nonconvex composite optimization
- Alternating direction method of multipliers for real and complex polynomial optimization models
- Online Object Tracking With Sparse Prototypes
- Receding Horizon Control
- Consensus-ADMM for General Quadratically Constrained Quadratic Programming
- Parallel Algorithms for Constrained Tensor Factorization via Alternating Direction Method of Multipliers
Cited In (10)
- Penalty alternating direction methods for mixed-integer optimal control with combinatorial constraints
- Low-Complexity Method for Hybrid MPC with Local Guarantees
- A general system for heuristic minimization of convex functions over non-convex sets
- Exact augmented Lagrangian duality for mixed integer quadratic programming
- Training recurrent neural networks by sequential least squares and the alternating direction method of multipliers
- An ADMM based method for underdetermined box-constrained integer least squares problems
- Alternating direction method of multipliers for truss topology optimization with limited number of nodes: a cardinality-constrained second-order cone programming approach
- The voice of optimization
- Decomposition methods for global solution of mixed-integer linear programs
- Sparse loss-aware ternarization for neural networks
Uses Software
This page was built for publication: A simple effective heuristic for embedded mixed-integer quadratic programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5207801)
