On nonconvex optimization problems with separated nonconvex variables

A mathematical programming problem is said to have separated nonconvex variables when the variables can be divided into two groups: x=(x ₁,...,x _n ) and y=( y ₁,...,y _n ), such that the objective function and any constraint function is a sum of a convex function of (x, y) jointly and a nonconvex function of x alone. A method is proposed for solving a class of such problems which includes Lipschitz optimization, reverse convex programming problems and also more general nonconvex optimization problems.     

An interior point method for general large-scale quadratic programming problems

In this paper, we present an interior point algorithm for solving both convex and nonconvex quadratic programs. The method, which is an extension of our interior point work on linear programming problems efficiently solves a wide class of largescale problems and forms the basis for a sequential quadratic programming (SQP) solver for general large scale nonlinear programs. The key to the algorithm is a three-dimensional cost improvement subproblem, which is solved at every interation. We have developed an approximate recentering procedure and a novel, adaptive big-M Phase I procedure that are essential to the sucess of the algorithm. We describe the basic method along with the recentering and big-M Phase I procedures. Details of the implementation and computational results are also presented.Contribution of the National Institute of Standards and Tedchnology and not subject to copyright in the United States. This research was supported in part by ONR Contract N-0014-87-F0053.     

Canonical dual least square method for solving general nonlinear systems of quadratic equations

This paper presents a canonical dual approach for solving general nonlinear algebraic systems. By using least square method, the nonlinear system of m-quadratic equations in n-dimensional space is first formulated as a nonconvex optimization problem. We then proved that, by the canonical duality theory developed by the second author, this nonconvex problem is equivalent to a concave maximization problem in ℝ ^m , which can be solved easily by well-developed convex optimization techniques. Both existence and uniqueness of global optimal solutions are discussed, and several illustrative examples are presented.     

Optimizing a polyhedral-semidefinite relaxation of completely positive programs

It has recently been shown (Burer, Math Program 120:479–495, 2009) that a large class of NP-hard nonconvex quadratic programs (NQPs) can be modeled as so-called completely positive programs, i.e., the minimization of a linear function over the convex cone of completely positive matrices subject to linear constraints. Such convex programs are NP-hard in general. A basic tractable relaxation is gotten by approximating the completely positive matrices with doubly nonnegative matrices, i.e., matrices which are both nonnegative and positive semidefinite, resulting in a doubly nonnegative program (DNP). Optimizing a DNP, while polynomial, is expensive in practice for interior-point methods. In this paper, we propose a practically efficient decomposition technique, which approximately solves the DNPs while simultaneously producing lower bounds on the original NQP. We illustrate the effectiveness of our approach for solving the basic relaxation of box-constrained NQPs (BoxQPs) and the quadratic assignment problem. For one quadratic assignment instance, a best-known lower bound is obtained. We also incorporate the lower bounds within a branch-and-bound scheme for solving BoxQPs and the quadratic multiple knapsack problem. In particular, to the best of our knowledge, the resulting algorithm for globally solving BoxQPs is the most efficient to date.     

An interior-point method for fractional programs with convex constraints

We present an interior-point method for a class of fractional programs with convex constraints. The proposed algorithm converges at a polynomial rate, similarly as in the case of a convex problem, even though fractional programs are only pseudo-convex. Here, the rate of convergence is measured in terms of the area of two-dimensional convex setsC _k containing the origin and certain projections of the optimal points, and the area ofC _k is reduced by a constant factorc < 1 at each iteration. The factorc depends only on the self-concordance parameter of a barrier function associated with the feasible set. We present an outline of a practical implementation of the proposed method, and we report results of some preliminary numerical experiments.Corresponding author.     

Global minimization of a generalized convex multiplicative function

This paper discusses an algorithm for generalized convex multiplicative programming problems, a special class of nonconvex minimization problems in which the objective function is expressed as a sum ofp products of two convex functions. It is shown that this problem can be reduced to a concave minimization problem with only 2p variables. An outer approximation algorithm is proposed for solving the resulting problem.     

A reformulation framework for global optimization

