Univariate parameterization for global optimization of mixed-integer polynomial problems

This paper presents a new relaxation technique to globally optimize mixed-integer polynomial programming problems that arise in many engineering and management contexts. Using a bilinear term as the basic building block, the underlying idea involves the discretization of one of the variables up to a chosen accuracy level (Teles, J.P., Castro, P.M., Matos, H.A. (2013). Multiparametric disaggregation technique for global optimization of polynomial programming problems. J. Glob. Optim. 55, 227–251), by means of a radix-based numeric representation system, coupled with a residual variable to effectively make its domain continuous. Binary variables are added to the formulation to choose the appropriate digit for each position together with new sets of continuous variables and constraints leading to the transformation of the original mixed-integer non-linear problem into a larger one of the mixed-integer linear programming type. The new underestimation approach can be made as tight as desired and is shown capable of providing considerably better lower bounds than a widely used global optimization solver for a specific class of design problems involving bilinear terms.     

Norm bounds and underestimators for unconstrained polynomial integer minimization

We consider the problem of minimizing a polynomial function over the integer lattice. Though impossible in general, we use a known sufficient condition for the existence of continuous minimizers to guarantee the existence of integer minimizers as well. In case this condition holds, we use sos programming to compute the radius of a p-norm ball which contains all integer minimizers. We prove that this radius is smaller than the radius known from the literature. Our numerical results show that the number of potentially optimal solutions is reduced by several orders of magnitude. Furthermore, we derive a new class of underestimators of the polynomial function. Using a Stellensatz from real algebraic geometry and again sos programming, we optimize over this class to get a strong lower bound on the integer minimum. Also our lower bounds are evaluated experimentally. They show a good performance, in particular within a branch and bound framework.     

Global optimality principles for polynomial optimization over box or bivalent constraints by separable polynomial approximations

In this paper we present necessary conditions for global optimality for polynomial problems with box or bivalent constraints using separable polynomial relaxations. We achieve this by first deriving a numerically checkable characterization of global optimality for separable polynomial problems with box as well as bivalent constraints. Our necessary optimality conditions can be numerically checked by solving semi-definite programming problems. Then, by employing separable polynomial under-estimators, we establish sufficient conditions for global optimality for classes of polynomial optimization problems with box or bivalent constraints. We construct underestimators using the sum of squares convex (SOS-convex) polynomials of real algebraic geometry. An important feature of SOS-convexity that is generally not shared by the standard convexity is that whether a polynomial is SOS-convex or not can be checked by solving a semidefinite programming problem. We illustrate the versatility of our optimality conditions by simple numerical examples.     

Outer approximation algorithms for separable nonconvex mixed-integer nonlinear programs

A rigorous decomposition approach to solve separable mixed-integer nonlinear programs where the participating functions are nonconvex is presented. The proposed algorithms consist of solving an alternating sequence of Relaxed Master Problems (mixed-integer linear program) and two nonlinear programming problems (NLPs). A sequence of valid nondecreasing lower bounds and upper bounds is generated by the algorithms which converge in a finite number of iterations. A Primal Bounding Problem is introduced, which is a convex NLP solved at each iteration to derive valid outer approximations of the nonconvex functions in the continuous space. Two decomposition algorithms are presented in this work. On finite termination, the first yields the global solution to the original nonconvex MINLP and the second finds a rigorous bound to the global solution. Convergence and optimality properties, and refinement of the algorithms for efficient implementation are presented. Finally, numerical results are compared with currently available algorithms for example problems, illuminating the potential benefits of the proposed algorithm.     

Derivative-free methods for mixed-integer nonsmooth constrained optimization

Computational Optimization and Applications - In this paper, mixed-integer nonsmooth constrained optimization problems are considered, where objective/constraint functions are available only as the...     

Derivative-free methods for bound constrained mixed-integer optimization

We consider the problem of minimizing a continuously differentiable function of several variables subject to simple bound constraints where some of the variables are restricted to take integer values. We assume that the first order derivatives of the objective function can be neither calculated nor approximated explicitly. This class of mixed integer nonlinear optimization problems arises frequently in many industrial and scientific applications and this motivates the increasing interest in the study of derivative-free methods for their solution. The continuous variables are handled by a linesearch strategy whereas to tackle the discrete ones we employ a local search-type approach. We propose different algorithms which are characterized by the way the current iterate is updated and by the stationarity conditions satisfied by the limit points of the sequences they produce.     

Binary decision rules for multistage adaptive mixed-integer optimization

Mathematical Programming - Decision rules provide a flexible toolbox for solving computationally demanding, multistage adaptive optimization problems. There is a plethora of real-valued decision...     

On the relaxation gap for PDE mixed-integer optimal control problems

