A simple effective heuristic for embedded mixed-integer quadratic programming

ABSTRACT

In this paper, we propose a fast optimisation algorithm for approximately minimising 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 optimisation problems. We discuss the favourable 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 see that in many cases, it finds the global solution.     

Inner approximations of completely positive reformulations of mixed binary quadratic programs: a unified analysis

Every quadratic programming problem with a mix of continuous and binary variables can be equivalently reformulated as a completely positive optimization problem, that is, a linear optimization problem over the convex but computationally intractable cone of completely positive matrices. In this paper, we focus on general inner approximations of the cone of completely positive matrices on instances of completely positive optimization problems that arise from the reformulation of mixed binary quadratic programming problems. We provide a characterization of the feasibility of such an inner approximation as well as the optimal value of a feasible inner approximation. In particular, our results imply that polyhedral inner approximations are equivalent to a finite discretization of the feasible region of the original completely positive optimization problem. Our characterization yields, as a byproduct, an upper bound on the gap between the optimal value of an inner approximation and that of the original instance. We discuss the implications of this error bound for standard and box-constrained quadratic programs as well as general mixed binary quadratic programs with a bounded feasible region.     

Convex ensemble learning with sparsity and diversity

Classifier ensemble has been broadly studied in two prevalent directions, i.e., to diversely generate classifier components, and to sparsely combine multiple classifiers. While most current approaches are emphasized on either sparsity or diversity only, we investigate classifier ensemble focused on both in this paper. We formulate the classifier ensemble problem with the sparsity and diversity learning in a general mathematical framework, which proves beneficial for grouping classifiers. In particular, derived from the error-ambiguity decomposition, we design a convex ensemble diversity measure. Consequently, accuracy loss, sparseness regularization, and diversity measure can be balanced and combined in a convex quadratic programming problem. We prove that the final convex optimization leads to a closed-form solution, making it very appealing for real ensemble learning problems. We compare our proposed novel method with other conventional ensemble methods such as Bagging, least squares combination, sparsity learning, and AdaBoost, extensively on a variety of UCI benchmark data sets and the Pascal Large Scale Learning Challenge 2008 webspam data. Experimental results confirm that our approach has very promising performance.     

Structured and simultaneous Lyapunov functions for system stability problems

It is shown that many system stability and robustness problems can be reduced to the question of when there is a quadratic Lyapunov function of a certain structure which establishes stability of x = Ax for some appropriate A. The existence of such a Lyapunov function can be determined by solving a convex program. We present several numerical methods for these optimization problems. A simple numerical example is given.     

Computing sum of squares decompositions with rational coefficients

Sum of squares (SOS) decompositions for nonnegative polynomials are usually computed numerically, using convex optimization solvers. Although the underlying floating point methods in principle allow for numerical approximations of arbitrary precision, the computed solutions will never be exact. In many applications such as geometric theorem proving, it is of interest to obtain solutions that can be exactly verified. In this paper, we present a numeric–symbolic method that exploits the efficiency of numerical techniques to obtain an approximate solution, which is then used as a starting point for the computation of an exact rational result. We show that under a strict feasibility assumption, an approximate solution of the semidefinite program is sufficient to obtain a rational decomposition, and quantify the relation between the numerical error versus the rounding tolerance needed. Furthermore, we present an implementation of our method for the computer algebra system Macaulay 2.     

On the Learnability and Design of Output Codes for Multiclass Problems

Output coding is a general framework for solving multiclass categorization problems. Previous research on output codes has focused on building multiclass machines given predefined output codes. In this paper we discuss for the first time the problem of designing output codes for multiclass problems. For the design problem of discrete codes, which have been used extensively in previous works, we present mostly negative results. We then introduce the notion of continuous codes and cast the design problem of continuous codes as a constrained optimization problem. We describe three optimization problems corresponding to three different norms of the code matrix. Interestingly, for the l ₂ norm our formalism results in a quadratic program whose dual does not depend on the length of the code. A special case of our formalism provides a multiclass scheme for building support vector machines which can be solved efficiently. We give a time and space efficient algorithm for solving the quadratic program. We describe preliminary experiments with synthetic data show that our algorithm is often two orders of magnitude faster than standard quadratic programming packages. We conclude with the generalization properties of the algorithm.     

