Necessary Optimality Conditions for Semi-vectorial Bi-level Optimization with Convex Lower Level: Theoretical Results and Applications to the Quadratic Case

doi:10.1007/s40305-020-00305-w

Abstract

Abstract: This paper explores related aspects to post-Pareto analysis arising from the multicriteria optimization problem. It consists of two main parts. In the first one, we give first-order necessary optimality conditions for a semi-vectorial bi-level optimization problem:the upper level is a scalar optimization problem to be solved by the leader, and the lower level is a multi-objective optimization problem to be solved by several followers acting in a cooperative way (greatest coalition multi-players game). For the lower level, we deal with weakly or properly Pareto (efficient) solutions and we consider the so-called optimistic problem, i.e. when followers choose amongst Pareto solutions one which is the most favourable for the leader. In order to handle reallife applications, in the second part of the paper, we consider the case where each follower objective is expressed in a quadratic form. In this setting, we give explicit first-order necessary optimality conditions. Finally, some computational results are given to illustrate the paper.

Key words: Bi-level optimization, Multi-objective optimization, Post-Pareto optimization, Multi-objective convex optimization, Quadratic optimization

CLC Number:

Julien Collonge. Necessary Optimality Conditions for Semi-vectorial Bi-level Optimization with Convex Lower Level: Theoretical Results and Applications to the Quadratic Case[J]. Journal of the Operations Research Society of China, 2021, 9(3): 691-712.

TrendMD

References

