Condition-Measure Bounds on the Behavior of the Central
Trajectory of a Semi-Definite Program
Manuel A. Nunez and Robert M. Freund
We present bounds on various quantities of interest regarding the
central trajectory of a semi-definite program (SDP), where the bounds
are functions of Renegar's condition number ${\cal C}(d)$ and other
naturally-occurring quantities such as the dimensions $n$ and $m$. The
condition number ${\cal C}(d)$ is defined in terms of the data
instance $d=(A,b,C)$ for SDP; it is the inverse of a relative measure
of the distance of the data instance to the set of ill-posed data
instances, that is, data instances for which arbitrary perturbations
would make the corresponding SDP either feasible or infeasible. We
provide upper and lower bounds on the solutions along the central
trajectory, and upper bounds on changes in solutions and objective
function values along the central trajectory when the data instance is
perturbed and/or when the path parameter defining the central
trajectory is changed. Based on these bounds, we prove that the
solutions along the central trajectory grow at most linearly and at a
rate proportional to the inverse of the distance to ill-posedness, and
grow at least linearly and at a rate proportional to the inverse of
${\cal C}(d)^2$, as the trajectory approaches an optimal solution to
the SDP. Furthermore, the change in solutions and in objective
function values along the central trajectory is at most linear in the
size of the changes in the data. All such bounds involve polynomial
functions of ${\cal C}(d)$, the size of the data, the distance to
ill-posedness of the data, and the dimensions $n$ and $m$ of the SDP.
School of Business and Economics,
Chapman University,
One University Drive, Orange,
CA 92866
MIT Sloan School of Management,
50 Memorial
Drive, Cambridge, MA 02142-1347
Contact: [email protected]