next up previous
Next: Primal and dual step-lengths Up: Homogeneous and self-dual algorithms Previous: Homogeneous and self-dual algorithms

The search direction

Let tex2html_wrap_inline2513 be the operator


Then the adjoint of tex2html_wrap_inline2513 with respect to the standard inner products in tex2html_wrap_inline2137 and tex2html_wrap_inline2519 is the operator


Our homogeneous and self-dual linear feasibility model for SDP is based on those appearing in [11] for linear programming (LP). It has the following form:


where tex2html_wrap_inline2521 are positive semidefinite. A solution to this system with tex2html_wrap_inline2523 positive either gives optimal solutions to the SDP and its dual or gives a certificate of primal or dual infeasibility.

At each iteration of our algorithms, we apply Newton's method to a perturbation of equation (22), namely,


where the right-hand side quantities are considered as fixed. Here tex2html_wrap_inline2179 and tex2html_wrap_inline2527 are parameters, and tex2html_wrap_inline2529 and tex2html_wrap_inline2531 are defined in (26) and (25) below, respectively.

Just as in the case of infeasible path-following methods, the search direction
tex2html_wrap_inline2533 at each iteration of our homogeneous algorithms is computed from a symmetrized Newton equation derived from the perturbed equation (23):

  tex2html_wrap2549 where tex2html_wrap_inline2535 and tex2html_wrap_inline2183 , tex2html_wrap_inline2185 are defined as in (6) and (7), respectively, and


We compute the search direction via a Schur complement equation as follows. First compute tex2html_wrap_inline2541 from the equation




Then compute tex2html_wrap_inline2193 , tex2html_wrap_inline2195 , and tex2html_wrap_inline2547 from the equations