Inexact-Restoration Algorithm for Constrained Optimization1

We introduce a new model algorithm for solving nonlinear programming problems. No slack variables are introduced for dealing with inequality constraints. Each iteration of the method proceeds in two phases. In the first phase, feasibility of the current iterate is improved; in second phase, the objective function value is reduced in an approximate feasible set. The point that results from the second phase is compared with the current point using a nonsmooth merit function that combines feasibility and optimality. This merit function includes a penalty parameter that changes between consecutive iterations. A suitable updating procedure for this penalty parameter is included by means of which it can be increased or decreased along consecutive iterations. The conditions for feasibility improvement at the first phase and for optimality improvement at the second phase are mild, and large-scale implementation of the resulting method is possible. We prove that, under suitable conditions, which do not include regularity or existence of second derivatives, all the limit points of an infinite sequence generated by the algorithm are feasible, and that a suitable optimality measure can be made as small as desired. The algorithm is implemented and tested against the LANCELOT algorithm using a set of hard-spheres problems.     

Local Convergence of the Affine-Scaling Interior-Point Algorithm for Nonlinear Programming

This paper addresses the local convergence properties of the affine-scaling interior-point algorithm for nonlinear programming. The analysis of local convergence is developed in terms of parameters that control the interior-point scheme and the size of the residual of the linear system that provides the step direction. The analysis follows the classical theory for quasi-Newton methods and addresses q-linear, q-superlinear, and q-quadratic rates of convergence.     

Local Convergence of the Interior-Point Newton Method for General Nonlinear Programming

In this paper, a formulation for an interior-point Newton method of general nonlinear programming problems is presented. The formulation uses the Coleman-Li scaling matrix. The local convergence and the q-quadratic rate of convergence for the method are established under the standard assumptions of the Newton method for general nonlinear programming.     

Local Convergence of a Primal-Dual Method for Degenerate Nonlinear Programming

In recent work, the local convergence behavior of path-following interior-point methods and sequential quadratic programming methods for nonlinear programming has been investigated for the case in which the assumption of linear independence of the active constraint gradients at the solution is replaced by the weaker Mangasarian–Fromovitz constraint qualification. In this paper, we describe a stabilization of the primal-dual interior-point approach that ensures rapid local convergence under these conditions without enforcing the usual centrality condition associated with path-following methods. The stabilization takes the form of perturbations to the coefficient matrix in the step equations that vanish as the iterates converge to the solution.     

Inexact-Restoration Method with Lagrangian Tangent Decrease and New Merit Function for Nonlinear Programming

A new inexact-restoration method for nonlinear programming is introduced. The iteration of the main algorithm has two phases. In Phase 1, feasibility is improved explicitly; in Phase 2, optimality is improved on a tangent approximation of the constraints. Trust regions are used for reducing the step when the trial point is not good enough. The trust region is not centered in the current point, as in many nonlinear programming algorithms, but in the intermediate more feasible point. Therefore, in this semifeasible approach, the more feasible intermediate point is considered to be essentially better than the current point. This is the first method in which intermediate-point-centered trust regions are combined with the decrease of the Lagrangian in the tangent approximation to the constraints. The merit function used in this paper is also new: it consists of a convex combination of the Lagrangian and the nonsquared norm of the constraints. The Euclidean norm is used for simplicity, but other norms for measuring infeasibility are admissible. Global convergence theorems are proved, a theoretically justified algorithm for the first phase is introduced, and some numerical insight is given.     

Local Convergence Analysis of Projection-Type Algorithms: Unified Approach

In this paper, we use a unified approach to analyze the local convergence behavior of a wide class of projection-type methods for solving variational inequality problems. Under certain conditions, it is shown that, in a finite number of iterations, either the sequence of iterates terminates at a solution of the concerned problem or all iterates enter and remain in the relative interior of the optimal face and, hence, the subproblem reduces to a simpler form.     

结合广义Armijo步长搜索的超记忆梯度算法及其收敛特征

对无约束规划 ( P) :minx∈ Rnf ( x) ,其中 f ( x)是 Rn→ R1上的一阶连续可微函数 ,设计了一个超记忆梯度求解算法 ,并在去掉迭代点列 { xk}有界和广义 Armijo步长搜索下 ,讨论了算法的全局的收敛性 ,证明了算法具有较强的收敛性质     

Local convergence of filter methods for equality constrained non-linear programming

In Gonzaga et al. [A globally convergent filter method for nonlinear programming, SIAM J. Optimiz. 14 (2003), pp. 646–669] we discuss general conditions to ensure global convergence of inexact restoration filter algorithms for non-linear programming. In this article we show how to avoid the Maratos effect by means of a second-order correction. The algorithms are based on feasibility and optimality phases, which can be either independent or not. The optimality phase differs from the original one only when a full Newton step for the tangential minimization of the Lagrangian is efficient but not acceptable by the filter method. In this case a second-order corrector step tries to produce an acceptable point keeping the efficiency of the rejected step. The resulting point is tested by trust region criteria. Under the usual hypotheses, the algorithm inherits the quadratic convergence properties of the feasibility and optimality phases. This article includes a comparison between classical Sequential Quadratic Programming (SQP) and Inexact Restoration (IR) iterations, showing that both methods share the same asymptotic convergence properties.     

Convergence Analysis of an Inexact Potential Reduction Method for Convex Quadratic Programming

We analyze the convergence of an infeasible inexact potential reduction method for quadratic programming problems. We show that the convergence of this method is achieved if the residual of the KKT system satisfies a bound related to the duality gap. This result suggests stopping criteria for inner iterations that can be used to adapt the accuracy of the computed direction to the quality of the potential reduction iterate in order to achieve computational efficiency. This research was partially supported by the Italian MIUR, Project FIRB—Large Scale Nonlinear Optimization # RBNE01WBBB and Project PRIN—Innovative Problems and Methods in Nonlinear Optimization # 2005017083.     

