共查询到20条相似文献,搜索用时 46 毫秒
1.
This article studies some geometrical aspects of the semidefinite linear complementarity problem (SDLCP), which can be viewed as a generalization of the well-known linear complementarity problem (LCP). SDLCP is a special case of a complementarity problem over a closed convex cone, where the cone considered is the closed convex cone of positive semidefinite matrices. It arises naturally in the unified formulation of a pair of primal-dual semidefinite programming problems. In this article, we introduce the notion of complementary cones in the semidefinite setting using the faces of the cone of positive semidefinite matrices and show that unlike complementary cones induced by an LCP, semidefinite complementary cones need not be closed. However, under R 0-property of the linear transformation, closedness of all the semidefinite complementary cones induced by L is ensured. We also introduce the notion of a principal subtransformation with respect to a face of the cone of positive semidefinite matrices and show that for a self-adjoint linear transformation, strict copositivity is equivalent to strict semimonotonicity of each principal subtransformation. Besides the above, various other solution properties of SDLCP will be interpreted and studied geometrically. 相似文献
2.
Immanuel M. Bomze Werner Schachinger Gabriele Uchida 《Journal of Global Optimization》2012,52(3):423-445
Copositive optimization is a quickly expanding scientific research domain with wide-spread applications ranging from global
nonconvex problems in engineering to NP-hard combinatorial optimization. It falls into the category of conic programming (optimizing
a linear functional over a convex cone subject to linear constraints), namely the cone C{\mathcal{C}} of all completely positive symmetric n × n matrices (which can be factorized into FFT{FF^\top} , where F is a rectangular matrix with no negative entry), and its dual cone C*{\mathcal{C}^*} , which coincides with the cone of all copositive matrices (those which generate a quadratic form taking no negative value
over the positive orthant). We provide structural algebraic properties of these cones, and numerous (counter-)examples which
demonstrate that many relations familiar from semidefinite optimization may fail in the copositive context, illustrating the
transition from polynomial-time to NP-hard worst-case behaviour. In course of this development we also present a systematic
construction principle for non-attainability phenomena, which apparently has not been noted before in an explicit way. Last
but not least, also seemingly for the first time, a somehow systematic clustering of the vast and scattered literature is
attempted in this paper. 相似文献
3.
This article studies some geometrical aspects of the semidefinite linear complementarity problem (SDLCP), which can be viewed as a generalization of the well-known linear complementarity problem (LCP). SDLCP is a special case of a complementarity problem over a closed convex cone, where the cone considered is the closed convex cone of positive semidefinite matrices. It arises naturally in the unified formulation of a pair of primal-dual semidefinite programming problems. In this article, we introduce the notion of complementary cones in the semidefinite setting using the faces of the cone of positive semidefinite matrices and show that unlike complementary cones induced by an LCP, semidefinite complementary cones need not be closed. However, under R0-property of the linear transformation, closedness of all the semidefinite complementary cones induced by L is ensured. We also introduce the notion of a principal subtransformation with respect to a face of the cone of positive semidefinite matrices and show that for a self-adjoint linear transformation, strict copositivity is equivalent to strict semimonotonicity of each principal subtransformation. Besides the above, various other solution properties of SDLCP will be interpreted and studied geometrically. 相似文献
4.
Solving semidefinite-quadratic-linear programs using SDPT3 总被引:3,自引:1,他引:2
This paper discusses computational experiments with linear optimization problems involving semidefinite, quadratic, and linear
cone constraints (SQLPs). Many test problems of this type are solved using a new release of SDPT3, a Matlab implementation
of infeasible primal-dual path-following algorithms. The software developed by the authors uses Mehrotra-type predictor-corrector
variants of interior-point methods and two types of search directions: the HKM and NT directions. A discussion of implementation
details is provided and computational results on problems from the SDPLIB and DIMACS Challenge collections are reported.
Received: March 19, 2001 / Accepted: January 18, 2002 Published online: October 9, 2002
Mathematics Subject Classification (2000): 90C05, 90C22 相似文献
5.
A unified kernel function approach to primal-dual interior-point algorithms for convex quadratic SDO
Kernel functions play an important role in the design and analysis of primal-dual interior-point algorithms. They are not
only used for determining the search directions but also for measuring the distance between the given iterate and the μ-center for the algorithms. In this paper we present a unified kernel function approach to primal-dual interior-point algorithms
for convex quadratic semidefinite optimization based on the Nesterov and Todd symmetrization scheme. The iteration bounds
for large- and small-update methods obtained are analogous to the linear optimization case. Moreover, this unifies the analysis
for linear, convex quadratic and semidefinite optimizations. 相似文献
6.
James Renegar 《Foundations of Computational Mathematics》2013,13(3):405-454
We develop a natural generalization to the notion of the central path, a concept that lies at the heart of interior-point methods for convex optimization. The generalization is accomplished via the “derivative cones” of a “hyperbolicity cone”, the derivatives being direct and mathematically appealing relaxations of the underlying (hyperbolic) conic constraint, be it the non-negative orthant, the cone of positive semidefinite matrices, or other. We prove that a dynamics inherent to the derivative cones generates paths always leading to optimality, the central path arising from a special case in which the derivative cones are quadratic. Derivative cones of higher degree better fit the underlying conic constraint, raising the prospect that the paths they generate lead to optimality quicker than the central path. 相似文献
7.
Roland W. Freund Florian Jarre Christoph H. Vogelbusch 《Mathematical Programming》2007,109(2-3):581-611
We consider the solution of nonlinear programs with nonlinear semidefiniteness constraints. The need for an efficient exploitation of the cone of positive semidefinite matrices makes the solution of such nonlinear semidefinite programs more complicated than the solution of standard nonlinear programs. This paper studies a sequential semidefinite programming (SSP) method, which is a generalization of the well-known sequential quadratic programming method for standard nonlinear programs. We present a sensitivity result for nonlinear semidefinite programs, and then based on this result, we give a self-contained proof of local quadratic convergence of the SSP method. We also describe a class of nonlinear semidefinite programs that arise in passive reduced-order modeling, and we report results of some numerical experiments with the SSP method applied to problems in that class. 相似文献
8.
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. 相似文献
9.
Let A,B be positive semidefinite matrices and any unitarily invariant norm on the space of matrices. We show for any non-negative operator monotone function f(t) on , and for non-negative increasing function g(t) on with g(0) = 0 and , whose inverse function is operator monotone.
Received: 1 February 1999 相似文献
10.
A. S. Shvedov 《Siberian Mathematical Journal》2012,53(1):182-192
We construct the first quadratic form and the volume element of the surface consisting of all positive semidefinite m × m matrices of rank r with r distinct positive eigenvalues. We give the density function of the singular gamma distribution. 相似文献
11.
Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions 总被引:5,自引:0,他引:5
In this paper we study primal-dual path-following algorithms for the second-order cone programming (SOCP) based on a family
of directions that is a natural extension of the Monteiro-Zhang (MZ) family for semidefinite programming. We show that the
polynomial iteration-complexity bounds of two well-known algorithms for linear programming, namely the short-step path-following
algorithm of Kojima et al. and Monteiro and Adler, and the predictor-corrector algorithm of Mizuno et al., carry over to the
context of SOCP, that is they have an O( logε-1) iteration-complexity to reduce the duality gap by a factor of ε, where n is the number of second-order cones. Since the MZ-type family studied in this paper includes an analogue of the Alizadeh,
Haeberly and Overton pure Newton direction, we establish for the first time the polynomial convergence of primal-dual algorithms
for SOCP based on this search direction.
Received: June 5, 1998 / Accepted: September 8, 1999?Published online April 20, 2000 相似文献
12.
Kazuhide Nakata Katsuki Fujisawa Mituhiro Fukuda Masakazu Kojima Kazuo Murota 《Mathematical Programming》2003,95(2):303-327
In Part I of this series of articles, we introduced a general framework of exploiting the aggregate sparsity pattern over
all data matrices of large scale and sparse semidefinite programs (SDPs) when solving them by primal-dual interior-point methods.
This framework is based on some results about positive semidefinite matrix completion, and it can be embodied in two different
ways. One is by a conversion of a given sparse SDP having a large scale positive semidefinite matrix variable into an SDP
having multiple but smaller positive semidefinite matrix variables. The other is by incorporating a positive definite matrix
completion itself in a primal-dual interior-point method. The current article presents the details of their implementations.
We introduce new techniques to deal with the sparsity through a clique tree in the former method and through new computational
formulae in the latter one. Numerical results over different classes of SDPs show that these methods can be very efficient
for some problems.
Received: March 18, 2001 / Accepted: May 31, 2001 Published online: October 9, 2002
RID="⋆"
ID="⋆"The author was supported by The Ministry of Education, Culture, Sports, Science and Technology of Japan.
Key Words. semidefinite programming – primal-dual interior-point method – matrix completion problem – clique tree – numerical results
Mathematics Subject Classification (2000): 90C22, 90C51, 05C50, 05C05 相似文献
13.
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. 相似文献
14.
Janez Povh 《Journal of Global Optimization》2010,48(3):447-463
Finding global optimum of a non-convex quadratic function is in general a very difficult task even when the feasible set is
a polyhedron. We show that when the feasible set of a quadratic problem consists of orthogonal matrices from
\mathbbRn×k{\mathbb{R}^{n\times k}} , then we can transform it into a semidefinite program in matrices of order kn which has the same optimal value. This opens new possibilities to get good lower bounds for several problems from combinatorial
optimization, like the Graph partitioning problem (GPP), the Quadratic assignment problem (QAP) etc. In particular we show how to improve significantly the well-known Donath-Hoffman eigenvalue lower bound for GPP
by semidefinite programming. In the last part of the paper we show that the copositive strengthening of the semidefinite lower
bounds for GPP and QAP yields the exact values. 相似文献
15.
In this paper, we analyze and characterize the cone of nonsymmetric positive semidefinite matrices (NS-psd). Firstly, we study basic properties of the geometry of the NS-psd cone and show that it is a hyperbolic but not homogeneous cone. Secondly, we prove that the NS-psd cone is a maximal convex subcone of P0-matrix cone which is not convex. But the interior of the NS-psd cone is not a maximal convex subcone of P-matrix cone. As the byproducts, some new sufficient and necessary conditions for a nonsymmetric matrix to be positive semidefinite are given. Finally, we present some properties of metric projection onto the NS-psd cone. 相似文献
16.
Jianzhong Zhang Liwei Zhang Xiantao Xiao 《Mathematical Methods of Operations Research》2010,72(3):379-404
We consider an inverse quadratic programming (QP) problem in which the parameters in both the objective function and the constraint
set of a given QP problem need to be adjusted as little as possible so that a known feasible solution becomes the optimal
one. We formulate this problem as a linear complementarity constrained minimization problem with a positive semidefinite cone
constraint. With the help of duality theory, we reformulate this problem as a linear complementarity constrained semismoothly
differentiable (SC1) optimization problem with fewer variables than the original one. We propose a perturbation approach to solve the reformulated
problem and demonstrate its global convergence. An inexact Newton method is constructed to solve the perturbed problem and
its global convergence and local quadratic convergence rate are shown. As the objective function of the problem is a SC1 function involving the projection operator onto the cone of positively semi-definite symmetric matrices, the analysis requires
an implicit function theorem for semismooth functions as well as properties of the projection operator in the symmetric-matrix
space. Since an approximate proximal point is required in the inexact Newton method, we also give a Newton method to obtain
it. Finally we report our numerical results showing that the proposed approach is quite effective. 相似文献
17.
We consider an inverse quadratic programming (QP) problem in which the parameters in the objective function of a given QP problem are adjusted as little as possible so that a known feasible solution becomes the optimal one. We formulate this problem as a minimization problem with a positive semidefinite cone constraint and its dual is a linearly constrained semismoothly differentiable (SC1) convex programming problem with fewer variables than the original one. We demonstrate the global convergence of the augmented Lagrangian method for the dual problem and prove that the convergence rate of primal iterates, generated by the augmented Lagrange method, is proportional to 1/r, and the rate of multiplier iterates is proportional to $1/\sqrt{r}$ , where r is the penalty parameter in the augmented Lagrangian. As the objective function of the dual problem is a SC1 function involving the projection operator onto the cone of symmetrically semi-definite matrices, the analysis requires extensive tools such as the singular value decomposition of matrices, an implicit function theorem for semismooth functions, and properties of the projection operator in the symmetric-matrix space. Furthermore, the semismooth Newton method with Armijo line search is applied to solve the subproblems in the augmented Lagrange approach, which is proven to have global convergence and local quadratic rate. Finally numerical results, implemented by the augmented Lagrangian method, are reported. 相似文献
18.
Kazuhiro Kobayashi Sunyoung Kim Masakazu Kojima 《Applied Mathematics and Optimization》2008,58(1):69-88
Exploiting sparsity has been a key issue in solving large-scale optimization problems. The most time-consuming part of primal-dual
interior-point methods for linear programs, second-order cone programs, and semidefinite programs is solving the Schur complement
equation at each iteration, usually by the Cholesky factorization. The computational efficiency is greatly affected by the
sparsity of the coefficient matrix of the equation which is determined by the sparsity of an optimization problem (linear
program, semidefinite program or second-order cone program). We show if an optimization problem is correlatively sparse, then the coefficient matrix of the Schur complement equation inherits the sparsity, and a sparse Cholesky factorization
applied to the matrix results in no fill-in.
S. Kim’s research was supported by Kosef R01-2005-000-10271-0 and KRF-2006-312-C00062. 相似文献
19.
Jos F. Sturm 《Mathematical Programming》2003,95(2):219-247
The matrix variables in a primal-dual pair of semidefinite programs are getting increasingly ill-conditioned as they approach
a complementary solution. Multiplying the primal matrix variable with a vector from the eigenspace of the non-basic part will
therefore result in heavy numerical cancellation. This effect is amplified by the scaling operation in interior point methods.
A complete example illustrates these numerical issues. In order to avoid numerical problems in interior point methods, we
propose to maintain the matrix variables in a Cholesky form. We discuss how the factors of the v-space Cholesky form can be updated after a main iteration of the interior point method with Nesterov-Todd scaling. An analogue
for second order cone programming is also developed. Numerical results demonstrate the success of this approach.
Received: June 16, 2001 / Accepted: April 5, 2002 Published online: October 9, 2002
Key Words. semidefinite programming – second order cone programming
Mathematics Subject Classification (2000): 90C22, 90C20 相似文献
20.
Non-Interior continuation methods for solving semidefinite complementarity problems 总被引:13,自引:0,他引:13
There recently has been much interest in non-interior continuation/smoothing methods for solving linear/nonlinear complementarity
problems. We describe extensions of such methods to complementarity problems defined over the cone of block-diagonal symmetric
positive semidefinite real matrices. These extensions involve the Chen-Mangasarian class of smoothing functions and the smoothed
Fischer-Burmeister function. Issues such as existence of Newton directions, boundedness of iterates, global convergence, and
local superlinear convergence will be studied. Preliminary numerical experience on semidefinite linear programs is also reported.
Received: October 1999 / Accepted: April 2002 Published online: December 19, 2002
RID="⋆"
ID="⋆" This research is supported by National Science Foundation Grant CCR-9731273.
Key words. semidefinite complementarity problem – smoothing function – non-interior continuation – global convergence – local superlinear
convergence 相似文献