A perspective-based convex relaxation for switched-affine optimal control

We consider the switched-affine optimal control problem, i.e., the problem of selecting a sequence of affine dynamics from a finite set in order to minimize a sum of convex functions of the system state. We develop a new reduction of this problem to a mixed-integer convex program (MICP), based on perspective functions. Relaxing the integer constraints of this MICP results in a convex optimization problem, whose optimal value is a lower bound on the original problem value. We show that this bound is at least as tight as similar bounds obtained from two other well-known MICP reductions (via conversion to a mixed logical dynamical system, and by generalized disjunctive programming), and our numerical study indicates it is often substantially tighter. Using simple integer-rounding techniques, we can also use our formulation to obtain an upper bound (and corresponding sequence of control inputs). In our numerical study, this bound was typically within a few percent of the optimal value, making it attractive as a stand-alone heuristic, or as a subroutine in a global algorithm such as branch and bound. We conclude with some extensions of our formulation to problems with switching costs and piecewise affine dynamics.     

Formulation of Closed-Loop Min–Max MPC as a Quadratically Constrained Quadratic Program

In this note, we show that min-max model predictive control (MPC) for linearly constrained polytopic systems with quadratic cost can be cast as a quadratically constrained quadratic program (QCQP). We use the rigorous closed loop formulation of min-max MPC, and show that any such min-max MPC problem with convex costs and constraints can be cast as a finite dimensional convex optimization problem, with the QCQP arising from quadratic costs as a special case. At the base of the proof is a lemma showing the convexity of the dynamic programming cost-to-go, which implies that the worst case on an infinite polytopic set is assumed on one of its finitely many vertices. As the approach is based on a scenario tree formulation, the number of variables in this problem grows exponentially with the horizon length. Fortunately, the QCQP is tree structured, and can thus be efficiently solved by specially tailored interior-point methods whose computational costs are linear in the number of variables. The new formulation as a tree sparse QCQP promises to facilitate online solution of the rigorous min-max MPC problem with quadratic costs     

An augmented Lagrangian approach to non-convex SAO using diagonal quadratic approximations

Successful gradient-based sequential approximate optimization (SAO) algorithms in simulation-based optimization typically use convex separable approximations. Convex approximations may however not be very efficient if the true objective function and/or the constraints are concave. Using diagonal quadratic approximations, we show that non-convex approximations may indeed require significantly fewer iterations than their convex counterparts. The nonconvex subproblems are solved using an augmented Lagrangian (AL) strategy, rather than the Falk-dual, which is the norm in SAO based on convex subproblems. The results suggest that transformation of large-scale optimization problems with only a few constraints to a dual form via convexification need sometimes not be required, since this may equally well be done using an AL formulation.     

Binary partitioning, perceptual grouping, and restoration with semidefinite programming

We introduce a novel optimization method based on semidefinite programming relaxations to the field of computer vision and apply it to the combinatorial problem of minimizing quadratic functionals in binary decision variables subject to linear constraints. The approach is (tuning) parameter-free and computes high-quality combinatorial solutions using interior-point methods (convex programming) and a randomized hyperplane technique. Apart from a symmetry condition, no assumptions (such as metric pairwise interactions) are made with respect to the objective criterion. As a consequence, the approach can be applied to a wide range of problems. Applications to unsupervised partitioning, figure-ground discrimination, and binary restoration are presented along with extensive ground-truth experiments. From the viewpoint of relaxation of the underlying combinatorial problem, we show the superiority of our approach to relaxations based on spectral graph theory and prove performance bounds.     

Nonlinear Q-Design for Convex Stochastic Control

