Tightening a copositive relaxation for standard quadratic optimization problems

We focus in this paper the problem of improving the semidefinite programming (SDP) relaxations for the standard quadratic optimization problem (standard QP in short) that concerns with minimizing a quadratic form over a simplex. We first analyze the duality gap between the standard QP and one of its SDP relaxations known as “strengthened Shor’s relaxation”. To estimate the duality gap, we utilize the duality information of the SDP relaxation to construct a graph G ^?. The estimation can be then reduced to a two-phase problem of enumerating first all the minimal vertex covers of G ^? and solving next a family of second-order cone programming problems. When there is a nonzero duality gap, this duality gap estimation can lead to a strictly tighter lower bound than the strengthened Shor’s SDP bound. With the duality gap estimation improving scheme, we develop further a heuristic algorithm for obtaining a good approximate solution for standard QP.     

Quartic Formulation of Standard Quadratic Optimization Problems

A standard quadratic optimization problem (StQP) consists of finding the largest or smallest value of a (possibly indefinite) quadratic form over the standard simplex which is the intersection of a hyperplane with the positive orthant. This NP-hard problem has several immediate real-world applications like the Maximum-Clique Problem, and it also occurs in a natural way as a subproblem in quadratic programming with linear constraints. To get rid of the (sign) constraints, we propose a quartic reformulation of StQPs, which is a special case (degree four) of a homogeneous program over the unit sphere. It turns out that while KKT points are not exactly corresponding to each other, there is a one-to-one correspondence between feasible points of the StQP satisfying second-order necessary optimality conditions, to the counterparts in the quartic homogeneous formulation. We supplement this study by showing how exact penalty approaches can be used for finding local solutions satisfying second-order necessary optimality conditions to the quartic problem: we show that the level sets of the penalty function are bounded for a finite value of the penalty parameter which can be fixed in advance, thus establishing exact equivalence of the constrained quartic problem with the unconstrained penalized version.     

Sparse solutions to random standard quadratic optimization problems

The standard quadratic optimization problem (StQP) refers to the problem of minimizing a quadratic form over the standard simplex. Such a problem arises from numerous applications and is known to be NP-hard. In this paper we focus on a special scenario of the StQP where all the elements of the data matrix Q are independently identically distributed and follow a certain distribution such as uniform or exponential distribution. We show that the probability that such a random StQP has a global optimal solution with k nonzero elements decays exponentially in k. Numerical evaluation of our theoretical finding is discussed as well.     

Solving Standard Quadratic Optimization Problems via Linear, Semidefinite and Copositive Programming