[1] Philip, J.:Algorithms for the vector maximization problem. Math. Program. 2, 207-229(1972)
[2] An, L.T.H., Muu, L.D., Tao, P.D.:Numerical solution for optimization over the efficient set by d.c. optimization algorithms. Oper. Res. Lett. 19, 117-128(1996)
[3] Benson, H.P., LEE, D.:Outcome-based algorithm for optimizing over the efficient set of a bi-criteria linear programming problem. J. Optim. Theory Appl. 88, 77-105(1996)
[4] Benson, H.P.:Generating the efficient outcome set in multiple objective linear programs:the bi-criteria case. Acta Math. Vietnam 22, 29-51(1997)
[5] Benson, H.P.:Further analysis of an outcome set-based algorithm for multiple objective linear programming. J. Optim. Theory Appl. 97, 1-10(1998)
[6] Benson, H.P.:Hybrid approach for solving multiple objective linear programs in outcome space. J. Optim. Theory Appl. 98, 17-35(1998)
[7] Benson, H.P.:An outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiple objective linear programming problem. J. Global Optim. 13, 1-24(1998)
[8] Bolintinéanu, S.:Optimality conditions for minimization over the (weakly or properly) efficient set. J. Math. Anal. Appl. 173(2), 523-541(1993)
[9] Bolintinéanu, S.:Necessary conditions for nonlinear suboptimization over the weakly-efficient set. J. Optim. Theory Appl. 78, 579-598(1993)
[10] Bonnel, H., Kaya, C.Y.:Optimization over the efficient set of multi-objective control problems. J. Optim. Theory Appl. 147(1), 93-112(2010)
[11] Craven, B.D.:Aspects of multicriteria optimization. In:Recent Developments in Mathematical Programming, pp. 93-100. Gordon and Breach Science Publishers (1991)
[12] Dauer, J.P.:Optimization over the efficient set using an active constraint approach. J. Oper. Res. 35, 185-195(1991)
[13] Dauer, J.P., Fosnaugh, T.A.:Optimization over the efficient set. J. Global Optim. 7, 261-277(1995)
[14] Fülöp, J.:A cutting plane algorithm for linear optimization over the efficient set. In:Generalized Convexity. Lecture notes in Economics and Mathematical System. vol. 405, pp. 374-385. Springer, Berlin (1994)
[15] Horst, R., Thoai, N.V.:Maximizing a concave function over the efficient or weakly-efficient set. Eur. J. Oper. Res. 117, 239-252(1999)
[16] Horst, R., Thoai, N.V., Yamamoto, Y., Zenke, D.:On optimization over the efficient set in linear multicriteria programming. J. Optim. Theory Appl. 134, 433-443(2007)
[17] Kim, N.T.B., Thang, T.N.:Optimization over the efficient set of a bi-criteria convex programming problem. Pac. J. Optim. 9, 103-115(2013)
[18] Bonnel, H., Collonge, J.:Stochastic optimization over a pareto set associated with a stochastic multiobjective optimization problem. J. Optim. Theory Appl. 162, 405-427(2014)
[19] Bonnel, H., Collonge, J.:Optimization over the pareto outcome set associated with a convex biobjective optimization problem:theoretical results, deterministic algorithm and application to the stochastic case. J. Global Optim. 62, 481-505(2015)
[20] Yamamoto, Y.:Optimization over the efficient set:an overview. J. Global Optim. 22, 285-317(2002)
[21] Konno, H., Thach, P.T., Yokota, D.:Dual approach to minimization on the set of pareto-optimal solutions. J. Optim. Theory Appl. 88, 689-707(1996)
[22] Konno, H., Inori, H.M.:Bond portfolio optimization by bilinear fractional programming. J Oper Res Soc Jpn 32, 143-158(1989)
[23] Benson, H.P.:Optimization over the efficient set. J. Math. Anal. Appl. 98, 562-580(1984)
[24] Benson, H.P.:A finite, non-adjacent extreme point search algorithm for optimization over the efficient set. J. Optim. Theory Appl. 73, 47-64(1992)
[25] Bolintinéanu, S.:Minimization of a quasi-concave function over an efficient set. Math. Program. 61, 89-110(1993)
[26] Bonnel, H., Morgan, J.:Semivectorial bilevel optimization problem:penalty approach. J. Optim. Theory Appl. 131, 365-382(2006)
[27] Bonnel, H., TodjihoundÉ, L., Udrişte, C.:Semivectorial bilevel optimization on Riemannian manifolds. J. Optim. Theory Appl. 167, 464-486(2015)
[28] Bonnel, H.:Optimality conditions for the semivectorial bilevel optimization problem. Pac. J. Optim. 2, 447-468(2006)
[29] Bonnel, H., Morgan, J.:Semivectorial bilevel convex optimal control problems. SIAM J. Control Optim. 50(6), 3224-3241(2012)
[30] Bonnel, H., Morgan, J.:Optimality Conditions for Semivectorial Bilevel Convex Optimal Control Problems Computational and analytical mathematics. Springer, New York (2013)
[31] Ren, A., Wang, Y.:A novel penalty function method for semivectorial bilevel programming problem Appl. Math. Model. 40(1), 135-149(2016)
[32] Dempe, S.:Foundations of Bilevel Programming. Kluwer Academic Publishers, Dordrecht (2002)
[33] Dempe, S., Dutta, J., Mordukhovich, B.S.:New necessary optimality conditions in optimistic bilevel programming. Optimization 56(5-6), 577-604(2007)
[34] Dempe, S., Gadhi, N., Zemkoho, A.B.:New optimality conditions for the semivectorial bilevel optimization problem. J. Optim. Theory Appl. 157(1), 54-74(2013)
[35] Dempe,S.,Mehlitz,P.:Semivectorialbilevelprogrammingversusbilevelprogramming.Optimization (2019). https://doi.org/10.1080/02331934.2019.1625900
[36] Liu, B., Wan, Z., Chen, J., et al.:Optimality conditions for pessimistic semivectorial bilevel programming problem. J. Inequal. Appl. 41(1), 1-26(2014)
[37] Zemkoho, A.B.:Solving ill-posed bilevel programs. Set-valued Var. Anal. 24(3), 423-448(2016)
[38] Zheng,Y.,Chen,J.,Cao,X.:Aglobalsolutionmethodforsemivectorialbilevelprogrammingproblem. Filomat 28(8), 1619-1627(2014)
[39] Ankhili, Z., Mansouri, A.:An exact penalty on bilevel programs with linear vector optimization lower level. Eur. J. Oper. Res. 197, 36-41(2009)
[40] Zheng, Y., Wan, Z.:A solution method for semivectorial bilevel programming problem via penalty method. J. Appl. Math. Comput. 37, 207-219(2011)
[41] Eichfelder, G.:Multiobjective bilevel optimization. Math. Program. Ser. 123, 419-449(2010)
[42] Morgan, J.:Constrained well-posed two-level optimization problems. In:Clarke, F., Demyanov, V., Giannessi, F. (eds.) Nonsmooth Optimization and Related Topics, pp. 307-326. Plenum Press, New York (1989)
[43] Loridan, P., Morgan, J.:A theoretical approximation scheme for stackelberg problems. J. Optim. Theory Appl. 61, 95-110(1989)
[44] Loridan,P.,Morgan,J.:Weakviastrongstackelbergproblem:newresults.J.GlobalOptim. 8,263-287(1996)
[45] Lignola, M.B., Morgan, J.:Stability of regularized bilevel programming problems. J. Optim. Theory Appl. 93, 575-596(1997)
[46] Calvete, H., Gale, C.:On linear bilevel problems with multiple objectives at the lower level. Omega 39, 33-40(2011)
[47] Bonnel, H., Morgan, J.:Optimality conditions for semivectorial bilevel convex optimal control problems. Computational and analytical mathematics. In:Bailey, D.H., Bauschke, H.H., Borwein, P., Garvan, F., Théra, M., J.D. Vanderwer, H. Wolkowicz (eds.) Honor of Jonathan Borwein's 60th Birthday, pp. 43-74. Springer (2013)
[48] Dempe, S.:Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints. Optimization 52, 333-359(2003)
[49] Ehrgott, M.:Multicriteria Optimization. Lecture Notes in Economics and Mathematical Systems, vol. 491. Springer, Berlin (2000)
[50] Göpfert, A., Riahi, H., Tammer, C., Zalinescu, C.:Variational Methods in Partially Ordered Spaces. Springer, New York (2003)
[51] Chen, G., Huang, X., Yang, X.:Vector Optimization:Set Valued and Variational Analysis. Springer, Berlin (2005)
[52] Jahn, J.:Vector Optimization. Springer, Berlin (2004)
[53] Luc, D.T.:Theory of Vector Optimization. Lecture Notes in Economics and Mathematical Systems 319. Springer, Berlin (1989)
[54] Miettinen, K.M.:Nonlinear Multiobjective Optimization. Kluwer Academic Publishers, Dordrecht (1998)
[55] Henig, M.I.:Proper efficiency with respect to cones. J. Optim. Theory Appl. 36, 387-407(1982)
[56] Phelps, R.R.:Convex Functions Monotone Operators and Differentiability. Lecture Notes in Mathematics. Springer, Berlin (1993)
[57] Yu, P.L.:Multiple-Criteria Decision Making. Plenum Press, New York (1985)
[58] Geoffrion, A.M.:Proper efficiency and the theory of vector maximization. J. Math. Anal. Appl. 22, 618-630(1968)
[59] Fiacco, A.V., McCormick, G.P.:Nonlinear Programming:Sequential Unconstrained Minimization Techniques. Wiley, New York (1968)