A hybrid trust region algorithm for unconstrained optimization

This paper presents a hybrid trust region algorithm for unconstrained optimization problems. It can be regarded as a combination of ODE-based methods, line search and trust region techniques. A feature of the proposed method is that at each iteration, a system of linear equations is solved only once to obtain a trial step. Further, when the trial step is not accepted, the method performs an inexact line search along it instead of resolving a new linear system. Under reasonable assumptions, the algorithm is proven to be globally and superlinearly convergent. Numerical results are also reported that show the efficiency of this proposed method.     

An ODE-based trust region method for unconstrained optimization problems

In this paper, a new trust region algorithm is proposed for solving unconstrained optimization problems. This method can be regarded as a combination of trust region technique, fixed step-length and ODE-based methods. A feature of this proposed method is that at each iteration, only a system of linear equations is solved to obtain a trial step. Another is that when a trial step is not accepted, the method generates an iterative point whose step-length is defined by a formula. Under some standard assumptions, it is proven that the algorithm is globally convergent and locally superlinear convergent. Preliminary numerical results are reported.     

A non-monotone trust region algorithm for unconstrained optimization with dynamic reference iteration updates using filter

We present a non-monotone trust region algorithm for unconstrained optimization. Using the filter technique of Fletcher and Leyffer, we introduce a new filter acceptance criterion and use it to define reference iterations dynamically. In contrast with the early filter criteria, the new criterion ensures that the size of the filter is finite. We also show a correlation between problem dimension and the filter size. We prove the global convergence of the proposed algorithm to first- and second-order critical points under suitable assumptions. It is significant that the global convergence analysis does not require the common assumption of monotonicity of the sequence of objective function values in reference iterations, as assumed by the standard non-monotone trust region algorithms. Numerical experiments on the CUTEr problems indicate that the new algorithm is competitive compared to some representative non-monotone trust region algorithms.     

结合有效集和多维滤子技术的拟Newton信赖域算法(英文)

针对界约束优化问题,提出一个修正的多维滤子信赖域算法.将滤子技术引入到拟Newton信赖域方法,在每步迭代,Cauchy点用于预测有效集,此时试探步借助于求解一个较小规模的信赖域子问题获得.在一定条件下,本文所提出的修正算法对于凸约束优化问题全局收敛.数值试验验证了新算法的实际运行结果.     

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.     

A modified SLP algorithm and its global convergence

This paper concerns a filter technique and its application to the trust region method for nonlinear programming (NLP) problems. We used our filter trust region algorithm to solve NLP problems with equality and inequality constraints, instead of solving NLP problems with just inequality constraints, as was introduced by Fletcher et al. [R. Fletcher, S. Leyffer, Ph.L. Toint, On the global converge of an SLP-filter algorithm, Report NA/183, Department of Mathematics, Dundee University, Dundee, Scotland, 1999]. We incorporate this filter technique into the traditional trust region method such that the new algorithm possesses nonmonotonicity. Unlike the tradition trust region method, our algorithm performs a nonmonotone filter technique to find a new iteration point if a trial step is not accepted. Under mild conditions, we prove that the algorithm is globally convergent.     

一类LC1规划问题的超线性收敛ODE信赖域算法

In this paper, a new trust region algorithm for unconstrained LC1 optimization problems is given. Compare with those existing trust regiion methods, this algorithm has a different feature: it obtains a stepsize at each iteration not by soloving a quadratic subproblem with a trust region bound, but by solving a system of linear equations. Thus it reduces computational complexity and improves computation efficiency. It is proven that this algorithm is globally convergent and locally superlinear under some conditions.     

一种求解序列二次规划结合信赖域的多维滤子算法

求解非线性规划问题最有效的方法之一为序列二次规划。但是,由于序列二次规划结合信赖域时,会出现可能无解的情况(即不相容性)。而本文针对不相容性提出了一类序列二次规划结合信赖域的多维相容滤子算法。首先,本文根据一般文献中提及的方法对其约束条件引进参数变量,对其目标函数加以惩罚,即实行了可行化处理(也就是无需可行性恢复阶段),从而克服了不相容性。其次,本文提出了多维滤子条件来对迭代步进行选择性的接受,从而避免了传统二维滤子算法的严格条件,使得对迭代步的接受程度大大的放松。最后针对可能出现的maratos效应,我们通过二阶校正策略提出了一种修改后的多维滤子算法。同时,在一定的假设条件下算法具有全局收敛性。     

A filter method for nonlinear semidefinite programming with global convergence

In this study, a new filter algorithm is presented for solving the nonlinear semidefinite programming. This algorithm is inspired by the classical sequential quadratic programming method. Unlike the traditional filter methods, the sufficient descent is ensured by changing the step size instead of the trust region radius. Under some suitable conditions, the global convergence is obtained. In the end, some numerical experiments are given to show that the algorithm is effective.     

一类非线性互补问题的信赖域算法

