DOI: https://doi.org/10.26089/NumMet.v20r437

A modified simplex embedding method for solving convex optimization problems with a large amount of constraints

Authors

  • A.V. Kolosnitsyn

Keywords:

simplex embedding method
convex nondifferentiable optimization
identification of inactive constraints

Abstract

A simplex embedding method adapted for solving convex optimization problems with a large amount of constraints is considered. Two modifications of the method are proposed for better performance. First of them uses a more economical approach to the residual computation for constraints, which allows one to significantly reduce the execution time of the algorithm in the case of a large amount of constraints. One of the important peculiarities of the simplex embedding method is its ability to find inactive constraints. This property of the method is used as the basis for its second modification. The numerical results obtained when solving a number of quadratic and convex nondifferentiable optimization problems show the efficiency of the proposed modifications.

New computational technologies

Downloads

Published

2019-10-29

Issue

Vol. 20 (2019): Issue 4.

Section

Section 1. Numerical methods and applications

Author Biography

A.V. Kolosnitsyn

Melentiev Energy Systems Institute of SB RAS (ESI SB RAS)
• Junior Researcher

References

  1. I. A. Aleksandrov, E. G. Antsiferov, and V. P. Bulatov, “On the Centered Cutting Methods in Convex Programming,” in Proc. Conf. on Methods of Mathematical Programming and Software Sverdlovsk, USSR, April 14-17, 1981 (Inst. Mat. Mekh. Akad. Nauk SSSR, Sverdlovsk, 1981), pp. 10-11.
  2. V. P. Bulatov and I. O. Shepot’ko, “The Gravity Center Method of Orthogonal Simplexes for Solving Convex Programming Problems,” in Optimization Methods and Their Applications (Energy Systems Inst. Akad. Nauk SSSR, Irkutsk, 1982), pp. 79-86.
  3. B. Yamnitsky and L. A. Levin, “An Old Linear Programming Algorithm Runs in Polynomial Time,” in Proc. 23rd Annual IEEE Symposium on Foundations of Computer Science, Chicago, USA, November 3-5, 1982 (IEEE Press, New York, 1982), Vol. 1, pp. 327-338.
  4. D. B. Yudin and A. S. Nemirovskii, “Informational Complexity and Effective Methods for the Solution of Convex Extremal Problems,” Ekonomika Mat. Metody 12 (2), 357-369 (1976).
  5. N. Z. Shor, “A Cutting Method with Space Dilation for Solving Convex Programming Problems,” Kibernetika, No. 1, 94-95 (1977).
  6. I. A. Aleksandrov E. G. Antsiferov, and V. P. Bulatov, Centered Cutting Methods in Convex Programming , Preprint (Energy Systems Inst. Akad. Nauk SSSR, Irkutsk, 1983).
  7. E. G. Antsiferov and V. P. Bulatov, “An Algorithm of Simplex Imbeddings in Convex Programming,” Zh. Vychisl. Mat. Mat. Fiz. 27 (3), 377-384 (1987) [USSR Comput. Math. Math. Phys. 27 (2), 36-41 (1987)].
  8. A. Yu. Levin, “A Minimization Algorithm for Convex Functions,” Dokl. Akad. Nauk SSSR 160 (6), 1244-1247 (1965).
  9. D. J. Newman, “Location of the Maximum on Unimodal Surfaces,” J. ACM 12 (3), 395-398 (1965).
  10. B. T. Polyak, Introduction to Optimization (Nauka, Moscow, 1983; Optimization Software, New York, 1987).
  11. L. A. Rademacher, “Approximating the Centroid is Hard,” in Proc. 23rd Annual Symp. on Computational Geometry, Gyeongju, South Korea, June 6-8, 2007 (ACM Press, New York, 2007), pp. 302-305.
  12. Yu. E. Nesterov, Introductory Lectures on Convex Programming: A Basic Course (Kluwer, Boston, 2004).
  13. J.-L. Goffin and J. P. Vial, “Convex Nondifferentiable Optimization: A Survey Focused on the Analytic Center Cutting Plane Method,” Optim. Methods Softw. 17 (5), 805-867 (2002).
  14. Y. V. Apekina and O. V. Khamisov, “A Modified Simplex Immersions Method with Simultaneous Introduction of Several Intersecting Planes,” Izv. Vyssh. Uchebn. Zaved., Mat., No. 12, 16-24 (1997) [Russ. Math. 41 (12), 14-22 (1997)].
  15. A. V. Kolosnitcyn, “Using of Modified Simplex Imbeddings Method for Solving Special Class of Convex Non-Differentiable Optimization Problems,” Vestn. Irkutsk Gos. Univ., Ser. Mat. 11, 54-68 (2015).
  16. A. Kolosnitcyn, “Modified Simplex Imbeddings Method in Convex Non-differentiable Optimization,” in Proc. 9th Int. Conf. on Discrete Optimization and Operations Research, Vladivostok, Russia, September 19-23, 2016 CEUR Workshop Proc. 1623, 226-233 (2016).
  17. A. V. Kolosnitsyn, “Computational Efficiency of the Simplex Embedding Method in Convex Nondifferentiable Optimization,” Zh. Vychisl. Mat. Mat. Fiz. 58 (2), 228-236 (2018) [Comput. Math. Math. Phys. 58 (2), 215-222 (2018)].
  18. E. A. Nurminskii, Numerical Methods of Convex Optimization (Nauka, Moscow, 1991) [in Russian].
  19. A. Bagirov, N. Karmitsa, and M. M. Makela, Introduction to Nonsmooth Optimization. Theory, Practice and Software (Springer, Cham, 2014).