Complementarity and nondegeneracy in semidefinite programming |
| |
Authors: | Farid Alizadeh Jean-Pierre A Haeberly Michael L Overton |
| |
Institution: | (1) RUTCOR, Rutgers University, New Brunswick, NJ, USA;(2) Mathematics Department, Fordham University, Bronx, NY, USA;(3) Computer Science Department, Courant Institute of Mathematical Sciences, New York University, 251 Mercer St., 10012 New York, NY, USA |
| |
Abstract: | Primal and dual nondegeneracy conditions are defined for semidefinite programming. Given the existence of primal and dual
solutions, it is shown that primal nondegeneracy implies a unique dual solution and that dual nondegeneracy implies a unique
primal solution. The converses hold if strict complementarity is assumed. Primal and dual nondegeneracy assumptions do not
imply strict complementarity, as they do in LP. The primal and dual nondegeneracy assumptions imply a range of possible ranks
for primal and dual solutionsX andZ. This is in contrast with LP where nondegeneracy assumptions exactly determine the number of variables which are zero. It
is shown that primal and dual nondegeneracy and strict complementarity all hold generically. Numerical experiments suggest
probability distributions for the ranks ofX andZ which are consistent with the nondegeneracy conditions.
Supported in part by the U.S. National Science Foundation grant CCR-9625955.
Supported in part by U.S. National Science Foundation grant CCR-9501941 and the U.S. Office of Naval Research grant N00014-96-1-0704.
Supported in part by U.S. National Science Foundation grant CCR-9401119. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|