nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

On a Solving Bilevel D.C.-Convex Optimization Problems

verfasst von : Andrei V. Orlov

Erschienen in: Mathematical Optimization Theory and Operations Research

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This work addresses the optimistic statement of a bilevel optimization problem with a general d.c. optimization problem at the upper level and a convex optimization problem at the lower level. First, we use the reduction of the bilevel problem to a nonconvex mathematical optimization problem using the well-known Karush-Kuhn-Tucker approach. Then we employ the novel Global Search Theory and Exact Penalty Theory to solve the resulting nonconvex optimization problem. Following this theory, the special method of local search in this problem is constructed. This method takes into account the structure of the problem in question.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Near-Optimal Hyperfast Second-Order Method for Convex Optimization

Nächstes Kapitel Strongly Convex Optimization for the Dual Formulation of Optimal Transport

Dempe, S.: Foundations of Bilevel Programming. Kluwer Academic Publishers, Dordrecht (2002)MATH

Dempe, S., Kalashnikov, V.V., Perez-Valdes, G.A., Kalashnykova, N.: Bilevel Programming Problems: Theory, Algorithms and Applications to Energy Networks. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-45827-3CrossRefMATH

Pang, J.-S.: Three modeling paradigms in mathematical programming. Math. Program. Ser. B 125, 297–323 (2010)MathSciNetCrossRef

Bazaraa, M.S., Shetty, C.M.: Nonlinear Programming: Theory and Algorithms. Wiley, New York (1979)MATH

Nocedal, J., Wright, S.J.: Numerical Optimization. ORFE. Springer, Heidelberg (2000). https://doi.org/10.1007/b98874CrossRefMATH

Bonnans, J.-F., Gilbert, J.C., Lemarechal, C., Sagastizabal, C.A.: Numerical Optimization: Theoretical and Practical Aspects. Springer, Heidelberg (2006). https://doi.org/10.1007/978-3-540-35447-5CrossRefMATH

Luo, Z.-Q., Pang, J.-S., Ralph, D.: Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Cambridge (1996)CrossRef

Dempe, S., Dutta, J.: Is bilevel programming a special case of a mathematical program with complementarity constraints? Math. Program. Ser. A 131, 37–48 (2012)MathSciNetCrossRef

Strekalovsky, A.S.: Global optimality conditions and exact penalization. Optim. Lett. 13(3), 597–615 (2017). https://doi.org/10.1007/s11590-017-1214-xMathSciNetCrossRefMATH

10.

Strekalovsky, A.S.: On a global search in D.C. optimization problems. In: Jaćimović, M., Khachay, M., Malkova, V., Posypkin, M. (eds.) OPTIMA 2019. CCIS, vol. 1145, pp. 222–236. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-38603-0_17CrossRef

11.

Strekalovsky, A.S.: Elements of Nonconvex Optimization. Nauka, Novosibirsk (2003). (in Russian)

12.

Strekalovsky, A.S.: On solving optimization problems with hidden nonconvex structures. In: Rassias, T.M., Floudas, C.A., Butenko, S. (eds.) Optimization in Science and Engineering, pp. 465–502. Springer, New York (2014). https://doi.org/10.1007/978-1-4939-0808-0_23CrossRefMATH

13.

Orlov, A.V.: Numerical solution of bilinear programming problems. Comput. Math. Math. Phys. 48, 225–241 (2008). https://doi.org/10.1134/S0965542508020061MathSciNetCrossRef

14.

Gruzdeva, T.V.: On a continuous approach for the maximum weighted clique problem. J. Glob. Optim. 56, 971–981 (2013). https://doi.org/10.1007/s10898-012-9885-4MathSciNetCrossRefMATH

15.

Strekalovsky, A.S., Gruzdeva, T.V., Orlov, A.V.: On the problem polyhedral reparability: a numerical solution. Autom. Remote Control 76, 1803–1816 (2015). https://doi.org/10.1134/S0005117915100082MathSciNetCrossRefMATH

16.

Orlov, A.V., Strekalovsky, A.S., Batbileg, S.: On computational search for Nash equilibrium in hexamatrix games. Optim. Lett. 10(2), 369–381 (2014). https://doi.org/10.1007/s11590-014-0833-8MathSciNetCrossRefMATH

17.

Gruzdeva, T.V., Petrova, E.G.: Numerical solution of a linear bilevel problem. Comput. Math. Math. Phys. 50, 1631–1641 (2010). https://doi.org/10.1134/S0965542510100015MathSciNetCrossRefMATH

18.

Orlov, A.: A nonconvex optimization approach to quadratic bilevel problems. In: Battiti, R., Kvasov, D.E., Sergeyev, Y.D. (eds.) LION 2017. LNCS, vol. 10556, pp. 222–234. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-69404-7_16CrossRef

19.

Orlov, A.V.: The global search theory approach to the bilevel pricing problem in telecommunication networks. In: Kalyagin, V.A., Pardalos, P.M., Prokopyev, O., Utkina, I. (eds.) NET 2016. SPMS, vol. 247, pp. 57–73. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96247-4_5CrossRef

