求解带均衡约束数学规划问题的一个连续化方法

In this paper, a continuation method for mathematical programs with equilibrium constraints (MPEC) is proposed. By using the KKT conditions for the variational inequality constraints, the MPEC is firstly reformulated as a nonsmooth constrained optimization problem, then we solve a sequence of smooth perturbation problems, which progressively approximate the nonsmooth problem, and study the convergence of the proposed method. Numerical results showing feasibility of the approach are given.     

关于双层规划约束规格的一个注记

本文表明了非线性规划中常见的约束规格对一般双层规划不成立,并对双层规划可以满足的较弱的约束规格“部分平静”,给出了使其成立的充分条件．     

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

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

一个求解对称线性互补问题的新的迭代法

§1.引言本文考虑求解对称线性互补问题     

应用正则化子建立求解不适定问题的正则化方法的探讨

根据紧算子的奇异系统理论,提出一种新的正则化子进而建立了一类新的求解不适定问题的正则化方法。分别通过正则参数的先验选取和后验确定方法,证明了正则解的收敛性并得到了其最优的渐近收敛阶;验证了应用Newton迭代法计算最佳参数的可行性。最后建立了当算子与右端均有扰动时相应的正则化求解策略。文中所述方法完善了一般优化正则化策略的构造理论。     

一个退化线性约束下的最优化方法

对于线性约束下的非线性规划问题，过去的绝大部分文献都建立在约束为非退化的假设上．该文将去掉这一假设，就一般的线性约束问题设计了一个结构简单的新算法，并在适当的假设下证明了算法的收敛性和超线性收敛速度．     

一般线性方法的正则性

１．引言数值方法的动力特征近年引起了人们的广泛关注。其中之一就是系统的平衡态和数值方法的平衡态相一致的问题,即用一个数值方法沿定步长求解系统时,是否会出现伪平衡。不可能出现伪平衡的方法称为是正则的。ＲＫ方法和线性多步法的正则性已被众多的文献研究［２,３,４］,其它方法的正则性显然是一亟待研究的问题。本文讨论较ＲＫ方法和线性多步法远为广泛的一般线性方法的正则性。设ｆ：Ｒ~（Ｎ）→Ｒ~（Ｎ）是一充分光滑的映射,考虑求解初值问题：的一般线性方法［１］：其中步长逼近于逼近于关于微分方程真解ｙ（ｔ）在第ｎ层…     

线性不适定问题的渐近正则化方法

对线性不适定问题考虑了一类近似求解方法,即渐近正则化方法,当数据精确给定时,考虑了渐近正则化解的收敛性及收敛速度,并给出了一些逆结果。如果右端数据是近似给定的,证明了所叙方法确实为正则化方法,并考虑了偏差原理对它的应用。为了使的工作更加实际可行,还考虑了算子和右端数据同时近似给定的情形,得到了一系列的结果。     

变分不等式与互补问题、双层规划与平衡约束数学规划问题的若干进展

考虑有限维变分不等式与互补问题、双层规划以及均衡约束的数学规划问题. 在简单介绍这些问题之后,重点介绍近年来这些领域中发展迅速的几个研究方向,包括对称锥互补问题的理论与算法、变分不等式的投影收缩算法、随机变分不等式与随机互补问题的模型与方法、双层规划以及均衡约束数学规划问题的新方法. 最后提出几个进一步研究的方向.     

A Robust SQP Method for Mathematical Programs with Linear Complementarity Constraints

The relationship between the mathematical program with linear complementarity constraints (MPLCC) and its inequality relaxation is studied. Based on this relationship, a new sequential quadratic programming (SQP) method is presented for solving the MPLCC. A certain SQP technique is introduced to deal with the possible infeasibility of quadratic programming subproblems. Global convergence results are derived without assuming the linear independence constraint qualification for MPEC, the nondegeneracy condition, and any feasibility condition of the quadratic programming subproblems. Preliminary numerical results are reported. Research is partially supported by Singapore-MIT Alliance and School of Business, National University of Singapore.     

A Modified Relaxation Scheme for Mathematical Programs with Complementarity Constraints

In this paper, we consider a mathematical program with complementarity constraints. We present a modified relaxed program for this problem, which involves less constraints than the relaxation scheme studied by Scholtes (2000). We show that the linear independence constraint qualification holds for the new relaxed problem under some mild conditions. We also consider a limiting behavior of the relaxed problem. We prove that any accumulation point of stationary points of the relaxed problems is C-stationary to the original problem under the MPEC linear independence constraint qualification and, if the Hessian matrices of the Lagrangian functions of the relaxed problems are uniformly bounded below on the corresponding tangent space, it is M-stationary. We also obtain some sufficient conditions of B-stationarity for a feasible point of the original problem. In particular, some conditions described by the eigenvalues of the Hessian matrices mentioned above are new and can be verified easily. This work was supported in part by the Scientific Research Grant-in-Aid from the Ministry of Education, Science, Sports, and Culture of Japan. The authors are grateful to an anonymous referee for critical comments.     

New Relaxation Method for Mathematical Programs with Complementarity Constraints

