求解互补约束优化问题的乘子松弛法

运筹学学报 ›› 2014, Vol. 18 ›› Issue (4): 119-130.

• 运筹学 • 上一篇

求解互补约束优化问题的乘子松弛法

刘水霞^1,*, 陈国庆¹

1. 内蒙古大学数学科学学院, 呼和浩特 010021

收稿日期:2014-04-18 出版日期:2014-12-15 发布日期:2014-12-15
通讯作者: 刘水霞 E-mail:liushuixia7573@sina.com
基金资助:
国家自然科学基金(No. 11261033), 内蒙古大学高层次人才引进科研启动基金(No. 210143)

A multiplier relaxation method for solving mathematical programs with complementarity constraints

LIU Shuixia^1,*, CHEN Guoqing¹

1. School of Mathematical Sciences, Inner Mongolia University, Hohhot 010021, China

Received:2014-04-18 Online:2014-12-15 Published:2014-12-15

摘要/Abstract

摘要： 利用互补问题的Lagrange函数, 给出了互补约束优化问题\,(MPCC)\,的一种新松弛问题. 在较弱的条件下, 新松弛问题满足线性独立约束规范. 在此基础上, 提出了求解互补约束优化问题的乘子松弛法. 在MPCC-LICQ条件下, 松弛问题稳定点的任何聚点都是MPCC的M-稳定点. 无需二阶必要条件, 只在ULSC条件下, 就可保证聚点是MPCC的B-稳定点. 另外, 给出了算法收敛于B-稳定点的新条件.

关键词: 互补约束优化问题, Lagrange函数, 上水平严格互补, B-稳定点

Abstract: By using the Lagrange function of the complementarity problem, a new relaxed problem of MPCC is given. We show that the linear independence constraint qualification holds for the new relaxed problem under some mild conditions. Based on this, a multiplier relaxed method for solving MPCC is presented. The limited point of stationary points of the relaxed problems is M-stationary point under the MPCC-LICQ. Without requiring the second-order necessary condition, the limited point is B-stationary point if the ULSC holds. At last, we propose a new condition for convergence to B-stationary point.

Key words: mathematical programs with complementarity constraints, Lagrange function, upper lever strict complementarity, B-stationary point

中图分类号:

O221.2

刘水霞, 陈国庆. 求解互补约束优化问题的乘子松弛法[J]. 运筹学学报, 2014, 18(4): 119-130.

LIU Shuixia, CHEN Guoqing. A multiplier relaxation method for solving mathematical programs with complementarity constraints[J]. Operations Research Transactions, 2014, 18(4): 119-130.

参考文献

Luo Z Q, Pang J S, Ralph D. Mathematical Programs with Equilibrium Contraints [M]. Cambridge: Cambridge University Press, 1996.

Outrata J, Kocvara M, Zowe J. Nonsmooth Approach to Optimization Problems with Equilibrium Constraints: Theory, Applications and Numerical Results [M]. New York: Kluwer Academic Publisher, 1998.

Fukushima M, Lin G H. Smoothing methods for mathematical programs with equilibrium constraints [J]. Proceedings of Informatics Research for Development of Knowledge Society Infrastructure, 2004, 206-213.

Chen Y, Florian M. The nonlinear bilevel programming problem: formulations, regularity and optimality conditions [J]. Optimization, 1995, 32: 193-209.

Scholtes S. Convergence properties of a regularization scheme for mathematical programs with complementarity constraints [J]. SIAM Journal on Optimization, 2001, 11: 918-936.

Lin G H, Fukushima M. A modified relaxation scheme for mathematical programs with complementarity constraints [J]. Annals of Operations Research, 2005, 133: 63-84.

Kadrani A, Dussault J P, Benchakroun A. A new regularization scheme for mathematical programs with complementarity constraints [J]. SIAM Journal on Optimization, 2009, 20: 78-103.

Fukushima M, Pang J S. Convergence of a smoothing continuation method for mathematical programs with complementarity constraints, Ill-posed variational problems and regularition techniques [J]. Lecture Notes in Economics and Mathematical Systems, 1999, 477: 105-116.

Facchinei F, Jiang H, Qi L. A smoothing method for mathematical programs with equilibrium constraints [J]. Mathematical Programming, 1999, 85: 107-134.

Hu X M, Ralph D. Convergence of a penalty method for mathematical programs with complementarity constraints [J]. Journal of Optimization Theory and Applications, 2004, 123: 365-390.

Huang X X, Yang X Q, Zhu D L. A sequential smooth penalization approach to mathematical programs with complementarity constraints [J]. Numerical Functional Analysis and Optimization, 2006, 27: 71-98.

Luo Z Q, Pang J S, Ralph D. Piece-wise sequential quadratic programming for mathematical programs with nonlinear complementarity constraints [M]//Complementarity and Variational Problems: State of the Art. Philadelphia: SIAM Publications, 1997.

Liu G S, Ye J J. Merit function piecewise SQP algorithm for mathematical programs with equilibrium constraints [J]. Journal of Optimization Theory and Applications, 2007, 135: 623-641.

Benson H Y, Sen A, Shanno D F, et al. Interior-point algorithm, penalty methods and equilibrium problems [J]. Computational Optimization and Applications, 2005, 34: 155-182.

Arvind U, Lorenz T. An interior point method for mathematical programs with complementarity constraints [J]. SIAM Journal on Optimization, 2005, 15: 720-750.

乌力吉, 陈国庆. 线性互补问题的一种新~Lagrange 乘子法 [J]. 高等学校计算数学学报, 2004, 26: 162-171.

乌力吉, 陈国庆. 线性互补问题的一类新的带参数价值函数的阻尼牛顿法 [J]. 应用数学, 2005, 18: 33-39.
Pang J S, Fukushima M. Complementarity constraint qualifications and simplified B-stationary conditions for mathematical programs with equilibrium constraints [J]. Computational Optimization and Applications, 1999, 13: 111-136.

Scheel H, Scholtes S. Mathematical programs with complementarity constraints: stationarity, optimality and sensitivity [J]. Mathematics of Operations Research, 2000, 25: 1-21.

Pang J S, Fukushima M. Complementarity constraint qualifications and simplified B-stationary conditions for mathematical programs with equilibrium constraints [J]. Computational Optimization and Applications, 1999, 13: 111-136.

Scheel H, Scholtes S. Mathematical programs with complementarity constraints: stationarity, optimality and sensitivity [J]. Mathematics of Operations Research, 2000, 25: 1-21.

Ye J J. Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints [J]. Journal of Mathematical Analysis and Applications, 2005, 307: 305-369.

求解互补约束优化问题的乘子松弛法

A multiplier relaxation method for solving mathematical programs with complementarity constraints

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价