Optimization of the Optimal Value Function in Problems of Convex Parametric Programming

O. V. Khamisov

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 29 (2023) no. 3, pp. 247-260

Résumé

We consider a problem of convex parametric programming in which the objective function and the constraint functions are convex functions of an external parameter. Computational procedures are suggested for finding the maximum and minimum values of the optimal value function and for finding inner and outer approximations to the set of parameters for which the problem is consistent. All procedures are based on the application of support functions. Illustrative examples are provided.

Détail

Keywords: parametric optimization, optimal value function, support function, inner and outer approximation.

Bibliographie

[1] Izmailov A.F., Chuvstvitelnost v optimizatsii, Fizmatlit, M., 2006, 248 pp.

[2] Levitin E.S., Teoriya vozmuschenii v matematicheskom programmirovanii i ee prilozheniya, Nauka, M., 1992, 360 pp. | MR

[3] Bank G., Guddat J., Klatte K., Kummer B., Tammer K., Non-linear parametric optimization, Birkhäuser, Basel, 1982, 228 pp. | DOI | MR

[4] Guddat J., Vasquez V.G., Jongen H.Th., Parametric optimization: singularities, pathfollowing and jumps, Springer Fachmedien, Wiesbaden, 1990, 191 pp. | DOI | MR

[5] Klatte D., Kummer B., Nonsmooth equations in optimization. Regularity, calculus, methods and applications, Kluwer Acad. Publ., Dordrecht, 2002, 362 pp. | DOI | MR | Zbl

[6] Zlobec S., Stable parametric programming, Springer-Science, NY, 2001, 329 pp. | DOI | MR

[7] Eremin I.I., Protivorechivye modeli modeli optimalnogo planirovaniya, Nauka, M., 1988, 160 pp. | MR

[8] Parametricheskaya optimizatsiya i metody approksimatsii nesobstvennykh zadach matematicheskogo programmirovaniya, Sb. statei, UNTs AN SSSR, Sverdlovsk, 1985, 136 pp.

[9] Eremin I.I., Mazurov V.D., Astafev N.N., Nesobstvennye zadachi lineinogo i vypuklogo programmirovaniya, Nauka, M., 1983, 336 pp.

[10] Fedorov V.V., Chislennye metody maksimina, Nauka, M., 1979, 280 pp.

[11] Fiacco A.V., Kyparisis J., “Convexity and concavity properties of the optimal value function in parametric nonlinear programming”, J. Optim. Theory Appl., 48 (1986), 95–126 | DOI | MR | Zbl

[12] Kyparisis J., Fiacco A.V., “Generalized convexity and concavity of the optimal value function in nonlinear programming”, Math. Progr., 39 (1987), 285–304 | DOI | MR | Zbl

[13] Aubin J.P., “Lipschitz behaviour of solutions to convex minimization problems”, Math. Oper. Research, 9:1 (1984), 87–111 | DOI | MR | Zbl

[14] Gfrerer H., Klatte D., “Lipschitz and Hölder stability of optimization problems and generalizex equations”, Math. Progr., Ser A, 158 (2016), 35–75 | DOI | MR | Zbl

[15] Sukharev A.G., Minimaksnye algoritmy v zadachakh chislennogo analiza, Nauka, M., 1989, 304 pp.

[16] Levitin E.S., “O reduktsii nevypuklykh zadach obobschennogo polubeskonechnogo matematicheskogo programmirovaniya k vypuklym zadacham polubeskonechnogo programmirovaniya”, Avtomatika i telemekhanika, 1998, no. 1, 28–34 | Zbl

[17] Bulatov V.P., “Metody resheniya mnogoekstremalnykh zadach (globalnyi poisk)”, Metody chislennogo analiza i optimizatsii, eds. red. B. A. Beltyukov, V. P. Bulatov, Novosibirsk, 1987, 133–157 | Zbl

[18] Khamisov O.V., “Globalnaya optimizatsiya funktsii s vognutoi minorantoi”, Zhurn. vychisl. matematiki i mat. fiziki, 44:9 (2004), 1552–1563 | MR

[19] Floudas C.A., Deterministic global optimization. Theory, methods and applications, Springer, NY, 2000, 742 pp. | MR

[20] Gorski J., Pfeuffer F., Klamroth K., “Biconvex sets and optimization with biconvex functions: a survey and extensions”, Math. Meth. Oper. Res., 66 (2007), 373–407 | DOI | MR | Zbl

[21] Meng Z., Jiang M., Shen R., Xu L., Dang C., “An objective penalty function method for biconvex programming”, J. Glob. Optim., 81 (2021), 599–620 | DOI | MR | Zbl

[22] Sukharev A.G., Timokhov A.V., Fedorov V.V., Kurs metodov optimizatsii, Fizmatlit, M., 2005, 368 pp. | MR

[23] Bulatov V.P., Metody pogruzheniya v zadachakh optimizatsii, Nauka, Novosibirsk, 1977, 164 pp.

[24] Bulatov V.P., Belykh T.I., “Chislennye metody resheniya mnogoekstremalnykh zadach, svyazannye s obratnymi zadachami matematicheskogo programmirovaniya”, Izv. vuzov. Matematika, 48:2 (2007), 14–20

[25] Norkin V.I., “O metode Piyavskogo dlya resheniya obschei zadachi globalnoi optimizatsii”, Zhurn. vychisl. matematiki i mat. fiziki, 32:7 (1992), 992–1006 | MR | Zbl

[26] Eremin I.I., “Nekotorye voprosy kusochno-lineinogo programmirovaniya”, Izv. vuzov. Matematika, 1997, no. 12, 49–61 | Zbl

[27] Horst R., Tuy H., Global optimization(Deterministic approaches), Springer-Verlag, Berlin, 1996, 727 pp. | MR | Zbl

[28] Bulatov V.P., Khamisov O.V., “Metody otsecheniya v $E^{n+1}$ dlya resheniya zadach globalnoi optimizatsii na odnom klasse funktsii”, Zhurn. vychisl. matematiki i mat. fiziki, 47:11 (2007), 1830–1842 | MR

[29] Pshenichnyi B.N., Neobkhodimye usloviya ekstremuma, Nauka, M., 1982, 144 pp. | MR

[30] Khamisov O.V., “Approximation of parametrically given polyhedral sets”, Proceedings of the Workshop on Applied Mathematics and Fundamental Computer Science, eds. Sergei S. Goncharov, Yuri G. Evtushenko, Omsk, 2020 URL: https://ceur-ws.org/Vol-2642/paper10.pdf

[31] Gaivin J., “A necessary and sufficient regularity condition to have bounded multipliers in nonconvex programming”, Math. Progr., 12 (1977), 136–138 | DOI | MR

[32] Hiriart-Urruty J.-B., Lemarèchal C., Convex analysis and minimization algorithms I, Springer-Verlag, Berlin, 1993, 431 pp. | DOI | MR