Geodesic
Minimization method with approximation of constraint zone and epigraph of objective function
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 11 (2016), pp. 91-96.

Voir la notice de l'article provenant de la source Math-Net.Ru

We propose a method for solving a convex programming problem which belongs to a class of cutting-plane methods. For construction of sequences this method uses approximation of the feasible set and the epigraph of the objective function of the solved problem. In the method cutting planes are constructed by subgradients of the objective function and functions which define the constrained set. In this case each iteration point can be found by solving a linear programming problem. The proposed method differs from other famous cutting-plane methods by possibility of updating approximation sets due to dropping accumulated constraints. We substantiate the convergence of the method and discuss its numerical realizations.
Keywords: convex programming, cutting-plane methods, approximating set, cutting plane, sequence of approximations
Mots-clés : convergence. 
@article{IVM_2016_11_a8,
     author = {I. Ya. Zabotin and O. N. Shul'gina and R. S. Yarullin},
     title = {Minimization method with approximation of constraint zone and epigraph of objective function},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {91--96},
     publisher = {mathdoc},
     number = {11},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2016_11_a8/}
}
TY  - JOUR
AU  - I. Ya. Zabotin
AU  - O. N. Shul'gina
AU  - R. S. Yarullin
TI  - Minimization method with approximation of constraint zone and epigraph of objective function
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2016
SP  - 91
EP  - 96
IS  - 11
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IVM_2016_11_a8/
LA  - ru
ID  - IVM_2016_11_a8
ER  - 
%0 Journal Article
%A I. Ya. Zabotin
%A O. N. Shul'gina
%A R. S. Yarullin
%T Minimization method with approximation of constraint zone and epigraph of objective function
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2016
%P 91-96
%N 11
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IVM_2016_11_a8/
%G ru
%F IVM_2016_11_a8
I. Ya. Zabotin; O. N. Shul'gina; R. S. Yarullin. Minimization method with approximation of constraint zone and epigraph of objective function. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 11 (2016), pp. 91-96. http://geodesic.mathdoc.fr/item/IVM_2016_11_a8/

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

[2] 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. fiziki, 47:11 (2007), 1830–1842 | MR

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

[4] Kolokolov A. A., “Regulyarnye razbieniya i otsecheniya v tselochislennom programmirovanii”, Sib. zhurn. issled. operatsii, 1:2 (1994), 18–39 | MR | Zbl

[5] Nesterov Yu. E., Vvedenie v vypukluyu optimizatsiyu, MTsNMO, M., 2010

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

[7] Polyak B. T., Vvedenie v optimizatsiyu, Nauka, M., 1983 | MR

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

[9] Demyanov V. F., Vasilev L. V., Nedifferentsiruemaya optimizatsiya, Mir, M., 1972

[10] Zabotin I. Ya., Yarullin R. S., “Algoritm otsechenii s approksimatsiei nadgrafika”, Uchen. zap. Kazansk. un-ta. Ser. Fiz.-matem. nauki, 155, no. 4, 2013, 48–54 | MR

[11] Zabotin I. Ya., Yarullin R. S., “Ob odnom podkhode k postroeniyu algoritmov otsechenii s otbrasyvaniem otsekayuschikh ploskostei”, Izv. vuzov. Matem., 2013, no. 3, 74–79 | Zbl

[12] Zabotin I. Ya., Yarullin R. S., “A cutting method for finding discrete minimax with dropping of cutting planes”, Lobachevskii J. Math., 35:4 (2013), 157–163 | MR