В. Ю. Протасов, “К вопросу об алгоритмах приближенного вычисления минимума выпуклой функции по ее значениям”, Матем. заметки, 59:1 (1996), 95–102; Math. Notes, 59:1 (1996), 69

Математические заметки

RUS ENG

ЖУРНАЛЫ ПЕРСОНАЛИИ ОРГАНИЗАЦИИ КОНФЕРЕНЦИИ СЕМИНАРЫ ВИДЕОТЕКА ПАКЕТ AMSBIB

JavaScript is disabled in your browser. Please switch it on to enable full functionality of the website

	Общая информация
	Последний выпуск
	Скоро в журнале
	Архив
	Импакт-фактор
	Правила для авторов
	Лицензионный договор
	Загрузить рукопись

	Поиск публикаций
	Поиск ссылок

	RSS
	Последний выпуск
	Текущие выпуски
	Архивные выпуски
	Что такое RSS

Матем. заметки:
Год:
Том:
Выпуск:
Страница:
	Найти

Персональный вход:
Логин:
Пароль:
	Запомнить пароль
	Войти
	Забыли пароль?
	Регистрация

Математические заметки, 1996, том 59, выпуск 1, страницы 95–102
DOI: https://doi.org/10.4213/mzm1697 (Mi mzm1697)

Эта публикация цитируется в 12 научных статьях (всего в 12 статьях)

К вопросу об алгоритмах приближенного вычисления минимума выпуклой функции по ее значениям

В. Ю. Протасов

Московский государственный университет им. М. В. Ломоносова

PDF полного текста (175 kB) Список цитирования (12)

Список литературы:

PDF

HTML

DOI: https://doi.org/10.4213/mzm1697

Аннотация: Статья посвящена одной из задач численных методов – нахождению с заданной точностью минимума выпуклой функции. Функция задана на выпуклой многомерной области и предполагается непрерывной (гладкость не обязательна). Пользователь может вычислять значения функции в любой заданной точке. Требуется найти минимум функции с данной точностью. В статье изложен новый алгоритм решения этой задачи, использующий (асимптотически по размерности области определения) значительно меньшее число операций, чем известные автору аналогичные алгоритмы. Оценка сложности понижена с

C n^{7} \ln^{2} (n + 1)

$Cn^7\ln^2(n+1)$ (см. [4]) до

C n^{2} \ln (n + 1)

$Cn^2\ln(n+1)$ (

n

$n$ – размерность области определения).
Библиография: 5 названий.

Поступило: 18.04.1994

Англоязычная версия:
Mathematical Notes, 1996, Volume 59, Issue 1, Pages 69–74
DOI: https://doi.org/10.1007/BF02312467

Реферативные базы данных:

УДК: 517

Образец цитирования: В. Ю. Протасов, “К вопросу об алгоритмах приближенного вычисления минимума выпуклой функции по ее значениям”, Матем. заметки, 59:1 (1996), 95–102; Math. Notes, 59:1 (1996), 69–74

Цитирование в формате AMSBIB

\RBibitem{Pro96}

\by В.~Ю.~Протасов

\paper К~вопросу об алгоритмах приближенного вычисления минимума выпуклой функции по ее значениям

\jour Матем. заметки

\yr 1996

\vol 59

\issue 1

\pages 95--102

\mathnet{http://mi.mathnet.ru/mzm1697}

\crossref{https://doi.org/10.4213/mzm1697}

\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=1391825}

\zmath{https://zbmath.org/?q=an:0870.90088}

\transl

\jour Math. Notes

\yr 1996

\vol 59

\issue 1

\pages 69--74

\crossref{https://doi.org/10.1007/BF02312467}

\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=A1996UP82900009}

Образцы ссылок на эту страницу:

https://www.mathnet.ru/rus/mzm1697

https://doi.org/10.4213/mzm1697

https://www.mathnet.ru/rus/mzm/v59/i1/p95

Эта публикация цитируется в следующих 12 статьяx:

Amitabh Basu, Hongyi Jiang, Phillip Kerger, Marco Molinaro, “Information complexity of mixed-integer convex optimization”, Math. Program., 2024
Alexander Gasnikov, Darina Dvinskikh, Pavel Dvurechensky, Eduard Gorbunov, Aleksandr Beznosikov, Alexander Lobanov, Encyclopedia of Optimization, 2024, 1
Amitabh Basu, Hongyi Jiang, Phillip Kerger, Marco Molinaro, Lecture Notes in Computer Science, 13904, Integer Programming and Combinatorial Optimization, 2023, 1
Eduard Gorbunov, Pavel Dvurechensky, Alexander Gasnikov, “An Accelerated Method for Derivative-Free Smooth Stochastic Convex Optimization”, SIAM J. Optim., 32:2 (2022), 1210
Bubeck S., Eldan R., Lee Y.T., “Kernel-Based Methods For Bandit Convex Optimization”, J. ACM, 68:4 (2021), 25
Jiang H., Lee Y.T., Song Zh., Wong S.Ch.-w., “An Improved Cutting Plane Method For Convex Optimization, Convex -Concave Games, and Its Applications”, Proceedings of the 52Nd Annual Acm Sigact Symposium on Theory of Computing (Stoc `20), Annual Acm Symposium on Theory of Computing, eds. Makarychev K., Makarychev Y., Tulsiani M., Kamath G., Chuzhoy J., Assoc Computing Machinery, 2020, 944–953
Yin Tat Lee, Aaron Sidford, Santosh S. Vempala, Bolyai Society Mathematical Studies, 28, Building Bridges II, 2019, 317
А. В. Гасников, Д. А. Ковалёв, “Гипотеза об оптимальных оценках скорости сходимости численных методов выпуклой оптимизации высоких порядков”, Компьютерные исследования и моделирование, 10:3 (2018), 305–314
А. В. Гасников, Э. А. Горбунов, Д. А. Ковалёв, А. А. М. Мохаммед, Е. О. Черноусова, “Обоснование гипотезы об оптимальных оценках скорости сходимости численных методов выпуклой оптимизации высоких порядков”, Компьютерные исследования и моделирование, 10:6 (2018), 737–753
Nesterov Yu., Spokoiny V., “Random Gradient-Free Minimization of Convex Functions”, Found. Comput. Math., 17:2 (2017), 527–566
Bubeck S., Lee Y.T., Eldan R., “Kernel-Based Methods For Bandit Convex Optimization”, Stoc'17: Proceedings of the 49Th Annual Acm Sigact Symposium on Theory of Computing, Annual Acm Symposium on Theory of Computing, eds. Hatami H., McKenzie P., King V., Assoc Computing Machinery, 2017, 72–85
Е. С. Горская, И. М. Митричева, В. Ю. Протасов, А. М. Райгородский, “Оценка хроматических чисел евклидова пространства методами выпуклой минимизации”, Матем. сб., 200:6 (2009), 3–22 ; E. S. Gorskaya, I. M. Mitricheva (Shitova), V. Yu. Protasov, A. M. Raigorodskii, “Estimating the chromatic numbers of Euclidean space by convex minimization methods”, Sb. Math., 200:6 (2009), 783–801

Citing articles in Google Scholar: Russian citations, English citations
Related articles in Google Scholar: Russian articles, English articles

Статистика просмотров:
Страница аннотации:	677
PDF полного текста:	319
Список литературы:	63
Первая страница:	1

Обратная связь:

Пользовательское соглашение

Регистрация посетителей портала

Логотипы