We consider a problem of convex parametric programming in which the objective function and the constraint functions are convex functions of an outer parameter. Computational procedures are suggested for finding the maximal and minimal values of the optimal value function and for finding inner and outer approximations of the set of parameters for which the problem is consistent. All procedures are based on the application of support functions. Illustrative examples are provided.
Keywords: parametric optimization, optimal value function, support function, inner and outer approximation
Received June 13, 2023
Revised August 14, 2023
Accepted August 21, 2023
Funding Agency: This work was carried out under the state task project no. FWEU-2021-0006 (registration number АААА-А21-121012090034-3).
Oleg V. Khamisov, Dr. Phys.-Math. Sci., Melentiev Energy Systems Institute of the Siberian Branch of the Russian Academy of Sciences, Irkutsk, 664033 Russia, e-mail: khamisov@isem.irk.ru
REFERENCES
1. Izmailov A.F. Chuvstvitel’nost’ v optimizatsii [Sensitivity in optimization], Moscow, Fizmatlit Publ., 2006, 248 p. ISBN: 978-5-9221-0655-9 .
2. Levitin E.S. Perturbation theory in mathematical programming and its applications, Chichester, NY, Wiley & Sons, 1994, 383 p. ISBN: 9780471939351 . Original Russian text was published in Levitin E.S., Teoriya vozmushchenii v matematicheskom programmirovanii i ee prilozheniya, Moscow, Nauka Publ., 1992, 360 p. ISBN: 5-02-014887-3 .
3. Bank B., Guddat J., Klatte D., Kummer B., Tammer K. Non-linear parametric optimization, Basel, Birkhäuser, 1982, 228 p. doi: 10.1007/978-3-0348-6328-5
4. Guddat J., Vasquez F.G., Jongen H.Th. Parametric optimization: singularities, pathfollowing and jumps. Wiesbaden, Springer Fachmedien, 1990. 191 p. doi: 10.1007/978-3-663-12160-2
5. Klatte D., Kummer B. Nonsmooth equations in optimization. Regularity, calculus, methods and applications, Dordrecht, Kluwer Acad. Publ., 2002, 362 p. doi: 10.1007/b130810
6. Zlobec S. Stable parametric programming, NY, Springer, 2001, 329 p. doi: 10.1007/978-1-4615-0011-7
7. Eremin I.I. Protivorechivye modeli optimal’nogo planirovaniya [Contradictory models of optimal planning], Moscow, Nauka Publ., 1988, 160 p. ISBN: 5-02-013773-1 .
8. Parametric optimization and approximation methods of improper mathematical programming problems. Collection of articles. Sverdlovsk, Ucheb. Nauch. Tsentr Akad. Nauk SSSR, 1985, 136 p.
9. Eremin I.I., Mazurov Vl.D., Astaf’ev N.N. Nesobstvennye zadachi lineinogo i vypuklogo programmirovaniya [Improper problems of linear and convex programming], Moscow, Nauka Publ., 1983, 336 p.
10. Fedorov V.V. Chislennye metody maksimina [Numerical maximin methods], Moscow, Nauka Publ., 1979, 280 p.
11. Fiacco A.V., Kyparisis J. Convexity and concavity properties of the optimal value function in parametric nonlinear programming. J. Optim. Theory Appl., 1986, vol. 48, pp. 95–126. doi: 10.1007/BF00938592
12. Kyparisis J., Fiacco A.V. Generalized convexity and concavity of the optimal value function in nonlinear programming. Math. Progr., 1987, vol. 39, no. 3, pp. 285–304. doi: 10.1007/BF02592078
13. Aubin J.P. Lipschitz behaviour of solutions to convex minimization problems. Math. Oper. Research, 1984, vol. 9, no. 1, pp. 87–111. doi: 10.1287/moor.9.1.87
14. Gfrerer H., Klatte D. Lipschitz and HЈolder stability of optimization problems and generalized equations. Math. Progr, Ser. A, 2016, vol. 158, no. 1–2, pp. 35–75. doi: 10.1007/s10107-015-0914-1
15. Sukharev A.G. Minimax models in the theory of numerical methods, Dordrecht, Springer, 1992, 258 p. doi: 10.1007/978-94-011-2759-2 Original Russian text was published in Sukharev A. G., Minimaksnye algoritmy v zadachakh chislennogo analiza, Moscow, Nauka Publ., 1989, 304 p. ISBN: 9785020139428 .
16. Levitin E.S. Reduction of nonconvex problems of generalized semi-infinite mathematical programming to convex problems of semi-infinite programming. Autom. Remote Control, 1998, vol. 59, no. 1, pp. 22–27.
17. Bulatov V.P. Methods for solving multiextremal problems (global search). In: Methods of numerical analysis and optimization, eds. B.A. Bel’tyukov, V.P. Bulatov, Novosibirsk, Nauka Publ., 1987, pp. 133–157 (in Russian).
18. Khamisov O.V. Global optimization of functions with concave support minorant. Comput. Math. Math. Phys., 2004, vol. 44, no. 9, pp. 1473–1483.
19. Floudas C.A. Deterministic Global Optimization. Theory, Methods and Applications, NY, Springer, 2000, 742 p. doi: 10.1007/978-1-4757-4949-6
20. Gorski J., Pfeuffer F., Klamroth K. Biconvex sets and optimization with biconvex functions: a survey and extensions. Math. Meth. Oper. Res., 2007, vol. 66, pp. 373–407. doi: 10.1007/s00186-007-0161-1
21. Meng Z., Jiang M., Shen R., Xu L., Dang C. An objective penalty function method for biconvex programming. J. Glob. Optim., 2021, vol. 81, pp. 599–620. doi: 10.1007/s10898-021-01064-5
22. Sukharev A.G., Timokhov A.V., and Fedorov V.V. Kurs metodov optimizatsii [Course of optimization methods]. Moscow: Fizmatlit Publ., 2005, 368 p.
23. Bulatov V.P. Metody pogruzheniya v zadachakh optimizatsii [Embedding methods in optimization problems], Novosibirsk, Nauka Publ., 1977, 164 p.
24. Bulatov V.P., Belykh T.I. Numerical solution methods for multiextremal problems connected with inverse problems in mathematical programming. Russian Math. (Iz. VUZ), 2007, vol. 51, no. 6, pp. 11–17. doi: 10.3103/S1066369X07060023
25. Norkin V.I. Piyavskij’s method for solving the general global optimization problem. Comput. Math. Math. Phys., 1992, vol. 32, no. 7, pp. 873–886.
26. Eremin I.I. Some questions of piecewise linear programming. Russian Math. (Iz. VUZ), 1997, vol. 41, no. 12, pp. 47–59.
27. Horst R., Tuy H. Global optimization (deterministic approaches), Berlin, Springer-Verlag, 1996, 727 p. doi: 10.1007/978-3-662-03199-5
28. Bulatov V.P., Khamisov O.V. Cutting methods in $E^{n+1}$ for global optimization of a class of functions. Comput. Math. Math. Phys., 2007, vol. 47, no. 11, pp. 1756–1767. doi: 10.1134/S0965542507110036
29. Pshenichnyi B.N. Neobkhodimye usloviya ekstremuma [Necessary conditions for an extremum], Moscow, Nauka Publ., 1982, 144 p.
30. Khamisov O.V. Approximation of parametrically given polyhedral sets. In: Proceedings of the Workshop on Applied Mathematics and Fundamental Computer Science, eds. Sergei S. Goncharov, Yuri G. Evtushenko, Omsk, 2020. Available on: 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., 1977, vol. 12, no. 1, pp. 136–138. doi: 10.1007/BF01593777
32. Hiriart-Urruty J.-B., Lemaréchal C. Convex analysis and minimization algorithms, Part I, Berlin, Springer-Verlag, 1993, 418 p. doi: 10.1007/978-3-662-02796-7
Cite this article as: O.V. Khamisov. Optimization of the optimal value function in problems of convex parametric programming. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2023, vol. 29, no. 3, pp. 247–260; Proceedings of the Steklov Institute of Mathematics (Suppl.), 2023, Vol. 323, Suppl. 1, pp. S133–S145.