In this note we describe a version of the Q-design method that can be used to design nonlinear dynamic controllers for a discrete-time linear time-varying plant, with convex cost and constraint functions and arbitrary disturbance distribution. Choosing a basis for the nonlinear Q-parameter yields a convex stochastic optimization problem, which can be solved by standard methods such as sampling. In principle (for a large enough basis, and enough sampling) this method can solve the controller design problem to any degree of accuracy; in any case it can be used to find a suboptimal controller, using convex optimization methods. We illustrate the method with a numerical example, comparing a nonlinear controller found using our method with the optimal linear controller, the certainty-equivalent model predictive controller, and a lower bound on achievable performance obtained by ignoring the causality constraint.     

Methods of searching for guaranteeing and optimistic solutions to integer optimization problems under uncertainty

The paper studies complex integer optimization problems with inexact coefficients of the linear objective function and convex quadratic constraint functions. Exact and approximate decomposition methods are developed and proved to search for guaranteeing and optimistic solutions to such problems. The methods are based on approximation of initial problems by problems of a simpler structure. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 103–114, January–February 2007.     

On convex transformability and the solution of nonconvex problems via the dual of Falk

In structural optimization, most successful sequential approximate optimization (SAO) algorithms solve a sequence of strictly convex subproblems using the dual of Falk. Previously, we have shown that, under certain conditions, a nonconvex nonlinear (sub)problem may also be solved using the Falk dual. In particular, we have demonstrated this for two nonconvex examples of approximate subproblems that arise in popular and important structural optimization problems. The first is used in the SAO solution of the weight minimization problem, while the topology optimization problem that results from volumetric penalization gives rise to the other. In both cases, the nonconvex subproblems arise naturally in the consideration of the physical problems, so it seems counter productive to discard them in favor of using standard, but less well-suited, strictly convex approximations. Though we have not required that strictly convex transformations exist for these problems in order that they may be solved via a dual approach, we have noted that both of these examples can indeed be transformed into strictly convex forms. In this paper we present both the nonconvex weight minimization problem and the nonconvex topology optimization problem with volumetric penalization as instructive numerical examples to help motivate the use of nonconvex approximations as subproblems in SAO. We then explore the link between convex transformability and the salient criteria which make nonconvex problems amenable to solution via the Falk dual, and we assess the effect of the transformation on the dual problem. However, we consider only a restricted class of problems, namely separable problems that are at least C ¹ continuous, and a restricted class of transformations: those in which the functions that represent the mapping are each continuous, monotonic and univariate.     

Optimization strategies for discrete multi-material stiffness optimization

Design of composite laminated lay-ups are formulated as discrete multi-material selection problems. The design problem can be modeled as a non-convex mixed-integer optimization problem. Such problems are in general only solvable to global optimality for small to moderate sized problems. To attack larger problem instances we formulate convex and non-convex continuous relaxations which can be solved using gradient based optimization algorithms. The convex relaxation yields a lower bound on the attainable performance. The optimal solution to the convex relaxation is used as a starting guess in a continuation approach where the convex relaxation is changed to a non-convex relaxation by introduction of a quadratic penalty constraint whereby intermediate-valued designs are prevented. The minimum compliance, mass constrained multiple load case problem is formulated and solved for a number of examples which numerically confirm the sought properties of the new scheme in terms of convergence to a discrete solution.     

Kriging代理模型在对地观测卫星系统优化中的应用

结构优化是对地观测卫星系统(Earth observation satellite system,EOSS)性能提高的关键,但其覆盖性能难以解析计算.为实现EOSS优化,提出了仿真优化的求解思路:构建Kriging代理模型对仿真数据进行拟合,采用代理模型最优和最大化期望提高相结合的机制选择更新点,并定义单位距离的函数改进对更新点进行过滤;提出了改进广义模式搜索算法求解代理模型,搜索步采用遗传算法和序列二次规划算法实现,筛选步采用不完全动态筛选.最后,通过仿真实例和对比实验验证了本文方法的有效性.     

A convex approach for NMPC based on second order Volterra series models