In this paper, we present a new relaxation method for mathematical programs with complementarity constraints. Based on the fact that a variational inequality problem defined on a simplex can be represented by a finite number of inequalities, we use an expansive simplex instead of the nonnegative orthant involved in the complementarity constraints. We then remove some inequalities and obtain a standard nonlinear program. We show that the linear independence constraint qualification or the Mangasarian–Fromovitz constraint qualification holds for the relaxed problem under some mild conditions. We consider also a limiting behavior of the relaxed problem. We prove that any accumulation point of stationary points of the relaxed problems is a weakly stationary point of the original problem and that, if the function involved in the complementarity constraints does not vanish at this point, it is C-stationary. We obtain also some sufficient conditions of B-stationarity for a feasible point of the original problem. In particular, some conditions described by the eigenvalues of the Hessian matrices of the Lagrangian functions of the relaxed problems are new and can be verified easily. Our limited numerical experience indicates that the proposed approach is promising.     

Hybrid Approach with Active Set Identification for Mathematical Programs with Complementarity Constraints

We consider a mathematical program with complementarity constraints (MPCC). Our purpose is to develop methods that enable us to compute a solution or a point with some kind of stationarity to MPCC by solving a finite number of nonlinear programs. We apply an active set identification technique to a smoothing continuation method (Ref. 1) and propose a hybrid algorithm for solving MPCC. We develop also two modifications: one makes use of an index addition strategy; the other adopts an index subtraction strategy. We show that, under reasonable assumptions, all the proposed algorithms possess a finite termination property. Further discussions and numerical experience are given as well This work was supported in part by the Scientific Research Grant-in-Aid from the Ministry of Education, Science, Sports, and Culture of Japan. The authors are grateful to Professor Paul Tseng for helpful suggestions on an earlier version of the paper.     

Global Optimization Method for Solving Mathematical Programs with Linear Complementarity Constraints

We propose a method for finding a global optimal solution of programs with linear complementarity constraints. This problem arises for instance in bilevel programming. The main idea of the method is to generate a sequence of points either ending at a global optimal solution within a finite number of iterations or converging to a global optimal solution. The construction of such sequence is based on branch-and-bound techniques, which have been used successfully in global optimization. Results on a numerical test of the algorithm are reported.The main part of this article was written during the first authors stay as Visiting Professor at the Institute of Policy and Planning Sciences, University of Tsukuba, Tsukuba, Japan. The second and the third authors were supported by Grant-in-Aid for Scientific Research C(2) 13650061 of the Ministry of Education, Culture, Sports, Science, and\break Technology of Japan.The authors thank P. B. Hermanns, Department of Mathematics, University of Trier, for carrying out the numerical test reported in Section 5. The authors also thank the referees and the Associate Editor for comments and suggestions which helped improving the first version of this article.     

Extension of Quasi-Newton Methods to Mathematical Programs with Complementarity Constraints

Quasi-Newton methods in conjunction with the piecewise sequential quadratic programming are investigated for solving mathematical programming with equilibrium constraints, in particular for problems with complementarity constraints. Local convergence as well as superlinear convergence of these quasi-Newton methods can be established under suitable assumptions. In particular, several well-known quasi-Newton methods such as BFGS and DFP are proved to exhibit the local and superlinear convergence.     

A Globally Convergent Sequential Quadratic Programming Algorithm for Mathematical Programs with Linear Complementarity Constraints

This paper presents a sequential quadratic programming algorithm for computing a stationary point of a mathematical program with linear complementarity constraints. The algorithm is based on a reformulation of the complementarity condition as a system of semismooth equations by means of Fischer-Burmeister functional, combined with a classical penalty function method for solving constrained optimization problems. Global convergence of the algorithm is established under appropriate assumptions. Some preliminary computational results are reported.     

非线性互补约束均衡问题的一个滤子SQP算法

提出了—个求解非线性互补约束均衡问题的滤子SQP算法.借助Fischer-Burmeister函数把均衡约束转化为—个非光滑方程组,然后利用逐步逼近和分裂思想,给出—个与原问题近似的一般的约束优化.引入滤子思想,避免了罚函数法在选择罚因子上的困难.在适当的条件下证明了算法的全局收敛性,部分的数值结果表明算法是有效的.     

A Class of Quadratic Programs with Linear Complementarity Constraints

We consider a class of quadratic programs with linear complementarity constraints (QPLCC) which belong to mathematical programs with equilibrium constraints (MPEC). We investigate various stationary conditions and present new and strong necessary and sufficient conditions for global and local optimality. Furthermore, we propose a Newton-like method to find an M-stationary point in finite steps without MEPC linear independence constraint qualification. The research of this author is partially supported by NSERC, and Research Grand Council of Hong Kong.     

Merit-Function Piecewise SQP Algorithm for Mathematical Programs with Equilibrium Constraints

We propose a merit-function piecewise SQP algorithm for mathematical programs with equilibrium constraints (MPEC) formulated as mathematical programs with complementarity constraints. Under mild conditions, the new algorithm is globally convergent to a piecewise stationary point. Moreover, if the partial MPEC linear independence constraint qualification (LICQ) is satisfied at the accumulation point, then the accumulation point is an S-stationary point. The research of the first author was supported by the National Natural Science Foundation of China under grants 10571177 and 70271014. The research of the second author was partially supported by NSERC.