一种双层规划的光滑化目标罚函数算法

doi:10.15960/j.cnki.issn.1007-6093.2015.03.004

运筹学学报 ›› 2015, Vol. 19 ›› Issue (3): 26-33.doi: 10.15960/j.cnki.issn.1007-6093.2015.03.004

一种双层规划的光滑化目标罚函数算法

孟志青^1,*, 沈瑞¹, 徐新生^1,2, 蒋敏¹

1. 浙江工业大学经贸管理学院，杭州, 310023; 2. 滨州学院数学与信息科学系，滨州, 256603

收稿日期:2015-04-15 出版日期:2015-09-15 发布日期:2015-09-15
通讯作者: 孟志青 mengzhiqing@zjut.edu.cn

A smoothing objective penalty function algorithm for bilevel programming problems

MENG Zhiqing^1,*, SHEN Rui¹, XU Xinsheng^1,2, JIANG Min¹

1. College of Business and Administration, Zhejiang University of Technology, Hangzhou 310023, China; 2. Department of Mathematics and Information Science, Binzhou University, Binzhou 256603, China

Received:2015-04-15 Online:2015-09-15 Published:2015-09-15

摘要/Abstract

摘要：

论文研究了一种双层规划的光滑化目标罚函数算法，在一些条件下，证明了光滑化罚优化问题等价于原双层规划问题，而且，当下层规划问题是凸规划问题时，
给出了一个求解算法和收敛性证明.

关键词: 双层规划问题, 目标罚函数, 光滑化, 最优解, 精确性

Abstract:

In this paper, a novel smoothing objective penalty function is introduced for bilevel programming problems. It is proved that an optimal solution to the smoothing objective penalty optimization problem is also an optimal solution to the riginal bilevel programming problem under some mild conditions. Furthermore, for the bilevel programming problems with convexity to the lower level problem, an algorithm based on the proposed method is introduced, its convergence is proved.

Key words: bilevel programming problems, objective penalty function, smoothing, optimal solution, exactness

孟志青, 沈瑞, 徐新生, 蒋敏. 一种双层规划的光滑化目标罚函数算法[J]. 运筹学学报, 2015, 19(3): 26-33.

MENG Zhiqing, SHEN Rui, XU Xinsheng, JIANG Min. A smoothing objective penalty function algorithm for bilevel programming problems[J]. Operations Research Transactions, 2015, 19(3): 26-33.

参考文献

Vicente Luis N, Calamai Paul H. Bilevel and multilevel programming: a bibliography review [J]. Journal of Global Optimization, 1994, 5: 291-306.

Bard J F. Some properties of the bilevel programming problem [J]. Journal of Optimization Theory and Applications, 1991, 68: 371-378.

Vicente L N, Savard G, Júdice J J. Discrete linear bilevel programming problem [J]. Journal of Optimization Theory and Applications, 1996, 89: 597-614.

Zhong W J, Xi N R. A Boltzmann Machine method of two level decision making [J]. Journal of Systems Engineering, 1995, 10: 7-13.

Bard J F. Practical Bilevel Optimization: Algorithms and Applications [M]. Boston: Kluwer Academic Publishers, 1998.

Dempe S. Foundations of Bilevel Programming [M]. Dordrecht: Kluwer Academic Publishers, 2002.

Closon B, Marcotte P, Savard G. A trust-region for nonlinear bilevel programming: Algorithm and computational experience [J]. Computational Optimization and Applications, 2005, 30: 211-227.

Wang G M, Wang X J, et al. A globally convergent algorithm for a class of bilevel nonlinear programming problem [J]. Applied Mathematics and Computation, 2007, 188: 166-172.

Jean Bosco Etoa Etoa. Solving quadratic convex bilevel programming problems using a smoothing method [J]. Applied Mathematics and Computation, 2011, 217: 6680-6690.

Le Dung Muu, Nguyen Van Quy. A global optimization method for solving convex quadratic bilevel programming problems [J]. Journal of Global Optimization, 2003, 26: 199-219.

Zhu D L, Xu Q, Lin Z H. A homotopy method for solving bilevel programming problem [J]. Nonlinear Analysis, 2004, 57: 917-928.

Zangwill W I. Nonlinear programming via penalty function [J]. Management Sciences, 1967, 13: 334-358.

Marcotte P, Zhu D L. Exact and inexact penalty methods for the generalized bilevel programming problem [J]. Mathematical Programming, Series A, 1996, 74: 141-157.

Ye J J, Zhu D L, Zhu Q J. Exact penalization and necessary optimality conditions for generalized bilevel programming problems [J]. SIAM Journal on optimization, 1997, 7: 481-507.