In model predictive control (MPC), the input sequence is computed, minimizing a usually quadratic cost function based on the predicted evolution of the system output. In the case of nonlinear MPC (NMPC), the use of nonlinear prediction models frequently leads to non‐convex optimization problems with several minimums. This paper proposes a new NMPC strategy based on second order Volterra series models where the original performance index is approximated by quadratic functions, which represent a lower bound of the original performance index. Convexity of the approximating quadratic cost functions can be achieved easily by a suitable choice of the weighting of the control increments in the performance index. The approximating cost functions can be globally minimized by convex optimization techniques in order to compute the input sequence. The minimization of the performance index is carried out by an iterative optimization procedure, which guarantees convergence to the solution. Furthermore, for a nominal prediction model, asymptotic stability for the proposed NMPC strategy can be shown. In the case of considering an estimation error in the prediction model, input‐to‐state practical stability is assured. The control performance of the NMPC strategy is illustrated by experimental results. Copyright © 2014 John Wiley & Sons, Ltd.     

A general system for heuristic minimization of convex functions over non-convex sets

We describe general heuristics to approximately solve a wide variety of problems with convex objective and decision variables from a non-convex set. The heuristics, which employ convex relaxations, convex restrictions, local neighbour search methods, and the alternating direction method of multipliers, require the solution of a modest number of convex problems, and are meant to apply to general problems, without much tuning. We describe an implementation of these methods in a package called NCVX, as an extension of CVXPY, a Python package for formulating and solving convex optimization problems. We study several examples of well known non-convex problems, and show that our general purpose heuristics are effective in finding approximate solutions to a wide variety of problems.     

Lyapunov functionals in complex /spl mu/ analysis

Conditions for robust stability of linear time-invariant systems subject to structured linear time-invariant uncertainties can be derived in the complex /spl mu/ framework, or, equivalently, in the framework of integral quadratic constraints. These conditions can be checked numerically with linear matrix inequality (LMI)-based convex optimization using the Kalman-Yakubovich-Popov lemma. We show how LMI tests also yield a convex parametrization of (a subset of) Lyapunov functionals that prove robust stability of such uncertain systems. We show that for uncertainties that are pure delays, the Lyapunov functionals reduce to the standard Lyapunov-Krasovksii functionals that are encountered in the stability analysis of delay systems. We demonstrate the practical utility of the Lyapunov functional parametrization by deriving bounds for a number of measures of robust performance (beyond the usual H/sub /spl infin// performance); these bounds can be efficiently computed using convex optimization over linear matrix inequalities.     

Performance analysis of reset control systems

In this paper we present a general linear matrix inequality‐based analysis method to determine the performance of a SISO reset control system in both the ??₂ gain and ??₂ sense. In particular, we derive convex optimization problems in terms of LMIs to compute an upperbound on the ??₂ gain performance and the ??₂ norm, using dissipativity theory with piecewise quadratic Lyapunov functions. The results are applicable to for all LTI plants and linear‐based reset controllers, thereby generalizing the available results in the literature. Furthermore, we provide simple though convincing examples to illustrate the accuracy of our proposed ??₂ gain and ??₂ norm calculations and show that, for an input constrained ??₂ problem, reset control can outperform a linear controller designed by a common nonlinear optimization method. Copyright © 2009 John Wiley & Sons, Ltd.     

Multi-period portfolio optimization with linear control policies

This paper is concerned with multi-period sequential decision problems for financial asset allocation. A model is proposed in which periodic optimal portfolio adjustments are determined with the objective of minimizing a cumulative risk measure over the investment horizon, while satisfying portfolio diversity constraints at each period and achieving or exceeding a desired terminal expected wealth target. The proposed solution approach is based on a specific affine parameterization of the recourse policy, which allows us to obtain a sub-optimal but exact and explicit problem formulation in terms of a convex quadratic program.In contrast to the mainstream stochastic programming approach to multi-period optimization, which has the drawback of being computationally intractable, the proposed setup leads to optimization problems that can be solved efficiently with currently available convex quadratic programming solvers, enabling the user to effectively attack multi-stage decision problems with many securities and periods.