20.

Strekalovsky, A.S., Orlov, A.V.: Linear and Linear-Quadratic Bilevel Optimization Problems. SB RAS, Novosibirsk (2019). (in Russian)

21.

Strekalovsky, A.S., Orlov, A.V.: Global search for bilevel optimization with quadratic data. In: Dempe, S., Zemkoho, A. (eds.) Bilevel Optimization: Advances and Next Challenges (2020)

22.

Saboia, C.H., Campelo, M., Scheimberg, S.: A computational study of global algorithms for linear bilevel programming. Numer. Algorithms 35, 155–173 (2004). https://doi.org/10.1023/B:NUMA.0000021760.62160.a4MathSciNetCrossRefMATH

23.

Muu, L.D., Quy, N.V.: A global optimization method for solving convex quadratic bilevel programming problems. J. Glob. Optim. 26, 199–219 (2003). https://doi.org/10.1023/A:1023047900333MathSciNetCrossRefMATH

24.

Pistikopoulos, E.N., Dua, V., Ryu, J.: Global optimization of bilevel programming problems via parametric programming. In: Floudas, C.A., Pardalos, P.M. (eds.) Frontiers in Global Optimization. NOIA, vol. 74, pp. 457–476. Springer, Boston (2004). https://doi.org/10.1007/978-1-4613-0251-3_25CrossRefMATH

25.

Colson, B., Marcotte, P., Savard, G.: A trust-region method for nonlinear bilevel programming: algorithm and computational experience. Comput. Optim. Appl. 30, 211–227 (2005). https://doi.org/10.1007/s10589-005-4612-4MathSciNetCrossRefMATH

26.

Etoa Etoa, J.B.: Solving quadratic convex bilevel programming problems using a smoothing method. Appl. Math. Comput. 217, 6680–6690 (2011)MathSciNetMATH

27.

Gumus, Z.H., Floudas, C.A.: Global optimization of nonlinear bilevel programming problems. J. Glob. Optim. 20, 1–31 (2001). https://doi.org/10.1023/A:1011268113791MathSciNetCrossRefMATH

28.

Dempe, S.: Bilevel programming. In: Audet, C., Hansen, P., Savard, G. (eds.) Essays and Surveys in Global Optimization, pp. 165–193. Springer, Boston (2005). https://doi.org/10.1007/0-387-25570-2_6CrossRef

29.

Colson, B., Marcotte, P., Savard, G.: An overview of bilevel optimization. Ann. Oper. Res. 153, 235–256 (2007). https://doi.org/10.1007/s10479-007-0176-2MathSciNetCrossRefMATH

30.

Horst, R., Tuy, H.: Global Optimization: Deterministic Approaches. Springer, Heidelberg (1993)CrossRef

31.

Horst, R., Thoai, N.V.: D.C. programming: overview. J. Optim. Theory Appl. 103(1), 1–43 (1999)MathSciNetCrossRef

32.

Strongin, R.G., Sergeyev, Y.D.: Global Optimization with Non-convex Constraints: Sequential and Parallel Algorithms. NOIA, vol. 45. Springer, Boston (2000). https://doi.org/10.1007/978-1-4615-4677-1CrossRefMATH

33.

Hiriart-Urruty, J.-B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms. GL, vol. 305. Springer, Heidelberg (1993). https://doi.org/10.1007/978-3-662-02796-7 CrossRefMATH

34.

Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)CrossRef

35.

Tao, P.D., Souad, L.B.: Algorithms for solving a class of non convex optimization. Methods of subgradients. In: Hiriart-Urruty, J.-B. (ed.) Fermat Days 85, pp. 249–271. Elsevier Science Publishers B.V., North Holland (1986)

36.

Byrd, R.H., Nocedal, J., Waltz, R.A.: Steering exact penalty methods for nonlinear programming. Optim. Methods Softw. 23, 197–213 (2008)MathSciNetCrossRef

37.

Byrd, R.H., Lopez-Calva, G., Nocedal, J.: A line search exact penalty method using steering rules. Math. Program. Ser. A 133, 39–73 (2012). https://doi.org/10.1007/s10107-010-0408-0MathSciNetCrossRefMATH

38.

Strekalovsky, A.S.: Local search for nonsmooth DC optimization with DC equality and inequality constraints. In: Bagirov, A.M., Gaudioso, M., Karmitsa, N., Mäkelä, M.M., Taheri, S. (eds.) Numerical Nonsmooth Optimization, pp. 229–261. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-34910-3_7CrossRef

39.

Ben-Tal, A., Nemirovski, A.: Non-Euclidean restricted memory level method for large-scale convex optimization. Math. Program. 102, 407–456 (2005). https://doi.org/10.1007/s10107-004-0553-4MathSciNetCrossRefMATH

Titel: On a Solving Bilevel D.C.-Convex Optimization Problems
verfasst von: Andrei V. Orlov
Verlag: Springer International Publishing
Buch: Mathematical Optimization Theory and Operations Research
Print ISBN: 978-3-030-58656-0

Electronic ISBN: 978-3-030-58657-7

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-58657-7_16

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"