next up previous
Next: The Mehrotra-type predictor-corrector algorithm Up: Infeasible-interior-point algorithms Previous: Computation of specific search

The primal-dual path-following algorithm

The algorithmic framework of our primal-dual path-following algorithm is as follows.



(a) The adaptive choice of the step-length parameter in (19) is used as the default in our implementation, but the user has the option of fixing the value of tex2html_wrap_inline2391 .
(b) It is known that as the parameter tex2html_wrap_inline2393 decreases to 0, the norm tex2html_wrap_inline2397 will tend to increase, even if the initial iterate is primal feasible, due to increasing numerical instability of the Schur complement approach. In our implementation of the algorithms, the user has the option of correcting for the loss in primal feasibility by projecting tex2html_wrap_inline2193 onto the null space of the operator tex2html_wrap_inline2163 . That is, before updating to tex2html_wrap_inline2403 , we replace tex2html_wrap_inline2193 by


where tex2html_wrap_inline2407 . Note that this step is inexpensive. The tex2html_wrap_inline2409 matrix tex2html_wrap_inline2411 need only to be formed once at the beginning of the algorithm.

(c) We only described termination when approximately optimal solutions are at hand. Nevertheless, our codes stop when other indications arise. For example, if the step makes little progress, or if the step-length taken in either primal or dual spaces becomes very small, we terminate. We also stop if we get an indication of infeasibility. For example, if the current iterate has tex2html_wrap_inline2413 much larger than tex2html_wrap_inline2415 , then a suitable scaling is an approximate solution of tex2html_wrap_inline2417 , which is a certificate that the primal problem is infeasible. Similarly, if tex2html_wrap_inline2419 is much larger than tex2html_wrap_inline2421 , we have an indication of dual infeasibility: a scaled iterate is then an approximate solution of tex2html_wrap_inline2423 , which is a certificate that the dual problem is infeasible. In either case, we return the appropriate scaled iterate suggesting primal or dual infeasibility.