Лаборатория теории и численных методов оптимизации

1. Общие сведения о лаборатории
2. Состав лаборатории
3. Направления исследований
4. Основные научные результаты
5. Научные гранты
6. Премии, награды, звания
7. Преподавание
8. Основные публикации
9. Программные реализации

---

1.  Общие сведения о лаборатории
 

2.

Лаборатория создана в январе 1987 года.
Руководитель лаборатории - д.ф.-м.н. Евгений Григорьевич Гольштейн.

В 2016 г. лаборатория вошла в состав Лаборатории динамических моделей экономики и оптимизации.

Адрес:	117418, Москва, Нахимовский проспект, д.47, ЦЭМИ РАН Лаборатория 1.04.
Телефон:	(8-499) 724-24-63
Факс:	(8-495) 718-96-15
E-mail:	golshtn@cemi.rssi.ru

2.  Состав лаборатории

1.

3.

   

3.  Направления исследований
    

2.

4.

Лаборатория занимается разработкой теоретических и прикладных вопросов оптимизации и смежными задачами.

Исследования в лаборатории ведутся в следующих направлениях:

• развитие эффективных методов математического программирования, включая гладкую и негладкую оптимизацию выпуклых задач,
• декомпозиционные подходы к решению структурированных оптимизационных задач большого размера, 
• численные методы решения вариационных неравенств, определяемых монотонными отображениями, и бескоалиционных игр выпуклой структуры, 
• общие и специальные задачи дискретного программирования,
• построение и анализ моделей экономической динамики, включающих инфляционные процессы и фискальную политику государства,
• развитие теории бескоалиционных игр многих лиц и разработка численных методов решения подобных игр.

Исследования возглавляет д.ф.-м.н., зав.лаб. Е.Г. Гольштейн.

В них участвуют:

д.ф.-м.н., г.н.с. А.С. Немировский,
к.ф.-м.н., в.н.с. Т.Д. Березнева	к.ф.-м.н., в.н.с. У.Х. Малков,
к.ф.-м.н., с.н.с. А.А. Вотяков,	к.т.н., с.н.с. А.А. Заславский,
к.ф.-м.н., с.н.с. Н.А. Соколов.

4.  Основные научные результаты
    

3.

5.

Главные научные достижения сотрудников лаборатории последних лет состоят в следующем.

• Получен ряд результатов в области теории и вычислительных методов для бескоалиционных игр многих лиц.
• Введено понятие выпуклой структуры игры, наличие которой обеспечивает возможность решения игры при помощи эффективного метода вариационных неравенств; найдены достаточные условия, гарантирующие выпуклую структуру игры; для случая конечных игр получены необходимые и достаточные условия наличия у игры выпуклой структуры.
• Определены оценки минимальных аддитивных возмущений игры, приводящих ее к игре с выпуклой структурой.
• Изучена задача равновесия, частным случаем которой является задача отыскания точки Нэша игры многих лиц, для которой предложен эффективный численный алгоритм решения.
• Выделен класс антагонистических игр, обладающих свойствами кососимметричной матричной игры; при соблюдении упомянутых выше достаточных условий игра многих лиц оказывается эквивалентной игре из этого класса.
• Разработан численный метод решения биматричных игр общего типа, основанный на минимизации некоторой вспомогательной функции, имеющей большое количество локальных минимумов; проведен представительный вычислительный эксперимент при числе чистых стратегий игроков до 1000, подтвердивший высокую эффективность метода.


• Предложена новая схема построения и интерпретации субградиентных методов для минимизации негладких функций на простых множествах; построен новый метод минимизации негладких функций, в котором допустимое множество задано самосогласованным барьером; созданы новые эффективные методы решения квазивариационных неравенств; получены новые прямо-двойственные алгоритмы внутренней точки.


• Получен ряд новых результатов в области робастной оптимизации и стохастического программирования, созданы новые методы первого порядка для решения выпуклых оптимизационных задач большой размерности. Развита теория детерминированных и стохастических алгоритмов зеркального спуска для решения задач выпуклой минимизации и антагонистических выпуклых игр. Созданы и обоснованы новые алгоритмы непараметрической регрессии.


