WHY A PURE PRIMAL NEWTON BARRIER STEP MAY BE INFEASIBLE

作     者：WRIGHT, MH 

出 版 物：《SIAM JOURNAL ON OPTIMIZATION》 (工业与应用数学会最优化杂志)

年 卷 期：1995年第5卷第1期

页      面：1-12页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：INTERIOR METHOD LOGARITHMIC BARRIER FUNCTION PRIMAL METHOD PRIMAL NEWTON STEP 

摘      要：Modern barrier methods for constrained optimization are sometimes portrayed conceptually as a sequence of inexact minimizations, with only a very few Newton iterations (perhaps just one) for each value of the barrier parameter. Unfortunately, this rosy image does not accurately reflect reality when the barrier parameter is reduced at a reasonable rate, as in a practical (long-step) method. Local analysis is presented indicating why a pure Newton step in a typical long-step barrier method for nonlinearly constrained optimization may be seriously infeasible, even when taken from an apparently favorable point;hence accurate calculation of the Newton direction does not guarantee an effective algorithm. The features described are illustrated numerically and connected to known theoretical results for well-behaved convex problems satisfying common assumptions such as self-concordancy. The contrasting nature of an approximate step to the desired minimizer of the barrier function is also discussed.