Affine scaling inexact generalized Newton algorithm with interior backtracking technique for solving bound-constrained semismooth equations

We develop and analyze an affine scaling inexact generalized Newton algorithm in association with nonmonotone interior backtracking line technique for solving systems of semismooth equations subject to bounds on variables. By combining inexact affine scaling generalized Newton with interior backtracking line search technique, each iterate switches to inexact generalized Newton backtracking step to strict interior point feasibility. The global convergence results are developed in a very general setting of computing trial steps by the affine scaling generalized Newton-like method that is augmented by an interior backtracking line search technique projection onto the feasible set. Under some reasonable conditions we establish that close to a regular solution the inexact generalized Newton method is shown to converge locally p-order q-superlinearly. We characterize the order of local convergence based on convergence behavior of the quality of the approximate subdifferentials and indicate how to choose an inexact forcing sequence which preserves the rapid convergence of the proposed algorithm. A nonmonotonic criterion should bring about speeding up the convergence progress in some ill-conditioned cases.     

A class of primal affine scaling algorithms

We obtain a class of primal affine scaling algorithms which generalize some known algorithms. This class, depending on a r-parameter, is constructed through a family of metrics generated by −r power, r ? 1, of the diagonal iterate vector matrix. We prove the so-called weak convergence of the primal class for nondegenerate linearly constrained convex programming. We observe the computational performance of the class of primal affine scaling algorithms, accomplishing tests with linear programs from the NETLIB library and with some quadratic programming problems described in the Maros and Mészáros repository.     

An interior affine scaling projective algorithm for nonlinear equality and linear inequality constrained optimization

In this paper, we propose a new nonmonotonic interior point backtracking strategy to modify the reduced projective affine scaling trust region algorithm for solving optimization subject to nonlinear equality and linear inequality constraints. The general full trust region subproblem for solving the nonlinear equality and linear inequality constrained optimization is decomposed to a pair of trust region subproblems in horizontal and vertical subspaces of linearize equality constraints and extended affine scaling equality constraints. The horizontal subproblem in the proposed algorithm is defined by minimizing a quadratic projective reduced Hessian function subject only to an ellipsoidal trust region constraint in a null subspace of the tangential space, while the vertical subproblem is also defined by the least squares subproblem subject only to an ellipsoidal trust region constraint. By introducing the Fletcher's penalty function as the merit function, trust region strategy with interior point backtracking technique will switch to strictly feasible interior point step generated by a component direction of the two trust region subproblems. The global convergence of the proposed algorithm while maintaining fast local convergence rate of the proposed algorithm are established under some reasonable conditions. A nonmonotonic criterion should bring about speeding up the convergence progress in some high nonlinear function conditioned cases.     

线性不等式约束优化的弧线路径信赖域算法

提供了弧线路径结合仿射内点信赖域策略的非单调回代算法解线性不等式约束的优化问题.基于仿射投影的信赖域子问题获得新的搜索方向,采用弧线路径的近似信赖域和线搜索结合技术得到回代步,获得新的步长.通过证明所提供的弧线路径具有一系列良好性质,从而在合理的条件下,证明所提供的算法不仅具有整体收敛性,而且保持算法的局部超线性收敛速率.数值测试表明了算法的有效性与可靠性.     

An affine scaling trust-region algorithm with interior backtracking technique for solving bound-constrained nonlinear systems

In this paper, we propose a new affine scaling trust-region algorithm in association with nonmonotonic interior backtracking line search technique for solving nonlinear equality systems subject to bounds on variables. The trust-region subproblem is defined by minimizing a squared Euclidean norm of linear model adding the augmented quadratic affine scaling term subject only to an ellipsoidal constraint. By using both trust-region strategy and interior backtracking line search technique, each iterate switches to backtracking step generated by the general trust-region subproblem and satisfies strict interior point feasibility by line search backtracking technique. The global convergence and fast local convergence rate of the proposed algorithm are established under some reasonable conditions. A nonmonotonic criterion should bring about speeding up the convergence progress in some ill-conditioned cases. The results of numerical experiments are reported to show the effectiveness of the proposed algorithm.     

Global and local convergence of a new affine scaling trust region algorithm for linearly constrained optimization

Chen and Zhang [Sci.China,Ser.A,45,1390–1397(2002)] introduced an affine scaling trust region algorithm for linearly constrained optimization and analyzed its global convergence.In this paper,we derive a new affine scaling trust region algorithm with dwindling filter for linearly constrained optimization.Different from Chen and Zhang's work,the trial points generated by the new algorithm are accepted if they improve the objective function or improve the first order necessary optimality conditions.Under mild conditions,we discuss both the global and local convergence of the new algorithm.Preliminary numerical results are reported.     

求解一般界约束优化问题的积极集信赖域方法

