A Dual Algorithm for Minimizing a Quadratic Function with Two Quadratic Constraints

In this paper, we present a dual algorithm for minimizing a convex quadratic function with two quadratic constraints. Such a minimization problem is a subproblem that appears in some trust region algorithms for general nonlinear programming. Some theoretical properties of the dual problem are given. Global convergence of the algorithm is proved and a local superlinear convergence result is presented. Numerical examples are also provided.     

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.     

LC1约束规划问题的超线性收敛ODE型信赖域算法

本文对带线性等式约束的LC^1优化问题提出了一个新的ODE型信赖域算法，它在每一次迭代时，不必求解带信赖域界的子问题，仅解一线性方程组而求得试验步。从而可以降低计算的复杂性，提高计算效率，在一定的条件下，文中还证明了该算法是超线性收敛的。     

An improved trust region algorithm for nonlinear equations

In this paper, we present a new trust region algorithm for the system of singular nonlinear equations with the regularized trust region subproblem. The new algorithm preserves the global convergence of the traditional trust region algorithm, and has the quadratic convergence under some suitable conditions. Finally, some numerical results are given.     

A superlinearly convergent ODE-type trust region algorithm for nonsmooth nonlinear equations

This paper presents a new trust region algorithm for solving nonsmooth nonlinear equation problems which posses the smooth plus non-smooth decomposition. At each iteration, this method obtains a trial step by solving a system of linear equations, hence avoiding the need for solving a quadratic programming subproblem with a trust region bound. From a computational point of view, this approach may reduce computational effort and hence improve computational efficiency. Furthermore, it is proved under appropriate assumptions that this algorithm is globally and locally super-linearly convergent. Some numerical examples are reported.     

Convergence of the BFGS-SQP Method for Degenerate Problems

In this paper, we propose a BFGS (Broyden–Fletcher–Goldfarb–Shanno)-SQP (sequential quadratic programming) method for nonlinear inequality constrained optimization. At each step, the method generates a direction by solving a quadratic programming subproblem. A good feature of this subproblem is that it is always consistent. Moreover, we propose a practical update formula for the quasi-Newton matrix. Under mild conditions, we prove the global and superlinear convergence of the method. We also present some numerical results.     

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

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

一类求解线性约束非线性规划问题的可行方向法

Wilson,Han和Powell提出的序列二次规划方法(简称SQP方法)是求解非线性规划问题的一个著名方法,这种方法每次迭代的搜索方向是通过求解一个二次规划子问题得到的,本文受[1]启发,得到二次规划子问题的一个近似解,进而给出了一类求解线性约束非线性规划问题的可行方向法,在约束集合满足正则性的条件下,证明了该算法对五种常用线性搜索方法具有全局收敛性。     

解等式约束优化的既约Hessian依赖域方法

本文提出了解等式约束优化的一个信赖域方法,该方法以既约Hessian逐步二次规划为基础,它享有信赖域方法与既约Hessian方法的优点,在通常条件下,证明了算法的全局收敛性。     

A kind of nonmonotone filter method for nonlinear complementarity problem

The nonlinear complementarity problem can be reformulated as a nonlinear programming. For solving nonlinear programming, sequential quadratic programming (SQP) type method is very effective. But the QP subproblem may be inconsistent. In this paper, we propose a kind nonmonotone filter method in which the QP subproblem is consistent. By means of nonmonotone filter, this method has no demand on the penalty parameter which is difficult to obtain. Moreover, the restoration phase is not needed any more. Under reasonable conditions, we obtain the global convergence of the algorithm. Some numerical results are presented.     

A feasible direction method for image restoration

In this work, a feasible direction method is proposed for computing the regularized solution of image restoration problems by simply using an estimate of the noise present on the data. The problem is formulated as an optimization problem with one quadratic constraint. The proposed method computes a feasible search direction by inexactly solving a trust region subproblem with the truncated Conjugate Gradient method of Steihaug. The trust region radius is adjusted to maintain feasibility and a line-search globalization strategy is employed. The global convergence of the method is proved. The results of image denoising and deblurring are presented in order to illustrate the effectiveness and efficiency of the proposed method.     

