Convergence Analysis for General Penalty Path-Following Newton Iterations

摘要

In the present paper rather general barrier and penalty methods (e.g. logarithmic barriers, SUMT, exponential penalties), which define a continuously differentiable primal and dual path, applied to linearly constrained optimization problems are studied. In particular, the radius of convergence of Newton's method depending on the barrier and penalty parameter is estimated. Unlike in most of the logarithmic barrier analysis which make use of self-concordance properties (cf. [6], [10], [11]) here the convergence bounds are derived by an approach developed in [1] via direct estimations of the solutions of the Newton equations (compare also [13]). There are established parameter selection rules which guarantee the overall convergence of the considered barrier and penalty techniques with only a single Newton step at each parameter level. Moreover, the obtained estimates support a scaling method which uses approximate dual multipliers as available in barrier and penalty methods.