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

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

有界约束半光滑方程组的非单调投影信赖域方法

投影信赖域策略结合非单调线搜索算法解有界约束非线性半光滑方程组.基于简单有界约束的非线性优化问题构建信赖域子问题,半光滑类牛顿步在可行域投影得到投影牛顿的试探步,获得新的搜索方向,结合非单调线搜索技术得到回代步,获得新的步长.在合理的条件下,证明算法不仅具有整体收敛性且保持超线性收敛速率.引入非单调技术能克服高度非线性的病态问题,加速收敛性进程,得到超线性收敛速率.     

解线性约束优化问题的新锥模型信赖域法

本文提出了一个解线性等式约束优化问题的新锥模型信赖域方法.论文采用零空间技术消除了新锥模型子问题中的线性等式约束,用折线法求解转换后的子问题,并给出了解线性等式约束优化问题的信赖域方法.论文提出并证明了该方法的全局收敛性,并给出了该方法解线性等式约束优化问题的数值实验.理论和数值实验结果表明新锥模型信赖域方法是有效的,这给出了用新锥模型进一步研究非线性优化的基础.     

非线性等式约束优化问题的仿射信赖域方法

提出非线性等式和有界约束优化问题的结合非单调技术的仿射信赖域方法. 结合信赖域方法和内点回代线搜索技术, 每一步迭代转到由一般信赖域子问题产生的回代步中且满足严格内点可行条件. 在合理的假设条件下, 证明了算法的整体收敛性和局部超线性收敛速率. 最后, 数值结果表明了所提供的算法具有有效性.     

解线性约束优化问题的新锥模型信赖域3法

本文提出了一个解线性等式约束优化问题的新锥模型信赖域方法．论文采用零空间技术消除了新锥模型子问题中的线性等式约束，用折线法求解转换后的子问题，并给出了解线性等式约束优化问题的信赖域方法．论文提出并证明了该方法的全局收敛性，并给出了该方法解线性等式约束优化问题的数值实验．理论和数值实验结果表明新锥模型信赖域方法是有效的，这给出了用新锥模型进一步研究非线性优化的基础．     

非单调技术预条件弧线路径信赖域解无约束优化

本文提供修正近似信赖域类型路经三类预条件弧线路径方法解无约束最优化问题.使用对称矩阵的稳定Bunch-Parlett易于形成信赖域子问题的弧线路径,使用单位下三角矩阵作为最优路径和修正梯度路径的预条件因子.运用预条件因子改进Hessian矩阵特征值分布加速预条件共轭梯度路径收敛速度.基于沿着三类路径信赖域子问题产生试探步,将信赖域策略与非单调线搜索技术相结合作为新的回代步.理论分析证明在合理条件下所提供的算法是整体收敛性,并且具有局部超线性收敛速率,数值结果表明算法的有效性.     

关于求解随机用户均衡问题的截断拟牛顿型信赖域法研究

信赖域法是一种保证全局收敛性的优化算法,为避免Hessian矩阵的计算,基于拟牛顿校正公式构造了求解带线性等式约束的非线性规划问题的截断拟牛顿型信赖域法.首先给出了截断拟牛顿型信赖域法的构造过程及具体步骤;然后针对随机用户均衡模型中变量和约束的特点对算法进行了修正,并将多种拟牛顿校正公式下所得结果与牛顿型信赖域法的结果进行了比较,结果发现基于对称秩1校正公式的信赖域法更为合适.最后基于数值算例结果得到了一些在算法编程过程中的重要结论,对其它形式信赖域法的编程实现具有一定的参考意义.     

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

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

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

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

等式约束优化的组合信赖域与拟牛顿算法

本文对等式约束问题提出了一个种组合信赖域与拟牛顿算法。该算法的特点是若Lagrangian函数的近似Ｈessian阵在等式约束Jacobi阵的零空间正定的,则选择拟牛顿算法,否则用信赖域算法,在通常信赖域算法的收敛假设下,该文证明了组合算法的全局收敛性。     

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…     

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.     

信赖域策略的内点投影既约Hessian方法解非线性约束优化

A interior point scaling projected reduced Hessian method with combination of nonmonotonic backtracking technique and trust region strategy for nonlinear equality constrained optimization with nonegative constraint on variables is proposed. In order to deal with large problems,a pair of trust region subproblems in horizontal and vertical subspaces is used to replace the general full trust region subproblem. The horizontal trust region subproblem in the algorithm is only a general trust region subproblem while the vertical trust region subproblem is defined by a parameter size of the vertical direction subject only to an ellipsoidal constraint. Both trust region strategy and line search technique at each iteration switch to obtaining a backtracking step generated by the two trust region subproblems. By adopting the l1 penalty function as the merit function, the global convergence and fast local convergence rate of the proposed algorithm are established under some reasonable conditions. A nonmonotonic criterion and the second order correction step are used to overcome Maratos effect and speed up the convergence progress in some ill-conditioned cases.     

Projected Hessian algorithm with backtracking interior point technique for linear constrained optimization

In this paper, we propose a new trust-region-projected Hessian algorithm with nonmonotonic backtracking interior point technique for linear constrained optimization. By performing the QR decomposition of an affine scaling equality constraint matrix, the conducted subproblem in the algorithm is changed into the general trust-region subproblem defined by minimizing a quadratic function subject only to an ellipsoidal constraint. By using both the trust-region strategy and the line-search technique, each iteration switches to a backtracking interior point step generated by the trustregion subproblem. The global convergence and fast local convergence rates for the proposed algorithm are established under some reasonable assumptions. A nonmonotonic criterion is used to speed up the convergence in some ill-conditioned cases. Selected from Journal of Shanghai Normal University (Natural Science), 2003, 32(4): 7–13     

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.     

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.     

An Affine Scaling Interior Trust-Region Algorithm Combining Backtracking Line Search with Filter Technique for Nonlinear Constrained Optimization

In this article, an affine scaling interior trust-region algorithm which employs backtracking line search with filter technique is presented for solving nonlinear equality constrained programming with nonnegative constraints on variables. At current iteration, the general full affine scaling trust-region subproblem is decomposed into a pair of trust-region subproblems in vertical and horizontal subspaces, respectively. The trial step is given by the solutions of the pair of trust-region subproblems. Then, the step size is decided by backtracking line search together with filter technique. This is different from traditional trust-region methods and has the advantage of decreasing the number of times that a trust-region subproblem must be resolved in order to determine a new iteration point. Meanwhile, using filter technique instead of merit function to determine a new iteration point can avoid the difficult decisions regarding the choice of penalty parameters. Under some reasonable assumptions, the new method possesses the property of global convergence to the first-order critical point. Preliminary numerical results show the effectiveness of the proposed algorithm.     

一类拟牛顿非单调信赖域算法及其收敛性

本文提出了一类求解无约束最优化问题的非单调信赖域算法.将非单调Wolfe线搜索技术与信赖域算法相结合,使得新算-法不仅不需重解子问题,而且在每步迭代都满足拟牛顿方程同时保证目标函数的近似Hasse阵Bk的正定性.在适当的条件下,证明了此算法的全局收敛性.数值结果表明该算法的有效性.