A trust region method for solving linearly constrained locally Lipschitz optimization problems

In this paper, we present a nonsmooth trust region method for solving linearly constrained optimization problems with a locally Lipschitz objective function. Using the approximation of the steepest descent direction, a quadratic approximation of the objective function is constructed. The null space technique is applied to handle the constraints of the quadratic subproblem. Next, the CG-Steihaug method is applied to solve the new approximation quadratic model with only the trust region constraint. Finally, the convergence of presented algorithm is proved. This algorithm is implemented in the MATLAB environment and the numerical results are reported.     

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     

An efficient Levenberg–Marquardt method with a new LM parameter for systems of nonlinear equations

A modified Levenberg–Marquardt method for solving singular systems of nonlinear equations was proposed by Fan [J Comput Appl Math. 2003;21;625–636]. Using trust region techniques, the global and quadratic convergence of the method were proved. In this paper, to improve this method, we decide to introduce a new Levenberg–Marquardt parameter while also incorporate a new nonmonotone technique to this method. The global and quadratic convergence of the new method is proved under the local error bound condition. Numerical results show the new algorithm is efficient and promising.     

A SUPERLINEARLY CONVERGENT TRUST REGION ALGORITHM FOR LC^1 CONSTRAINED OPTIMIZATION PROBLEMS

In this paper, a new trust region algorithm for nonlinear equality constrained LC^1 optimization problems is given. It obtains a search direction at each iteration not by solving a quadratic programming subproblem with a trust region bound, but by solving a system of linear equations. Since the computational complexity of a QP-Problem is in general much larger than that of a system of linear equations, this method proposed in this paper may reduce the computational complexity and hence improve computational efficiency. Furthermore, it is proved under appropriate assumptions that this algorithm is globally and super-linearly convergent to a solution of the original problem. Some numerical examples are reported, showing the proposed algorithm can be beneficial from a computational point of view.     

An adaptive trust region method and its convergence

In this paper, a new trust region subproblem is proposed. The trust radius in the new subproblem adjusts itself adaptively. As a result, an adaptive trust region method is constructed based on the new trust region subproblem. The local and global convergence results of the adaptive trust region method are proved. Numerical results indicate that the new method is very efficient.     

A ROBUST SQP METHOD FOR OPTIMIZATION WITH INEQUALITY CONSTRAINTS

A new algorithm for inequality constrained optimization is presented, which solves a linear programming subproblem and a quadratic subproblem at each iteration. The algorithm can circumvent the difficulties associated with the possible inconsistency of QP subproblem of the original SQP method. Moreover, the algorithm can converge to a point which satisfies a certain first-order necessary condition even if the original problem is itself infeasible. Under certain condition, some global convergence results are proved and local superlinear convergence results are also obtained. Preliminary numerical results are reported.     

A NEW INEXACT SEQUENTIAL QUADRATIC PROGRAMMING ALGORITHM

This paper represents an inexact sequential quadratic programming (SQP) algorithm which can solve nonlinear programming (NLP) problems. An inexact solution of the quadratic programming subproblem is determined by a projection and contraction method such that only matrix-vector product is required. Some truncated criteria are chosen such that the algorithm is suitable to large scale NLP problem. The global convergence of the algorithm is proved.     

A new nonmonotone adaptive trust region method based on simple quadratic models

Based on simple quadratic models of the trust region subproblem, we combine the trust region method with the nonmonotone and adaptive techniques to propose a new nonmonotone adaptive trust region algorithm for unconstrained optimization. Unlike traditional trust region method, our trust region subproblem is very simple by using a new scale approximation of the minimizing function??s Hessian. The new method needs less memory capacitance and computational complexity. The convergence results of the method are proved under certain conditions. Numerical results show that the new method is effective and attractive for large scale unconstrained problems.     

An efficient sequential quadratic programming algorithm for nonlinear programming

In this paper, a new feasible sequential quadratic programming (FSQP) algorithm is proposed to solve the nonlinear programming, where a feasible descent direction is obtained by solving only one QP subproblem. In order to avoid Maratos effect, a high-order revised direction is computed by solving a linear system with involving some “active” constraints. The theoretical analysis shows that global and superlinear convergence can be deduced.