Mixed-integer optimal control problems require taking discrete and continuous control decisions for the optimization of a dynamical system. We consider dynamics governed by partial differential equations of evolution type and assess the problem by relaxation and rounding strategies. For this solution approach, we present a priori estimates for semilinear evolutions on Banach spaces concerning the optimality gap. The theoretical results show that the gap can be made arbitrary small. We demonstrate the numerical performance of the approach on benchmark problems of parabolic type motivated from thermal manufacturing and of hyperbolic type motivated from traffic flow control. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Relaxation methods for mixed-integer optimal control of partial differential equations

We consider integer-restricted optimal control of systems governed by abstract semilinear evolution equations. This includes the problem of optimal control design for certain distributed parameter systems endowed with multiple actuators, where the task is to minimize costs associated with the dynamics of the system by choosing, for each instant in time, one of the actuators together with ordinary controls. We consider relaxation techniques that are already used successfully for mixed-integer optimal control of ordinary differential equations. Our analysis yields sufficient conditions such that the optimal value and the optimal state of the relaxed problem can be approximated with arbitrary precision by a control satisfying the integer restrictions. The results are obtained by semigroup theory methods. The approach is constructive and gives rise to a numerical method. We supplement the analysis with numerical experiments.     

Partitioning procedure for polynomial optimization

We consider the problem of finding the minimum of a real-valued multivariate polynomial function constrained in a compact set defined by polynomial inequalities and equalities. This problem, called polynomial optimization problem (POP), is generally nonconvex and has been of growing interest to many researchers in recent years. Our goal is to tackle POPs using decomposition, based on a partitioning procedure. The problem manipulations are in line with the pattern used in the generalized Benders decomposition, namely projection followed by relaxation. Stengle’s and Putinar’s Positivstellensätze are employed to derive the feasibility and optimality constraints, respectively. We test the performance of the proposed partitioning procedure on a collection of benchmark problems and present the numerical results.     

Polyhedral approximation in mixed-integer convex optimization

Generalizing both mixed-integer linear optimization and convex optimization, mixed-integer convex optimization possesses broad modeling power but has seen relatively few advances in general-purpose solvers in recent years. In this paper, we intend to provide a broadly accessible introduction to our recent work in developing algorithms and software for this problem class. Our approach is based on constructing polyhedral outer approximations of the convex constraints, resulting in a global solution by solving a finite number of mixed-integer linear and continuous convex subproblems. The key advance we present is to strengthen the polyhedral approximations by constructing them in a higher-dimensional space. In order to automate this extended formulation we rely on the algebraic modeling technique of disciplined convex programming (DCP), and for generality and ease of implementation we use conic representations of the convex constraints. Although our framework requires a manual translation of existing models into DCP form, after performing this transformation on the MINLPLIB2 benchmark library we were able to solve a number of unsolved instances and on many other instances achieve superior performance compared with state-of-the-art solvers like Bonmin, SCIP, and Artelys Knitro.     

Generalized symmetric ADMM for separable convex optimization

The alternating direction method of multipliers (ADMM) has been proved to be effective for solving separable convex optimization subject to linear constraints. In this paper, we propose a generalized symmetric ADMM (GS-ADMM), which updates the Lagrange multiplier twice with suitable stepsizes, to solve the multi-block separable convex programming. This GS-ADMM partitions the data into two group variables so that one group consists of p block variables while the other has q block variables, where \(p \ge 1\) and \(q \ge 1\) are two integers. The two grouped variables are updated in a Gauss–Seidel scheme, while the variables within each group are updated in a Jacobi scheme, which would make it very attractive for a big data setting. By adding proper proximal terms to the subproblems, we specify the domain of the stepsizes to guarantee that GS-ADMM is globally convergent with a worst-case \({\mathcal {O}}(1/t)\) ergodic convergence rate. It turns out that our convergence domain of the stepsizes is significantly larger than other convergence domains in the literature. Hence, the GS-ADMM is more flexible and attractive on choosing and using larger stepsizes of the dual variable. Besides, two special cases of GS-ADMM, which allows using zero penalty terms, are also discussed and analyzed. Compared with several state-of-the-art methods, preliminary numerical experiments on solving a sparse matrix minimization problem in the statistical learning show that our proposed method is effective and promising.     

On optimal polynomial meshes

