A multi-parametric programming algorithm for special classes of non-convex multilevel optimization problems
A global solution strategy for multilevel optimization problems with special non-convexityformulation in the objectives of the inner level problems is presented based on branch-and-bound andmulti-parametric programming approach. An algorithm to such problems is proposed by convexifyingthe inner level problem while the variables from upper level problems are considered as parameters.The resulting convex parametric under-estimator problem is solved using multi-parametric program-ming approach. A branch-and-bound procedure is employed until a pre-specied positive tolerance issatised. Moreover, a ϵ-convergence proof is given for the algorithm.
[1] Migdalas, A., Pardalos, M.P., and V¨arbrand, P., Multilevel optimization: algorithm, the- ory and applications. Kluwer Acadamic Pub- lisher, (1992).
[2] Vicente, N.L. and Calamai, H.P., Bilevel and multilevel programming: a bibliography re- view. Journal of Global Optimization, 5, 1 - 9 (1994).
[3] Hansen, P., Jaumard, B., and Savard, G., New branch-and-bound rules for linear bilevel programming. SIAM Journal on Sci- entific and Statistical Computing, 13, 1194 - 1217 (1992).
[4] Blair, C., The computational complexity of multi-level linear programs. Annals of Oper- ations Research, 34, 13 - 19 (1992).
[5] Bard, J.F., An investigation of the lin- ear three level programming problem. IEEE Transactions on Systems, Man, and Cyber- netics, 14, 711 – 717 (1984).
[6] Zhang, G., Lu, J., Montero, J., Zeng, Y., Model, solution concept, and Kth-best algo- rithm for linear trilevel programming. Infor- mation Sciences, 180, 481 - 492 (2010).
[7] Mersha, A.Y., Dempe S., Feasible direction method for bilevel programming problem. Optimization, 61(5), 597 - 616 (2012).
[8] G¨um¨us, Z.H., Floudas C.A., Global Opti- mization of Nonlinear Bilevel Programming Problems. Journal of Global Optimization, 20, 1 - 31 (2001).
[9] Tilahun, S.L., Kassa S.M., and Ong, H.C., A new algorithm for multilevel optimiza- tion problems using evolutionary strategy, inspired by natural selection. In: Anthony, A., Ishizuka, M., and Lukose, D., (Eds.): PRICAI 2012, LNAI 7458, Springer-Verlag, Berlin Heidelberg, 577 - 588 (2012).
[10] Fa´ısca, P.N., Dua, V., Rustem, B., Saraiva, M.P., Pistikopoulos, N.E., Parametric global optimisation for bilevel programming. Jour- nal of Global Optimization, 38, 609 - 623 (2006).
[11] Fa´ısca, P.N., Saraiva, M.P., Rustem, B., Pistikopoulos, N.E., A multiparametric pro- gramming approach for multilevel hierarchi- cal and decentralized optimization problems. Computational Management Science, 6, 377 - 397 (2009).
[12] Fiacco, V.A., Sensitivity analysis for non- linear programming using penalty methods. Mathematical Programming, 10, 287 - 311 (1976).
[13] Dua, V., Pistikopoulos, N.E., An algorithm for the solution of multiparametric mixed in- teger linear programming problems. Annals of Operations Research, 99, 123 - 139 (2001).
[14] Pistikopoulos, N.E., Georgiadis C.M. and Dua V., (Editors) Multiparametric program- ming: Theory, algorithm, and application. WILEY-VCH Verlag GmbH and Co. KGaA,(2007).
[15] Fiacco, V.A., Introduction to sensitivity and stability analysis in nonlinear programming. Acadamic press, (1983).
[16] Al-Khayyal, F.A., Jointly constrained bi- linear programs and related problems: an overview. Computers Math. Applic. , 19(11), 53 - 62 (1990).
[17] Androulakis, P.I., Maranas, D.C., and Floudas, A.C., αBB: A Global optimization method for general constrained nonconvex problems. Journal of Global Optimization, 7, 1 - 27 (1995).
[18] Adjiman, S.C., Dallwing, S., Floudas, A.C., Neumaier, A., A global optimization method, αBB, for general twice-defferentiable con- strained NLPs – I. Theoretical advances. Computers and Chemical Engineering, 22, 1137 - 1158 (1998).
[19] Adjiman, S.C., Androulakis, P.I., Floudas, A.C., A global optimization method, αBB, for general twice-defferentiable constrained NLPs – II. Implementaion and Computa- tional results. Computers and Chemical En- gineering, 22, 1159 - 1179 (1998).