Mathematics – Optimization and Control
Scientific paper
2011-12-06
Mathematics
Optimization and Control
A previous, and short version of the paper is posted here: http://www.optimization-online.org/DB_HTML/2010/11/2809.html This i
Scientific paper
We say that the conic linear system P is badly behaved, if for some linear objective function "c" the value sup {cx : x in P} is finite, but the dual program has no solution attaining the same value. We give several characterizations of badly behaved conic linear systems. Our main motivation is the curious similarity of badly behaved semidefinite systems appearing in the literature. The characterizations of such systems turn out to be particularly simple, and intuitive. It turns out that -- somewhat surprisingly -- a certain system with one variable, and two by two matrices appears as a minor in all badly behaved semidefinite systems in a well-defined sense. We prove analogous results for second order conic systems. For semidefinite and second order conic systems our characterizations provide NP \cap co-NP certificates to verify their good or bad behavior. The main tool we use is one of our recent results, that characterizes when the linear image of a closed convex cone is closed.
No associations
LandOfFree
Bad semidefinite programs: they all look the same does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Bad semidefinite programs: they all look the same, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bad semidefinite programs: they all look the same will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-593910