ABSTRACT
Chapter 5 presents the first arc-search algorithm aiming at solve the dilemmas discussed in the previous chapters. The idea is to keep the path-following method because it is known more efficient than potential reduction method but to use arc-search to replace line search because an arc is a better tool to approximate the central path than a straight line. An ideal simple arc would be the ellipse defined in high-dimensional space which is characterized by a long axis, a short axis, and the center. By change these axes and the center, one can place the ellipse at any place and approximate the central path with different curvatures. To construct an ellipse, oneneeds to know the first- and the second-derivatives of the central-path, therefore, arc-search algorithm is a high-order algorithm. This chapter devises an arc-search algorithm and shows that it has the same polynomial bound as the best first-order algorithm, which solves part of the dilemmas we presented in Chapters 2, 3, and 4.