• Исследована модификация неоклассической модели оптимального экономического роста, в которой выпуск задается производственной функцией, зависящей от капитала и двух типов трудовых ресурсов, изучены предельно оптимальные траектории этой модели и траектории скользящего планирования.

5.  Научные гранты
  

4.

6.

Большая часть сотрудников лаборатории участвовала в следующих грантах: 

• Грант РФФИ (1993-1995) №93-012-499 "Эффективные методы оптимизации для cпециальных и общих выпуклых (квазивыпуклых) задач". Руководитель Е.Г. Гольштейн. Исполнители: А.С. Немировский, Ю.Е. Нестеров, Э.П. Борисова, С.С. Лебедев, У.Х. Малков, Н.А. Соколов, В.А. Скоков, Б.В. Черкасский, Т.М. Королева, Е.С. Левенко.
• Грант РФФИ (1996-1998) №96-01-00293а "Эффективные методы внутренней точки, негладкой и дискретной оптимизации". Руководитель Е.Г. Гольштейн. Исполнители: А.С. Немировский, Ю.Е. Нестеров, А.А. Заславский, С.С. Лебедев, У.Х. Малков, Н.А. Соколов, В.А. Скоков.
• Грант РФФИ (1999-2001) №99-01-01125а "Негладкие задачи оптимизации и равновесия, декомпозиция и дискретная оптимизация". Руководитель Е.Г. Гольштейн. Исполнители: А.А. Заславский, С.С. Лебедев, У.Х. Малков, Н.А. Соколов, В.А. Скоков.
• Грант РФФИ (2002-2004) №02-01-00532а "Разработка эффективных вычислительных методов для задач равновесия и целочисленного программирования". Руководитель Е.Г. Гольштейн. Исполнители: А.А. Заславский, С.С. Лебедев, У.Х. Малков, Ю.Е. Нестеров, Н.А. Соколов.
• Грант РФФИ (2005-2007) №05-01-00491а "Методы решения задач оптимизации и равновесия с неточными данными; декомпозиционные методы дискретной оптимизации". Руководитель Е.Г. Гольштейн. Исполнители: А.А. Заславский, У.Х. Малков, Ю.Е. Нестеров, Н.А. Соколов.
• Грант РФФИ (2009-2011) №09-01-00156а "Численные методы решения бескоалиционных игр многих лиц; эффективные оценочные функции для декомпозиционных алгоритмов дискретной оптимизации". Руководитель Е.Г. Гольштейн. Исполнители: А.А. Заславский, У.Х. Малков, Ю.Е. Нестеров, Н.А. Соколов.

Участие в грантах других подразделений

6.  Премии, награды, звания

5.

7.

• Е.Г. Гольштейну присвоено звание "Заслуженный деятель науки РФ" (1999).
• А.С. Немировский удостоен Фалкерсоновской премии Международного общества математического программирования и Американского математического общества (1982), премии Дж. Данцига Международного общества математического программирования и Общества индустриальной и прикладной математики (1991), премии Дж. фон Неймана (2003).
• Ю.Е. Нестеров удостоен международной премии Дж. Данцига Международного общества математического программирования и Общества индустриальной и прикладной математики (2000) и премии Дж. фон Неймана (2009).
• Международный научный фонд экономических исследований академика Н.П. Федоренко присудил Е.Г. Гольштейну в 2014 году премию фонда за выдающийся вклад в развитие экономической науки России.

7.  Преподавание

6.

8.

• Т.Д. Березнева читает курс лекций по линейной алгебре в институте экономики Государственного академического университета гуманитарных наук.
• А.А. Заславский читает курс по количественным методам в экономике в Государственном  академическом университете гуманитарных наук и курс лекций "Математические методы экономики" в Московском энергетическом институте.

8.  Основные публикации
 

7.

9.

Важнейшие опубликованные за последние годы научные труды сотрудников лаборатории. 

2015