The problem of minimizing a (non-convex) quadratic function over the simplex (the standard quadratic optimization problem) has an exact convex reformulation as a copositive programming problem. In this paper we show how to approximate the optimal solution by approximating the cone of copositive matrices via systems of linear inequalities, and, more refined, linear matrix inequalities (LMI's). In particular, we show that our approach leads to a polynomial-time approximation scheme for the standard quadratic optimzation problem. This is an improvement on the previous complexity result by Nesterov who showed that a 2/3-approximation is always possible. Numerical examples from various applications are provided to illustrate our approach.     

A low-rank bilinear programming approach for sub-optimal solution of the quadratic assignment problem

This paper is concerned with a new approach for solving quadratic assignment problems (QAP). We first reformulate QAP as a concave quadratic programming problem and apply an outer approximation algorithm. In addition, an improvement routine is incorporated in the final stage of the algorithm. Computational experiments on a set of standard data demonstrate that this algorithm can yield favorable results with a relatively low computational effort.     

带交易费用的投资组合模型的割平面解法

本文讨论了带交易费用的投资组合模型，因对这一类带二次约束的线性优化问题没有特殊的处理方法，我们利用割平面法使这一非线性优化间题可通过解一系列线性规划问题来求解．     

A Method for Solving Certain Quadratic Programming Problems Arising in Nonsmooth Optimization

We present a finite algorithm for minimizing a piecewise linearconvex function augmented with a simple quadratic term. To solvethe dual problem, which is of least-squares form with an additionallinear term, we include in a standard active-set quadratic programmingalgorithm a new column-exchange strategy for treating positivesemidefinite problems. Numerical results are given for an implementationusing the Cholesky factorization.     

A cutting plane algorithm for MV portfolio selection model

This paper deals with a portfolio selection problem with fuzzy return rates. A possibilistic mean variance (FMVC) portfolio selection model was proposed. The possibilistic programming problem can be transformed into a linear optimal problem with an additional quadratic constraint by possibilistic theory. For such problems there are no special standard algorithms. We propose a cutting plane algorithm to solve (FMVC). The nonlinear programming problem can be solved by sequence linear programming problem. A numerical example is given to illustrate the behavior of the proposed model and algorithm.     

A clique algorithm for standard quadratic programming

A standard Quadratic Programming problem (StQP) consists in minimizing a (nonconvex) quadratic form over the standard simplex. For solving a StQP we present an exact and a heuristic algorithm, that are based on new theoretical results for quadratic and convex optimization problems. With these results a StQP is reduced to a constrained nonlinear minimum weight clique problem in an associated graph. Such a clique problem, which does not seem to have been studied before, is then solved with an exact and a heuristic algorithm. Some computational experience shows that our algorithms are able to solve StQP problems of at least one order of magnitude larger than those reported in the literature.     

A linear programming reformulation of the standard quadratic optimization problem

The problem of minimizing a quadratic form over the standard simplex is known as the standard quadratic optimization problem (SQO). It is NP-hard, and contains the maximum stable set problem in graphs as a special case. In this note, we show that the SQO problem may be reformulated as an (exponentially sized) linear program (LP). This reformulation also suggests a hierarchy of polynomial-time solvable LP’s whose optimal values converge finitely to the optimal value of the SQO problem. The hierarchies of LP relaxations from the literature do not share this finite convergence property for SQO, and we review the relevant counterexamples.     

Lagrangian decomposition and mixed-integer quadratic programming reformulations for probabilistically constrained quadratic programs

Probabilistically constrained quadratic programming (PCQP) problems arise naturally from many real-world applications and have posed a great challenge in front of the optimization society for years due to the nonconvex and discrete nature of its feasible set. We consider in this paper a special case of PCQP where the random vector has a finite discrete distribution. We first derive second-order cone programming (SOCP) relaxation and semidefinite programming (SDP) relaxation for the problem via a new Lagrangian decomposition scheme. We then give a mixed integer quadratic programming (MIQP) reformulation of the PCQP and show that the continuous relaxation of the MIQP is exactly the SOCP relaxation. This new MIQP reformulation is more efficient than the standard MIQP reformulation in the sense that its continuous relaxation is tighter than or at least as tight as that of the standard MIQP. We report preliminary computational results to demonstrate the tightness of the new convex relaxations and the effectiveness of the new MIQP reformulation.     

On standard quadratic programs with exact and inexact doubly nonnegative relaxations

Mathematical Programming - The problem of minimizing a (nonconvex) quadratic form over the unit simplex, referred to as a standard quadratic program, admits an exact convex conic formulation over...     

Convex relaxations and MIQCQP reformulations for a class of cardinality-constrained portfolio selection problems

In this paper we investigate a class of cardinality-constrained portfolio selection problems. We construct convex relaxations for this class of optimization problems via a new Lagrangian decomposition scheme. We show that the dual problem can be reduced to a second-order cone program problem which is tighter than the continuous relaxation of the standard mixed integer quadratically constrained quadratic program (MIQCQP) reformulation. We then propose a new MIQCQP reformulation which is more efficient than the standard MIQCQP reformulation in terms of the tightness of the continuous relaxations. Computational results are reported to demonstrate the tightness of the SOCP relaxation and the effectiveness of the new MIQCQP reformulation.     

An improved linearization strategy for zero-one quadratic programming problems

We present a new linearized model for the zero-one quadratic programming problem, whose size is linear in terms of the number of variables in the original nonlinear problem. Our derivation yields three alternative reformulations, each varying in model size and tightness. We show that our models are at least as tight as the one recently proposed in [7], and examine the theoretical relationship of our models to a standard linearization of the zero-one quadratic programming problem. Finally, we demonstrate the efficacy of solving each of these models on a set of randomly generated test instances.     

On Standard Quadratic Optimization Problems

A standard quadratic optimization problem (QP) consists of finding (global) maximizers of a quadratic form over the standard simplex. Standard QPs arise quite naturally in copositivity-based procedures which enable an escape from local solutions. Furthermore, several important applications yield optimization problems which can be cast into a standard QP in a straightforward way. As an example, a new continuous reformulation of the maximum weight clique problem in undirected graphs is presented which considerably improves previous attacks both as numerical stability and interpretation of the results are concerned. Apparently also for the first time, an equivalence between standard QPs and QPs on the positive orthant is established. Also, a recently presented global optimization procedure (GENF - genetical engineering via negative fitness) is shortly reviewed.     

Properties of the spectrum in the John problem on a freely floating submerged body in a finite basin

We consider a problem on the interaction of surface waves with a freely floating submerged body, which combines a spectral Steklov problem with a system of algebraic equations. We reduce this spectral problem to a quadratic pencil and then to the standard spectral equation for a self-adjoint operator in a certain Hilbert space. In addition to general properties of the spectrum, we investigate the asymptotics of eigenvalues and eigenvectors with respect to an intrinsic small parameter.     

Branch and bound algorithm for multidimensional scaling with city-block metric

A two level global optimization algorithm for multidimensional scaling (MDS) with city-block metric is proposed. The piecewise quadratic structure of the objective function is employed. At the upper level a combinatorial global optimization problem is solved by means of branch and bound method, where an objective function is defined as the minimum of a quadratic programming problem. The later is solved at the lower level by a standard quadratic programming algorithm. The proposed algorithm has been applied for auxiliary and practical problems whose global optimization counterpart was of dimensionality up to 24.     

Long-Step Path-Following Algorithm for Convex Quadratic Programming Problems in a Hilbert Space

We develop an interior-point technique for solving quadratic programming problems in a Hilbert space. As an example, we consider an application of these results to the linear-quadratic control problem with linear inequality constraints. It is shown that the Newton step in this situation is basically reduced to solving the standard linear-quadratic control problem.     

New and old bounds for standard quadratic optimization: dominance,equivalence and incomparability

A standard quadratic optimization problem (StQP) consists in minimizing a quadratic form over a simplex. Among the problems which can be transformed into a StQP are the general quadratic problem over a polytope, and the maximum clique problem in a graph. In this paper we present several new polynomial-time bounds for StQP ranging from very simple and cheap ones to more complex and tight constructions. The main tools employed in the conception and analysis of most bounds are Semidefinite Programming and decomposition of the objective function into a sum of two quadratic functions, each of which is easy to minimize. We provide a complete diagram of the dominance, incomparability, or equivalence relations among the bounds proposed in this and in previous works. In particular, we show that one of our new bounds dominates all the others. Furthermore, a specialization of such bound dominates Schrijver’s improvement of Lovász’s θ function bound for the maximum size of a clique in a graph.      

Design of a wind farm collection network when several cable types are available

In this article we consider a real-world problem submitted to us by the Hatch company. This problem consists of designing a collection network for a wind farm, assuming that the locations of the turbines and the potential cables are known, several cable types are available, and the cost of the energy that dissipates through the cables is known. We propose a mixed integer quadratic programme to model the network design problem and then linearize the quadratic programme because the latter is too difficult to solve using a standard mathematical programming software. We describe several classes of inequalities that strengthen the resulting mixed integer linear programme. Finally we use real-world data supplied by Hatch to carry out computational experiments with several versions of our model.