Differentiable McCormick relaxations

McCormick’s classical relaxation technique constructs closed-form convex and concave relaxations of compositions of simple intrinsic functions. These relaxations have several properties which make them useful for lower bounding problems in global optimization: they can be evaluated automatically, accurately, and computationally inexpensively, and they converge rapidly to the relaxed function as the underlying domain is reduced in size. They may also be adapted to yield relaxations of certain implicit functions and differential equation solutions. However, McCormick’s relaxations may be nonsmooth, and this nonsmoothness can create theoretical and computational obstacles when relaxations are to be deployed. This article presents a continuously differentiable variant of McCormick’s original relaxations in the multivariate McCormick framework of Tsoukalas and Mitsos. Gradients of the new differentiable relaxations may be computed efficiently using the standard forward or reverse modes of automatic differentiation. Extensions to differentiable relaxations of implicit functions and solutions of parametric ordinary differential equations are discussed. A C++ implementation based on the library MC++ is described and applied to a case study in nonsmooth nonconvex optimization.     

Generalized McCormick relaxations

Convex and concave relaxations are used extensively in global optimization algorithms. Among the various techniques available for generating relaxations of a given function, McCormick’s relaxations are attractive due to the recursive nature of their definition, which affords wide applicability and easy implementation computationally. Furthermore, these relaxations are typically stronger than those resulting from convexification or linearization procedures. This article leverages the recursive nature of McCormick’s relaxations to define a generalized form which both affords a new framework within which to analyze the properties of McCormick’s relaxations, and extends the applicability of McCormick’s technique to challenging open problems in global optimization. Specifically, relaxations of the parametric solutions of ordinary differential equations are considered in detail, and prospects for relaxations of the parametric solutions of nonlinear algebraic equations are discussed. For the case of ODEs, a complete computational procedure for evaluating convex and concave relaxations of the parametric solutions is described. Through McCormick’s composition rule, these relaxations may be used to construct relaxations for very general optimal control problems.     

Convergence rate of McCormick relaxations

Theory for the convergence order of the convex relaxations by McCormick (Math Program 10(1):147–175, 1976) for factorable functions is developed. Convergence rules are established for the addition, multiplication and composition operations. The convergence order is considered both in terms of pointwise convergence and of convergence in the Hausdorff metric. The convergence order of the composite function depends on the convergence order of the relaxations of the factors. No improvement in the order of convergence compared to that of the underlying bound calculation, e.g., via interval extensions, can be guaranteed unless the relaxations of the factors have pointwise convergence of high order. The McCormick relaxations are compared with the αBB relaxations by Floudas and coworkers (J Chem Phys, 1992, J Glob Optim, 1995, 1996), which guarantee quadratic convergence. Illustrative and numerical examples are given.     

On the strength of recursive McCormick relaxations for binary polynomial optimization

Recursive McCormick relaxations are among the most popular convexification techniques for binary polynomial optimization. It is well-understood that both the quality and the size of these relaxations depend on the recursive sequence and finding an optimal sequence amounts to solving a difficult combinatorial optimization problem. We prove that any recursive McCormick relaxation is implied by the extended flower relaxation, a linear programming relaxation, which for binary polynomial optimization problems with fixed degree can be solved in strongly polynomial time.     

Semidefinite relaxations of ordering problems

Ordering problems assign weights to each ordering and ask to find an ordering of maximum weight. We consider problems where the cost function is either linear or quadratic. In the first case, there is a given profit if the element $u$ is before $v$ in the ordering. In the second case, the profit depends on whether $u$ is before $v$ and $r$ is before $s$ . The linear ordering problem is well studied, with exact solution methods based on polyhedral relaxations. The quadratic ordering problem does not seem to have attracted similar attention. We present a systematic investigation of semidefinite optimization based relaxations for the quadratic ordering problem, extending and improving existing approaches. We show the efficiency of our relaxations by providing computational experience on a variety of problem classes.     

Rigorous filtering using linear relaxations