In this paper,an ODE-type trust region algorithm for solving a class of nonlinear complementarity problems is proposed.A feature of this algorithm is that only the solution of linear systems of equations is required at each iteration,thus avoiding the need for solving a quadratic subproblem with a trust region bound.Under some conditions,it is proven that this algorithm is globally and locally superlinear convergent.The limited numerical examples show its efficiency.     

A new hybrid method for nonlinear complementarity problems

In this paper, a new hybrid method is proposed for solving nonlinear complementarity problems (NCP) with P ₀ function. In the new method, we combine a smoothing nonmonotone trust region method based on a conic model and line search techniques. We reformulate the NCP as a system of semismooth equations using the Fischer-Burmeister function. Using Kanzow’s smooth approximation function to construct the smooth operator, we propose a smoothing nonmonotone trust region algorithm of a conic model for solving the NCP with P ₀ functions. This is different from the classical trust region methods, in that when a trial step is not accepted, the method does not resolve the trust region subproblem but generates an iterative point whose steplength is defined by a line search. We prove that every accumulation point of the sequence generated by the algorithm is a solution of the NCP. Under a nonsingularity condition, the superlinear convergence of the algorithm is established without a strict complementarity condition.     

A nonmonotone filter trust region method for nonlinear constrained optimization

In this paper, we present a nonmonotone filter trust region algorithm for solving nonlinear equality constrained optimization. Similar to Bryd–Omojokun class of algorithms, each step is composed of a quasi-normal step and a tangential step. This new method has more flexibility for the acceptance of the trial step compared to the filter methods, and requires less computational costs compared with the monotone methods. Under reasonable conditions, we give the globally convergence properties. Numerical tests are presented that confirm the efficiency of the approach.     

A new supermemory gradient method for unconstrained optimization problems

This paper presents a new supermemory gradient method for unconstrained optimization problems. It can be regarded as a combination of ODE-based methods, line search and subspace techniques. The main characteristic of this method is that, at each iteration, a lower dimensional system of linear equations is solved only once to obtain a trial step, thus avoiding solving a quadratic trust region subproblem. Another is that when a trial step is not accepted, this proposed method generates an iterative point whose step-length satisfies Armijo line search rule, thus avoiding resolving linear system of equations. Under some reasonable assumptions, the method is proven to be globally convergent. Numerical results show the efficiency of this proposed method in practical computation.     

Truncated Trust Region Methods Based on Preconditioned Iterative Subalgorithms for Large Sparse Systems of Nonlinear Equations

This paper is devoted to globally convergent methods for solving large sparse systems of nonlinear equations with an inexact approximation of the Jacobian matrix. These methods include difference versions of the Newton method and various quasi-Newton methods. We propose a class of trust region methods together with a proof of their global convergence and describe an implementable globally convergent algorithm which can be used as a realization of these methods. Considerable attention is concentrated on the application of conjugate gradient-type iterative methods to the solution of linear subproblems. We prove that both the GMRES and the smoothed COS well-preconditioned methods can be used for the construction of globally convergent trust region methods. The efficiency of our algorithm is demonstrated computationally by using a large collection of sparse test problems.     

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

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

A smoothing conic trust region filter method for the nonlinear complementarity problem

This paper discusses nonlinear complementarity problems; its goal is to present a globally and superlinearly convergent algorithm for the discussed problems. Filter methods are extensively studied to handle nonlinear complementarity problem. Because of good numerical results, filter techniques are attached. By means of a filter strategy, we present a new trust region method based on a conic model for nonlinear complementarity problems. Under a proper condition, the superlinear convergence of the algorithm is established without the strict complementarity condition.     

一个无约束有限内存信赖域方法及其实现

本文针对大规模无约束优化问题研究了一个新的有限内存信赖域实现方法,提出了一个在有限维（维数≤2m＋1）子空间上精确求解信赖域子问题的方法,大大减少了计算量;分析了方法的收敛性,并详细给出了数值计算方法,最后通过数值实验验证了方法的有效性.     

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.     

Dealing with singularities in nonlinear unconstrained optimization

We propose a new trust region based optimization algorithm for solving unconstrained nonlinear problems whose second derivatives matrix is singular at a local solution. We give a theoretical characterization of the singularity in this context and we propose an iterative procedure which allows to identify a singularity in the objective function during the course of the optimization algorithm, and artificially adds curvature to the objective function. Numerical tests are performed on a set of unconstrained nonlinear problems, both singular and non-singular. Results illustrate the significant performance improvement compared to classical trust region and filter algorithms proposed in the literature. The approach is also shown to be competitive with tensor methods in terms of efficiency while reaching a higher level of robustness.     

带非线性不等式约束优化问题的信赖域算法

借助于KKT条件和NCP函数,提出了求解带非线性不等式约束优化问题的信赖域算法.该算法在每一步迭代时,不必求解带信赖域界的二次规划子问题,仅需求一线性方程组系统.在适当的假设条件下,它还是整体收敛的和局部超线性收敛的.数值实验结果表明该方法是有效的.