Abstract
A generic constrained permutation-based optimization problem is considered. It is reduced to a Euclidean discrete permutation-based optimization problem, which a discrete optimization problem over vertices of the generalized permutohedron. To this Euclidean combinatorial problem, an equivalent permutation-based optimization problem with convex objective function and convex constraints is formed based on applying the convex extensions theory and a vertex locality of a feasible set. A hybrid approach to solving a polyhedral relaxation of this optimization problem is presented. It jointly uses the penalty method and an offered modification of the conditional gradient method. As a result, a lower bound of the global minimum is found in an arbitrary permutation-based problem.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bazaraa, M.S., Sherali, H.D., Shetty, C.M.: Nonlinear Programming: Theory and Algorithms, 3rd edn. Wiley-Interscience (2006)
Bertsekas, D.P.: Nonlinear Programming, 2nd edn. Athena Scientific (1999)
Bertsekas, D.P.: Convex Optimization Algorithms, 1st edn. Athena Scientific (2015)
Borwein, J., Lewis, A.S.: Convex Analysis and Nonlinear Optimization: Theory and Examples. CMS Books in Mathematics, 2nd edn. Springer (2006). https://doi.org/10.1007/978-0-387-31256-9
Boyd, S., Vandenberghe, L.: Convex Optimization, 1st edn. Cambridge University Press, Cambridge (2004)
Burer, S., Letchford, A.N.: Non-convex mixed-integer nonlinear programming: a survey. Surv. Oper. Res. Manag. Sci. 17(2), 97–106 (2012). https://doi.org/10.1016/j.sorms.2012.08.001
Butenko, S., Pardalos, P.M., Shylo, V. (eds.): Optimization Methods and Applications: In Honor of Ivan V. Sergienko’s 80th Birthday. Springer Optimization and Its Applications. Springer International Publishing (2017). https://doi.org/10.1007/978-3-319-68640-0
Christ, M.: The extension problem for certain function spaces involving fractional orders of differentiability. Arkiv för Matematik 22(1), 63–81 (1984). https://doi.org/10.1007/BF02384371
Cook, W.J., Cunningham, W.H., Pulleyblank, W.R., Schrijver, A.: Combinatorial optimization. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1998)
Dahl, J.: Convex Optimization in Signal Processing and Communications, Department of Communication Technology, Aalborg University (2003)
Ferreira, O.P., Iusem, A.N., Németh, S.Z.: Concepts and techniques of optimization on the sphere. TOP 22(3), 1148–1170 (2014). https://doi.org/10.1007/s11750-014-0322-3
Gimadi, E., Khachay, M.: Extremal Problems on Sets of Permutations. UMC UPI, Ekaterinburg (2016). (in Russian)
Gmys, J.: Heterogeneous cluster computing for many-task exact optimization - Application to permutation problems. Université de Mons (UMONS), University de Lille, Mons (2017)
Graf, M., Hielscher, R.: Fast global optimization on the torus, the sphere, and the rotation group. SIAM J. Optim. 25(1), 540–563 (2015). https://doi.org/10.1137/130950070
Horst, R., Tuy, H.: Global Optimization: Deterministic Approaches, 3rd edn. Springer (1996). https://doi.org/10.1007/978-3-662-03199-5
de Kierk, E.: The complexity of optimizing over a simplex, hypercube or sphere: a short survey. CEJOR 16(2), 111–125 (2008). https://doi.org/10.1007/s10100-007-0052-9
Koliechkina, L., Pichugina, O.: A horizontal method of localizing values of a linear function in permutation-based optimization. In: Le Thi, H.A., Le, H.M., Pham Dinh, T. (eds.) Optimization of Complex Systems: Theory, Models, Algorithms and Applications. Advances in Intelligent Systems and Computing, pp. 355–364. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-21803-4_36
Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms, 6th edn. Springer (2018). https://doi.org/10.1007/978-3-662-56039-6
Lang, S.: Algebra. Graduate Texts in Mathematics, 3rd edn. Springer (2002). https://doi.org/10.1007/978-1-4613-0041-0
Mehdi, M.: Parallel Hybrid Optimization Methods for permutation based problems. University des Sciences et Technologie de Lille, Lille (2011)
Nocedal, J., Wright, S.: Numerical Optimization. Springer Series in Operations Research and Financial Engineering, 2nd edn. Springer (2006). https://doi.org/10.1007/b98874
Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Dover Publications (1998)
Pardalos, P.M., Du, D., Graham, R.L.: Handbook of combinatorial optimization. Springer Reference. Springer, New York (2005). https://doi.org/10.1007/b102533
Pichugina, O., Yakovlev, S.: Euclidean combinatorial configurations: continuous representations and convex extensions. In: Lytvynenko, V., Babichev, S., Wójcik, W., Vynokurova, O., Vyshemyrskaya, S., Radetskaya, S. (eds.) Lecture Notes in Computational Intelligence and Decision Making, Advances in Intelligent Systems and Computing, pp. 65–80. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26474-1_5
Pichugina, O., Yakovlev, S.: Quadratic optimization models and convex extensions on permutation matrix set. In: Shakhovska, N., Medykovskyy, M.O. (eds.) Advances in Intelligent Systems and Computing IV. Advances in Intelligent Systems and Computing, pp. 231–246. Springer (2019). https://doi.org/10.1007/978-3-030-33695-0_17
Pogorelov, A.V.: Extrinsic Geometry of Convex Surfaces. American Mathematical Society, 1st edn. (1973)
Postnikov, A.: Permutohedra, associahedra, and beyond. IMRN: International Mathematics Research Notices 2009(6), 1026–1106 (2009). https://doi.org/10.1093/imrn/rnn153
Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1996)
Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics. Springer (2003)
Stetsyuk, P.I.: Dual bounds in quadratic extremal problems. A series of scientific publications “Non-differentiable optimization and its applications” dedicated to academician N.Z. Shor, Eureka (2018)
Stoyan, Y.G., Yemets’, O.: Theory and methods of Euclidean combinatorial optimization (in Ukrainian). ISSE (1993)
Stoyan, Y.G., Yakovlev, S.V., Emets, O.A., Valuŏskaya, O.A.: Construction of convex continuations for functions defined on a hypersphere. Cybern. Syst. Anal. 34(2), 27–36 (1998). https://doi.org/10.1007/BF02742066
Stoyan, Y.G., Yakovlev, S.V., Pichugina, O.S.: The Euclidean combinatorial configurations, Constanta (2017)
Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications. Nonconvex Optimization and Its Applications, 1st edn. vol. 65, Springer (2002). https://doi.org/10.1007/978-1-4757-3532-1
Tuy, H.: Convex Analysis and Global Optimization, 2nd edn. Springer (2016)
Yakovlev, S., Pichugina, O., Yarovaya, O.: On optimization problems on the polyhedral-spherical configurations with their properties. In: 2018 IEEE First International Conference on System Analysis Intelligent Computing (SAIC), pp. 94–100 (2018). https://doi.org/10.1109/SAIC.2018.8516801
Yakovlev, S.V.: Bounds on the minimum of convex functions on euclidean combinatorial sets. Cybernetics 25(3), 385–391 (1989). https://doi.org/10.1007/BF01069996
Yakovlev, S.V.: The theory of convex continuations of functions on vertices of convex polyhedra. Comput. Math. Math. Phys. 34(7), 1112–1119 (1994)
Yakovlev, S.V., Pichugina, O.S.: Properties of combinatorial optimization problems over polyhedral-spherical sets. Cybern. Syst. Anal. 54(1), 99–109 (2018). https://doi.org/10.1007/s10559-018-0011-6
Yakovlev, S.: Convex extensions in combinatorial optimization and their applications. In: Optimization Methods and Applications. Springer Optimization and Its Applications, pp. 567–584. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-68640-0_27
Yakovlev, S., Kartashov, O., Pichugina, O.: Optimization on combinatorial configurations using genetic algorithms. In: Proceedings of the Second International Workshop on Computer Modeling and Intelligent Systems (CMIS-2019), CEUR, vol-2353, pp. 28–40 (2019). urn:nbn:de:0074-2353-0
Yakovlev, S., Pichugina, O.: On constrained optimization of polynomials on permutation set. In: Proceedings of the Second International Workshop on Computer Modeling and Intelligent Systems (CMIS-2019). CEUR, vol. 2353, pp. 570–580 (2019). urn:nbn:de:0074-2353-0
Yemelichev, V.A., Kovalev, M.M., Kravtsov, M.K.: Polytopes. Graphs and Optimisation. Cambridge University Press, Cambridge (1984). translated from the Russian by G. H. Lawden
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Yakovlev, S., Pichugina, O., Koliechkina, L. (2021). A Lower Bound for Optimization of Arbitrary Function on Permutations. In: Babichev, S., Lytvynenko, V., Wójcik, W., Vyshemyrskaya, S. (eds) Lecture Notes in Computational Intelligence and Decision Making. ISDMCI 2020. Advances in Intelligent Systems and Computing, vol 1246. Springer, Cham. https://doi.org/10.1007/978-3-030-54215-3_13
Download citation
DOI: https://doi.org/10.1007/978-3-030-54215-3_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-54214-6
Online ISBN: 978-3-030-54215-3
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)