共查询到20条相似文献,搜索用时 125 毫秒
1.
Copositive optimization problems are particular conic programs: optimize linear forms over the copositive cone subject to
linear constraints. Every quadratic program with linear constraints can be formulated as a copositive program, even if some
of the variables are binary. So this is an NP-hard problem class. While most methods try to approximate the copositive cone
from within, we propose a method which approximates this cone from outside. This is achieved by passing to the dual problem,
where the feasible set is an affine subspace intersected with the cone of completely positive matrices, and this cone is approximated
from within. We consider feasible descent directions in the completely positive cone, and regularized strictly convex subproblems.
In essence, we replace the intractable completely positive cone with a nonnegative cone, at the cost of a series of nonconvex
quadratic subproblems. Proper adjustment of the regularization parameter results in short steps for the nonconvex quadratic
programs. This suggests to approximate their solution by standard linearization techniques. Preliminary numerical results
on three different classes of test problems are quite promising. 相似文献
2.
We consider semidefinite, copositive, and more general, set-semidefinite programming relaxations of general nonconvex quadratic problems. For the semidefinite case a comparison between the feasible set of the original program and the feasible set of the relaxation has been given by Kojima and Tunçel (SIAM J Optim 10(3):750–778, 2000). In this paper the comparison is presented for set-positive relaxations which contain copositive relaxations as a special case. 相似文献
3.
We propose in this paper a general D.C. decomposition scheme for constructing SDP relaxation formulations for a class of nonconvex
quadratic programs with a nonconvex quadratic objective function and convex quadratic constraints. More specifically, we use
rank-one matrices and constraint matrices to decompose the indefinite quadratic objective into a D.C. form and underestimate
the concave terms in the D.C. decomposition formulation in order to get a convex relaxation of the original problem. We show
that the best D.C. decomposition can be identified by solving an SDP problem. By suitably choosing the rank-one matrices and
the linear underestimation, we are able to construct convex relaxations that dominate Shor’s SDP relaxation and the strengthened
SDP relaxation. We then propose an extension of the D.C. decomposition to generate an SDP bound that is tighter than the SDP+RLT
bound when additional box constraints are present. We demonstrate via computational results that the optimal D.C. decomposition
schemes can generate both tight SDP bounds and feasible solutions with good approximation ratio for nonconvex quadratically
constrained quadratic problems. 相似文献
4.
An eigenvalue decomposition based branch-and-bound algorithm for nonconvex quadratic programming problems with convex quadratic constraints 总被引:1,自引:0,他引:1
In this paper, we propose a branch-and-bound algorithm for finding a global optimal solution for a nonconvex quadratic program with convex quadratic constraints (NQPCQC). We first reformulate NQPCQC by adding some nonconvex quadratic constraints induced by eigenvectors of negative eigenvalues associated with the nonconvex quadratic objective function to Shor’s semidefinite relaxation. Under the assumption of having a bounded feasible domain, these nonconvex quadratic constraints can be further relaxed into linear ones to form a special semidefinite programming relaxation. Then an efficient branch-and-bound algorithm branching along the eigendirections of negative eigenvalues is designed. The theoretic convergence property and the worst-case complexity of the proposed algorithm are proved. Numerical experiments are conducted on several types of quadratic programs to show the efficiency of the proposed method. 相似文献
5.
Florian Jarre 《Optimization Letters》2012,6(3):593-599
Burer has shown that completely positive relaxations of nonconvex quadratic programs with nonnegative and binary variables
are exact when the binary variables satisfy a so-called key assumption. Here we show that introducing binary slack variables
to obtain an equivalent problem that satisfies the key assumption will not improve the semidefinite relaxation. In contrast,
such slack variables will improve the doubly nonnegative relaxation, but the same improvement can be obtained in a simpler
fashion by adding certain linear inequality constraints. 相似文献
6.
Samuel Burer 《Mathematical Programming Computation》2010,2(1):1-19
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. 相似文献
7.
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. 相似文献
8.
Motivated by the fact that important real-life problems, such as the protein docking problem, can be accurately modeled by
minimizing a nonconvex piecewise-quadratic function, a nonconvex underestimator is constructed as the minimum of a finite
number of strictly convex quadratic functions. The nonconvex underestimator is generated by minimizing a linear function on
a reverse convex region and utilizes sample points from a given complex function to be minimized. The global solution of the
piecewise-quadratic underestimator is known exactly and gives an approximation to the global minimum of the original function.
Successive shrinking of the initial search region to which this procedure is applied leads to fairly accurate estimates, within
0.0060%, of the global minima of synthetic nonconvex functions for which the global minima are known. Furthermore, this process
can approximate a nonconvex protein docking function global minimum within four-figure relative accuracy in six refinement
steps. This is less than half the number of refinement steps required by previous models such as the convex kernel underestimator
(Mangasarian et al., Computational Optimization and Applications, to appear) and produces higher accuracy here. 相似文献
9.
Decomposition Methods for Solving Nonconvex Quadratic Programs via Branch and Bound* 总被引:1,自引:0,他引:1
The aim of this paper is to suggest branch and bound schemes, based on a relaxation of the objective function, to solve nonconvex
quadratic programs over a compact polyhedral feasible region. The various schemes are based on different d.c. decomposition
methods applied to the quadratic objective function. To improve the tightness of the relaxations, we also suggest solving
the relaxed problems with an algorithm based on the so called “optimal level solutions” parametrical approach.
*This paper has been partially supported by M.I.U.R. and C.N.R. 相似文献
10.
In this paper, a new global optimization method is proposed for an optimization problem with twice-differentiable objective
and constraint functions of a single variable. The method employs a difference of convex underestimator and a convex cut function,
where the former is a continuous piecewise concave quadratic function, and the latter is a convex quadratic function. The
main objectives of this research are to determine a quadratic concave underestimator that does not need an iterative local
optimizer to determine the lower bounding value of the objective function and to determine a convex cut function that effectively
detects infeasible regions for nonconvex constraints. The proposed method is proven to have a finite ε-convergence to locate
the global optimum point. The numerical experiments indicate that the proposed method competes with another covering method,
the index branch-and-bound algorithm, which uses the Lipschitz constant. 相似文献
11.
We show that SDP (semidefinite programming) and SOCP (second order cone programming) relaxations provide exact optimal solutions for a class of nonconvex quadratic optimization problems. It is a generalization of the results by S. Zhang for a subclass of quadratic maximization problems that have nonnegative off-diagonal coefficient matrices of quadratic objective functions and diagonal coefficient matrices of quadratic constraint functions. A new SOCP relaxation is proposed for the class of nonconvex quadratic optimization problems by extracting valid quadratic inequalities for positive semidefinite cones. Its effectiveness to obtain optimal values is shown to be the same as the SDP relaxation theoretically. Numerical results are presented to demonstrate that the SOCP relaxation is much more efficient than the SDP relaxation. 相似文献
12.
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. 相似文献
13.
This paper describes the construction of convex underestimators for twice continuously differentiable functions over box domains
through piecewise quadratic perturbation functions. A refinement of the classical α BB convex underestimator, the underestimators
derived through this approach may be significantly tighter than the classical αBB underestimator. The convex underestimator
is the difference of the nonconvex function f and a smooth, piecewise quadratic, perturbation function, q. The convexity of the underestimator is guaranteed through an analysis of the eigenvalues of the Hessian of f over all subdomains of a partition of the original box domain. Smoothness properties of the piecewise quadratic perturbation
function are derived in a manner analogous to that of spline construction. 相似文献
14.
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. 相似文献
15.
We present effective linear programming based computational techniques for solving nonconvex quadratic programs with box constraints (BoxQP). We first observe that known cutting planes obtained from the Boolean Quadric Polytope (BQP) are computationally effective at reducing the optimality gap of BoxQP. We next show that the Chvátal–Gomory closure of the BQP is given by the odd-cycle inequalities even when the underlying graph is not complete. By using these cutting planes in a spatial branch-and-cut framework, together with a common integrality-based preprocessing technique and a particular convex quadratic relaxation, we develop a solver that can effectively solve a well-known family of test instances. Our linear programming based solver is competitive with SDP-based state of the art solvers on small instances and sparse instances. Most of our computational techniques have been implemented in the recent version of CPLEX and have led to significant performance improvements on nonconvex quadratic programs with linear constraints. 相似文献
16.
Convex integer quadratic programming involves minimization of a convex quadratic objective function with affine constraints and is a well-known NP-hard problem with a wide range of applications. We proposed a new variable reduction technique for convex integer quadratic programs (IQP). Based on the optimal values to the continuous relaxation of IQP and a feasible solution to IQP, the proposed technique can be applied to fix some decision variables of an IQP simultaneously at zero without sacrificing optimality. Using this technique, computational effort needed to solve IQP can be greatly reduced. Since a general convex bounded IQP (BIQP) can be transformed to a convex IQP, the proposed technique is also applicable for the convex BIQP. We report a computational study to demonstrate the efficacy of the proposed technique in solving quadratic knapsack problems. 相似文献
17.
Ioannis G. Akrotirianakis Christodoulos A. Floudas 《Journal of Global Optimization》2004,30(4):367-390
We present a new class of convex underestimators for arbitrarily nonconvex and twice continuously differentiable functions. The underestimators are derived by augmenting the original nonconvex function by a nonlinear relaxation function. The relaxation function is a separable convex function, that involves the sum of univariate parametric exponential functions. An efficient procedure that finds the appropriate values for those parameters is developed. This procedure uses interval arithmetic extensively in order to verify whether the new underestimator is convex. For arbitrarily nonconvex functions it is shown that these convex underestimators are tighter than those generated by the BB method. Computational studies complemented with geometrical interpretations demonstrate the potential benefits of the proposed improved convex underestimators. 相似文献
18.
Nonconvex quadratic programming (QP) is an NP-hard problem that optimizes a general quadratic function over linear constraints.
This paper introduces a new global optimization algorithm for this problem, which combines two ideas from the literature—finite
branching based on the first-order KKT conditions and polyhedral-semidefinite relaxations of completely positive (or copositive)
programs. Through a series of computational experiments comparing the new algorithm with existing codes on a diverse set of
test instances, we demonstrate that the new algorithm is an attractive method for globally solving nonconvex QP. 相似文献
19.
稠密k-子图问题是组合优化里面一类经典的优化问题,其在通常情况下是非凸且NP-难的。本文给出了求解该问题的一个新凸松弛方法-双非负松弛方法,并建立了问题的相应双非负松弛模型,而且证明了其在一定的条件下等价于一个新的半定松弛模型。最后,我们使用一些随机例子对这些模型进行了数值测试,测试的结果表明双非负松弛的计算效果要优于等价的半定松弛。 相似文献
20.
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. 相似文献