不等式约束优化一个新型可行QP-free算法

本文对非线性不等式约束优化问题提出了一个新的可行 QP-free 算法. 新算法保存了现有算法的优点, 并具有以下特性: (1) 算法每次迭代只需求解三个具有相同系数矩阵的线性方程组, 计算量小; (2) 可行下降方向只需通过求解一个线性方程组即可获得, 克服了以往分别求解两个线性方程组获得下降方向和可行方向, 然后再做凸组合的困难;(3) 迭代点均为可行点, 并不要求是严格内点; (4) 算法中采用了试探性线搜索,可以进一步减少计算量; (5) 算法中参数很少,数值试验表明算法具有较好的数值效果和较强的稳定性.     

非线性半定规划一个全局收敛的无罚无滤子SSDP算法

提出了一个求解非线性半定规划的无罚函数无滤子序列二次半定规划(SSDP)算法. 算法每次迭代只需求解一个二次半定规划子问题确定搜索方向; 非单调线搜索保证目标函数或约束违反度函数的充分下降, 从而产生新的迭代点. 在适当的假设条件下, 证明了算法的全局收敛性. 最后给出了初步的数值实验结果.     

A New Superlinearly Convergent SQP Algorithm for Nonlinear Minimax Problems

In this paper, the nonlinear minimax problems are discussed. By means of the Sequential Quadratic Programming （SQP）, a new descent algorithm for solving the problems is presented. At each iteration of the proposed algorithm, a main search direction is obtained by solving a Quadratic Programming （QP） which always has a solution. In order to avoid the Maratos effect, a correction direction is obtained by updating the main direction with a simple explicit formula. Under mild conditions without the strict complementarity, the global and superlinear convergence of the algorithm can be obtained. Finally, some numerical experiments are reported.     

A norm-relaxed method of feasible directions for finely discretized problems from semi-infinite programming

In this paper, a class of finely discretized Semi-Infinite Programming (SIP) problems is discussed. Combining the idea of the norm-relaxed Method of Feasible Directions (MFD) and the technique of updating discretization index set, we present a new algorithm for solving the Discretized Semi-Infinite (DSI) problems from SIP. At each iteration, the iteration point is feasible for the discretized problem and an improved search direction is computed by solving only one direction finding subproblem, i.e., a quadratic program, and some appropriate constraints are chosen to reduce the computational cost. A high-order correction direction can be obtained by solving another quadratic programming subproblem with only equality constraints. Under weak conditions such as Mangasarian–Fromovitz Constraint Qualification (MFCQ), the proposed algorithm possesses weak global convergence. Moreover, the superlinear convergence is obtained under Linearly Independent Constraint Qualification (LICQ) and other assumptions. In the end, some elementary numerical experiments are reported.     

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

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

An improved sequential quadratic programming algorithm for solving general nonlinear programming problems

In this paper, a class of general nonlinear programming problems with inequality and equality constraints is discussed. Firstly, the original problem is transformed into an associated simpler equivalent problem with only inequality constraints. Then, inspired by the ideals of the sequential quadratic programming (SQP) method and the method of system of linear equations (SLE), a new type of SQP algorithm for solving the original problem is proposed. At each iteration, the search direction is generated by the combination of two directions, which are obtained by solving an always feasible quadratic programming (QP) subproblem and a SLE, respectively. Moreover, in order to overcome the Maratos effect, the higher-order correction direction is obtained by solving another SLE. The two SLEs have the same coefficient matrices, and we only need to solve the one of them after a finite number of iterations. By a new line search technique, the proposed algorithm possesses global and superlinear convergence under some suitable assumptions without the strict complementarity. Finally, some comparative numerical results are reported to show that the proposed algorithm is effective and promising.     

Generalized monotone line search SQP algorithm for constrained minimax problems

In this article, non-linear minimax problems with general constraints are discussed. By means of solving one quadratic programming an improved direction is yielded and a second-order correction direction can also be at hand via one system of linear equations. So a new algorithm for solving the discussed problems is presented. In connection with a special merit function, the generalized monotone line search is used to yield the step size at each iteration. Under mild conditions, we can ensure global and superlinear convergence. Finally, some numerical experiments are operated to test our algorithm, and the results demonstrate that it is promising.     

一个新的SQP方法及其超线性收敛性

由Ｗｉｌｓｏｎ,Ｈａｎ,Ｐｏｗｅｌｌ发展的ＳＱＰ技术是解非线性规划的最有效的方法之一,但是,如果其中的二次子规划问题无可行解或者其搜索方向向量无界,该方法ａｎ和Ｂｕｒｋｅ「３」,周广路「２」分别对二次规划问题作了修正,克服了上述矛盾,本文在「２」的基础上,进上步修正,证明在Ａｒｍｉｊｏ搜索下算法具有全局收敛性,并通过解一辅助线性方程组,利用弧式搜索,得出该方法具有超线性收敛性。     

An improved interior-type feasible QP-free algorithm for inequality constrained optimization problems

In this paper, an improved interior-type feasible QP-free algorithm for inequality constrained optimization problems is proposed. At each iteration, by solving three systems of linear equations with the same coefficient matrix, a search direction is generated. The algorithm is proved to be globally and superlinearly convergent under some mild conditions. Preliminary numerical results show that the proposed algorithm may be promising. Advantages of the algorithm include: the uniformly nonsingularity of the coefficient matrices without the strictly complementarity condition is obtained. Moreover, the global convergence is achieved even if the number of the stationary points is infinite.     

A superlinearly convergent norm-relaxed SQP method of strongly sub-feasible directions for constrained optimization without strict complementarity

