General primal-dual penalty/barrier path-following Newton methods for nonlinear programming

In the present article rather general penalty/barrier-methods are considered, that define a local continuously differentiable primal-dual path. The class of penalty/barrier terms includes most of the usual techniques like logarithmic barriers, SUMT, quadratic loss functions as well as exponential penalties, and the optimization problem which may contain inequality as well as equality constraints. The convergence of the corresponding general primal-dual path-following method is shown for local minima that satisfy strong second-order sufficiency conditions with linear independence constraint qualification (LICQ) and strict complementarity. A basic tool in the analysis of these methods is to estimate the radius of convergence of Newton's method depending on the penalty/barrier-parameter. Without using self-concordance properties convergence bounds are derived by direct estimations of the solutions of the Newton equations. Parameter selection rules are proposed which guarantee the local convergence of the considered penalty/barrier-techniques with only a finite number of Newton steps at each parameter level. Numerical examples illustrate the practical behavior of the proposed class of methods.     

Path-following barrier and penalty methods for linearly constrained problems

In the present paper some barrier and penalty methods (e.g. logarithmic barriers, SUMT, exponential penalties), which define a continuously differentiable primal and dual path, applied to linearly constrained convex problems are studied, in particular, the radius of convergence of Newton’s method depending on the barrier and penalty para-meter is estimated, Unlike using self-concordance properties the convergence bounds are derived by direct estimations of the solutions of the Newton equations. The obtained results establish parameter selection rules which guarantee the overall convergence of the considered barrier and penalty techniques with only a finite number of Newton steps at each parameter level. Moreover, the obtained estimates support scaling method which uses approximate dual multipliers as available in barrier and penalty methods     

High-order Newton-penalty algorithms

Recent efforts in differentiable non-linear programming have been focused on interior point methods, akin to penalty and barrier algorithms. In this paper, we address the classical equality constrained program solved using the simple quadratic loss penalty function/algorithm. The suggestion to use extrapolations to track the differentiable trajectory associated with penalized subproblems goes back to the classic monograph of Fiacco & McCormick. This idea was further developed by Gould who obtained a two-steps quadratically convergent algorithm using prediction steps and Newton correction. Dussault interpreted the prediction step as a combined extrapolation with respect to the penalty parameter and the residual of the first order optimality conditions. Extrapolation with respect to the residual coincides with a Newton step.We explore here higher-order extrapolations, thus higher-order Newton-like methods. We first consider high-order variants of the Newton–Raphson method applied to non-linear systems of equations. Next, we obtain improved asymptotic convergence results for the quadratic loss penalty algorithm by using high-order extrapolation steps.     

A globally convergent method for nonlinear programming

Recently developed Newton and quasi-Newton methods for nonlinear programming possess only local convergence properties. Adopting the concept of the damped Newton method in unconstrained optimization, we propose a stepsize procedure to maintain the monotone decrease of an exact penalty function. In so doing, the convergence of the method is globalized.This research was supported in part by the National Science Foundation under Grant No. ENG-75-10486.     

An interior-point piecewise linear penalty method for nonlinear programming

We present an interior-point penalty method for nonlinear programming (NLP), where the merit function consists of a piecewise linear penalty function and an ? ₂-penalty function. The piecewise linear penalty function is defined by a set of break points that correspond to pairs of values of the barrier function and the infeasibility measure at a subset of previous iterates and this set is updated at every iteration. The ? ₂-penalty function is a traditional penalty function defined by a single penalty parameter. At every iteration the step direction is computed from a regularized Newton system of the first-order equations of the barrier problem proposed in Chen and Goldfarb (Math Program 108:1?C36, 2006). Iterates are updated using a line search. In particular, a trial point is accepted if it provides a sufficient reduction in either of the penalty functions. We show that the proposed method has the same strong global convergence properties as those established in Chen and Goldfarb (Math Program 108:1?C36, 2006). Moreover, our method enjoys fast local convergence. Specifically, for each fixed small barrier parameter???, iterates in a small neighborhood (roughly within o(??)) of the minimizer of the barrier problem converge Q-quadratically to the minimizer. The overall convergence rate of the iterates to the solution of the nonlinear program is Q-superlinear.     

On the convergence of the Newton/log-barrier method