In this paper, we present a global optimization method for solving nonconvex mixed integer nonlinear programming (MINLP) problems. A convex overestimation of the feasible region is obtained by replacing the nonconvex constraint functions with convex underestimators. For signomial functions single-variable power and exponential transformations are used to obtain the convex underestimators. For more general nonconvex functions two versions of the so-called αBB-underestimator, valid for twice-differentiable functions, are integrated in the actual reformulation framework. However, in contrast to what is done in branch-and-bound type algorithms, no direct branching is performed in the actual algorithm. Instead a piecewise convex reformulation is used to convexify the entire problem in an extended variable-space, and the reformulated problem is then solved by a convex MINLP solver. As the piecewise linear approximations are made finer, the solution to the convexified and overestimated problem will form a converging sequence towards a global optimal solution. The result is an easily-implementable algorithm for solving a very general class of optimization problems.     

The DC (Difference of Convex Functions) Programming and DCA Revisited with DC Models of Real World Nonconvex Optimization Problems

The DC programming and its DC algorithm (DCA) address the problem of minimizing a function f=g−h (with g,h being lower semicontinuous proper convex functions on R ⁿ ) on the whole space. Based on local optimality conditions and DC duality, DCA was successfully applied to a lot of different and various nondifferentiable nonconvex optimization problems to which it quite often gave global solutions and proved to be more robust and more efficient than related standard methods, especially in the large scale setting. The computational efficiency of DCA suggests to us a deeper and more complete study on DC programming, using the special class of DC programs (when either g or h is polyhedral convex) called polyhedral DC programs. The DC duality is investigated in an easier way, which is more convenient to the study of optimality conditions. New practical results on local optimality are presented. We emphasize regularization techniques in DC programming in order to construct suitable equivalent DC programs to nondifferentiable nonconvex optimization problems and new significant questions which have to be answered. A deeper insight into DCA is introduced which really sheds new light on DCA and could partly explain its efficiency. Finally DC models of real world nonconvex optimization are reported.     

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.

     

An outer approximation method for minimizing the product of several convex functions on a convex set

This paper addresses the minimization of the product ofp convex functions on a convex set. It is shown that this nonconvex problem can be converted to a concave minimization problem withp variables, whose objective function value is determined by solving a convex minimization problem. An outer approximation method is proposed for obtaining a global minimum of the resulting problem. Computational experiments indicate that this algorithm is reasonable efficient whenp is less than 4.This research was partly supported by Grant-in-Aid for Scientific Research of the Ministry of Education, Science and Culture, Grant No. (C)03832018 and (C)04832010.     

A generalized Dantzig—Wolfe decomposition principle for a class of nonconvex programming problems

Since Dantzig—Wolfe's pioneering contribution, the decomposition approach using a pricing mechanism has been developed for a wide class of mathematical programs. For convex programs a linear space of Lagrangean multipliers is enough to define price functions. For general mathematical programs the price functions could be defined by using a subclass of nondecreasing functions. However the space of nondecreasing functions is no longer finite dimensional. In this paper we consider a specific nonconvex optimization problem min {f(x):h _j (x)g(x),j=1, ,m, xX}, wheref(·),h _j (·) andg(·) are finite convex functions andX is a closed convex set. We generalize optimal price functions for this problem in such a way that the parameters of generalized price functions are defined in a finite dimensional space. Combining convex duality and a nonconvex duality we can develop a decomposition method to find a globally optimal solution.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.     

Successive projection method for solving the unbalanced Procrustes problem

We present a successive projection method for solving the unbalanced Procrustes problem: given matrix A∈Rn×n and B∈Rn×k, n>k, minimize the residual‖AQ-B‖F with the orthonormal constraint QTQ = Ik on the variant Q∈Rn×k. The presented algorithm consists of solving k least squares problems with quadratic constraints and an expanded balance problem at each sweep. We give a detailed convergence analysis. Numerical experiments reported in this paper show that our new algorithm is superior to other existing methods.     

A General Duality Scheme for Nonconvex Minimization Problems with a Strict Inequality Constraint

We establish a duality formula for the problem Minimize f(x)+g(x) for h(x)+k(x)<0 where g, k are extended-real-valued convex functions and f, h belong to the class of functions that can be written as the lower envelope of an arbitrary family of convex functions. Applications in d.c. and Lipschitzian optimization are given.     

The complementary convex structure in global optimization

We show the importance of exploiting the complementary convex structure for efficiently solving a wide class of specially structured nonconvex global optimization problems. Roughly speaking, a specific feature of these problems is that their nonconvex nucleus can be transformed into a complementary convex structure which can then be shifted to a subspace of much lower dimension than the original underlying space. This approach leads to quite efficient algorithms for many problems of practical interest, including linear and convex multiplicative programming problems, concave minimization problems with few nonlinear variables, bilevel linear optimization problems, etc...     