In this paper, a kind of optimization problems with nonlinear inequality constraints is discussed. Combined the ideas of norm-relaxed SQP method and strongly sub-feasible direction method as well as a pivoting operation, a new fast algorithm with arbitrary initial point for the discussed problem is presented. At each iteration of the algorithm, an improved direction is obtained by solving only one direction finding subproblem which possesses small scale and always has an optimal solution, and to avoid the Maratos effect, another correction direction is yielded by a simple explicit formula. Since the line search technique can automatically combine the initialization and optimization processes, after finite iterations, the iteration points always get into the feasible set. The proposed algorithm is proved to be globally convergent and superlinearly convergent under mild conditions without the strict complementarity. Finally, some numerical tests are reported.     

一个带固定步长的ODE型算法

提出了一种新的求解无约束优化问题的ODE型方法,其特点是:它在每次迭代时仅求解一个线性方程组系统来获得试探步;若该试探步不被接受,算法就沿着该试探步的方向求得下一个迭代点,其中步长通过固定公式计算得到.这样既避免了传统的ODE型算法中为获得可接受的试探步而重复求解线性方程组系统,又不必执行线搜索,从而减少了计算量.在适当的条件下,还证明了新算法的整体收敛性和局部超线性收敛性.数值试验结果表明:提出的算法是有效的.     

利用Fisher函数解非线性不等式约束优化问题的梯度投影算法

本文将利用梯度投影与Fisher函数提出一个新的二阶段搜索方向,给出相应的解非线性不等式约束优化问题的梯度投影算法,并证明了该算法具有全局收敛性.     

On a space extension algorithm for nondifferentiable optimization

This paper presents a version of an algorithm, due to Shor, for solving unconstrained nondifferentiable optimization problems. The algorithm uses a space extension operator in the direction of the difference between two successive subgradients. The search direction is determined by multiplying the negative of a subgradient by a positive-definite and symmetric matrix. This matrix is updated by a formula similar to the DFP updating formula for differentiable problems. An approximate line search due to Wolfe is presented. A linear rate of convergence of the successive function values is established.     

An Algorithm for Continuous Type Optimal Location Problem

In this paper, we extend the ordinary discrete type facility location problems to continuous type ones. Unlike the discrete type facility location problem in which the objective function isn't everywhere differentiable, the objective function in the continuous type facility location problem is strictly convex and continuously differentiable. An algorithm without line search for solving the continuous type facility location problems is proposed and its global convergence, linear convergence rate is proved. Numerical experiments illustrate that the algorithm suggested in this paper have smaller amount of computation, quicker convergence rate than the gradient method and conjugate direction method in some sense.     

A three-term conjugate gradient algorithm for large-scale unconstrained optimization problems

In this paper, a three-term conjugate gradient algorithm is developed for solving large-scale unconstrained optimization problems. The search direction at each iteration of the algorithm is determined by rectifying the steepest descent direction with the difference between the current iterative points and that between the gradients. It is proved that such a direction satisfies the approximate secant condition as well as the conjugacy condition. The strategies of acceleration and restart are incorporated into designing the algorithm to improve its numerical performance. Global convergence of the proposed algorithm is established under two mild assumptions. By implementing the algorithm to solve 75 benchmark test problems available in the literature, the obtained results indicate that the algorithm developed in this paper outperforms the existent similar state-of-the-art algorithms.     

一类新型DL共轭梯度法研究

提出了求解无约束优化问题的新型DL共轭梯度方法. 同已有方法不同之处在于,该方法构造了一种修正的Armijo线搜索规则,它不仅能给出当前迭代步步长, 而且还能同时确定计算下一步搜索方向时需要用到的共轭参数值. 在较弱的条件下, 建立了算法的全局收敛性理论. 数值试验表明,新型共轭梯度算法比同类方法具有更好的计算效率.     

Active-Set Projected Trust-Region Algorithm for Box-Constrained Nonsmooth Equations

In this paper, by means of an active-set strategy, we present a trust-region method for solving box-constrained nonsmooth equations. Nice properties of the proposed method include: (a) all iterates remain feasible; (b) the search direction, as adequate combination of the projected gradient direction and the trust-region direction, is an asymptotic Newton direction under mild conditions; (c) the subproblem of the proposed method, possessing the form of an unconstrained trust-region subproblem, can be solved by existing methods; (d) the subproblem of the proposed method is of reduced dimension, which is potentially cheaper when applied to solve large-scale problems. Under appropriate conditions, we establish global and local superlinear/quadratic convergence of the method. Preliminary numerical results are given.     

An SQP algorithm with cautious updating criteria for nonlinear degenerate problems

An efficient SQP algorithm for solving nonlinear degenerate problems is proposed in the paper. At each iteration of the algorithm, a quadratic programming subproblem, which is always feasible by introducing a slack variable, is solved to obtain a search direction. The steplength along this direction is computed by employing the 1∞ exact penalty function through Armijo-type line search scheme. The algorithm is proved to be convergent globally under mild conditions.     

A Coordinate Gradient Descent Method for Nonsmooth Nonseparable Minimization

This paper presents a coordinate gradient descent approach for minimizing the sum of a smooth function and a nonseparable convex function. We find a search direction by solving a subproblem obtained by a second-order approximation of the smooth function and adding a separable convex function. Under a local Lipschitzian error bound assumption, we show that the algorithm possesses global and local linear convergence properties. We also give some numerical tests (including image recovery examples) to illustrate the efficiency of the proposed method.     

带非精确线搜索的调整搜索方向DFP算法

本文介绍一类新的带调整搜索方向的Broyden算法．我们着重讨论带调整搜索方向的DFP算法的收敛性，在某些非精确线搜索的情况下，我们证明对连续可微目标函数，这算法是整体收敛的，而对一致凸目标函数，收敛速度是一步超线收敛的．从这篇文章的证明过程中，可以得到对一致凸目标函数，DFP算法具有一步超线形收敛．