Cutting-plane method based on epigraph approximation with discarding the cutting planes
Tóm tắt
Propose a method for solving a mathematical programming problem from the class of cutting methods. In our method, on each step the epigraph of the objective function is embedded into a specifically constructed polyhedral set, and on this set an auxiliary linear function is minimized in order to construct the iteration point. Proposed method does not require that each approximation set is embedded in the previous ones. This feature lets us periodically discard additional constraints that form the approximation sets obtained during the solution process. Prove the method’s convergence and discuss possible implementations.
Tài liệu tham khảo
Bulatov, V.P., Metody pogruzheniya v zadachakh optimizatsii (Immersion Methods in Optimization Problems), Novosibirsk: Nauka, 1977.
Bulatov, V.P. and Khamisov, O.V., Cutting Methods in E n+1 for Global Optimization Problems on a Class of Functions, Zh. Vychisl. Mat. Mat. Fiz., 2007, vol. 47, no. 11, pp. 1830–1842.
Zabotin, I.Ya., On Some Immersion-Severance Algorithms for Mathematical Programming Problems, Izv. Irkutsk. Gos. Univ., Ser. Mat., 2011, vol. 4, no. 2, pp. 91–101.
Zabotin, I.Ya. and Yarullin, R.S., On One Approach to Constructing Branch and Bound Algorithms with Discarding Separating Planes, Izv. Vyssh. Uchebn. Zaved., Mat., 2013, no. 3, pp. 74–79.
Zangwill, W.I., Nonlinear Programming: A Unified Approach, Englewood Cliffs: Prentice Hall, 1969. Translated under the title Nelineinoe programmirovanie, Moscow: Sovetskoe Radio, 1973.
Kolokolov, A.A., Regular Partitions and Cuts in Integer Programming, Sib. Zh. Issled. Oper., 1994, vol. 1, no. 2, pp. 18–39.
Nesterov, Yu.E., Vvedenie v vypukluyu optimizatsiyu (Introduction to Convex Optimization), Moscow: MTsNMO, 2010.
Nurminskii, E.A., The Separating Planes Method with Bounded Memory for Convex Nonsmooth Optimization Problems, Vychisl. Metod. Programm., 2006, vol. 7, pp. 133–137.
Polyak, B.T., Vvedenie v optimizatsiyu (Introduction to Optimization), Moscow: Nauka, 1983.
Kelley, J.E., The Cutting-Plane Method for Solving Convex Programs, SIAM J., 1960, vol. 8, no. 4, pp. 703–712.
Lemarechal, C., Nemirovskii, A., and Nesterov, Yu., New Variants of Bundle Methods, Math. Program., 1995, vol. 69, pp. 111–148.
Vasil’ev, F.P., Chislennye metody resheniya ekstremal’nykh zadach (Numerical Methods for Extremal Problems), Moscow: Nauka, 1988.