Linear conic programming: genericity and stability
|PhD ceremony:||Ms B. (Bolor) Jargalsaikhan|
|When:||May 08, 2015|
|Where:||Academy building RUG|
|Faculty:||Science and Engineering|
In linear conic programming, we maximize or minimize a linear function over the intersection of an affine space and a convex cone. Conic programming contains linear programs, semidefinite programs and copositive programs as subclasses.
In this thesis, we study genericity and stability of properties of conic programs. We say that a property is weakly generic if the property holds for almost all problem instances. Numerically, stability is desirable. A property is said to be stable at a problem instance if the property still holds under a small perturbation of the problem data. I
n this thesis, we show that Slater's condition is weakly generic and stable. It is known that uniqueness of the optimal solution, nondegeneracy and strict complementarity are weakly generic in conic programming. We investigate the stability of these weakly generic properties. For semidefinite programs, we show that all these weakly generic properties are stable.
Another property of interest is the order of maximizers. Geometrically, it is related to the curvature of the feasible set around the solution. We characterize first order optimal solutions in conic programming and give necessary and sufficient conditions for their stability.
In the last part of the thesis, we consider copositive problems and some particular cases where copositivity of a matrix can be efficiently checked. In particular, we prove that a matrix with exactly one positive eigenvalue is copositive if and only if it is a nonnegative matrix.