Randomized algorithm for the k-server problem on decomposable spaces

We study the randomized k-server problem on metric spaces consisting of widely separated subspaces. We give a method which extends existing algorithms to larger spaces with the growth rate of the competitive quotients being at most O(logk). This method yields o(k)-competitive algorithms solving the randomized k-server problem for some special underlying metric spaces, e.g. HSTs of “small” height (but unbounded degree). HSTs are important tools for probabilistic approximation of metric spaces.     

Minimum Distance to the Complement of a Convex Set: Duality Result

The subject of this paper is to study the problem of the minimum distance to the complement of a convex set. Nirenberg has stated a duality theorem treating the minimum norm problem for a convex set. We state a duality result which presents some analogy with the Nirenberg theorem, and we apply this result to polyhedral convex sets. First, we assume that the polyhedral set is expressed as the intersection of some finite collection of m given half-spaces. We show that a global solution is determined by solving m convex programs. If the polyhedral set is expressed as the convex hull of a given finite set of extreme points, we show that a global minimum for a polyhedral norm is obtained by solving a finite number of linear programs.     

Duality Bound Method for the General Quadratic Programming Problem with Quadratic Constraints

The purpose of this article is to develop a branch-and-bound algorithm using duality bounds for the general quadratically-constrained quadratic programming problem and having the following properties: (i) duality bounds are computed by solving ordinary linear programs; (ii) they are at least as good as the lower bounds obtained by solving relaxed problems, in which each nonconvex function is replaced by its convex envelope; (iii) standard convergence properties of branch-and-bound algorithms for nonconvex global optimization problems are guaranteed. Numerical results of preliminary computational experiments for the case of one quadratic constraint are reported.     

Canonical Dual Transformation Method and Generalized Triality Theory in Nonsmooth Global Optimization*

This paper presents, within a unified framework, a potentially powerful canonical dual transformation method and associated generalized duality theory in nonsmooth global optimization. It is shown that by the use of this method, many nonsmooth/nonconvex constrained primal problems in ⁿ can be reformulated into certain smooth/convex unconstrained dual problems in ^m with m n and without duality gap, and some NP-hard concave minimization problems can be transformed into unconstrained convex minimization dual problems. The extended Lagrange duality principles proposed recently in finite deformation theory are generalized suitable for solving a large class of nonconvex and nonsmooth problems. The very interesting generalized triality theory can be used to establish nice theoretical results and to develop efficient alternative algorithms for robust computations.     

Sparse Convex Clustering

Convex clustering, a convex relaxation of k-means clustering and hierarchical clustering, has drawn recent attentions since it nicely addresses the instability issue of traditional nonconvex clustering methods. Although its computational and statistical properties have been recently studied, the performance of convex clustering has not yet been investigated in the high-dimensional clustering scenario, where the data contains a large number of features and many of them carry no information about the clustering structure. In this article, we demonstrate that the performance of convex clustering could be distorted when the uninformative features are included in the clustering. To overcome it, we introduce a new clustering method, referred to as Sparse Convex Clustering, to simultaneously cluster observations and conduct feature selection. The key idea is to formulate convex clustering in a form of regularization, with an adaptive group-lasso penalty term on cluster centers. To optimally balance the trade-off between the cluster fitting and sparsity, a tuning criterion based on clustering stability is developed. Theoretically, we obtain a finite sample error bound for our estimator and further establish its variable selection consistency. The effectiveness of the proposed method is examined through a variety of numerical experiments and a real data application. Supplementary material for this article is available online.     

Splitting Methods for Convex Clustering

Clustering is a fundamental problem in many scientific applications. Standard methods such as k-means, Gaussian mixture models, and hierarchical clustering, however, are beset by local minima, which are sometimes drastically suboptimal. Recently introduced convex relaxations of k-means and hierarchical clustering shrink cluster centroids toward one another and ensure a unique global minimizer. In this work, we present two splitting methods for solving the convex clustering problem. The first is an instance of the alternating direction method of multipliers (ADMM); the second is an instance of the alternating minimization algorithm (AMA). In contrast to previously considered algorithms, our ADMM and AMA formulations provide simple and unified frameworks for solving the convex clustering problem under the previously studied norms and open the door to potentially novel norms. We demonstrate the performance of our algorithm on both simulated and real data examples. While the differences between the two algorithms appear to be minor on the surface, complexity analysis and numerical experiments show AMA to be significantly more efficient. This article has supplementary materials available online.