本文提出了一种求解一般界约束优化问题的新方法. 每步迭代分为两个阶段. 在第一阶段, 从 当前迭代点x_k 出发, 沿着经过仿射变换后的梯度步, 得到试探点x_k¹, 记录下它的积极集. 这里用到的仿射变换矩阵不仅依赖于变量到边界的距离, 还依赖于当前迭代点的梯度以及该步迭代中的信赖域半 径. 在第二阶段, 从x_k¹ 出发, 通过在积极约束的零空间里面求解一个信赖域子问题得到新的试探点. 然后判断是否接受这个试探点作为下一个迭代点. 文中证明了算法的全局收敛性, 并且迭代点列的每 个聚点都是一阶稳定点. 文中还对国际著名的CUTEr 算例库中所有的界约束优化问题进行了测试. 数值结果表明我们的方法是有效的, 并且可以与L-BFGS-B 方法相媲美.     

Superlinearly convergent affine scaling interior trust-region method for linear constrained LC<Superscript>1</Superscript> minimization

We extend the classical affine scaling interior trust region algorithm for the linear constrained smooth minimization problem to the nonsmooth case where the gradient of objective function is only locally Lipschitzian. We propose and analyze a new affine scaling trust-region method in association with nonmonotonic interior backtracking line search technique for solving the linear constrained LC1 optimization where the second-order derivative of the objective function is explicitly required to be locally Lipschitzian. The general trust region subproblem in the proposed algorithm is defined by minimizing an augmented affine scaling quadratic model which requires both first and second order information of the objective function subject only to an affine scaling ellipsoidal constraint in a null subspace of the augmented equality constraints. The global convergence and fast local convergence rate of the proposed algorithm are established under some reasonable conditions where twice smoothness of the objective function is not required. Applications of the algorithm to some nonsmooth optimization problems are discussed.     

仿射内点既约投影Hessian算法解非线性约束优化

本文结合非单调内点回代技术,提供了新的仿射信赖域方法解含有非负变量约束和非线性等式约束的优化问题.为求解大规模问题,采用等式约束的Jacobian矩阵的QR分解和两块校正的双边既约Hessian矩阵投影,将问题分解成零空间和值空间两个信赖域子问题.零空间的子问题为通常二次目标函数只带椭球约束的信赖域子问题,而值空间的子问题使用满足信赖域约束参数的值空间投影向量方向.通过引入Fletcher罚函数作为势函数,将由两个子问题结合信赖域策略构成的合成方向,并使用非单调线搜索技术回代于可接受的非负约束内点步长.在合理的条件下,算法具有整体收敛性且两块校正的双边既约Hessian投影法将保持超线性收敛速率.非单调技术将克服高度非线性情况,加快收敛进展.     

An affine scaling interior trust-region method combining with line search filter technique for optimization subject to bounds on variables

This paper proposes and analyzes an affine scaling trust-region method with line search filter technique for solving nonlinear optimization problems subject to bounds on variables. At the current iteration, the trial step is generated by the general trust-region subproblem which is defined by minimizing a quadratic function subject only to an affine scaling ellipsoidal constraint. Both trust-region strategy and line search filter technique will switch to trail backtracking step which is strictly feasible. Meanwhile, the proposed method does not depend on any external restoration procedure used in line search filter technique. A new backtracking relevance condition is given which is weaker than the switching condition to obtain the global convergence of the algorithm. The global convergence and fast local convergence rate of this algorithm are established under reasonable assumptions. Preliminary numerical results are reported indicating the practical viability and show the effectiveness of the proposed algorithm.     

A trust region and affine scaling interior point method for nonconvex minimization with linear inequality constraints

A trust region and affine scaling interior point method (TRAM) is proposed for a general nonlinear minimization with linear inequality constraints [8]. In the proposed approach, a Newton step is derived from the complementarity conditions. Based on this Newton step, a trust region subproblem is formed, and the original objective function is monotonically decreased. Explicit sufficient decrease conditions are proposed for satisfying the first order and second order necessary conditions.?The objective of this paper is to establish global and local convergence properties of the proposed trust region and affine scaling interior point method. It is shown that the proposed explicit decrease conditions are sufficient for satisfy complementarity, dual feasibility and second order necessary conditions respectively. It is also established that a trust region solution is asymptotically in the interior of the proposed trust region subproblem and a properly damped trust region step can achieve quadratic convergence. Received: January 29, 1999 / Accepted: November 22, 1999?Published online February 23, 2000     

Affine scaling interior Levenberg–Marquardt method for bound-constrained semismooth equations under local error bound conditions

We develop and analyze a new affine scaling Levenberg–Marquardt method with nonmonotonic interior backtracking line search technique for solving bound-constrained semismooth equations under local error bound conditions. The affine scaling Levenberg–Marquardt equation is based on a minimization of the squared Euclidean norm of linear model adding a quadratic affine scaling matrix to find a solution that belongs to the bounded constraints on variable. The global convergence results are developed in a very general setting of computing trial directions by a semismooth Levenberg–Marquardt method where a backtracking line search technique projects trial steps onto the feasible interior set. We establish that close to the solution set the affine scaling interior Levenberg–Marquardt algorithm is shown to converge locally Q-superlinearly depending on the quality of the semismooth and Levenberg–Marquardt parameter under an error bound assumption that is much weaker than the standard nonsingularity condition, that is, BD-regular condition under nonsmooth case. A nonmonotonic criterion should bring about speed up the convergence progress in the contours of objective function with large curvature.     