On the Global Convergence of a Modified Augmented Lagrangian Linesearch Interior-Point Newton Method for Nonlinear Programming

We consider a linesearch globalization of the local primal-dual interior-point Newton method for nonlinear programming introduced by El-Bakry, Tapia, Tsuchiya, and Zhang. The linesearch uses a new merit function that incorporates a modification of the standard augmented Lagrangian function and a weak notion of centrality. We establish a global convergence theory and present promising numerical experimentation.     

Local convergence of quasi-Newton methods for B-differentiable equations

We study local convergence of quasi-Newton methods for solving systems of nonlinear equations defined by B-differentiable functions. We extend the classical linear and superlinear convergence results for general quasi-Newton methods as well as for Broyden's method. We also show how Broyden's method may be applied to nonlinear complementarity problems and illustrate its computational performance on two small examples.     

线性二阶锥规划的一个光滑化方法及其收敛性

首先讨论了用Chen-Harker-Kanzow-Smale光滑函数刻画线性二阶锥规划的中心路径条件;基于此,提出了求解线性二阶锥规划的一个光滑化算法,然后分析了该算法的全局及其局部二次收敛性质.     

Self-Tuning Norm-Relaxed Method of Feasible Directions

This paper presents three updating techniques for the scaling matrix or the scalar weight used in the norm-relaxed method of feasible directions, a generalization of the popular Pironneau–Polak algorithm. These techniques include variable metric updates and tuning of a scalar weight in a way characteristic of trust-region methods, and also techniques based on the idea of multiple directions, where the update decision is made by comparing results of searching along several directions determined by distinct values of weights. Numerical results obtained on a standard test set are provided. These results indicate that the updating techniques allow considerable computational savings when compared with the original Pironneau-Polak method.     

Local Minima and Convergence in Low-Rank Semidefinite Programming

The low-rank semidefinite programming problem LRSDP_r is a restriction of the semidefinite programming problem SDP in which a bound r is imposed on the rank of X, and it is well known that LRSDP_r is equivalent to SDP if r is not too small. In this paper, we classify the local minima of LRSDP_r and prove the optimal convergence of a slight variant of the successful, yet experimental, algorithm of Burer and Monteiro [5], which handles LRSDP_r via the nonconvex change of variables X=RR^T. In addition, for particular problem classes, we describe a practical technique for obtaining lower bounds on the optimal solution value during the execution of the algorithm. Computational results are presented on a set of combinatorial optimization relaxations, including some of the largest quadratic assignment SDPs solved to date.This author was supported in part by NSF Grant CCR-0203426.This author was supported in part by NSF Grants CCR-0203113 and INT-9910084 and ONR grant N00014-03-1-0401.     

Generalized reduced gradient method as an extension of feasible direction methods

The paper presents modifications of the generalized reduced gradient method which allows for a convergence proof. For that, a special construction of the basis is introduced, and some tools of the theory of feasible direction are used to modify the common choice of the direction at every step.Thanks are due to G. de Ghellinck and E. Loute for many fruitful discussions on this paper.     

Local Compactness in Fuzzy Convergence Spaces

Two notions of local precompactness in the realm of fuzzy convergence spaces are investigated. It is shown that the property of local precompactness possesses a “good extension.” Moreover, for each given fuzzy convergence space, there exists a coarsest locally precompact space which is finer than the original space. Continuity between fuzzy spaces is preserved between the associated locally precompact spaces. Invariance of regularity with respect to taking locally precompact modifications is discussed.     

Updating the Multipliers Associated with Inequality Constraints in an Augmented Lagrangian Multiplier Method

This paper contributes to the development of the field of augmented Lagrangian multiplier methods for general nonlinear programming by introducing a new update for the multipliers corresponding to inequality constraints. The update maintains naturally the nonnegativity of the multipliers without the need for a positive-orthant projection, as a result of the verification of the first-order necessary conditions for the minimization of a modified augmented Lagrangian penalty function.In the new multiplier method, the roles of the multipliers are interchanged: the multipliers corresponding to the inequality constraints are updated explicitly, whereas the multipliers corresponding to the equality constraints are approximated implicitly. It is shown that the basic properties of local convergence of the traditional multiplier method are valid also for the proposed method.     

约束优化的一个改进的强次可行SQP算法及数值试验

本文对约束优化一个强次可行SQP算法进行改进,使之产生的迭代点在有限次迭代后全落入可行域;并对算法数值效果进行了大量的比较试验.     

Global Convergence of the Newton Interior-Point Method for Nonlinear Programming

The aim of this paper is to show that the theorem on the global convergence of the Newton interior–point (IP) method presented in Ref. 1 can be proved under weaker assumptions. Indeed, we assume the boundedness of the sequences of multipliers related to nontrivial constraints, instead of the hypothesis that the gradients of the inequality constraints corresponding to slack variables not bounded away from zero are linearly independent. By numerical examples, we show that, in the implementation of the Newton IP method, loss of boundedness in the iteration sequence of the multipliers detects when the algorithm does not converge from the chosen starting point.     

Convergence Analysis of an Inexact Infeasible Interior Point Method for Semidefinite Programming

In this paper we present an extension to SDP of the well known infeasible Interior Point method for linear programming of Kojima, Megiddo and Mizuno (A primal-dual infeasible-interior-point algorithm for Linear Programming, Math. Progr., 1993). The extension developed here allows the use of inexact search directions; i.e., the linear systems defining the search directions can be solved with an accuracy that increases as the solution is approached. A convergence analysis is carried out and the global convergence of the method is proved.