An efficient compact quadratic convex reformulation for general integer quadratic programs

We address the exact solution of general integer quadratic programs with linear constraints. These programs constitute a particular case of mixed-integer quadratic programs for which we introduce in Billionnet et al. (Math. Program., 2010) a general solution method based on quadratic convex reformulation, that we called MIQCR. This reformulation consists in designing an equivalent quadratic program with a convex objective function. The problem reformulated by MIQCR has a relatively important size that penalizes its solution time. In this paper, we propose a convex reformulation less general than MIQCR because it is limited to the general integer case, but that has a significantly smaller size. We call this approach Compact Quadratic Convex Reformulation (CQCR). We evaluate CQCR from the computational point of view. We perform our experiments on instances of general integer quadratic programs with one equality constraint. We show that CQCR is much faster than MIQCR and than the general non-linear solver BARON (Sahinidis and Tawarmalani, User??s manual, 2010) to solve these instances. Then, we consider the particular class of binary quadratic programs. We compare MIQCR and CQCR on instances of the Constrained Task Assignment Problem. These experiments show that CQCR can solve instances that MIQCR and other existing methods fail to solve.     

Reformulation and solution approach for non-separable integer quadratic programs

We consider quadratic programs with pure general integer variables. The objective function is quadratic and convex and the constraints are linear. An exact solution approach is proposed. It is decomposed into two phases. In the first phase, the initial problem is reformulated into an equivalent problem with a separable objective function. This is done by use of a Gauss decomposition of the Hessian matrix of the initial problem and requires the addition of some continuous variables and constraints. In the second phase, the reformulated problem is linearized by an approximation of each squared term by a set of K linear functions that correspond to the tangents of a hyperbola in K points. We give a proof of the intuitive property that when K is large enough, the optimal value of the obtained linear program is very close to optimal value of the two previous problems, the initial problem and the reformulated separable problem. The reminder is dedicated to the implementation of a branch-and-bound algorithm for the solution of linearized problem, and its application to a set of instances. Several points are considered among which choice of the right value for parameter K and the implementation of a sophisticated heuristic solution algorithm. The numerical comparison is done with CPLEX 12.2 since, in this case, the initial problem as well as the problem reformulated by the first step can be solved by CPLEX. We show that with our approach, the total CPU time is divided by a factor ranging from 1.2 to 131.6 for instances with 40–60 variables.     

Lipschitz continuity of the optimal value function and KKT solution set in indefinite quadratic programs

When all the involved data in indefinite quadratic programs change simultaneously,we show the locally Lipschtiz continuity of the KKT set of the quadratic programming problem firstly, then we establish the locally Lipschtiz continuity of the KKT solution set. Finally, the similar conclusion for the corresponding optimal value function is obtained.     

G恰当有效点集和G恰当有效解集的连通性

与多目标规划问题的G恰当有效解相应，引进了集合的G恰当有效点的概念，并互研究了G恰当有效点集和G恰当有效解集的连通性．利用所得的结果，还获得多目标规划问题的Pareto有效解集是连通的一个新的结论。     

Stability of the solution of definite quadratic programs

This paper studies how the solution of the problem of minimizingQ(x) = 1/2x ^T Kx – k ^T x subject toGx g andDx = d behaves whenK, k, G, g, D andd are perturbed, say by terms of size, assuming thatK is positive definite. It is shown that in general the solution moves by roughly ifG, g, D andd are not perturbed; whenG, g, D andd are in fact perturbed, much stronger hypotheses allow one to show that the solution moves by roughly. Many of these results can be extended to more general, nonquadratic, functionals.This research was supported in part by contract number N00014-67-A-0126-0015, NR 044-425 from the Office of Naval Research.     

A direct active set algorithm for large sparse quadratic programs with simple bounds

We show how a direct active set method for solving definite and indefinite quadratic programs with simple bounds can be efficiently implemented for large sparse problems. All of the necessary factorizations can be carried out in a static data structure that is set up before the numeric computation begins. The space required for these factorizations is no larger than that required for a single sparse Cholesky factorization of the Hessian of the quadratic. We propose several improvements to this basic algorithm: a new way to find a search direction in the indefinite case that allows us to free more than one variable at a time and a new heuristic method for finding a starting point. These ideas are motivated by the two-norm trust region problem. Additionally, we also show how projection techniques can be used to add several constraints to the active set at each iteration. Our experimental results show that an algorithm with these improvements runs much faster than the basic algorithm for positive definite problems and finds local minima with lower function values for indefinite problems.Research partially supported by the Applied Mathematical Sciences Research Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under grant DE-FG02-86ER25013.A000.     

A Solver for large-scale indefinite quadratic programs

Based on an active set strategy, a method for solving linearly constrained indefinite quadratic programs to solve the corresponding system of equations at each iteration is presented. The algorithm takes two descent directions to strictly decrease the value of objective function and obtains a suitable step to maintain feasibility. Computational results on a range of quadratic test problems are given.     