Liu G S, Han J Y, Zhang J Z. Exact penalty functions for convex Bilevel programming problems [J]. Journal of Optimization Theory and Applications, 2000, 110: 621-643.

L\"{u} Y B, Hu T S, Wang G M, et al. A penalty function method based on Kuhn-Tucker condition for solving linear bilevel programming [J]. Applied Mathematics and Computation, 2007, 188: 808-813.

Herminia I. Calvete, Carmen Galé. Bilevel multiplicative problems: A penalty approach to optimality and a cutting plane based algorithm [J]. Journal of Computational and Applied Mathematics, 2008, 218: 259-269.

Ankhili A M. An exact penalty on bilevel programs with linear vector optimization lower level [J]. European Journal of Operational Research, 2009, 197: 36-41.

L\"{u} Y B, Chen Z, Wan Z P, ey al. A penalty function method for solving nonlinear-linear bilevel programming problem [J]. Journal of Systems Science and Mathematic Sciences, 2009, 29: 630-636.

L\"{u} Y B, et al. A global optimization method for solving linear bilevel programming problem [J]. Lecture Notes in Decision Making Sciences, 2009, 12 : 249-254.

L\"{u} Y B, Wan Z P. {A penalty method based on BLP for solving inverse optimal value problem [J]. Applied Mathematics Letters, 2010, 23: 170-175.

Wan Z P, Wang G M, L\"{u} Y B.A dual-relax penalty function approach for solving nonlinear bilevel programming with linear lower level problem [J]. Acta Mathematica Scientia, 2011, 31B: 652-660.

Meng Z Q, Hu Q Y, Dang C Y, et al. An Objective Penalty Function Method for Nonlinear Programming [J]. Applied Mathematics Letter, 2004, 17: 683-689.
Meng Z Q, Hu Q Y, Dang C Y. A penalty function algorithm with objective parameters for nonlinear mathematical programming [J]. Journal of Industrial and Management Optimization, 2009, 5: 585-601.
Meng Z Q, Dang C Y, Jiang M, et al. A smoothing objective penalty function algorithm for inequality constrained optimization problems [J]. Numerical Functional Analysis and Optimization, 2011, 32: 806-820.

Meng Z Q, Dang C Y, Jiang M, et al. Exactness and Algorithm of An Objective Penalty Function [J]. Journal of of Global Optimization, 2013, 56: 691–711.
Meng Z Q, Dang C Y, Shen R, et al. An Objective Penalty Function of Bilevel Programming [J]. J Optim Theory Appl, 2012, 153: 377-387.
Xu X S, Meng Z Q, Sun J W, et al.A penalty function method based on smoothing lower order penalty function [J]. Journal of Computational and Applied
Mathematics, 2011, 235: 4047-4058.

Rosenberg E. Exact penalty functions and stability in locally Lipschitz programming [J]. Math Programming, 1984, 30: 340-356.

[1]	何程, 韩鑫鑫. 同时最小化最大费用和最大完工时间的双代理无界平行分批排序[J]. 运筹学学报, 2018, 22(3): 109-116.
[2]	康志林, 李仲飞. CVaR鲁棒均值-CVaR投资组合模型与求解[J]. 运筹学学报, 2017, 21(1): 1-12.
[3]	霍永亮. 极大极小随机规划逼近问题最优解集和最优值的稳定性[J]. 运筹学学报, 2016, 20(1): 75-83.
[4]	张惠珍, 魏欣, 马良. 求解无容量设施选址问题的半拉格朗日松弛新方法[J]. 运筹学学报, 2015, 19(4): 37-47.
[5]	吕一兵, 万仲平. 线性半向量二层规划问题的全局优化方法[J]. 运筹学学报, 2015, 19(2): 29-36.
[6]	孟志青，高嵩 . 非线性约束优化的光滑化平方根罚函数[J]. 运筹学学报, 2013, 17(2): 70-80.
[7]	白富生, 罗晓艳. 基于二次函数光滑化逼近的修正低阶罚函数[J]. 运筹学学报, 2012, 16(2): 9-22.
[8]	尚有林, 刘牧华, 李璞. 一种新的逼近精确罚函数的罚函数及性质[J]. 运筹学学报, 2012, 16(1): 56-66.
[9]	闻振卫. 依赖机器的两台机自由作业排序问题[J]. 运筹学学报, 2011, 15(4): 65-74.
[10]	王立柱, 刘阳. 分配小于人数和任务数的指派问题的反点算法[J]. 运筹学学报, 2011, 15(3): 124-128.

一种双层规划的光滑化目标罚函数算法

A smoothing objective penalty function algorithm for bilevel programming problems

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 10

编辑推荐

Metrics

本文评价