共查询到20条相似文献,搜索用时 31 毫秒
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 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. 相似文献
2.
We introduce the notion of a complementary cone and a nondegenerate linear transformation and characterize the finiteness of the solution set of a linear complementarity problem over a closed convex cone in a finite dimensional real inner product space. In addition to the above, other geometrical properties of complementary cones have been explored. 相似文献
3.
We consider two notions for the representations of convex cones G-representation and lifted-G-representation. The former represents a convex cone as a slice of another; the latter allows in addition, the usage of auxiliary
variables in the representation. We first study the basic properties of these representations. We show that some basic properties
of convex cones are invariant under one notion of representation but not the other. In particular, we prove that lifted-G-representation is closed under duality when the representing cone is self-dual. We also prove that strict complementarity
of a convex optimization problem in conic form is preserved under G-representations. Then we move to study efficiency measures for representations. We evaluate the representations of homogeneous
convex cones based on the “smoothness” of the transformations mapping the central path of the representation to the central
path of the represented optimization problem.
Research of the first author was supported in part by a grant from the Faculty of Mathematics, University of Waterloo and
by a Discovery Grant from NSERC. Research of the second author was supported in part by a Discovery Grant from NSERC and a
PREA from Ontario, Canada. 相似文献
4.
The class of sufficient matrices is important in the study of the linear complementarity problem (LCP)—some interior point
methods (IPM’s) for LCP’s with sufficient data matrices have complexity polynomial in the bit size of the matrix and its handicap.In
this paper we show that the handicap of a sufficient matrix may be exponential in its bit size, implying that the known complexity
bounds of interior point methods are not polynomial in the input size of the LCP problem. We also introduce a semidefinite
programming based heuristic, that provides a finite upper bond on the handicap, for the sub-class of P{\mathcal{P}} -matrices (where all principal minors are positive). 相似文献
5.
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. 相似文献
6.
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. 相似文献
7.
On the Analyticity of Underlying HKM Paths for Monotone Semidefinite Linear Complementarity Problems
C. K. Sim 《Journal of Optimization Theory and Applications》2009,141(1):193-215
An interior point method (IPM) defines a search direction at an interior point of the feasible region. These search directions
form a direction field, which in turn defines a system of ordinary differential equations (ODEs). The solutions of the system
of ODEs are called off-central paths, underlying paths lying in the interior of the feasible region. It is known that not
all off-central paths are analytic, whether w.r.t. μ or
, where μ represents the duality gap, at a solution of a given semidefinite linear complementarity problem, SDLCP (Sim and Zhao, Math.
Program. 110:475–499, 2007). In Sim and Zhao (J. Optim. Theory Appl. 137:11–25, 2008), we give a necessary and sufficient condition for when an off-central path is analytic as a function of
at a solution of a general SDLCP. It is then natural to ask about the analyticity of a SDLCP off-central path at a solution,
as a function of μ. We investigate this in the current paper. Again, we work under the assumption that the given SDLCP satisfies strict complementarity
condition. 相似文献
8.
It has been shown by Lemke that if a matrix is copositive plus on
n
, then feasibility of the corresponding linear complementarity problem implies solvability. In this article we show, under suitable conditions, that feasibility of ageneralized linear complementarity problem (i.e., defined over a more general closed convex cone in a real Hilbert space) implies solvability whenever the operator is copositive plus on that cone. We show that among all closed convex cones in a finite dimensional real Hilbert Space, polyhedral cones are theonly ones with the property that every copositive plus, feasible GLCP is solvable. We also prove a perturbation result for generalized linear complementarity problems.This research has been partially supported by the Air Force Office of Scientific Research under grants #AFOSR-82-0271 and #AFOSR-87-0350. 相似文献
9.
《European Journal of Operational Research》1997,102(3):657-666
We show that the block principal pivot algorithm (BPPA) for the linear complementarity problem (LCP) solves the problem for a special class of matrices in at most n block principal pivot steps. We provide cycling examples for the BPPA in which the matrix is positive definite or symmetric positive definite. For LCP of order three, we prove that strict column (row) diagonal dominance is a sufficient condition to avoid cycling. 相似文献
10.
We introduce a Cartesian P-property for linear transformations between the space of symmetric matrices and present its applications to the semidefinite linear complementarity problem (SDLCP). With this Cartesian P-property, we show that the SDLCP has GUS-property (i.e., globally unique solvability), and the solution map of the SDLCP
is locally Lipschitzian with respect to input data. Our Cartesian P-property strengthens the corresponding P-properties of Gowda and Song [15] and allows us to extend several numerical approaches for monotone SDLCPs to solve more
general SDLCPs, namely SDLCPs with the Cartesian P-property. In particular, we address important theoretical issues encountered in those numerical approaches, such as issues
related to the stationary points in the merit function approach, and the existence of Newton directions and boundedness of
iterates in the non-interior continuation method of Chen and Tseng [6].
This work is supported by the annual grant A2004/23 of University of Southampton. 相似文献
11.
We develop algorithms to construct inner approximations of the cone of positive semidefinite matrices via linear programming and second order cone programming. Starting with an initial linear algebraic approximation suggested recently by Ahmadi and Majumdar, we describe an iterative process through which our approximation is improved at every step. This is done using ideas from column generation in large-scale linear programming. We then apply these techniques to approximate the sum of squares cone in a nonconvex polynomial optimization setting, and the copositive cone for a discrete optimization problem. 相似文献
12.
Walter D. Morris jr. 《Mathematical Programming》2002,92(2):285-296
We study orientations of the n-cube that come from simple principal pivot algorithms for the linear complementarity problem with a P-matrix. We show that these orientations properly generalize those that are obtained from linear objective functions on polytopes
combinatorially equivalent to the cube. The orientations from LCP with a P-matrix may admit directed cycles. We give a sequence of problems on which the algorithm RANDOM-EDGE performs very badly.
Received: February 12, 2001 / Accepted: September 9, 2001?Published online April 12, 2002 相似文献
13.
Bidushi Chakraborty Sudarshan Nanda Mahendra Prasad Biswal 《Mediterranean Journal of Mathematics》2005,2(3):291-299
In this paper, generalization of a vertical block linear complementarity problem associated with two different types of matrices,
one of which is a square matrix and the other is a vertical block matrix, is proposed. The necessary and sufficient conditions
for the existence of the solution of the generalized vertical block linear complementarity problem is derived and the relationship
between the solution set of the generalized vertical block linear complementarity problem and the linear complementarity problem
is established. It is proved that the generalized vertical block linear complementarity problem has the P-property if and only if the vertical block linear complementarity problem has the P-property. 相似文献
14.
We consider semidefinite monotone linear complementarity problems (SDLCP) in the space n of real symmetric n×n-matrices equipped with the cone n+ of all symmetric positive semidefinite matrices. One may define weighted (using any Mn++ as weight) infeasible interior point paths by replacing the standard condition XY=rI, r>0, (that defines the usual central path) by (XY+YX)/2=rM. Under some mild assumptions (the most stringent is the existence of some strictly complementary solution of (SDLCP)), these paths have a limit as r0, and they depend analytically on all path parameters (such as r and M), even at the limit point r=0.Mathematics Subject Classification (1991): 90C33, 65K05 相似文献
15.
The convex feasibility problem asks to find a point in the intersection of finitely many closed convex sets in Euclidean space. This problem is of fundamental importance in the mathematical and physical sciences, and it can be solved algorithmically by the classical method of cyclic projections.In this paper, the case where one of the constraints is an obtuse cone is considered. Because the nonnegative orthant as well as the set of positive-semidefinite symmetric matrices form obtuse cones, we cover a large and substantial class of feasibility problems. Motivated by numerical experiments, the method of reflection-projection is proposed: it modifies the method of cyclic projections in that it replaces the projection onto the obtuse cone by the corresponding reflection.This new method is not covered by the standard frameworks of projection algorithms because of the reflection. The main result states that the method does converge to a solution whenever the underlying convex feasibility problem is consistent. As prototypical applications, we discuss in detail the implementation of two-set feasibility problems aiming to find a nonnegative [resp. positive semidefinite] solution to linear constraints in n [resp. in
, the space of symmetric n×n matrices] and we report on numerical experiments. The behavior of the method for two inconsistent constraints is analyzed as well. 相似文献
16.
This paper deals with bounded linear regularity, linear regularity and the strong conical hull intersection property (CHIP)
of a collection of finitely many closed convex intersecting sets in Banach spaces. It is shown that, as in finite dimensional
space setting (see [6]), the standard constraint qualification implies bounded linear regularity, which in turn yields the
strong conical hull intersection property, and that the collection of closed convex sets {C
1, . . . ,C
n
} is bounded linearly regular if and only if the tangent cones of {C
1, . . . ,C
n
} has the CHIP and the normal cones of {C
1, . . . ,C
n
} has the property (G)(uniformly on a neighborhood in the intersection C). As applications, we study the global error bounds for systems of linear and convex inequalities.
The work of this author was partially supported by the National Natural Sciences Grant (No. 10471032) and the Excellent Young
Teachers Program of MOE, P.R.C
The authors thank professor K.F.Ng for his helpful discussion and the referee for their helpful suggestions on improving the
first version of this paper 相似文献
17.
Sergey P. Tarasov 《Discrete Applied Mathematics》2008,156(11):2070-2078
We address the exact semidefinite programming feasibility problem (SDFP) consisting in checking that intersection of the cone of positive semidefinite matrices and some affine subspace of matrices with rational entries is not empty. SDFP is a convex programming problem and is often considered as tractable since some of its approximate versions can be efficiently solved, e.g. by the ellipsoid algorithm.We prove that SDFP can decide comparison of numbers represented by the arithmetic circuits, i.e. circuits that use standard arithmetical operations as gates. Our reduction may give evidence to the intrinsic difficulty of SDFP (contrary to the common expectations) and clarify the complexity status of the exact SDP—an old open problem in the field of mathematical programming. 相似文献
18.
Given a linear transformation L:?
n
→?
n
and a matrix Q∈?
n
, where ?
n
is the space of all symmetric real n×n matrices, we consider the semidefinite linear complementarity problem SDLCP(L,?
n
+,Q) over the cone ?
n
+ of symmetric n×n positive semidefinite matrices. For such problems, we introduce the P-property and its variants, Q- and GUS-properties. For a matrix A∈R
n×n
, we consider the linear transformation L
A
:?
n
→?
n
defined by L
A
(X):=AX+XA
T
and show that the P- and Q-properties for L
A
are equivalent to A being positive stable, i.e., real parts of eigenvalues of A are positive. As a special case of this equivalence, we deduce a theorem of Lyapunov.
Received: March 1999 / Accepted: November 1999?Published online April 20, 2000 相似文献
19.
The second-order cone linear complementarity problem (SOCLCP) is a generalization of the linear complementarity problem (LCP). In this paper we characterize the solution set of a monotone SOCLCP with the help of the Jordan-algebraic technique. 相似文献
20.
S. Z. Németh 《Acta Mathematica Hungarica》2010,127(4):376-390
A mapping is called isotone if it is monotone increasing with respect to the order defined by a pointed closed convex cone.
Finding the pointed closed convex generating cones for which the projection mapping onto the cone is isotone is a difficult
problem which was analyzed in [1, 2, 3, 4, 5]. Such cones are called isotone projection cones. In particular it was shown
that any isotone projection cone is latticial [2]. This problem is extended by replacing the projection mapping with a continuous
isotone retraction onto the cone. By introducing the notion of sharp mappings, it is shown that a pointed closed convex generating
cone is latticial if and only if there is a continuous isotone retraction onto the cone whose complement is sharp. This result
is used for characterizing a subdual latticial cone by the isotonicity of a generalization of the positive part mapping x ↦ x
+. This generalization is achieved by generalizing the infimum for subdual cones. The theoretical results of this paper exhibit
fundamental properties of the lattice structure of the space which were not analysed before. 相似文献