Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation

We present a decomposition-approximation method for generating convex relaxations for nonconvex quadratically constrained quadratic programming (QCQP). We first develop a general conic program relaxation for QCQP based on a matrix decomposition scheme and polyhedral (piecewise linear) underestimation. By employing suitable matrix cones, we then show that the convex conic relaxation can be reduced to a semidefinite programming (SDP) problem. In particular, we investigate polyhedral underestimations for several classes of matrix cones, including the cones of rank-1 and rank-2 matrices, the cone generated by the coefficient matrices, the cone of positive semidefinite matrices and the cones induced by rank-2 semidefinite inequalities. We demonstrate that in general the new SDP relaxations can generate lower bounds at least as tight as the best known SDP relaxations for QCQP. Moreover, we give examples for which tighter lower bounds can be generated by the new SDP relaxations. We also report comparison results of different convex relaxation schemes for nonconvex QCQP with convex quadratic/linear constraints, nonconvex quadratic constraints and 0–1 constraints.     

On equating the difference between optimal and marginal values of general convex programs

Unlike elementary finite linear programming, the optimal program value of a convex optimization problem is generally different from the vector product of the marginal price vector and the resource right-hand side vector. In this paper, a duality approach is developed, based on objective function parametrizations, to characterize this difference under rather general circumstances.The approach generalizes the concept of Kuhn-Tucker vectors of a convex program. It is shown that nonstandard polynomial Kuhn-Tucker vectors exist for any convex program having finite value. Two examples illustrate the procedure.An earlier version of this paper was presented at the International Symposium on Extremal Methods and Systems Analysis on the Occasion of Professor A. Charnes' Sixtieth Birthday, Austin, Texas, 1977. Partial support of the research of the first author was provided by NSF Grants Nos. ENG-76-05191 and ENG-78-25488. The authors gratefully acknowledge Professor F. J. Gould, University of Chicago, for bringing the valuable Balinski-Baumol reference (Ref. 1) to their attention. They also gratefully acknowledge criticisms of a referee reminding them of the sophistication which a convex analysis approach can bring to bear on the main problem treated in this paper. This paper is dedicated to Professor Charnes.     

Existence of Global Minima for Constrained Optimization

We present a unified approach to establishing the existence of global minima of a (non)convex constrained optimization problem. Our results unify and generalize previous existence results for convex and nonconvex programs, including the Frank-Wolfe theorem, and for (quasi) convex quadratically constrained quadratic programs and convex polynomial programs. For example, instead of requiring the objective/constraint functions to be constant along certain recession directions, we only require them to linearly recede along these directions. Instead of requiring the objective/constraint functions to be convex polynomials, we only require the objective function to be a (quasi)convex polynomial over a polyhedral set and the constraint functions to be convex polynomials or the composition of coercive functions with linear mappings.We thank Professor Dimitri Bertsekas for his comments and support in the writing of this paper.     

DC approach to weakly convex optimization and nonconvex quadratic optimization problems

Motivated by weakly convex optimization and quadratic optimization problems, we first show that there is no duality gap between a difference of convex (DC) program over DC constraints and its associated dual problem. We then provide certificates of global optimality for a class of nonconvex optimization problems. As an application, we derive characterizations of robust solutions for uncertain general nonconvex quadratic optimization problems over nonconvex quadratic constraints.     

A posteriori error analysis of an augmented fully mixed formulation for the nonisothermal Oldroyd–Stokes problem

In this article, we consider an augmented fully mixed variational formulation that has been recently proposed for the nonisothermal Oldroyd–Stokes problem, and develop an a posteriori error analysis for the 2‐D and 3‐D versions of the associated mixed finite element scheme. More precisely, we derive two reliable and efficient residual‐based a posteriori error estimators for this problem on arbitrary (convex or nonconvex) polygonal and polyhedral regions. The reliability of the proposed estimators draws mainly upon the uniform ellipticity of the bilinear forms of the continuous formulation, suitable assumptions on the domain and the data, stable Helmholtz decompositions, and the local approximation properties of the Clément and Raviart–Thomas operators. On the other hand, inverse inequalities, the localization technique based on bubble functions, and known results from previous works are the main tools yielding the efficiency estimate. Finally, several numerical results confirming the properties of the a posteriori error estimators and illustrating the performance of the associated adaptive algorithms are reported.     