• Березнева Т.Д. О влиянии разделения труда на экономический рост / Сб. "Теоретические и прикладные задачи нелинейного анализа". М.: ВЦ РАН, 2015, с.147-156.
• Вотяков А.А. Об оптимальном вложении тела в октаэдр // Экономика и математические методы, 2015, т.51, №3, с.117-126.
• GolshteynE., MalkovU., SokolovN. AHybridMethodforSolvingBimatrixGames/ Материалы VIМеждународной конференции «Optimizationandapplications» OPTIMA-2015 (г. Петровац, Черногория, 27 сентября - 3 октября 2015 г.). М.: ВЦ РАН, 2015, с.79-80.
• Juditsky A., Nemirovski, A. Solving Variational Inequalities with Monotone Operators on Domains Given by Linear Minimization Oracles // Mathematical Programming Online First, March 22, 2015, http://www.springerlink.com/openurl.asp?genre=article\&id=doi:10.1007/s10107-015-0876-3.
• He N., Juditsky A., Nemirovski A. Mirror Prox Algorithm for Multi-Term Composite Minimization and Semi-Separable Problems // Computational Optimization and Applications Vol. 61 No. 2 (2015), 275-319.

2014

• Гольштейн Е.Г. Приближенный метод решения конечной игры трех лиц // Экономика и математические методы, 2014, т.50, №1, с.104-110.
• Заславский А.А. Новые подходы к анализу парных сравнений // Экономика и математические методы, 2014, т.50, №2, с.120-129.
• Березнева Т.Д. Анализ траекторий роста в однопродуктовой модели с терминальным ограничением на капитал / Сб. "Теоретические и прикладные задачи нелинейного анализа". М.: ВЦ РАН, 2014, с.120-129.
• Golshteyn E., MalkovU., Sokolov N. On an Approximate Solution Method of a Finite Three-Player Game / Материалы V Международнойконференции «Optimization and applications» OPTIMA-2014 (г. Петровац, Черногория, 28 сентября - 4 октября 2014 г.). М.: ВЦРАН, 2014, с.84-85.
• Juditsky A., Kilinc Karzan F., Nemirovski A. On unified view of nullspace-type conditions for recoveries associated with general sparsity structures // Linear Algebra and its Applications, 2014, vol. 441, p.124-151.
• Guzman C., Nemirovski A. On Lower Complexity Bounds for Large-Scale Smooth Convex Optimization / Journal of Complexity Available online 13 August 2014.
• Ben-Tal A., Nemirovski A. On solving large scale polynomial convex problems by randomized first-order algorithms. http://dx.doi.org.prx.library.gatech.edu/10.1287/moor.2014.0681, Published Online: September 29, 2014.
• Nesterov Yu., Shpirko S. Primal-dual subgradient methods for huge-scale linear conic problems / SIOPT, 2014, v.24, №3, p.1444-1457.
• Nesterov Yu. Subgradient methods for huge-scale Optimization problems // Mathematical Programming, 2014, v.146, №1-2, p.275-297.
• Devolder O., Glineur F., Nesterov Yu. First order methods of smooth convex optimization with inexact oracle // Mathematical Programming, 2014, v.146, №1-2, p.37-75.

2013

• Гольштейн Е.Г., Малков У.Х., Соколов Н.А. Об одном численном методе решения биматричных игр // Экономика и математические методы, 2013, т.49, №4, с.94-104.
• Baes M, Buergisser M., Nemirovski A. Randomized Mirror-Prox method for solving structured large-scale matrix saddle-point problems // SIAM Journal on Optimization, 2013, v.23, No.2, p.934-962.
• Juditsky A., Kilinc Karzan F., Nemirovski A. On unified view of nullspace-type conditions for recoveries associated with general sparsity structures // Linear Algebra and its Applications, 2013, http://dx.doi.org/10.1016/j.laa.2013.07.025
• Nesterov Yu., Nemirovski A. On first order algorithms for $\ell_1$/nuclear norm minimization // Acta Numerica, 2013, v. 22, p. 509-575.

2012

