A TRUST REGION METHOD WITH A CONIC MODEL FOR NONLINEARLY CONSTRAINED OPTIMIZATION

Trust region methods are powerful and effective optimization methods.The conic model method is a new type of method with more information available at each iteration than standard quadratic-based methods.The advantages of the above two methods can be combined to form a more powerful method for constrained optimization.The trust region subproblem of our method is to minimize a conic function subject to the linearized constraints and trust region bound.At the same time,the new algorithm still possesses robust global properties.The global convergence of the new algorithm under standard conditions is established.     

A GLOBAL LINEAR AND LOCAL QUADRATIC SINGLE-STEP NONINTERIOR CONTINUATION METHOD FOR MONOTONE SEMIDEFINITE COMPLEMENTARITY PROBLEMS

A noninterior continuation method is proposed for semidefinite complementarity problem (SDCP). This method improves the noninterior continuation methods recently developed for SDCP by Chen and Tseng. The main properties of our method are: (i) it is well defined for the monotones SDCP; (ii) it has to solve just one linear system of equations at each step; (iii) it is shown to be both globally linearly convergent and locally quadratically convergent under suitable assumptions.     

INEXACT DAMPED NEWTON METHOD FOR NONLINEAR COMPLEMENTARITY PROBLEMS

In this paper, we propose an inexact clamped Newton method for solving nonlinear complementarity problems based on the equivalent B-differentiable equations.Global convergence and locally quadratic convergence are obtained,and numerical results are given.     

TWO-LEVEL METHOD FOR UNSTEADY NAVIER-STOKES EQUATIONS IN STREAM FUNCTION FORM

Two-level finite element approximation to stream function form of unsteady Navier-Stokes equations is studied. This algorithm involves solving one nonlinear system on a coarse grid and one linear problem on a fine grid. Moreover,the scaling between these two grid sizes is super-linear. Approximation,stability and convergence aspects of a fully discrete scheme are analyzed. At last a numrical example is given whose results show that the algorithm proposed in this paper is effcient.     

A CLASS OF GENERALIZED MULTISPLITTING RELAXATION METHODS FOR LINEAR COMPLEMENTARITY PROBLEMS

In this paper,a class of generalized parallel matrix multisplitting relaxation methods for solving linear complementarity problems on the high-speed multiprocessor systems is set up. This class of methods not only includes all the existing relaxation methods for the linear complementarity problems ,but also yields a lot of novel ones in the sense of multisplittlng. We establish the convergence theories of this class of generalized parallel multisplitting relaxation methods under the condition that the system matrix is an H-metrix with positive diagonal elements.     

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

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

MIXED FINITE ELEMENT METHOD FOR THE CONVECTION-DOMINATED DIFFUSION PROBLEMS WITH SMALL PARAMETER ε

In rids paper a mixed finite element method for the convection-dominated diffusion problems with small parameter ε is presented,the effect of the parameter ε on the approximation error is considered and a sufficient condition for optimal error estimates is derived. The paper also shows that under some conditions,the standard finite dement method only gives a hounded solution,however the mixed finite element method gives a convergent one.     

GLOBAL COVERGENCE OF THE NON-QUASI-NEWTON METHOD FOR UNCONSTRAINED OPTIMIZATION PROBLEMS

In this paper, the non-quasi-Newton＇s family with inexact line search applied to unconstrained optimization problems is studied. A new update formula for non-quasi-Newton＇s family is proposed. It is proved that the constituted algorithm with either Wolfe-type or Armijotype line search converges globally and Q-superlinearly if the function to be minimized has Lipschitz continuous gradient.     

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

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

CHEBYSHEV SPECTRAL-FINITE ELEMENT METHOD FOR INCOMPRESSIBLE FLUID FLOW

In this paper, we propose a mixed method for solving two-dimensional unsteady vorticity equations by using Chebyshev spectral-fiuite element approximation. The generalized stability and the optimal rate of convergence are proved. The numerical results show the advantages of such method. The technique in this paper is also useful for other nonlinear problems.     

具有分片线性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.     

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.     

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.