解约束优化的分段线性有理NCP函数

本文给出新的NCP函数,这些函数是分段线性有理正则伪光滑的,且具有良好的性质.把这些NCP函数应用到解非线性优化问题的方法中.例如,把求解非线性约束优化问题的KKT点问题分别用QP-free方法,乘子法转化为解半光滑方程组或无约束优化问题.然后再考虑用非精确牛顿法或者拟牛顿法来解决该半光滑方程组或无约束优化问题.这个方法是可实现的,且具有全局收敛性.可以证明在一定假设条件下,该算法具有局部超线性收敛性.     

具有分片线性NCP函数的QP-Free可行域方法

In this paper, a QP-free feasible method with piecewise NCP functions is proposed for nonlinear inequality constrained optimization problems. The new NCP functions are piecewise linear-rational, regular pseudo-smooth and have nice properties. This method is based on the solutions of linear systems of equation reformulation of KKT optimality conditions, by using the piecewise NCP functions. This method is implementable and globally convergent without assuming the strict complementarity condition, the isolatedness of accumulation points. Furthermore, the gradients of active constraints are not requested to be linearly independent. The submatrix which may be obtained by quasi-Newton methods, is not requested to be uniformly positive definite. Preliminary numerical results indicate that this new QP-free method is quite promising.     

带NCP函数的信赖域滤子方法

滤子方法最初是由Fletcher和Leyffer在2002年提出的.这种方法的原理是:在一个试探步,如果相应的目标函数值或约束违反度函数值下降,那么该试探步就会被接受.利用Fischer-Burmeister NCP函数来修正滤子中的约束违反度函数,同时证明了这个新的滤子方法具有全局收敛性.     

New reformulation and feasible semismooth Newton method for a class of stochastic linear complementarity problems

A class of stochastic linear complementarity problems (SLCPs) with finitely many realizations is considered. We first formulate the problem as a new constrained minimization problem. Then, we propose a feasible semismooth Newton method which yields a stationary point of the constrained minimization problem. We study the condition for the level set of the objective function to be bounded. As a result, the condition for the solution set of the constrained minimization problem is obtained. The global and quadratic convergence of the proposed method is proved under certain assumptions. Preliminary numerical results show that this method yields a reasonable solution with high safety and within a small number of iterations.     

不等式约束优化一个可行序列线性方程组算法

提出了求解非线性不等式约束优化问题的一个可行序列线性方程组算法. 在每次迭代中, 可行下降方向通过求解两个线性方程组产生, 系数矩阵具有较好的稀疏性. 在较为温和的条件下, 算法具有全局收敛性和强收敛性, 数值试验表明算法是有效的.     

A feasible descent SQP algorithm for general constrained optimization without strict complementarity

In this paper, a class of optimization problems with equality and inequality constraints is discussed. Firstly, the original problem is transformed to an associated simpler problem with only inequality constraints and a parameter. The later problem is shown to be equivalent to the original problem if the parameter is large enough (but finite), then a feasible descent SQP algorithm for the simplified problem is presented. At each iteration of the proposed algorithm, a master direction is obtained by solving a quadratic program (which always has a feasible solution). With two corrections on the master direction by two simple explicit formulas, the algorithm generates a feasible descent direction for the simplified problem and a height-order correction direction which can avoid the Maratos effect without the strict complementarity, then performs a curve search to obtain the next iteration point. Thanks to the new height-order correction technique, under mild conditions without the strict complementarity, the globally and superlinearly convergent properties are obtained. Finally, an efficient implementation of the numerical experiments is reported.     

Unified steerable phase I-phase II method of feasible directions for semi-infinite optimization