• Гольштейн Е.Г. Об одном классе антагонистических игр // Экономика и математические методы, 2012, т.48, №3, с.113-120.
• Березнева Т.Д. Скользящие планы в модели роста с неоднородными трудовыми ресурсами / Сб. «Теоретические и прикладные задачи нелинейного анализа». М.: ВЦ РАН, 2012, с.132–143.
• Беленький В.З., Заславский А.А. Фидуциальный подход в инвариантной задаче оптимальной остановки // Экономика и математические методы, 2012, т.48, в.1, с.80-93.
• Заславский А.А., Липатова А.Н. Двойственный метод решения биматричных игр // Экономика и математические методы, 2012, т.48, в.4.
• Мартынов Г.В., Малков У.Х., Ермакова И.Г. Динамическая модель сбалансированности финансовых потоков макроэкономики / Препринт # WP/2012/295. М.: ЦЭМИ РАН, 2012.-70с.
• Nemirovski A. On Safe Tractable Approximations of Chance Constraints // European Journal of Operational Research, 2012, v.2 19, p.707-718.
• Juditsky A., Kilinс Karzan F., Nemirovski A. Randomized first order algorithms with applications to $\ell_1$ minimization // Mathematical Programming Online First, 1 August 2012, DOI: 10.1007/s10107-012-0575-2.
• Juditsky A., Nemirovski A. First Order Methods for Nonsmooth Large-Scale Convex Minimization, I: General Purpose Methods II: Utilizing Problem's Structure. - In: S. Sra, S. Nowozin, S. Wright, Eds., «Optimization for Machine Learning». 2012, The MIT Press, p.121-184.
• Nesterov Yu. Towards nonsymmetric conic optimization // Optimization Methods and Software, 2012, v.27, No.4-5, p.893-918.
• Babonneau F., Nesterov Yu., Vial J.-Ph. Design and operations of gas transmission networks // Operations Research, February 2012, p.1-14.
• Nesterov Yu. Efficiency of coordinate descent methods on huge-scale optimization problems // SIAM Journal on Optimization, 2012, v.22, No.2, p.341-362.

2011

• Гольштейн Е.Г. Численное решение одной задачи равновесия, основанное на обобщенном методе уровней // Журнал вычислительной математики и математической физики, 2011, т.51, №9, с.1588-1593.
• Березнева Т.Д. Об однопродуктовых моделях роста при бесконечном горизонте планирования / Сб. «Теоретические и прикладные задачи нелинейного анализа». М.: ВЦ РАН, 2011, с.87-99.
• Беленький В.З., Заславский А.А. Основания теории фидуциальных вероятностей: принцип инертности // Экономика и математические методы, 2011, т.47, №3, с.80-93.
• Juditsky A., Nemirovski A. On verifiable sufficient conditions for sparse signal recovery via $\ell_1$ minimization // Mathematical Programming Series B, 2011, v.127, p.57-88.
• Juditsky A., Kilinc Karzan F., Nemirovski A. Verifiable conditions of $\ell_1$-recovery of sparse signals with sign restrictions // Mathematical Programming Series B, 2011, v.127, p.89-122.
• Lan G., Nemirovski A., Shapiro A. Validation analysis of mirror descent stochastic approximation method // Mathematical Programming Online First, Feb. 03, 2011, DOI 10.1007/s10107-011-0442-6, 34p.
• Juditsky A., Nemirovski A., Tauvel C. Solving variational inequalities with Stochastic Mirror Prox algorithm // Stochastic Systems, 2011, v.1, №1, DOI: 10.1214/10-SSY011, 17-58.
• Juditsky A., Nemirovski A. First Order Methods for Nonsmooth Large-Scale Convex Minimization, I: General Purpose Methods / In: S.Sra, S.Nowozin, S.Wright, Eds., Optimization for Machine Learning. The MIT Press, 2011, p.121-148.
• Juditsky A., Nemirovski A. First Order Methods for Nonsmooth Large-Scale Convex Minimization, II: Utilizing Problem's Structure / In: S.Sra, S.Nowozin, S.Wright, Eds., Optimization for Machine Learning. The MIT Press, 2011, p.149-184.
• Nesterov Yu. Towards non-symmetric conic optimization Optimization Methods and Software, iFirst, 2011, p.1-25, DOI:10.1080/10556788.2011.567270.
• Nesterov Yu., Scrimali L. Solving strongly monotone variational and quasi-variational inequalities // Discrete and Continuous Dynamical Systems, 2011, v.31, №4, p.1383-1396, DOI 10.3934/dcds.2011.31.1383.
• Nesterov Yu. Barrier subgradient method // Mathematical Programming, 2011, v.127, №1, p.31-56.

