Abstract
The paper is dedicated to extensions of functions and applications in combinatorial optimization. We present a review of the main contributions in the area of continuous and smooth extensions of functions, on the basis of which we formulate the singularities of such extensions for finite sets. We consider a class of finite sets coinciding with their convex hull. For such sets, the existence of convex extensions of functions is proved, which makes it possible to apply the methods of convex analysis to solve relaxation problems. For combinatorial sets, we formulated an equivalent statement of the discrete optimization problem with a convex objective function and proposed methods for estimating the optimum.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Yakovlev, S.: In: Optimization Methods and Applications: In Honor of Ivan V. Sergienko’s 80th Birthday, Butenko, S., Pardalos, P.M., Shylo, V. (eds.), Springer Optimization and Its Applications (Springer International Publishing), pp. 567–584. https://doi.org/10.1007/978-3-319-68640-0_27
Christ, M.: Arkiv för Matematik 22(1–2), 63 (1984). https://doi.org/10.1007/BF02384371
Christ, M., Lima: Proc. London Math. Soc. s3–25(1), 27 (1972). https://doi.org/10.1112/plms/s3-25.1.27
Peters, H.J.M., Wakker, P.P.: Econ. Lett. 22(2), 251 (1986). https://doi.org/10.1016/0165-1765(86)90242-9
Bucicovschi, O., Lebl, J.: 1012 (2010). arXiv:1012.5796
Rzymowski, W.: J. Math. Anal. Appl. 212(1), 30 (1997). https://doi.org/10.1006/jmaa.1997.5093
Laptin, Y.P.: Cybern. Syst. Anal. 52(1), 85 (2016). https://doi.org/10.1007/s10559-016-9803-8
Crama, Y.: Math. Program. 61(1–3), 53 (1993). https://doi.org/10.1007/BF01582138
Whitney, H.: Hassler Whitney Collected Papers, Contemporary Mathematicians, pp. 228–254. Birkhäuser Boston (1992). https://doi.org/10.1007/978-1-4612-2972-8_14
Tawarmalani, M., Sahinidis, N.V.: In: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming, no. 65 in Nonconvex Optimization and Its Applications, pp. 25–70. Springer, US (2002). https://doi.org/10.1007/978-1-4757-3532-1_2
Frölicher, A., Kriegl, A.: Diff. Geom. Appl. 3(1), 71 (1993). https://doi.org/10.1016/0926-2245(93)90023-T
Jansson, C.: BIT Numer. Math. 40(2), 291 (2000). https://doi.org/10.1023/A:1022343007844
Kirchheim, B., Kristensen, J.: Comptes Rendus de l’Académie des Sciences—Series I-Mathematics 333(8), 725 (2001). https://doi.org/10.1016/S0764-4442(01)02117-6
Sherali, H.D.: In: Pardalos, P.M., Romeijn, H.E. (eds.), Handbook of Global Optimization, no. 62 in Nonconvex Optimization and Its Applications, pp. 1–63. Springer, US (2002)
Yakovlev, S.V.: Comput. Math. Math. Phys. 34(7), 1112 (1994)
Yan, M.: J. Convex Anal. 21(4), 965 (2014)
Alexandrov, A.: Leningrad State University. Ann. [Uchenye Zapiski] Math. Ser. (6), 3 (1939)
Pichugina, O., Yakovlev, S.: In: Shakhovska, N., Medykovskyy, M.O. (eds.), Advances in Intelligent Systems and Computing IV. Advances in Intelligent Systems and Computing, pp. 231–246. Springer International Publishing (2019). https://doi.org/10.1007/978-3-030-33695-0_17
Yakovlev, S., Pichugina, O., Koliechkina, L.: In: Lecture Notes in Computational Intelligence and Decision Making. Advances in Intelligent Systems and Computing, pp. 195–212. Springer International Publishing, Cham (2021). https://doi.org/10.1007/978-3-030-54215-3_13
Yakovlev, S., Pichugina, O.: In: Proceedings of the Second International Workshop on Computer Modeling and Intelligent Systems (CMIS-2019), pp. 570–580. CEUR Vol-2353 urn:nbn:de:0074-2353-0, Zaporizhzhia, Ukraine (2019)
Dragomirescu, F., Ivan, C.: Optimization 24(3–4), 193 (1992). https://doi.org/10.1080/02331939208843789
Yakovlev, S.V.: Cybernetics 25(3), 385 (1989). https://doi.org/10.1007/BF01069996
Hadjisavvas, N., Komlósi, S., Schaible, S.S. (eds.): Handbook of Generalized Convexity and Generalized Monotonicity, 2005th edn. Springer (2006)
Azagra, D., Mudarra, C.: Cal. Var. Part. Diff. Equ. 58(3), 84 (2019). https://doi.org/10.1007/s00526-019-1542-z
Stoyan, Y.G., Yakovlev, S.V., Emets, O.A., Valuĭskaya, O.A.: Cybern. Syst. Anal. 34(2), 27 (1998). https://doi.org/10.1007/BF02742066
Jiang, B., Liu, Y., Wen, Z.: SIAM J. Optim. 26(4), 2284 (2016). https://doi.org/10.1137/15M1048021
Yakovlev, S.V., Pichugina, O.S.: Cybern. Syst. Anal. 54(1), 99 (2018). https://doi.org/10.1007/s10559-018-0011-6
Berge, C.: Principles of Combinatorics. Academic Press (1971)
Stoyan, Y.G., Yakovlev, S.V., Pichugina, O.S.: The Euclidean Combinatorial Aonfigurations: a Monograph. Constanta, Kharkiv (2017)
Berstein, Y., Lee, J., Onn, S., Weismantel, R.: Math. Program. 124(1–2), 233 (2010). https://doi.org/10.1007/s10107-010-0358-6
Stoyan, Y.G., Yakovlev, S.V.: Mathematical Models and Optimization Methods in Geometric Design. Naukova Dumka, Kiev (2020)
Yemelichev, V.A., Kovalëv, M.M., Kravtsov, M.K.: Polytopes, Graphs and Optimisation. Cambridge University Press, Cambridge (1984). http://www.ams.org/mathscinet-getitem?mr=744197
Grebennik, I.V., Kovalenko, A.A., Romanova, T.E., Urniaieva, I.A., Shekhovtsov, S.B.: Cybern. Syst. Anal. 54(2), 221 (2018). https://doi.org/10.1007/s10559-018-0023-2
Iemets, O.O., Yemets’, O.O., Polyakov, I.M.: 54(5), 796. https://doi.org/10.1007/s10559-018-0081-5
Yemets, O.A., Yemets, A.O., Polyakov, I.M.: 49(12). https://doi.org/10.1615/JAutomatInfScien.v49.i12.20
Stoyan, Y.G., Yakovlev, S.V.: Cybern. Syst. Anal. 56(3), 366 (2020). https://doi.org/10.1007/s10559-020-00253-6
Valuiskaya, O.A., Pichugina, O.S., Yakovlev, S.V.: Radioelectron. Inf. J. (2(15)), 121 (2001)
Yemets’, O., Romanova, N.G.: Optimization Over Polypermutations. Naukova Dumka, Kyiv (2010)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this chapter
Cite this chapter
Yakovlev, S., Pichugina, O. (2023). Continuous and Convex Extensions Approaches in Combinatorial Optimization. In: Zgurovsky, M., Pankratova, N. (eds) System Analysis and Artificial Intelligence . Studies in Computational Intelligence, vol 1107. Springer, Cham. https://doi.org/10.1007/978-3-031-37450-0_15
Download citation
DOI: https://doi.org/10.1007/978-3-031-37450-0_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-37449-4
Online ISBN: 978-3-031-37450-0
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)