An Affine Scaling Interior Trust Region Method via Optimal Path for Solving Monotone Variational Inequality Problem with Linear Constraints

Based on a differentiable merit function proposed by Taji et al. in ＂Math. Prog. Stud., 58, 1993, 369-383＂, the authors propose an affine scaling interior trust region strategy via optimal path to modify Newton method for the strictly monotone variational inequality problem subject to linear equality and inequality constraints. By using the eigensystem decomposition and affine scaling mapping, the authors form an affine scaling optimal curvilinear path very easily in order to approximately solve the trust region subproblem. Theoretical analysis is given which shows that the proposed algorithm is globally convergent and has a local quadratic convergence rate under some reasonable conditions.     

仿射变换内点信赖域类方法解单调变分不等式问题

基于Taji引入的一类可微的简单边界约束的严格单调变分不等式问题的势函数,本文提出了仿射变换内点信赖域类修正牛顿法.进一步,作者不仅从理论上证明了该算法的整体收敛性,并且在合理的假设条件下,给出了算法具有局部二次收敛速率.     

线性不等式约束的广义非线性互补问题的仿射内点信赖域方法

提供了一种新的非单调内点回代线搜索技术的仿射内点信赖域方法解线性不等式约束的广义非线性互补问题(GCP).基于广义互补问题构成的半光滑方程组的广义Jacobian矩阵,算法使用l2范数作为半光滑方程组的势函数,形成的信赖域子问题为一个带椭球约束的线性化的二次模型.利用广义牛顿方程计算试探迭代步,通过内点映射回代技术确保迭代点是严格内点,保证了算法的整体收敛性.在合理的条件下,证明了信赖域算法在接近最优点时可转化为广义拟牛顿步,进而具有局部超线性收敛速率.非单调技术将克服高度非线性情况加速收敛进展.最后,数值结果表明了算法的有效性.     

Combining trust region and linesearch algorithm for equality constrained optimization

In this paper, a combining trust region and line search algorithm for equality constrained optimization is proposed. At each iteration, we only need to solve the trust region subproblem once, when the trust region trial step can not be accepted, we switch to line search to obtain the next iteration. Hence, the difficulty of repeated solving trust region subproblem in an iterate is avoided. In order to allow the direction of negative curvature, we add second correction step in trust region step and employ nommonotone technique in line search. The global convergence and local superlinearly rate are established under certain assumptions. Some numerical examples are given to illustrate the efficiency of the proposed algorithm.     

On convergence analysis of a derivative-free trust region algorithm for constrained optimization with separable structure

In this paper,we propose a derivative-free trust region algorithm for constrained minimization problems with separable structure,where derivatives of the objective function are not available and cannot be directly approximated.At each iteration,we construct a quadratic interpolation model of the objective function around the current iterate.The new iterates are generated by minimizing the augmented Lagrangian function of this model over the trust region.The filter technique is used to ensure the feasibility and optimality of the iterative sequence.Global convergence of the proposed algorithm is proved under some suitable assumptions.     

Global and local convergence of a class of penalty-free-type methods for nonlinear programming

We present a class of trust region algorithms without using a penalty function or a filter for nonlinear inequality constrained optimization and analyze their global and local convergence. In each iteration, the algorithms reduce the value of objective function or the measure of constraints violation according to the relationship between optimality and feasibility. A sequence of steps focused on improving optimality is referred to as an f-loop, while some restoration phase focuses on improving feasibility and is called an h-loop. In an f-loop, the algorithms compute trial step by solving a classic QP subproblem rather than using composite-step strategy. Global convergence is ensured by requiring the constraints violation of each iteration not to exceed an progressively tighter bound on constraints violation. By using a second order correction strategy based on active set identification technique, Marato’s effect is avoided and fast local convergence is shown. The preliminary numerical results are encouraging.     

INTERIOR POINT PROJECTED REDUCED HESSIAN METHOD WITH TRUST REGION STRATEGY FOR NONLINEAR CONSTRAINED OPTIMIZATION

§1　IntroductionIn this paper we analyze an interior point scaling projected reduced Hessian methodwith trust region strategy for solving the nonlinear equality constrained optimizationproblem with nonnegative constraints on variables:min　f(x)s.t.　c(x) =0 (1.1)x≥0where f∶Rn→R is the smooth nonlinear function,notnecessarily convex and c(x)∶Rn→Rm(m≤n) is the vector nonlinear function.There are quite a few articles proposing localsequential quadratic programming reduced Hessian methods…     

一类变分不等式问题的信赖域算法

基于J.M.Peng研究一类变分不等式问题（简记为VIP）时所提出的价值函数，本文提出了求解强单调的VIP的一个新的信赖域算法。和已有的处理VIP的信赖域方法不同的是：它在每步迭代时，不必求解带信赖域界的子问题，仅解一线性方程组而求得试验步。这样，计算的复杂性一般来说可降低。在通常的假设条件下，文中还证明了算法的整体收敛性。最后，在梯度是半光滑和约束是矩形域的假设下，该算法还是超线性收敛的。