Let $P_n^d$ be the space of real algebraic polynomials of $d$ variables and degree at most $n$, $K?{\mathbb{R}}^d$ a compact set, ${6p6}_K:={sup}_{x\in K}\left|p\left(x\right)\right|$ the usual supremum norm on $K$, and $card\left(Y\right)$ the cardinality of a finite set $Y$. A family of sets $Y=\{Y_n?K,n\in \mathbb{N}\}$ is called an admissible mesh in $K$ if there exists a constant $c_1>0$ depending only on $K$ such that ${6p6}_K\le c_1{6p6}_{Y_n}\text{,}p\in P_n^d,n\in \mathbb{N}\text{,}$ where the cardinality of $Y_n$ grows at most polynomially. If $card\left(Y_n\right)\le c_2{n}^d,n\in \mathbb{N}$ with some $c_2>0$ depending only on $K$ then we say that the admissible mesh is optimal. This notion of admissible meshes is related to norming sets which are widely used in the literature. In this paper we present some general families of sets possessing admissible meshes which are optimal or near optimal in the sense that the cardinality of sets $Y_n$ does not grow too fast. In particular, it will be shown that graph domains bounded by polynomial graphs, convex polytopes and star like sets with $C^2$ boundary possess optimal admissible meshes. In addition, graph domains with piecewise analytic boundary and any convex sets in ${\mathbb{R}}^2$ possess almost optimal admissible meshes in the sense that the cardinality of admissible meshes is larger than optimal only by a $logn$ factor.     

Penalty alternating direction methods for mixed-integer optimal control with combinatorial constraints

Mathematical Programming - We consider mixed-integer optimal control problems with combinatorial constraints that couple over time such as minimum dwell times. We analyze a lifting and...     

Direct methods with maximal lower bound for mixed-integer optimal control problems

Many practical optimal control problems include discrete decisions. These may be either time-independent parameters or time-dependent control functions as gears or valves that can only take discrete values at any given time. While great progress has been achieved in the solution of optimization problems involving integer variables, in particular mixed-integer linear programs, as well as in continuous optimal control problems, the combination of the two is yet an open field of research. We consider the question of lower bounds that can be obtained by a relaxation of the integer requirements. For general nonlinear mixed-integer programs such lower bounds typically suffer from a huge integer gap. We convexify (with respect to binary controls) and relax the original problem and prove that the optimal solution of this continuous control problem yields the best lower bound for the nonlinear integer problem. Building on this theoretical result we present a novel algorithm to solve mixed-integer optimal control problems, with a focus on discrete-valued control functions. Our algorithm is based on the direct multiple shooting method, an adaptive refinement of the underlying control discretization grid and tailored heuristic integer methods. Its applicability is shown by a challenging application, the energy optimal control of a subway train with discrete gears and velocity limits.      

Quadrature-based polynomial optimization

We show that Lasserre measure-based hierarchies for polynomial optimization can be implemented by directly computing the discrete minimum at a suitable set     

Completely positive reformulations for polynomial optimization

Polynomial optimization encompasses a very rich class of problems in which both the objective and constraints can be written in terms of polynomials on the decision variables. There is a well established body of research on quadratic polynomial optimization problems based on reformulations of the original problem as a conic program over the cone of completely positive matrices, or its conic dual, the cone of copositive matrices. As a result of this reformulation approach, novel solution schemes for quadratic polynomial optimization problems have been designed by drawing on conic programming tools, and the extensively studied cones of completely positive and of copositive matrices. In particular, this approach has been applied to solve key combinatorial optimization problems. Along this line of research, we consider polynomial optimization problems that are not necessarily quadratic. For this purpose, we use a natural extension of the cone of completely positive matrices; namely, the cone of completely positive tensors. We provide a general characterization of the class of polynomial optimization problems that can be formulated as a conic program over the cone of completely positive tensors. As a consequence of this characterization, it follows that recent related results for quadratic problems can be further strengthened and generalized to higher order polynomial optimization problems. Also, we show that the conditions underlying the characterization are conceptually the same, regardless of the degree of the polynomials defining the problem. To illustrate our results, we discuss in further detail special and relevant instances of polynomial optimization problems.     

Approximation methods for complex polynomial optimization

Complex polynomial optimization problems arise from real-life applications including radar code design, MIMO beamforming, and quantum mechanics. In this paper, we study complex polynomial optimization models where the objective function takes one of the following three forms: (1) multilinear; (2) homogeneous polynomial; (3) symmetric conjugate form. On the constraint side, the decision variables belong to one of the following three sets: (1) the \(m\) -th roots of complex unity; (2) the complex unity; (3) the Euclidean sphere. We first discuss the multilinear objective function. Polynomial-time approximation algorithms are proposed for such problems with assured worst-case performance ratios, which depend only on the dimensions of the model. Then we introduce complex homogenous polynomial functions and establish key linkages between complex multilinear forms and the complex polynomial functions. Approximation algorithms for the above-mentioned complex polynomial optimization models with worst-case performance ratios are presented. Numerical results are reported to illustrate the effectiveness of the proposed approximation algorithms.     

An exact penalty global optimization approach for mixed-integer programming problems

In this work, we propose a global optimization approach for mixed-integer programming problems. To this aim, we preliminarily define an exact penalty algorithm model for globally solving general problems and we show its convergence properties. Then, we describe a particular version of the algorithm that solves mixed-integer problems and we report computational results on some MINLP problems.