In this paper, we complete a cycle in the construction of methods of feasible directions for solving semi-infinite constrained optimization problems. Earlier phase I-phase II methods of feasible directions used one search direction rule in all of ⁿ with two stepsize rules, one for feasible points and one for infeasible points. The algorithm presented in this paper uses both a single search direction rule and a single stepsize rule in all of ⁿ . In addition, the new algorithm incorporates a steering parameter which can be used to control the speed with which feasibility is achieved. The new algorithm is simpler to analyze and performs somewhat better than existing, first order, phase I-phase II methods. The new algorithm is globally convergent, with linear rate.The research reported herein was sponsored in part by the National Science Foundation Grant ECS-8713334, the Air Force Office of Scientific Research Contract AFOSR-86-0116, and the State of California MICRO Program Grant 532410-19900.The authors would like to thank Dr. J. Higgins for providing the C-code of Algorithm 3.1.     

A smoothing QP-free infeasible method for nonlinear inequality constrained optimization

In this paper,a smoothing QP-free infeasible method is proposed for nonlinear inequality constrained optimization problems.This iterative method is based on the solution of nonlinear equations which is obtained by the multipliers and the smoothing Fisher-Burmeister function for the KKT first-order optimality conditions.Comparing with other QP-free methods, this method does not request the strict feasibility of iteration.In particular,this method is implementable and globally convergent without assuming the strict complementarity condition and the isolatedness of accumulation points.Furthermore,the gradients of active constraints are not requested to be linearly independent.Preliminary numerical results indicate that this smoothing QP-free infeasible method is quite promising.     

Properties of Restricted NCP Functions for Nonlinear Complementarity Problems

In this paper, we study restricted NCP functions which may be used to reformulate the nonlinear complementarity problem as a constrained minimization problem. In particular, we consider three classes of restricted NCP functions, two of them introduced by Solodov and the other proposed in this paper. We give conditions under which a minimization problem based on a restricted NCP function enjoys favorable properties, such as equivalence between a stationary point of the minimization problem and the nonlinear complementarity problem, strict complementarity at a solution of the minimization problem, and boundedness of the level sets of the objective function. We examine these properties for three restricted NCP functions and show that the merit function based on the restricted NCP function proposed in this paper enjoys favorable properties compared with those based on the other restricted NCP functions.     

解非线性约束优化问题的依赖域算法

本文对一般非线性约束优化问题提出了一个信赖域算法,导出了等价的KKT条件.在试探步满足适当条件下,证明了算法的全局收敛性,并进行了数值试验.     

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 QP Free Feasible Method

In [12], a QP free feasible method was proposed for the minimization of a smooth function subject to smooth inequality constraints. This method is based on the solutions of linear systems of equations, the reformulation of the KKT optimality conditions by using the Fischer-Burmeister NCP function. This method ensures the feasibility of all iterations. In this paper, we modify the method in [12] slightly to obtain the local convergence under some weaker conditions. In particular, this method is implementable and globally convergent without assuming the linear independence of the gradients of active constrained functions and the uniformly positive definiteness of the submatrix obtained by the Newton or Quasi Newton methods. We also prove that the method has superlinear convergence rate under some mild conditions. Some preliminary numerical results indicate that this new QP free feasible method is quite promising.     

A type of efficient feasible SQP algorithms for inequality constrained optimization

In this paper, motivated by Zhu et al. methods [Z.B. Zhu, K.C. Zhang, J.B. Jian, An improved SQP algorithm for inequality constrained optimization, Math. Meth. Oper. Res. 58 (2003) 271-282; Zhibin Zhu, Jinbao Jian, An efficient feasible SQP algorithm for inequality constrained optimization, Nonlinear Anal. Real World Appl. 10(2) (2009) 1220-1228], we propose a type of efficient feasible SQP algorithms to solve nonlinear inequality constrained optimization problems. By solving only one QP subproblem with a subset of the constraints estimated as active, a class of revised feasible descent directions are generated per single iteration. These methods are implementable and globally convergent. We also prove that the algorithms have superlinear convergence rate under some mild conditions.     

基于一个新的NCP函数的光滑牛顿法求解非线性互补问题

