Geodesic
Algorithms for approximate calculation of the minimum of a~convex function from its values
Matematičeskie zametki, Tome 59 (1996) no. 1, pp. 95-102.

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

The paper deals with a numerical minimization problem for a convex function defined on a convex $n$-dimensional domain and continuous (but not necessarily smooth). The values of the function can be calculated at any given point. It is required to find the minimum with desired accuracy. A new algorithm for solving this problem is presented, whose computational complexity as $n\to\infty$ is considerably less than that of similar algorithms known to the author. In fact, the complexity is improved from $Cn^7\ln^2(n+1)$ [4] to $Cn^2\ln(n+1)$. 
@article{MZM_1996_59_1_a8,
     author = {V. Yu. Protasov},
     title = {Algorithms for approximate calculation of the minimum of a~convex function from its values},
     journal = {Matemati\v{c}eskie zametki},
     pages = {95--102},
     publisher = {mathdoc},
     volume = {59},
     number = {1},
     year = {1996},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_1996_59_1_a8/}
}
TY  - JOUR
AU  - V. Yu. Protasov
TI  - Algorithms for approximate calculation of the minimum of a~convex function from its values
JO  - Matematičeskie zametki
PY  - 1996
SP  - 95
EP  - 102
VL  - 59
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_1996_59_1_a8/
LA  - ru
ID  - MZM_1996_59_1_a8
ER  - 
%0 Journal Article
%A V. Yu. Protasov
%T Algorithms for approximate calculation of the minimum of a~convex function from its values
%J Matematičeskie zametki
%D 1996
%P 95-102
%V 59
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_1996_59_1_a8/
%G ru
%F MZM_1996_59_1_a8
V. Yu. Protasov. Algorithms for approximate calculation of the minimum of a~convex function from its values. Matematičeskie zametki, Tome 59 (1996) no. 1, pp. 95-102. http://geodesic.mathdoc.fr/item/MZM_1996_59_1_a8/

[1] Nemirovskii A. S., Yudin D. B., “Informativnaya slozhnost i effektivnye metody resheniya vypuklykh ekstremalnykh zadach”, Ekonomika i matem. metody, 12:2 (1976), 357–369 | MR | Zbl

[2] Levin A. Yu., “Ob odnom algoritme minimizatsii vypuklykh funktsii”, Dokl. AN SSSR, 160:6 (1965), 1241–1243

[3] Yudin D. B., Goryashko D. M., Nemirovskii A. S., Matematicheskie metody optimizatsii ustroistv i algoritmov na ASU, Radio i svyaz, M., 1982 | Zbl

[4] Gusman M., Differentsirovanie integralov v $\mathbb R^n$, Mir, M., 1978

[5] Mityagin B. S., “Dva neravenstva dlya ob'emov vypuklykh tel”, Matem. zametki, 5:5 (1959), 20–26