Source-linked AI summary
A Simple Effective Heuristic for Embedded Mixed-Integer Quadratic Programming
Reza Takapoui, Nicholas Moehle, Stephen Boyd, Alberto Bemporad
TL;DR
The paper tackles convex quadratic optimization with affine and separable nonconvex constraints, a formulation that includes NP-hard problems. It develops an ADMM-based heuristic to obtain approximate solutions quickly, and experiments report fast solutions that often have small objective values or attain the global solution. The method remains without global-optimality or convergence guarantees and can fail to find feasibility.
Problem
Quadratic optimization over nonconvex separable constraints includes NP-hard problems, while embedded applications require feasible, low-objective solutions under limited computation and short time budgets.
Method
The paper extends ADMM into a computationally efficient heuristic that uses projections onto the Cartesian-product constraint set to seek approximate solutions.
Results
Numerical experiments suggest that the heuristic usually finds feasible points with reasonable objective values and often finds the global solution; examples include solutions in under 2 seconds versus more than 4 hours for MOSEK.
Takeaways & Limitations
The heuristic is useful for embedded optimization applications where a feasible point with a relatively small objective can provide performance practically indistinguishable from the global solution.
Takeaways & Limitations
For nonconvex constraints, the method has no guarantee of global optimality or convergence and may fail to find a feasible point even when one exists.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper addresses quadratic optimization over affine and separable, possibly nonconvex constraints, a class encompassing NP-hard problems. It proposes an ADMM-based heuristic for rapidly finding feasible, low-objective solutions in resource-constrained embedded applications.
- 1.1 The problem: The problem minimizes a convex quadratic objective subject to affine equality constraints and a Cartesian product of possibly nonconvex sets.This formulation includes convex and nonconvex variables through the individual sets X_i.
- 1.1 The problem: When the constraint set is nonconvex, the problem generalizes mixed-integer quadratic programming and can encode NP-complete problems.Global-solution methods therefore have non-polynomial worst-case time unless P = NP.
- 1.2 Solve techniques: Exact methods such as brute force, branch-and-bound, and branch-and-cut provide global solutions, but their runtime can vary substantially.Heuristics instead trade optimality guarantees for quick approximate or feasible solutions.
- 1.3 Embedded applications: Embedded applications require feasible solutions with relatively small objectives under limited computational resources and short time budgets.The paper targets settings where such solutions can perform practically indistinguishably from global solutions.
- 1.4 Contributions: The proposed computationally efficient heuristic is based on ADMM and is not guaranteed to find a global solution or converge.It is designed to find approximate solutions quickly for the nonconvex problem class.
- 1.4 Contributions: Numerical experiments suggest that the heuristic often finds feasible points with reasonable objective values and sometimes finds global solutions.Comparisons with commercial solvers indicate substantially faster solution of global optimization problems with competitive practical performance.
2 Our heuristic
The heuristic extends ADMM to nonconvex separable constraints by alternating a quadratic minimization, projection onto the constraint set, and dual update. It favors fast approximate solutions through cached linear algebra, parallel projections, preconditioning, and repeated random initializations.
- 2.1 Algorithm: The algorithm extends ADMM from convex constrained optimization to problems with possibly nonconvex Cartesian-product constraint sets.It is not guaranteed to find the global solution or even converge when the constraint set is nonconvex.
- 2.1 Algorithm: Each iteration minimizes a strongly convex quadratic, projects onto X, and performs a computationally inexpensive dual update.Projection onto X decomposes into independent projections onto Xi and can therefore be parallelized.
- 2.2 Convergence: For convex feasible X, the method is guaranteed to converge to an optimal point; for nonconvex X, it instead targets an approximate solution quickly.The paper explicitly trades accuracy guarantees for short solution time in the nonconvex setting.
- 2.3 Initialization: Randomly initialized repeated runs increase the chance of finding a feasible point with smaller objective value, so the best feasible point is reported.The initialization uses a random point in Co X and sets u0 = 0.
- 2.4 Computational cost: Precomputed LDLT factorization reduces each subsequent dense iteration to O(n^2) after an O(n^3) factorization cost.The factorization can be reused across instances when P and A remain constant, while sparse matrices can reduce both costs.
- 2.5 Preconditioning: Diagonal scaling preconditions the problem by normalizing rows of A with E and setting F to the identity, avoiding more expensive equilibration procedures.The scaling is intended to improve convergence properties while respecting limited embedded computational resources.
3 Numerical examples
The numerical examples evaluate the ADMM heuristic on mixed-Boolean quadratic programming, hybrid vehicle control, switched-mode power conversion, and signal decoding. Across these settings, the method finds feasible, relatively low-objective solutions quickly, though parameter choices trade off feasibility and optimality.
- 3.1 Randomly generated QP: Small ρ values often produce lower-objective feasible points but may fail to find feasibility, whereas large ρ values find feasible points faster with higher objective values.
- 3.2 Hybrid vehicle control: For hybrid vehicle control, the heuristic achieved objective 375.7 versus 339.2 for the global solution, with qualitatively similar trajectories.The algorithm used 1000 iterations from five initializations.
- 3.3 Power converter control: The power-converter experiment produced an approximate solution in less than 2 seconds, while MOSEK took more than 4 hours to find the global solution.The comparison concerns the switch configuration and output voltage trajectories.
- 3.4 Signal decoding: For MIMO signal decoding, the heuristic was tested on 1000 random instances using one initialization and 10 iterations per instance.Each instance had a 2000 × 400 channel matrix, and the average runtime including preprocessing was 80 milliseconds.
4 Conclusions
The paper presents the heuristic as an effective approach for approximate optimization over affine and nonconvex separable constraints. It demonstrates applicability to embedded mixed-integer and related control and decoding problems.
- 4 Conclusions: The heuristic targets approximate solutions to convex quadratic minimization over intersections of affine and nonconvex sets.
- 4 Conclusions: The method is reported as effective across hybrid vehicle control, power converter control, and signal decoding applications.