本文研究了非线性互补的光滑化问题.利用一个新的光滑NCP函数将非线性互补问题转化为等价的光滑方程组,并在此基础上建立了求解P0-函数非线性互补问题的一个完全光滑化牛顿法,获得了算法的全局收敛性和局部二次收敛性的结果.并给出数值实验验证了理论分析的正确性.     

Properties of a family of merit functions and a merit function method for the NCP

A family of merit functions are proposed, which are the generalization of several existing merit functions. A number of favorable properties of the proposed merit functions are established. By using these properties, a merit function method for solving nonlinear complementarity problem is investigated, and the global convergence of the proposed algorithm is proved under some standard assumptions. Some preliminary numerical results are given.     

New multiplier method for solving linear complementarity problems

A new multiplier method for solving the linear complementarity problem LCP(q, M) is proposed. By introducing a Lagrangian of LCP(q, M), a new smooth merit function ϑ(x, λ) for LCP(q, M) is constructed. Based on it, a simple damped Newton-type algorithm with multiplier self-adjusting step is presented. When M is a P-matrix, the sequence {ϑ(x ^k, λ ^k)} (where {(x ^k, λ ^k)} is generated by the algorithm) is globally linearly convergent to zero and convergent in a finite number of iterations if the solution is degenerate. Numerical results suggest that the method is highly efficient and promising. Selected from Numerical Mathematics (A Journal of Chinese Universities), 2004, 26(2): 162–171     

An exact penalty function method with global convergence properties for nonlinear programming problems

In this paper a new continuously differentiable exact penalty function is introduced for the solution of nonlinear programming problems with compact feasible set. A distinguishing feature of the penalty function is that it is defined on a suitable bounded open set containing the feasible region and that it goes to infinity on the boundary of this set. This allows the construction of an implementable unconstrained minimization algorithm, whose global convergence towards Kuhn-Tucker points of the constrained problem can be established.     

A new sequential systems of linear equations algorithm of feasible descent for inequality constrained optimization

Based on a new efficient identification technique of active constraints introduced in this paper, a new sequential systems of linear equations （SSLE） algorithm generating feasible iterates is proposed for solving nonlinear optimization problems with inequality constraints. In this paper, we introduce a new technique for constructing the system of linear equations, which recurs to a perturbation for the gradients of the constraint functions. At each iteration of the new algorithm, a feasible descent direction is obtained by solving only one system of linear equations without doing convex combination. To ensure the global convergence and avoid the Maratos effect, the algorithm needs to solve two additional reduced systems of linear equations with the same coefficient matrix after finite iterations. The proposed algorithm is proved to be globally and superlinearly convergent under some mild conditions. What distinguishes this algorithm from the previous feasible SSLE algorithms is that an improving direction is obtained easily and the computation cost of generating a new iterate is reduced. Finally, a preliminary implementation has been tested.     

An improved feasible QP-free algorithm for inequality constrained optimization

In this paper, an improved feasible QP-free method is proposed to solve nonlinear inequality constrained optimization problems. Here, a new modified method is presented to obtain the revised feasible descent direction. In view of the computational cost, the most attractive feature of the new algorithm is that only one system of linear equations is required to obtain the revised feasible descent direction. Thereby, per single iteration, it is only necessary to solve three systems of linear equations with the same coefficient matrix. In particular, without the positive definiteness assumption on the Hessian estimate, the proposed algorithm is still global convergence. Under some suitable conditions, the superlinear convergence rate is obtained.     

3-分片线性NCP函数的滤子QP-free算法

本文定义一个3-分片线性的NCP函数,并对非线性约束优化问题,提出了带有这分片NCP函数的QP-free非可行域算法.根据优化问题的一阶KKT条件,利用乘子和NCP函数,得到非光滑方程,本文给出一个非光滑方程的迭代算法.这算法包含原始-对偶变量,在局部意义下,可看成关于一阶KKT最优条件的的扰动拟牛顿迭代算法.在线性搜索时,这算法采用滤子方法.本文给出的算法是可实现的并具有全局收敛性,且在适当假设下具有超线性收敛性.