On solving simple bilevel programs with a nonconvex lower level program

In this paper, we consider a simple bilevel program where the lower level program is a nonconvex minimization problem with a convex set constraint and the upper level program has a convex set constraint. By using the value function of the lower level program, we reformulate the bilevel program as a single level optimization problem with a nonsmooth inequality constraint and a convex set constraint. To deal with such a nonsmooth and nonconvex optimization problem, we design a smoothing projected gradient algorithm for a general optimization problem with a nonsmooth inequality constraint and a convex set constraint. We show that, if the sequence of penalty parameters is bounded then any accumulation point is a stationary point of the nonsmooth optimization problem and, if the generated sequence is convergent and the extended Mangasarian-Fromovitz constraint qualification holds at the limit then the limit point is a stationary point of the nonsmooth optimization problem. We apply the smoothing projected gradient algorithm to the bilevel program if a calmness condition holds and to an approximate bilevel program otherwise. Preliminary numerical experiments show that the algorithm is efficient for solving the simple bilevel program.     

On polyhedral approximations in an <Emphasis Type="Italic">n</Emphasis>-dimensional space

The polyhedral approximation of a positively homogeneous (and, in general, nonconvex) function on a unit sphere is investigated. Such a function is presupporting (i.e., its convex hull is the supporting function) for a convex compact subset of Rⁿ. The considered polyhedral approximation of this function provides a polyhedral approximation of this convex compact set. The best possible estimate for the error of the considered approximation is obtained in terms of the modulus of uniform continuous subdifferentiability in the class of a priori grids of given step in the Hausdorff metric.     

Support vector machine classification with indefinite kernels

We propose a method for support vector machine classification using indefinite kernels. Instead of directly minimizing or stabilizing a nonconvex loss function, our algorithm simultaneously computes support vectors and a proxy kernel matrix used in forming the loss. This can be interpreted as a penalized kernel learning problem where indefinite kernel matrices are treated as noisy observations of a true Mercer kernel. Our formulation keeps the problem convex and relatively large problems can be solved efficiently using the projected gradient or analytic center cutting plane methods. We compare the performance of our technique with other methods on several standard data sets.     

Proximal alternating linearized minimization for nonconvex and nonsmooth problems

We introduce a proximal alternating linearized minimization (PALM) algorithm for solving a broad class of nonconvex and nonsmooth minimization problems. Building on the powerful Kurdyka–?ojasiewicz property, we derive a self-contained convergence analysis framework and establish that each bounded sequence generated by PALM globally converges to a critical point. Our approach allows to analyze various classes of nonconvex-nonsmooth problems and related nonconvex proximal forward–backward algorithms with semi-algebraic problem’s data, the later property being shared by many functions arising in a wide variety of fundamental applications. A by-product of our framework also shows that our results are new even in the convex setting. As an illustration of the results, we derive a new and simple globally convergent algorithm for solving the sparse nonnegative matrix factorization problem.     

A coordinate gradient descent method for nonsmooth separable minimization

We consider the problem of minimizing the sum of a smooth function and a separable convex function. This problem includes as special cases bound-constrained optimization and smooth optimization with ?₁-regularization. We propose a (block) coordinate gradient descent method for solving this class of nonsmooth separable problems. We establish global convergence and, under a local Lipschitzian error bound assumption, linear convergence for this method. The local Lipschitzian error bound holds under assumptions analogous to those for constrained smooth optimization, e.g., the convex function is polyhedral and the smooth function is (nonconvex) quadratic or is the composition of a strongly convex function with a linear mapping. We report numerical experience with solving the ?₁-regularization of unconstrained optimization problems from Moré et al. in ACM Trans. Math. Softw. 7, 17–41, 1981 and from the CUTEr set (Gould and Orban in ACM Trans. Math. Softw. 29, 373–394, 2003). Comparison with L-BFGS-B and MINOS, applied to a reformulation of the ?₁-regularized problem as a bound-constrained optimization problem, is also reported.     

