Geodesic
A cutting plane algorithm with an approximation of an epigraph
Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 155 (2013) no. 4, pp. 48-54 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

For the conditional minimization problem, we propose a cutting plane algorithm with an approximation of the epigraph of the objective function. The algorithm makes it possible to update approximating sets by dropping the cutting planes which accumulate during the solution process. We prove the convergence of the algorithm and describe its properties.
Keywords: approximating set, cutting hyperplane, sequence of approximations, conditional minimization, epigraph.
Mots-clés : convergence 
@article{UZKU_2013_155_4_a4,
     author = {I. Ya. Zabotin and R. S. Yarullin},
     title = {A cutting plane algorithm with an approximation of an epigraph},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {48--54},
     year = {2013},
     volume = {155},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2013_155_4_a4/}
}
TY  - JOUR
AU  - I. Ya. Zabotin
AU  - R. S. Yarullin
TI  - A cutting plane algorithm with an approximation of an epigraph
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2013
SP  - 48
EP  - 54
VL  - 155
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/UZKU_2013_155_4_a4/
LA  - ru
ID  - UZKU_2013_155_4_a4
ER  - 
%0 Journal Article
%A I. Ya. Zabotin
%A R. S. Yarullin
%T A cutting plane algorithm with an approximation of an epigraph
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2013
%P 48-54
%V 155
%N 4
%U http://geodesic.mathdoc.fr/item/UZKU_2013_155_4_a4/
%G ru
%F UZKU_2013_155_4_a4
I. Ya. Zabotin; R. S. Yarullin. A cutting plane algorithm with an approximation of an epigraph. Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 155 (2013) no. 4, pp. 48-54. http://geodesic.mathdoc.fr/item/UZKU_2013_155_4_a4/

[1] Bulatov V. P., Metody pogruzheniya v zadachakh optimizatsii, Nauka, Novosibirsk, 1977, 161 pp. | MR

[2] Zabotin I. Ya., “O nekotorykh algoritmakh pogruzhenii-otsechenii dlya zadachi matematicheskogo programmirovaniya”, Izv. Irkutskogo gos. un-ta. Ser. Matem., 4:2 (2011), 91–101 | Zbl

[3] Nurminskii E. A., “Metod otdelyayuschikh ploskostei s ogranichennoi pamyatyu dlya resheniya zadach vypukloi negladkoi optimizatsii”, Vychisl. metody i programmirovanie, 7, 2006, 133–137

[4] Bulatov V. P., Khamisov O. V., “Metody otsecheniya v $E^{n+1}$ dlya resheniya zadach globalnoi optimizatsii na odnom klasse funktsii”, Zhurn. vychisl. matem. i matem. fiz., 47:11 (2007), 1830–1842 | MR

[5] Levitin E. S., Polyak B. T., “Metody minimizatsii pri nalichii ogranichenii”, Zhurn. vychisl. matem. i matem. fiz., 6:5 (1966), 787–823 | MR | Zbl

[6] Nesterov Yu. E., Vvedenie v vypukluyu optimizatsiyu, MTsNMO, M., 2010, 274 pp.

[7] Kelley J. E., “The cutting-plane method for solving convex programs”, J. Soc. Ind. Appl. Math., 8:4 (1960), 703–712 | DOI | MR

[8] Zabotin I. Ya., Yarullin R. S., “One approach to constructing cutting algorithms with dropping of cutting planes”, Russ. Math. (Iz. VUZ), 57:3 (2013), 60–64 | DOI | Zbl

[9] Zabotin I. Ya., Yarullin R. S., “Metod otsechenii s obnovleniem pogruzhayuschikh mnozhestv i otsenki tochnosti resheniya”, Uchen. zap. Kazan. un-ta. Ser. Fiz.-matem. nauki, 155, no. 2, 2013, 54–64

[10] Zabotin I. Ya., Yarullin R. S., “Algoritm otsechenii s approksimatsiei nadgrafika bez vlozheniya pogruzhayuschikh mnozhestv”, Informatsionnye tekhnologii i sistemy, 37-ya konf. molodykh uchenykh i spetsialistov IPPI RAN (Kaliningrad, 1–5 sent. 2013 g.), In-t problem peredachi informatsii im. A. A. Kharkevicha RAN, M., 2013, 8–11