共查询到20条相似文献,搜索用时 15 毫秒
1.
This paper addresses the problem of generating strong convex relaxations of Mixed Integer Quadratically Constrained Programming (MIQCP) problems. MIQCP problems are very difficult because they combine two kinds of non- convexities: integer variables and non-convex quadratic constraints. To produce strong relaxations of MIQCP problems, we use techniques from disjunctive programming and the lift-and-project methodology. In particular, we propose new methods for generating valid inequalities from the equation Y = x x T . We use the non-convex constraint ${ Y - x x^T \preccurlyeq 0}$ to derive disjunctions of two types. The first ones are directly derived from the eigenvectors of the matrix Y ? x x T with positive eigenvalues, the second type of disjunctions are obtained by combining several eigenvectors in order to minimize the width of the disjunction. We also use the convex SDP constraint ${ Y - x x^T \succcurlyeq 0}$ to derive convex quadratic cuts, and we combine both approaches in a cutting plane algorithm. We present computational results to illustrate our findings. 相似文献
2.
Azuma Godai Fukuda Mituhiro Kim Sunyoung Yamashita Makoto 《Journal of Global Optimization》2022,82(2):243-262
Journal of Global Optimization - We study the exactness of the semidefinite programming (SDP) relaxation of quadratically constrained quadratic programs (QCQPs). With the aggregate sparsity matrix... 相似文献
3.
Robert G. Jeroslow 《Annals of Operations Research》1988,12(1):241-276
We study the formation of mixed-integer programming (MIP) constraints through the development of constructions which syntactically parallel the set operations of union, intersection, Cartesian product, and linear affine transformation. In this manner, we are able to both modularize the work of constructing representations (as the representations for base sets of a composite construction need not be disjunctively derived) and to make connections to certain of the logic-based approaches to artificial intelligence which utilize the intersection (and) and union (or) operations. We provide results which allow one to calculate the linear relaxation of a composite construction, in terms of set operations on the relaxation of the base sets. We are also able to compare the size of the relaxations for different formulations of the same MIP set, when these different formulations arise from one another through distributive laws. Utilizing these results, we generalize the Davis-Putnam algorithm of propositional logic to an MIP form, and answer a question regarding the relative efficiency of two versions of this algorithm. In this context, the subroutines of the logic algorithm correspond to list processing subroutines for MIP to be used prior to running linear programs. They are similar in nature to preprocessing routines, wherein entire MIP constraint sets are manipulated as formal symbols of logic.This work has been partially supported by National Science Foundation Grant MCS-8304075. 相似文献
4.
Samuel Burer Sunyoung Kim Masakazu Kojima 《Computational Optimization and Applications》2014,59(1-2):27-45
We introduce a new relaxation framework for nonconvex quadratically constrained quadratic programs (QCQPs). In contrast to existing relaxations based on semidefinite programming (SDP), our relaxations incorporate features of both SDP and second order cone programming (SOCP) and, as a result, solve more quickly than SDP. A downside is that the calculated bounds are weaker than those gotten by SDP. The framework allows one to choose a block-diagonal structure for the mixed SOCP-SDP, which in turn allows one to control the speed and bound quality. For a fixed block-diagonal structure, we also introduce a procedure to improve the bound quality without increasing computation time significantly. The effectiveness of our framework is illustrated on a large sample of QCQPs from various sources. 相似文献
5.
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. 相似文献
6.
7.
Laurence A. Wolsey 《Mathematical Programming》2003,97(1-2):423-447
We examine progress over the last fifteen years in finding strong valid inequalities and tight extended formulations for
simple mixed integer sets lying both on the ``easy' and ``hard' sides of the complexity frontier. Most progress has been
made in studying sets arising from knapsack and single node flow sets, and a variety of sets motivated by different lot-sizing
models. We conclude by citing briefly some of the more intriguing new avenues of research.
Received: January 15, 2003 / Accepted: April 10, 2003
Published online: May 28, 2003
Key words. mixed integer programming – strong valid inequalities – convex hull – extended formulations – single node flow sets – lot-sizing
This paper presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian
State, Prime Minister's Office, Science Policy Programming. The scientific responsibility is assumed by the authors.
Research carried out with financial support of the project TMR-DONET nr. ERB FMRX–CT98–0202 of the European Union. 相似文献
8.
In this paper we study robust convex quadratically constrained programs, a subset of the class of robust convex programs introduced by Ben-Tal and Nemirovski [4]. In contrast to [4], where it is shown that such robust problems can be formulated as semidefinite programs, our focus in this paper is to identify uncertainty sets that allow this class of problems to be formulated as second-order cone programs (SOCP). We propose three classes of uncertainty sets for which the robust problem can be reformulated as an explicit SOCP and present examples where these classes of uncertainty sets are natural.
Research partially supported by DOE grant GE-FG01-92ER-25126, NSF grants DMS-94-14438, CDA-97-26385, DMS-01-04282 and ONR grant N000140310514.Research partially supported by NSF grants CCR-00-09972, DMS-01-04282 and ONR grant N000140310514. 相似文献
9.
Kurt M. Anstreicher 《Mathematical Programming》2012,136(2):233-251
We consider convex relaxations for the problem of minimizing a (possibly nonconvex) quadratic objective subject to linear and (possibly nonconvex) quadratic constraints. Let $\mathcal{F }$ denote the feasible region for the linear constraints. We first show that replacing the quadratic objective and constraint functions with their convex lower envelopes on $\mathcal{F }$ is dominated by an alternative methodology based on convexifying the range of the quadratic form $\genfrac(){0.0pt}{}{1}{x}\genfrac(){0.0pt}{}{1}{x}^T$ for $x\in \mathcal{F }$ . We next show that the use of ?? $\alpha $ BB?? underestimators as computable estimates of convex lower envelopes is dominated by a relaxation of the convex hull of the quadratic form that imposes semidefiniteness and linear constraints on diagonal terms. Finally, we show that the use of a large class of D.C. (??difference of convex??) underestimators is dominated by a relaxation that combines semidefiniteness with RLT constraints. 相似文献
10.
Shabbir Ahmed 《Optimization Letters》2014,8(1):1-12
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. 相似文献
11.
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. 相似文献
12.
This paper is about set packing relaxations of combinatorial optimization problems associated with acyclic digraphs and linear orderings, cuts and multicuts, and set
packings themselves. Families of inequalities that are valid for such a relaxation as well as the associated separation routines
carry over to the problems under investigation.
Received: September 1997 / Accepted: November 1999?Published online June 8, 2000 相似文献
13.
At the intersection of nonlinear and combinatorial optimization, quadratic programming has attracted significant interest
over the past several decades. A variety of relaxations for quadratically constrained quadratic programming (QCQP) can be
formulated as semidefinite programs (SDPs). The primary purpose of this paper is to present a systematic comparison of SDP
relaxations for QCQP. Using theoretical analysis, it is shown that the recently developed doubly nonnegative relaxation is
equivalent to the Shor relaxation, when the latter is enhanced with a partial first-order relaxation-linearization technique.
These two relaxations are shown to theoretically dominate six other SDP relaxations. A computational comparison reveals that
the two dominant relaxations require three orders of magnitude more computational time than the weaker relaxations, while
providing relaxation gaps averaging 3% as opposed to gaps of up to 19% for weaker relaxations, on 700 randomly generated problems
with up to 60 variables. An SDP relaxation derived from Lagrangian relaxation, after the addition of redundant nonlinear constraints
to the primal, achieves gaps averaging 13% in a few CPU seconds. 相似文献
14.
In this paper, we discuss complex convex quadratically constrained optimization with uncertain data. Using S-Lemma, we show that the robust counterpart of complex convex quadratically constrained optimization with ellipsoidal or intersection-of-two-ellipsoids uncertainty set leads to a complex semidefinite program. By exploring the approximate S-Lemma, we give a complex semidefinite program which approximates the NP-hard robust counterpart of complex convex quadratic optimization with intersection-of-ellipsoids uncertainty set. 相似文献
15.
Faiz A. Al-Khayyal Christian Larsen Timothy Van Voorhis 《Journal of Global Optimization》1995,6(3):215-230
We present an algorithm for finding approximate global solutions to quadratically constrained quadratic programming problems. The method is based on outer approximation (linearization) and branch and bound with linear programming subproblems. When the feasible set is non-convex, the infinite process can be terminated with an approximate (possibly infeasible) optimal solution. We provide error bounds that can be used to ensure stopping within a prespecified feasibility tolerance. A numerical example illustrates the procedure. Computational experiments with an implementation of the procedure are reported on bilinearly constrained test problems with up to sixteen decision variables and eight constraints.This research was supported in part by National Science Foundation Grant DDM-91-14489. 相似文献
16.
17.
We propose verifiable necessary and sufficient conditions for the solution existence of a convex quadratic program whose constraint
set is defined by finitely many convex linear-quadratic inequalities. A related stability analysis of the problem is also
considered. 相似文献
18.
Maziar Salahi 《Central European Journal of Operations Research》2010,18(2):181-187
In this paper, first we show that for rank deficient matrices, the optimal solution of a single equality constrained quadratic minimization problem can be found by relaxing the equality constraint to the inequality one, which makes the problem a convex problem. Then we show that for full rank matrices, an optimal solution can be obtained using semidefinite optimization framework. 相似文献
19.
Jeff Linderoth 《Mathematical Programming》2005,103(2):251-282
We propose a branch-and-bound algorithm for solving nonconvex quadratically-constrained quadratic programs. The algorithm is novel in that branching is done by partitioning the feasible region into the Cartesian product of two-dimensional triangles and rectangles. Explicit formulae for the convex and concave envelopes of bilinear functions over triangles and rectangles are derived and shown to be second-order cone representable. The usefulness of these new relaxations is demonstrated both theoretically and computationally. 相似文献
20.
Computational Optimization and Applications - We propose a Jacobi-style distributed algorithm to solve convex, quadratically constrained quadratic programs (QCQPs), which arise from a broad range... 相似文献