Geodesic
On stability of the gradient algorithm in convex discrete optimisation problems and related questions
Diskretnaya Matematika, Tome 23 (2011) no. 3, pp. 82-92.

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

We introduce the notion of steepness of a coordinate-convex function of discrete argument on an ordinal-convex set. In terms of guaranteed estimates it is shown that in problems of optimisation of coordinate-convex functions on an ordinal-convex set the gradient coordinatewise lifting algorithm is stable under small perturbations of the utility function. As corollaries we obtain improved guaranteed estimates for accuracy of the gradient algorithm, and also new sufficient conditions for the values of the utility function of the problem under consideration to coincide in the global and gradient extrema. 
@article{DM_2011_23_3_a5,
     author = {A. B. Ramazanov},
     title = {On stability of the gradient algorithm in convex discrete optimisation problems and related questions},
     journal = {Diskretnaya Matematika},
     pages = {82--92},
     publisher = {mathdoc},
     volume = {23},
     number = {3},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2011_23_3_a5/}
}
TY  - JOUR
AU  - A. B. Ramazanov
TI  - On stability of the gradient algorithm in convex discrete optimisation problems and related questions
JO  - Diskretnaya Matematika
PY  - 2011
SP  - 82
EP  - 92
VL  - 23
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2011_23_3_a5/
LA  - ru
ID  - DM_2011_23_3_a5
ER  - 
%0 Journal Article
%A A. B. Ramazanov
%T On stability of the gradient algorithm in convex discrete optimisation problems and related questions
%J Diskretnaya Matematika
%D 2011
%P 82-92
%V 23
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2011_23_3_a5/
%G ru
%F DM_2011_23_3_a5
A. B. Ramazanov. On stability of the gradient algorithm in convex discrete optimisation problems and related questions. Diskretnaya Matematika, Tome 23 (2011) no. 3, pp. 82-92. http://geodesic.mathdoc.fr/item/DM_2011_23_3_a5/

[1] Gordeev E. N., Leontev V. K., “Obschii podkhod k issledovaniyu ustoichivosti reshenii v zadachakh diskretnoi optimizatsii”, Zhurnal vychislitelnoi matematiki i matematicheskoi fiziki, 36:1 (1996), 66–72 | MR | Zbl

[2] Emelichev V. A., Krichko V. N., “Formula radiusa ustoichivosti vektornoi $l_\infty$-ekstremalnoi traektornoi zadachi”, Diskretnaya matematika, 16:1 (2004), 14–20 | MR | Zbl

[3] Sergienko I. V., Kozeratskaya L. N., Lebedeva T. T., Issledovanie ustoichivosti i parametricheskii analiz diskretnykh optimizatsionnykh zadach, Naukova dumka, Kiev, 1995

[4] Devyaterikova M. V., Kolokolov A. A., “Analiz ustoichivosti nekotorykh algoritmov diskretnoi optimizatsii”, Avtomatika i telemekhanika, 2004, no. 3, 48–54 | MR | Zbl

[5] Tikhonov A. N., Arsenin V. Ya., Metody resheniya nekorrektnykh zadach, Nauka, Moskva, 1986 | MR

[6] Ramazanov A. B., “Ob otsenke tochnosti gradientnogo algoritma v odnoi zadache vypukloi diskretnoi optimizatsii i nekotorye smezhnye voprosy”, Trudy 13-i Baikalskoi Mezhdunarodnoi seminar-shkoly, Izd-vo Instituta sistem energetiki im. L. A. Melenteva SO RAN, Irkutsk, 2005, 571–576

[7] Ramazanov A. B., “Ob otsenke krivizny poryadkovo-vypuklogo mnozhestva na tselochislennoi reshetke i nekotorye smezhnye voprosy”, Matematicheskie zametki, 84:1 (2008), 153–156 | MR | Zbl

[8] Conforti M., Cornuejols G., “Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado–Edmonds theorem”, Discrete Appl. Math., 7 (1984), 251–274 | DOI | MR | Zbl

[9] Glebov N. I., “O primenimosti metoda pokoordinatnogo spuska k nekotorym zadacham vypuklogo tselochislennogo programmirovaniya”, Upravlyaemye sistemy, 17, 1978, 52–59 | MR | Zbl

[10] Emelichev V. A., Kovalev M. M., Ramazanov A. B., “Pogreshnost gradientnykh ekstremumov strogo vypukloi funktsii diskretnogo argumenta”, Diskretnaya matematika, 2:2 (1990), 127–137 | MR | Zbl

[11] Kovalev M. M., Matroidy v diskretnoi optimizatsii, Izd-vo Universitetskoe, Minsk, 1987 | MR | Zbl

[12] Ramazanov A. B., “Otsenki tochnosti poluchaemykh algoritmom pokoordinatnogo pod'ema reshenii zadach diskretnoi vypukloi optimizatsii”, Diskretnyi analiz i issledovanie operatsii, Ser. 1, 12:4 (2005), 60–80 | MR