On extreme points of bounded sets of generalized finite sequence spaces

The Linear Independence Extreme Point Theorem and Opposite Sign Theorem of semiinfinite programming provide algebraic characterizations of unbounded infinite dimensional convex polyhedral sets in terms of their extreme points. The Charnes, Kortanek, and Raike purification algorithm, which transforms any non-extreme point to an extreme point having objective function value at least as great, is based upon the constructive proofs of these two theorems. In this paper these extreme point characterizations are extended to additionally constrained, bounded convex polyhedral constraint sets of semi-infinite programming. It is shown that each of these bounded sets is spanned by a possibly infinite number of extreme points, and as before the proofs are constructive, thereby expanding the range of applicability of the purification algorithm to these cases.     

A smoothing augmented Lagrangian method for solving simple bilevel programs

In this paper, we design a numerical algorithm for solving a simple bilevel program where the lower level program is a nonconvex minimization problem with a convex set constraint. We propose to solve a combined problem where the first order condition and the value function are both present in the constraints. Since the value function is in general nonsmooth, the combined problem is in general a nonsmooth and nonconvex optimization problem. We propose a smoothing augmented Lagrangian method for solving a general class of nonsmooth and nonconvex constrained optimization problems. We show that, if the sequence of penalty parameters is bounded, then any accumulation point is a Karush-Kuch-Tucker (KKT) point of the nonsmooth optimization problem. The smoothing augmented Lagrangian method is used to solve the combined problem. Numerical experiments show that the algorithm is efficient for solving the simple bilevel program.     

An alternative perspective on copositive and convex relaxations of nonconvex quadratic programs

We study convex relaxations of nonconvex quadratic programs. We identify a family of so-called feasibility preserving convex relaxations, which includes the well-known copositive and doubly nonnegative relaxations, with the property that the convex relaxation is feasible if and only if the nonconvex quadratic program is feasible. We observe that each convex relaxation in this family implicitly induces a convex underestimator of the objective function on the feasible region of the quadratic program. This alternative perspective on convex relaxations enables us to establish several useful properties of the corresponding convex underestimators. In particular, if the recession cone of the feasible region of the quadratic program does not contain any directions of negative curvature, we show that the convex underestimator arising from the copositive relaxation is precisely the convex envelope of the objective function of the quadratic program, strengthening Burer’s well-known result on the exactness of the copositive relaxation in the case of nonconvex quadratic programs. We also present an algorithmic recipe for constructing instances of quadratic programs with a finite optimal value but an unbounded relaxation for a rather large family of convex relaxations including the doubly nonnegative relaxation.

     

A polyhedral branch-and-cut approach to global optimization

A variety of nonlinear, including semidefinite, relaxations have been developed in recent years for nonconvex optimization problems. Their potential can be realized only if they can be solved with sufficient speed and reliability. Unfortunately, state-of-the-art nonlinear programming codes are significantly slower and numerically unstable compared to linear programming software.In this paper, we facilitate the reliable use of nonlinear convex relaxations in global optimization via a polyhedral branch-and-cut approach. Our algorithm exploits convexity, either identified automatically or supplied through a suitable modeling language construct, in order to generate polyhedral cutting planes and relaxations for multivariate nonconvex problems. We prove that, if the convexity of a univariate or multivariate function is apparent by decomposing it into convex subexpressions, our relaxation constructor automatically exploits this convexity in a manner that is much superior to developing polyhedral outer approximators for the original function. The convexity of functional expressions that are composed to form nonconvex expressions is also automatically exploited.Root-node relaxations are computed for 87 problems from globallib and minlplib, and detailed computational results are presented for globally solving 26 of these problems with BARON 7.2, which implements the proposed techniques. The use of cutting planes for these problems reduces root-node relaxation gaps by up to 100% and expedites the solution process, often by several orders of magnitude.The research was supported in part by ExxonMobil Upstream Research Company, the National Science Foundation under awards DMII 0115166 and CTS 0124751, and the Joint NSF/NIGMS Initiative to Support Research in the Area of Mathematical Biology under NIH award GM072023.     