In the Newton/log-barrier method, Newton steps are taken for the log-barrier function for a fixed value of the barrier parameter until a certain convergence criterion is satisfied. The barrier parameter is then decreased and the Newton process is repeated. A naive analysis indicates that Newton’s method does not exhibit superlinear convergence to the minimizer of each instance of the log-barrier function until it reaches a very small neighborhood, namely within O(μ²) of the minimizer, where μ is the barrier parameter. By analyzing the structure of the barrier Hessian and gradient in terms of the subspace of active constraint gradients and the associated null space, we show that this neighborhood is in fact much larger –O(μ^σ) for any σ∈(1,2] – thus explaining why reasonably fast local convergence can be attained in practice. Moreover, we show that the overall convergence rate of the Newton/log-barrier algorithm is superlinear in the number of function/derivative evaluations, provided that the nonlinear program is formulated with a linear objective and that the schedule for decreasing the barrier parameter is related in a certain way to the step length and convergence criteria for each Newton process. Received: October 10, 1997 / Accepted: September 10, 2000?Published online February 22, 2001     

A regularization smoothing method for second-order cone complementarity problem

In this paper, the second-order cone complementarity problem is studied. Based on the Fischer–Burmeister function with a perturbed parameter, which is also called smoothing parameter, a regularization smoothing Newton method is presented for solving the sequence of regularized problems of the second-order cone complementarity problem. Under proper conditions, the global convergence and local superlinear convergence of the proposed algorithm are obtained. Moreover, the local superlinear convergence is established without strict complementarity conditions. Preliminary numerical results suggest the effectiveness of the algorithm.     

On the Superlinear Convergence Order of the Logarithmic Barrier Algorithm

Since the pioneering work of Karmarkar, much interest was directed to penalty algorithms, in particular to the log barrier algorithm. We analyze in this paper the asymptotic convergence rate of a barrier algorithm when applied to non-linear programs. More specifically, we consider a variant of the SUMT method, in which so called extrapolation predictor steps allowing reducing the penalty parameter r_k +1}k are followed by some Newton correction steps. While obviously related to predictor-corrector interior point methods, the spirit differs since our point of view is biased toward nonlinear barrier algorithms; we contrast in details both points of view. In our context, we identify an asymptotically optimal strategy for reducing the penalty parameter r and show that if r_k+1=r _k with < 8/5, then asymptotically only 2 Newton corrections are required, and this strategy achieves the best overall average superlinear convergence order (1.1696). Therefore, our main result is to characterize the best possible convergence order for SUMT type methods.     

An interior penalty method for a finite-dimensional linear complementarity problem in financial engineering

In this work we study an interior penalty method for a finite-dimensional large-scale linear complementarity problem (LCP) arising often from the discretization of stochastic optimal problems in financial engineering. In this approach, we approximate the LCP by a nonlinear algebraic equation containing a penalty term linked to the logarithmic barrier function for constrained optimization problems. We show that the penalty equation has a solution and establish a convergence theory for the approximate solutions. A smooth Newton method is proposed for solving the penalty equation and properties of the Jacobian matrix in the Newton method have been investigated. Numerical experimental results using three non-trivial test examples are presented to demonstrate the rates of convergence, efficiency and usefulness of the method for solving practical problems.     

On the quadratic convergence of Newton’s method under center-Lipschitz but not necessarily Lipschitz hypotheses

We provide new local and semilocal convergence results for Newton’s method in a Banach space. The sufficient convergence conditions do not include the Lipschitz constant usually associated with Newton’s method. Numerical examples demonstrating the expansion of Newton’s method are also provided in this study.     

一维凸函数牛顿法的全局收敛性及其应用

牛顿法是求解非线性方程F（x)＝0的一种经典方法。在一般假设条件下，牛顿法只具有局部收敛性。本文证明了一维凸函数牛顿法的全局收敛性，并且给出了它在全局优化积分水平集方法中的应用。     

The convergence of the perturbed Newton method and its application for ill-conditioned problems

Iterative methods, such as Newton’s, behave poorly when solving ill-conditioned problems: they become slow (first order), and decrease their accuracy. In this paper we analyze deeply and widely the convergence of a modified Newton method, which we call perturbed Newton, in order to overcome the usual disadvantages Newton’s one presents. The basic point of this method is the dependence of a parameter affording a degree of freedom that introduces regularization. Choices for that parameter are proposed. The theoretical analysis will be illustrated through examples.     

Asymptotic analysis of a path-following barrier method for linearly constrained convex problems *

In the present paper the logarithmic barrier method applied to the linearly constrained convex optimization problems is studied from the view point of classical path-following algorithms. In particular, the radius of convergence of Newton's method which depends on the barrier parameter itself is estimated in standard norms, being independent of the parameter, without explicitly using self-concordance properties. The obtained results establish a parameter selection rule which guarantees the overall convergence of a barrier technique with only one Newton step at each parameter level and the complexity of the method can be estimated.     