Convex dual for quadratic concave fractional programs

For a fractional program with a quadratic numerator and an arbitrary concave denominator, a new convex dual program is derived. Concepts of conjugate duality are used to obtain an explicit representation of the dual.The authors are grateful to two anonymous referees and the Associate Editor for their comments.     

Gap inequalities for non-convex mixed-integer quadratic programs

Laurent and Poljak introduced a very general class of valid linear inequalities, called gap inequalities, for the max-cut problem. We show that an analogous class of inequalities can be defined for general non-convex mixed-integer quadratic programs. These inequalities dominate some inequalities arising from a natural semidefinite relaxation.     

Controlled perturbations for quadratically constrained quadratic programs

Consider a minimization problem of a convex quadratic function of several variables over a set of inequality constraints of the same type of function. The duel program is a maximization problem with a concave objective function and a set of constrains that are essentially linear. However, the objective function is not differentiable over the constraint region. In this paper, we study a general theory of dual perturbations and derive a fundamental relationship between a perturbed dual program and the original problem. Based on this relationship, we establish a perturbation theory to display that a well-controlled perturbation on the dual program can overcome the nondifferentiability issue and generate an ε-optimal dual solution for an arbitrarily small number ε. A simple linear program is then constructed to make an easy conversion from the dual solution to a corresponding ε-optimal primal solution. Moreover, a numerical example is included to illustrate the potential of this controlled perturbation scheme.     

New reformulations for probabilistically constrained quadratic programs

The mixed integer quadratic programming (MIQP) reformulation by Zheng, Sun, Li, and Cui (2012) for probabilistically constrained quadratic programs (PCQP) recently published in EJOR significantly dominates the standard MIQP formulation ( and ) which has been widely adopted in the literature. Stimulated by the dimensionality problem which Zheng et al. (2012) acknowledge themselves for their reformulations, we study further the characteristics of PCQP and develop new MIQP reformulations for PCQP with fewer variables and constraints. The results from numerical tests demonstrate that our reformulations clearly outperform the state-of-the-art MIQP in Zheng et al. (2012).     

Characterizations of robust solution set of convex programs with uncertain data

In this paper, we study convex programming problems with data uncertainty in both the objective function and the constraints. Under the framework of robust optimization, we employ a robust regularity condition, which is much weaker than the ones in the open literature, to establish various properties and characterizations of the set of all robust optimal solutions of the problems. These are expressed in term of subgradients, Lagrange multipliers and epigraphs of conjugate functions. We also present illustrative examples to show the significances of our theoretical results.     

Structure of the first-order solution set for a class of nonlinear programs with parameters

This paper studies the set of first-order solutions of a family of nonlinear programs in which the inequality constraints are fixed but the right hand side of the equality constraints varies. It is shown that under certain conditions this set is a topological manifold. The results are applied to the problem of describing the set of first-order Pareto optima in a pure exchange economy with monotone utility functions.     

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.     

A heuristic for quadratic Boolean programs with applications to quadratic assignment problems

A heuristic for quadratic Boolean programs is presented. Computational tests with quadratic assignment problems (QAP) showed that it finds very good suboptimal solutions in moderate time and behaves computationally stable. In the appendix a FORTRAN-program for QAP is listed which improves an earlier code published by Burkard and Derigs.     

Reduction of indefinite quadratic programs to bilinear programs

Indefinite quadratic programs with quadratic constraints can be reduced to bilinear programs with bilinear constraints by duplication of variables. Such reductions are studied in which: (i) the number of additional variables is minimum or (ii) the number of complicating variables, i.e., variables to be fixed in order to obtain a linear program, in the resulting bilinear program is minimum. These two problems are shown to be equivalent to a maximum bipartite subgraph and a maximum stable set problem respectively in a graph associated with the quadratic program. Non-polynomial but practically efficient algorithms for both reductions are thus obtaine.d Reduction of more general global optimization problems than quadratic programs to bilinear programs is also briefly discussed.     

A new Pareto set generating method for multi-criteria optimization problems

This paper proposes a new classical method to capture the complete Pareto set of a multi-criteria optimization problem (MOP) even without having any prior information about the location of Pareto surface. The solutions obtained through the proposed method are globally Pareto optimal. Moreover, each and every global Pareto optimal point is within the attainable range. This paper also suggests a procedure to ensure the proper Pareto optimality of the outcomes if slight modifications are allowed in the constraint set of the MOP under consideration. Among the set of all outcomes, the proposed method can effectively detect the regions of unbounded trade-offs between the criteria, if they exist.     

Simple and efficient FE for quadratic functions

Designs, Codes and Cryptography - This paper presents two functional encryption schemes for quadratic functions (or degree-2 polynomials) achieving simulation-based security in the semi-adaptive...