Technical efficiency and distance to a reverse convex set

The problem of finding the distance to a reverse (or complement of a) convex subset in a normed vector space is considered. This nonconvex and, in general, nonsmooth optimization problem arises in quantitative economics in the theory of measuring the technical efficiency of production units. In this context, applying a suitable duality theorem similar to the Nirenberg's one known for the distance to a convex subset, the problem reduces to a finite number of independent linear programming problems.     

A class of problems where dual bounds beat underestimation bounds

We investigate the problem of minimizing a nonconvex function with respect to convex constraints, and we study different techniques to compute a lower bound on the optimal value: The method of using convex envelope functions on one hand, and the method of exploiting nonconvex duality on the other hand. We investigate which technique gives the better bound and develop conditions under which the dual bound is strictly better than the convex envelope bound. As a byproduct, we derive some interesting results on nonconvex duality.     

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.     

A nonconvex approach to low‐rank matrix completion using convex optimization

This paper deals with the problem of recovering an unknown low‐rank matrix from a sampling of its entries. For its solution, we consider a nonconvex approach based on the minimization of a nonconvex functional that is the sum of a convex fidelity term and a nonconvex, nonsmooth relaxation of the rank function. We show that by a suitable choice of this nonconvex penalty, it is possible, under mild assumptions, to use also in this matrix setting the iterative forward–backward splitting method. Specifically, we propose the use of certain parameter dependent nonconvex penalties that with a good choice of the parameter value allow us to solve in the backward step a convex minimization problem, and we exploit this result to prove the convergence of the iterative forward–backward splitting algorithm. Based on the theoretical results, we develop for the solution of the matrix completion problem the efficient iterative improved matrix completion forward–backward algorithm, which exhibits lower computing times and improved recovery performance when compared with the best state‐of‐the‐art algorithms for matrix completion. Copyright © 2016 John Wiley & Sons, Ltd.     

Fast computation of the modality of polygons

The modality of a vertex of a polygon is the number of minima or maxima in the distance function from the vertex under consideration to each of the other vertices taken in order around the polygon. Modality was defined by Avis, Toussaint, and Bhattacharya (Comput. Math Appl., 8 (1982), 153–156) and has been further studied by Toussaint and Bhattacharya (Technical Report, No. SOCS-81.3, School of Computer Science, McGill University, January 1981). These authors have defined modality for polygons, both convex and nonconvex, but have not given an algorithm to compute the modality of a polygon, other than the obvious algorithm derived from the definition, which is quadratic in the number of vertices of the polygon. Our paper gives a modality-determination algorithm for convex polygons whose running time is linear in the sum of the number of vertices and the total modality of the polygon. As a special case, we can test if a convex polygon is unimodal (a term introduced by Avis et al.) in time O(n) for a polygon with n vertices. This latter result is shown to be optimal to within a constant factor. We then extend our technique to nonconvex polygons and derive a modality-determination algorithm which is better than the obvious algorithm, but probably not optimal. We conclude by posing some open problems and indicating a connection between modality determination and a range query problem which has received some attention in the Computational Geometry literature.     

Hidden Convex Minimization

A class of nonconvex minimization problems can be classified as hidden convex minimization problems. A nonconvex minimization problem is called a hidden convex minimization problem if there exists an equivalent transformation such that the equivalent transformation of it is a convex minimization problem. Sufficient conditions that are independent of transformations are derived in this paper for identifying such a class of seemingly nonconvex minimization problems that are equivalent to convex minimization problems. Thus, a global optimality can be achieved for this class of hidden convex optimization problems by using local search methods. The results presented in this paper extend the reach of convex minimization by identifying its equivalent with a nonconvex representation.