×

zbMATH — the first resource for mathematics

On a solving bilevel d.c.-convex optimization problems. (English) Zbl 07315681
Kochetov, Yury (ed.) et al., Mathematical optimization theory and operations research. 19th international conference, MOTOR 2020, Novosibirsk, Russia, July 6–10, 2020. Revised selected papers. Cham: Springer (ISBN 978-3-030-58656-0/pbk; 978-3-030-58657-7/ebook). Communications in Computer and Information Science 1275, 179-191 (2020).
Summary: 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.
For the entire collection see [Zbl 1454.90004].
MSC:
90C26 Nonconvex programming, global optimization
90C25 Convex programming
Software:
PLCP; SQPlab
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Dempe, S.: Foundations of Bilevel Programming. Kluwer Academic Publishers, Dordrecht (2002) · Zbl 1038.90097
[2] 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-3 · Zbl 1338.90005
[3] Pang, J.-S.: Three modeling paradigms in mathematical programming. Math. Program. Ser. B 125, 297-323 (2010) · Zbl 1202.90254
[4] Bazaraa, M.S., Shetty, C.M.: Nonlinear Programming: Theory and Algorithms. Wiley, New York (1979) · Zbl 0476.90035
[5] Nocedal, J., Wright, S.J.: Numerical Optimization. ORFE. Springer, Heidelberg (2000). https://doi.org/10.1007/b98874 · Zbl 0930.65067
[6] 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-5 · Zbl 1108.65060
[7] Luo, Z.-Q., Pang, J.-S., Ralph, D.: Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Cambridge (1996) · Zbl 0898.90006
[8] 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) · Zbl 1235.90145
[9] Strekalovsky, A.S.: Global optimality conditions and exact penalization. Optim. Lett. 13(3), 597-615 (2017). https://doi.org/10.1007/s11590-017-1214-x · Zbl 1432.90126
[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_17
[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_23 · Zbl 1335.90075
[13] Orlov, A.V.: Numerical solution of bilinear programming problems. Comput. Math. Math. Phys. 48, 225-241 (2008). https://doi.org/10.1134/S0965542508020061 · Zbl 1224.90171
[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-4 · Zbl 1272.90106
[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/S0005117915100082 · Zbl 1354.90099
[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-8 · Zbl 1336.91010
[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/S0965542510100015 · Zbl 1224.90135
[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_16
[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_5
[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.a4 · Zbl 1054.65060
[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:1023047900333 · Zbl 1053.90104
[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_25 · Zbl 1048.90159
[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-4 · Zbl 1078.90041
[26] Etoa Etoa, J.B.: Solving quadratic convex bilevel programming problems using a smoothing method. Appl. Math. Comput. 217, 6680-6690 (2011) · Zbl 1211.65070
[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:1011268113791 · Zbl 0987.90074
[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_6 · Zbl 1136.90505
[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-2 · Zbl 1159.90483
[30] Horst, R., Tuy, H.: Global Optimization: Deterministic Approaches. Springer, Heidelberg (1993) · Zbl 0867.90105
[31] Horst, R., Thoai, N.V.: D.C. programming: overview. J. Optim. Theory Appl. 103(1), 1-43 (1999) · Zbl 1073.90537
[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-1 · Zbl 0987.90068
[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 · Zbl 0795.49001
[34] Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970) · Zbl 0932.90001
[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) · Zbl 1211.90224
[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-0 · Zbl 1254.90221
[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_7
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.