next up previous
Next: Computation of specific search Up: Infeasible-interior-point algorithms Previous: Infeasible-interior-point algorithms

The search direction

For later discussion, let us first introduce the operator tex2html_wrap_inline2163 defined by


The adjoint of tex2html_wrap_inline2163 with respect to the standard inner products in tex2html_wrap_inline2137 and tex2html_wrap_inline2169 is the operator


The main step at each iteration of our algorithms is the computation of the search direction tex2html_wrap_inline2171 from the symmetrized Newton equation (with respect to an invertible matrix P which is usually chosen as a function of the current iterate X,Z) given below.

  tex2html_wrap2201 where tex2html_wrap_inline2177 and tex2html_wrap_inline2179 is the centering parameter. Here tex2html_wrap_inline2181 is the symmetrization operator defined by


and tex2html_wrap_inline2183 and tex2html_wrap_inline2185 are the linear operators


where tex2html_wrap_inline2187 denotes the linear operator defined by


Assuming that tex2html_wrap_inline2189 , we compute the search direction via a Schur complement equation as follows (the reader is referred to [2] and [8] for details). First compute tex2html_wrap_inline2191 from the Schur complement equation




Then compute tex2html_wrap_inline2193 and tex2html_wrap_inline2195 from the equations


If tex2html_wrap_inline2197 , solving (9) by a direct method is overwhelmingly expensive; in this case, the user should consider using an implementation that solves (9) by an iterative method such as CG or QMR. In our package, we assume that tex2html_wrap_inline2189 and (9) is solved by a direct method such as LU or Cholesky decomposition.