A branch-and-bound multi-parametric programming approach for non-convex multilevel optimization with polyhedral constraints

详细信息    查看全文

• 作者：Abay Molla Kassa ; Semu Mitiku Kassa
• 关键词：Multilevel optimization ; Multi ; parametric programming ; Convex relaxation
• 刊名：Journal of Global Optimization
• 出版年：2016
• 出版时间：April 2016
• 年：2016
• 卷：64
• 期：4
• 页码：745-764
• 全文大小：1,701 KB
• 参考文献：1.Adjiman, S.C., Dallwing, S., Floudas, A.C., Neumaier, A.: A global optimization method, \(\alpha \) BB, for general twice-defferentiable constrained NLPs—I. Theoretical advances. Comput. Chem. Eng. 22, 1137–1158 (1998)CrossRef
  2.Al-Khayyal, A.F.: Jointly constrained bilinear programms and related problems: an overview. Comput. Math. Appl. 19, 53–62 (1990)MathSciNet CrossRef MATH
  3.Androulakis, P.I., Maranas, D.C., Floudas, A.C.: \(\alpha \) BB: a global optimization method for general constrained nonconvex problems. J. Glob. Optim. 7, 337–363 (1995)MathSciNet CrossRef MATH
  4.Bialas, W.F., Karwan, M.H.: Multilevel Otimization: A Mathematical Programming Perspective. M.Sc. thesis, State University of New York (1980)
  5.Dua, V., Pistikopoulos, N.E.: An algorithm for the solution of multiparametric mixed integer linear programming problems. Ann. Oper. Res. 99, 123–139 (2001)MathSciNet CrossRef MATH
  6.Dua, V., Bozinis, N.A., Pistikopoulos, N.E.: A multiparametric programming approach for mixed-integer quadratic engineering problem. Comput. Chem. Eng. 26(45), 715733 (2002)
  7.Faísca, N.P., Dua, V., Rustem, B., Saraiva, M.P., Pistikopoulos, N.E.: Parametric global optimisation for bilevel programming. J. Glob. Optim. 38, 609–623 (2006)MathSciNet CrossRef MATH
  8.Faísca, N.P., Saraiva, M.P., Rustem, B., Pistikopoulos, N.E.: A multiparametric programming approach for multilevel hierarchical and decentralized optimization problems. Comput. Manag. Sci. 6, 377–397 (2009)MathSciNet CrossRef MATH
  9.Fiacco, A.V.: Sensitivity analysis for nonlinear programming using penalty methods. Math. Program. 10, 287–311 (1976)MathSciNet CrossRef MATH
  10.Fiacco, A.V.: Introduction to Sensitivity and Stability Analysis in Nonlinear Programming. Acadamic Press, New York (1983)MATH
  11.Gümüs, Z.H., Floudas, C.A.: Global optimization of nonlinear bilevel programming problems. J. Glob. Optim. 20, 1–31 (2001)MathSciNet CrossRef MATH
  12.Hansen, P., Jaumard, B., Savard, G.: New branch-and-bound rules for linear bilevel programming. SIAM J. Sci. Comput. 13, 1192–1217 (1992)MathSciNet MATH
  13.Kassa, A.M., Kassa, S.M.: A multi-parametric programming algorithm for special classes of non-convex multilevel optimization problems. Int. J. Optim. Control Theor. Appl. 3, 133–144 (2013)MathSciNet CrossRef MATH
  14.Kassa, A.M., Kassa, S.M.: Approximate solution algorithm for multi-parametric non-convex programming problems with polyhedral constraints. Int. J. Optim. Control Theor. Appl. 4(2), 89–98 (2014)
  15.Lakie, E.: Linear Three Level Programming Problem with the Application to Hierarchical Organizations. M.Sc. thesis, Department of mathematics, Addis Ababa University (2007)
  16.Mersha, A.G., Dempe, S.: Feasible direction method for bilevel programming problem. Optimization 61, 597–616 (2012)MathSciNet CrossRef MATH
  17.Migdalas, A., Värbrand, P.: Multilevel Optimization: Algorithm, Theory and Applications. Kluwer, Dordrecht (1992)
  18.Pistikopoulos, N.E., Georgiadis, M.C., Dua, V. (eds.): Multiparametric Programming: Theory, Algorithm and Applications. Wiley-VCH, Weinheim (2007)
  19.Rao, S.: Engineering Optimization: Theory and Practice, 4th edn. Wiley, Hoboken (2009)CrossRef
  20.Shi, C., Lu, J., Zhang, G.: An extended branch and bound algorithm for linear bilevel programming. Appl. Math. Comput. 180, 529–537 (2006)MathSciNet MATH
  21.Tilahun, S.L., Kassa, S.M., Ong, H.C.: A new algorithm for multilevel optimization problems using evolutionary strategy, inspired by natural selection. In: Anthony, A., Ishizuka, M., Lukose, D. (eds.) PRICAI 2012, LNAI, vol. 7458, pp. 577–588. Springer, Berlin (2012)
  22.Vicente, L.N., Calamai, H.P.: Bilevel and multilevel programming: a bibliography review. J. Glob. Optim. 5, 1–9 (1994)MathSciNet CrossRef MATH
  23.Wang, Y., Jiao, Y., Li, H.: An evolutionary algorithm for solving nonlinear bilevel programming based on a new constraint-handling scheme. IEEE Trans. Syst. Man Cybern. Part C Appl. Rev. 35, 221–231 (2005)CrossRef
  
• 作者单位：Abay Molla Kassa (1)
  Semu Mitiku Kassa (2)
  
  1. Department of Chemical and Bio Engineering, Addis Ababa Institute of Technology, Addis Ababa University, P.O. Box 385, Addis Ababa, Ethiopia
  2. Department of Mathematics, Addis Ababa University, P.O. Box 1176, Addis Ababa, Ethiopia
  
• 刊物类别：Business and Economics
• 刊物主题：Economics
  Operation Research and Decision Theory
  Computer Science, general
  Real Functions
  Optimization
  
• 出版者：Springer Netherlands
• ISSN：1573-2916

文摘

In this paper we develop a general but smooth global optimization strategy for nonlinear multilevel programming problems with polyhedral constraints. At each decision level successive convex relaxations are applied over the non-convex terms in combination with a multi-parametric programming approach. The proposed algorithm reaches the approximate global optimum in a finite number of steps through the successive subdivision of the optimization variables that contribute to the non-convexity of the problem and partitioning of the parameter space. The method is implemented and tested for a variety of bilevel, trilevel and fifth level problems which have non-convexity formulation at their inner levels.