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

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

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

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.

References

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]	SHAO Shuting, DU Shouqiang. Smoothing cautious DPRP conjugate gradient method for solving a kind of special nonsmooth equations with max-type function [J]. Operations Research Transactions, 2018, 22(3): 69-78.
[2]	HE Cheng, HAN Xinxin. Two-agent scheduling on an unbounded parallel-batching machine to minimize maximum cost and makespan [J]. Operations Research Transactions, 2018, 22(3): 109-116.
[3]	CHEN Yuanyuan, GAO Yan, LIU Zhimin, DU Shouqiang. The smoothing gradient method for a kind of special optimization problem [J]. Operations Research Transactions, 2017, 21(2): 119-125.
[4]	KANG Zhilin, LI Zhongfei. CVaR robust mean-CVaR portfolio optimization model and the solving methods [J]. Operations Research Transactions, 2017, 21(1): 1-12.
[5]	HUO Yongliang. Stability of optimal solution set and optimal value for minimax stochastic programming approximation problems [J]. Operations Research Transactions, 2016, 20(1): 75-83.
[6]	ZHANG Huizhen, WEI Xin, MA Liang. A new semi-Lagrangian relaxation method to solve the un-capacitated facility location problem [J]. Operations Research Transactions, 2015, 19(4): 37-47.
[7]	MENG Zhiqing,GAO Song. Smoothed square-root penalty function for nonlinear constrained optimization [J]. Operations Research Transactions, 2013, 17(2): 70-80.
[8]	Bai-Fu-Sheng, LUO Xiao-Yan. Modified lower order penalty functions based on quadratic smoothing approximation [J]. Operations Research Transactions, 2012, 16(2): 9-22.
[9]	Shang-You-Lin, LIU Mu-Hua, LI Pu. A New Penalty Function Based on Non-coercive Penalty Functions [J]. Operations Research Transactions, 2012, 16(1): 56-66.
[10]	Zhen-Wei WEN. Two-machine open shop scheduling with machine-dependent processing times [J]. Operations Research Transactions, 2011, 15(4): 65-74.
[11]	WANG Li-Zhu, LIU Yang. Reverse Point Algorithm of Assignment Problem on Assignment Less Than Jobs and Persons [J]. Operations Research Transactions, 2011, 15(3): 124-128.

A smoothing objective penalty function algorithm for bilevel programming problems

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 11

Recommended Articles

Metrics

Comments