2010

• Гольштейн Е.Г. О модификациях конечной бескоалиционной игры, имеющих выпуклую структуру // Экономика и математические методы, 2010, т.46, в.4.
• Березнева Т.Д. Асимптотические свойства траекторий в модели экономического роста с разделением труда / Сб. «Теоретические и прикладные задачи нелинейного анализа». - М.: ВЦ РАН, 2010, с.50-61.
• Березнева Т.Д. О предельных стационарных состояниях в модели оптимального экономического роста / Сб. «Теоретические и прикладные задачи нелинейного анализа». - М.: ВЦ РАН, 2010, с.134-143.
• Нестеров Ю.Е. Введение в выпуклую оптимизацию. М.: МЦНМО, 2010.
• Nesterov Yu. Barrier subgradient method // Mathematical programming, 2010, DOI: 10.1007/s10107-010-0421-3.
• Nemirovski A., Onn S., Rothblum U. Accuracy certificates for computational problems with convex structure // Mathematics of Operations Research, 2010, v.35, No.1, p.52-78.
• Tunccel L., Nemirovski A. Self-Concordant Barriers for Convex Approximations of Structured Convex Sets // Foundations of Computational Mathematics, 2010, v.10, No.5, p.485-525.
• Заславский А.А. Об усилении оценок в задачах целочисленного линейного программирования // Экономика и математические методы, 2010, т.46, в.4.

2009

• Гольштейн Е.Г. Об одной задаче равновесия, связанной с бескоалиционными играми // Экономика и математические методы, 2009, т.45, в.4.
• Гольштейн Е.Г. О монотонности отображения, связанного с неантагонистической игрой многих лиц // Журнал вычислительной математики и математической физики, 2009, т.49, №9.
• Соколов Н.А. Новые модификации обобщенного седлового варианта метода уровней // Журнал вычислительной математики и математической физики, 2009, т.49, №1.
• Заславский А.А., Френкин Б.Р. Математика турниров. М.: МЦ НМО, 2009.
• Березнева Т.Д. Некоторые свойства траекторий однопродуктовой модели с разноэффективными ресурсами / Сб. "Теоретические и прикладные задачи нелинейного анализа". М.: ВЦ РАН, 2009.
• Blondel V., Nesterov Yu. Polynomial-time computation of the joint spectral radius for some sets of nonnegative matrices // SIAM J. Matrix Anal. Appl., 2009, v.31(3), p.865-876.
• Nesterov Yu. Unconstrained convex minimization in relative scale // Mathematics of Operation Research, 2009, v.34(1), p.180-193.
• Nesterov Yu. Primal-dual subgradient methods for convex problems // Mathematical programming, 2009, v.120(1), p.261-283.
• Ben-Tal A., Nemirovski A. On safe tractable approximations of chance constrained linear matrix inequalities // Mathematics of Operations Research, 2009, v.34(1), p.1-25.
• Nemirovski A., Juditsky A., Lan G., Shapiro A. Stochastic approximation approach to stochastic programming // SIAM Journal on Optimization, 2009, v.19(4), p.1574-1609.
• Juditsky A., Nemirovski A. Non-parametric estimation via convex programming // Annals of Statistics, 2009, v.37(5A), p.2278-2300.
• Juditsky A., Nemirovski A. Nonparametric denoising of signals with unknown local structure, I: Oracle inequalities // Applied and Computational Harmonic Analysis, 2009, v.27, p.157-179.
• Ben-Tal A., El Ghaoui L., Nemirovski A. Robust Optimization. Princeton: Princeton Univ. Press, 2009, 564 p.

9.  Программные реализации

8.

1. ПАОЭМ - библиотека научных программ по оптимизации.
2. Программа PDLEV прямой декомпозиции задач линейного программирования, основанной на методе уровней:
   Аннотация;  Описание алгоритма и программы, PDF-файл, 716Kb;
   Приложения, ZIP-файл с текстами процедур и программ, FORTRAN, 26Kb.