Globalizing a nonsmooth Newton method via nonmonotone path search

We give a framework for the globalization of a nonsmooth Newton method. In part one we start with recalling B. Kummer’s approach to convergence analysis of a nonsmooth Newton method and state his results for local convergence. In part two we give a globalized version of this method. Our approach uses a path search idea to control the descent. After elaborating the single steps, we analyze and prove the global convergence resp. the local superlinear or quadratic convergence of the algorithm. In the third part we illustrate the method for nonlinear complementarity problems.     

A Gauss–Newton Approach for Solving Constrained Optimization Problems Using Differentiable Exact Penalties

We propose a Gauss–Newton-type method for nonlinear constrained optimization using the exact penalty introduced recently by André and Silva for variational inequalities. We extend their penalty function to both equality and inequality constraints using a weak regularity assumption, and as a result, we obtain a continuously differentiable exact penalty function and a new reformulation of the KKT conditions as a system of equations. Such reformulation allows the use of a semismooth Newton method, so that local superlinear convergence rate can be proved under an assumption weaker than the usual strong second-order sufficient condition and without requiring strict complementarity. Besides, we note that the exact penalty function can be used to globalize the method. We conclude with some numerical experiments using the collection of test problems CUTE.     

On the iteratively regularized Gauss–Newton method in Banach spaces with applications to parameter identification problems

In this paper we propose an extension of the iteratively regularized Gauss–Newton method to the Banach space setting by defining the iterates via convex optimization problems. We consider some a posteriori stopping rules to terminate the iteration and present the detailed convergence analysis. The remarkable point is that in each convex optimization problem we allow non-smooth penalty terms including $L^1$ and total variation like penalty functionals. This enables us to reconstruct special features of solutions such as sparsity and discontinuities in practical applications. Some numerical experiments on parameter identification in partial differential equations are reported to test the performance of our method.     

A predictor-corrector smoothing method for second-order cone programming

In this paper, the second order cone programming problem is studied. By introducing a parameter into the Fischer-Burmeister function, a predictor-corrector smoothing Newton method for solving the problem is presented. The proposed algorithm does neither have restrictions on its starting point nor need additional computation which keep the iteration sequence staying in the given neighborhood. Furthermore, the global and the local quadratic convergence of the algorithm are obtained, among others, the local quadratic convergence of the algorithm is established without strict complementarity. Preliminary numerical results indicate that the algorithm is effective.     

An Augmented Lagrangian Method for a Class of Inverse Quadratic Programming Problems

We consider an inverse quadratic programming (QP) problem in which the parameters in the objective function of a given QP problem are adjusted as little as possible so that a known feasible solution becomes the optimal one. We formulate this problem as a minimization problem with a positive semidefinite cone constraint and its dual is a linearly constrained semismoothly differentiable (SC¹) convex programming problem with fewer variables than the original one. We demonstrate the global convergence of the augmented Lagrangian method for the dual problem and prove that the convergence rate of primal iterates, generated by the augmented Lagrange method, is proportional to 1/r, and the rate of multiplier iterates is proportional to  $1/\sqrt{r}$ , where r is the penalty parameter in the augmented Lagrangian. As the objective function of the dual problem is a SC¹ function involving the projection operator onto the cone of symmetrically semi-definite matrices, the analysis requires extensive tools such as the singular value decomposition of matrices, an implicit function theorem for semismooth functions, and properties of the projection operator in the symmetric-matrix space. Furthermore, the semismooth Newton method with Armijo line search is applied to solve the subproblems in the augmented Lagrange approach, which is proven to have global convergence and local quadratic rate. Finally numerical results, implemented by the augmented Lagrangian method, are reported.     

牛顿方法的两个新格式

给出牛顿迭代方法的两个新格式,S im pson牛顿方法和几何平均牛顿方法,证明了它们至少三次收敛到单根,线性收敛到重根.文末给出数值试验,且与其它已知牛顿法做了比较.结果表明收敛性方法具有较好的优越性,它们丰富了非线性方程求根的方法,在理论上和应用上都有一定的价值.     

A PENALTY TECHNIQUE FOR NONLINEAR COMPLEMENTARITY PROBLEMS

1.IntroductionConsiderthefollowingnonlinearcomplementarityproblemsNCP(F)offindinganxER",suchthatwhereFisamappingfromR"intoitself.ItisanimportantformofthefollowingvariationalinequalityVI(F,X)offindinganxEX,suchthatwhereXCReisaclosedconvexset.WhenX=R7,(1.1)…