This paper presents rigorous filtering methods for continuous constraint satisfaction problems based on linear relaxations, designed to efficiently handle the linear inequalities coming from a linear relaxation of quadratic constraints. Filtering or pruning stands for reducing the search space of constraint satisfaction problems. Discussed are old and new approaches for rigorously enclosing the solution set of linear systems of inequalities, as well as different methods for computing linear relaxations. This allows custom combinations of relaxation and filtering. Care is taken to ensure that all methods correctly account for rounding errors in the computations. The methods are implemented in the GloptLab environment for solving quadratic constraint satisfaction problems. Demonstrative examples and tests comparing the different linear relaxation methods are also presented.     

Stochastic nuclear outages semidefinite relaxations

This paper deals with stochastic scheduling of nuclear power plant outages. Focusing on the main constraints of the problem, we propose a stochastic formulation with a discrete distribution for random variables, that leads to a mixed 0/1 quadratically constrained quadratic program. Then we investigate semidefinite relaxations for solving this hard problem. Numerical results on several instances of the problem show the efficiency of this approach, i.e., the gap between the optimal solution and the continuous relaxation is on average equal to 53.35 % whereas the semidefinite relaxation yields an average gap of 2.76 %. A feasible solution is then obtained with a randomized rounding procedure.     

Disjunctive programming and relaxations of polyhedra

Given a polyhedron \(L\) with \(h\) facets, whose interior contains no integral points, and a polyhedron \(P\), recent work in integer programming has focused on characterizing the convex hull of \(P\) minus the interior of \(L\). We show that to obtain such a characterization it suffices to consider all relaxations of \(P\) defined by at most \(n(h-1)\) among the inequalities defining \(P\). This extends a result by Andersen, Cornuéjols, and Li.     

Exact relaxations of non-convex variational problems

Here, we solve non-convex, variational problems given in the form

Semidefinite programming relaxations for semialgebraic problems

 A hierarchy of convex relaxations for semialgebraic problems is introduced. For questions reducible to a finite number of polynomial equalities and inequalities, it is shown how to construct a complete family of polynomially sized semidefinite programming conditions that prove infeasibility. The main tools employed are a semidefinite programming formulation of the sum of squares decomposition for multivariate polynomials, and some results from real algebraic geometry. The techniques provide a constructive approach for finding bounded degree solutions to the Positivstellensatz, and are illustrated with examples from diverse application fields. Received: May 10, 2001 / Accepted May 2002 Published online: April 10, 2003 Key Words. semidefinite programming – convex optimization – sums of squares – polynomial equations – real algebraic geometry The majority of this research has been carried out while the author was with the Control & Dynamical Systems Department, California Institute of Technology, Pasadena, CA 91125, USA.     

Stronger linear programming relaxations of max-cut

We consider linear programming relaxations for the max cut problem in graphs, based on k-gonal inequalities. We show that the integrality ratio for random dense graphs is asymptotically 1+1/k and for random sparse graphs is at least 1+3/k. There are O(n^k)k-gonal inequalities. These results generalize work by Poljak and Tuza, who gave similar results for k=3.     

Semidefinite relaxations for semi-infinite polynomial programming

This paper studies how to solve semi-infinite polynomial programming (SIPP) problems by semidefinite relaxation methods. We first recall two SDP relaxation methods for solving polynomial optimization problems with finitely many constraints. Then we propose an exchange algorithm with SDP relaxations to solve SIPP problems with compact index set. At last, we extend the proposed method to SIPP problems with noncompact index set via homogenization. Numerical results show that the algorithm is efficient in practice.     

Approximating Pareto curves using semidefinite relaxations

We approximate as closely as desired the Pareto curve associated with bicriteria polynomial optimization problems. We use three formulations (including the weighted sum approach and the Chebyshev approximation) and each of them is viewed as a parametric polynomial optimization problem. For each case is associated a hierarchy of semidefinite relaxations and from an optimal solution of each relaxation one approximates the Pareto curve by solving an inverse problem (first two cases) or by building a polynomial underestimator (third case).     

Convex relaxations of chance constrained optimization problems

In this paper we develop convex relaxations of chance constrained optimization problems in order to obtain lower bounds on the optimal value. Unlike existing statistical lower bounding techniques, our approach is designed to provide deterministic lower bounds. We show that a version of the proposed scheme leads to a tractable convex relaxation when the chance constraint function is affine with respect to the underlying random vector and the random vector has independent components. We also propose an iterative improvement scheme for refining the bounds.