PaperlayerView exact revision on arXiv

Source-linked AI summary

Convex optimization

Evgeniya Vorontsova, Roland Hildebrand, Alexander Gasnikov, Fedor Stonyakin

arXiv:2106.01946v4math.OCmath.NA

TL;DR

Convex optimization education needs methods that exploit problem structure and a coherent treatment spanning analysis, algorithms, and conic models. This textbook presents a two-semester curriculum covering convex analysis, numerical methods, conic optimization, and robust optimization, with oracle complexity and optimality results as central themes. It emphasizes that efficient methods depend on the problem class and highlights optimality results such as the center-of-gravity method for first-order convex optimization.

Abstract

from arXiv · show

This textbook is based on lectures given by the authors at MIPT (Moscow), HSE (Moscow), FEFU (Vladivostok), V.I. Vernadsky KFU (Simferopol), ASU (Republic of Adygea), and the University of Grenoble-Alpes (Grenoble, France). First of all, the authors focused on the program of a two-semester course of lectures on convex optimization, which is given to students of MIPT. The first chapter of this book contains the materials of the first semester ("Fundamentals of convex analysis and optimization"), the second and third chapters contain the materials of the second semester ("Numerical methods of convex optimization"). The textbook has a number of features. First, in contrast to the classic manuals, this book does not provide proofs of all the theorems mentioned. This allowed, on one side, to describe more themes, but on the other side, made the presentation less self-sufficient. The second important point is that part of the material is advanced and is published in the Russian educational literature, apparently for the first time. Third, the accents that are given do not always coincide with the generally accepted accents in the textbooks that are now popular. First of all, we talk about a sufficiently advanced presentation of conic optimization, including robust optimization, as a vivid demonstration of the capabilities of modern convex analysis.

R. Tyrrell Rockafellar [282]

The textbook presents convex optimization as an interplay of theory, mathematical modeling, and numerical methods, drawing on lectures delivered at several universities. It covers a two-semester curriculum while emphasizing advanced conic and robust optimization, accelerated gradient methods, and selected recent developments.

R. Tyrrell Rockafellar [282]

  • R. Tyrrell Rockafellar [282] frames optimization around convex analysis, mathematical modeling, and numerical methods, whose interaction supports optimality conditions and duality-based analysis.The passage describes these three components as mutually connected foundations of optimization.Source: R. Tyrrell Rockafellar [282] · p. 3

Введение

  • The textbook is based on lectures at six universities and follows a two-semester course covering convex analysis and optimization before numerical methods.It omits some nonconvex and stochastic optimization material included in another book.Source: Введение · p. 9
  • The book proves fewer stated results than classical textbooks to cover more connections and constructions, while offering advanced treatments of conic, robust, accelerated-gradient, and tensor optimization.Its separate examples chapter illustrates the roles of convex analysis in formulation and modern numerical methods in solving convex optimization problems.Source: Введение · pp. 9–10

Основы выпуклого анализа

Раздел излагает основы выпуклого анализа и их применение к задачам гладкой, негладкой, минимаксной, квадратичной и линейной оптимизации, включая топологию, выпуклые множества и функции, дифференциальное и субдифференциальное исчисление, условия Лагранжа и KKT, двойственность и теоремы об альтернативах. Особое внимание уделено коническим представлениям и релаксациям, факторизационным характеристикам конусов, а также робастной оптимизации и аппроксимациям при неопределённости данных.

Основы выпуклого анализа

  • Выпуклая оптимизация рассматривает минимизацию выпуклой функции на выпуклом множестве и использует разделение гиперплоскостью для обоснования принципа множителей Лагранжа.Материал не предполагает конечномерности пространств и подготавливает эффективные численные методы и их переформулировки.Source: Основы выпуклого анализа · p. 14
  • Глава выделяет теоремы min max = max min, Демьянова–Данскина–Рубинова, теорию двойственности и теоремы об альтернативах, а также продвинутое коническое и робастное программирование.Рассматриваются примеры спектральных, log-det и матрично-дробных выпуклых функций, условия Липшица и теорема Радемахера о дифференцируемости почти всюду.Source: Основы выпуклого анализа · p. 14, §1.2 · pp. 22–24

1.1 Элементы топологии

  • Нормы задают метрику и расстояние до множества, а в конечномерных пространствах все нормы эквивалентны; рассматриваются евклидова, Гёльдера, max- и ℓ1-нормы.Неравенство Коши–Буняковского выводится через положительность скалярного произведения и отрицательность дискриминанта соответствующего квадратичного полинома.Source: §1.1 · pp. 15–16

1.2 Выпуклые множества и выпуклые функции

  • Выпуклое множество содержит каждый отрезок между своими точками, а выпуклая функция удовлетворяет неравенству Йенсена, эквивалентному выпуклости её надграфика.Выпуклость функции многих переменных можно проверять по всем одномерным сечениям; для дважды дифференцируемых функций она эквивалентна неотрицательной определённости гессиана.Source: §1.2 · pp. 18–20
  • Функция f(x)=|x| непрерывна по Липшицу с константой L0=1.Source: §1.2 · p. 24

1.3 Конусы и отношения порядка в евклидовых пространствах

  • Выпуклые конусы замкнуты относительно неотрицательного масштабирования и выпуклых комбинаций, задают обобщённые частичные порядки, а двойственный конус является замкнутым выпуклым конусом.Для замкнутого конуса выполняется (K*)*=K; конус положительно полуоси задаёт обычный порядок, а положительный ортант — покомпонентные неравенства.Source: §1.3 · pp. 24–27

1.4 Как получать выпуклые функции?

  • Выпуклость сохраняется при неотрицательных взвешенных суммах, а также при аффинном преобразовании аргумента f(Ax+b).Для вогнутых функций аналогично сохраняется вогнутость.Source: §1.4.1 · p. 27, §1.4.2 · p. 28

1.4.3 Композиция, максимум и точная верхняя грань функций

  • Композиция выпуклой функции с выпуклой неубывающей функцией, поточечный максимум и точная верхняя грань семейства выпуклых функций сохраняют выпуклость.Через максимум можно, например, получить выпуклость суммы k максимальных компонент.Source: §1.4.3 · p. 28

1.4.4 Минимизация

  • Минимизация совместно выпуклой функции G(x,y) по переменной y на непустом выпуклом множестве Q в определённых условиях сохраняет выпуклость по x.В частности, это применяется к функциям, построенным через норму ∥x−y∥.Source: §1.4.4 · p. 29

1.5 Негладкие задачи

  • Для негладких выпуклых функций субградиент заменяет градиент: глобальный минимум x* эквивалентен условию 0∈∂f(x*).Субградиенты задают глобальные нижние аффинные оценки; направленная производная равна максимуму a^Ts по a∈∂f(x0), а субдифференциал |x| в нуле равен [−1,1].Source: §1.5 · pp. 30–32

1.6 Формула Демьянова–Данскина

  • Формула Демьянова–Данскина дифференцирует по направлению максимум по компактному множеству: при выпуклости G по x результирующая функция выпукла, а при единственном максимизаторе используется ∇xG(x,y(x)).Теорема мотивирована минимаксными приложениями и известна также как теорема Данскина.Source: §1.6 · pp. 32–33
  • Теорема Демьянова–Данскина задаёт направленную производную функции, определённой как максимум параметризованного семейства, а теоремы об очистке позволяют уменьшать число ограничений.Субдифференциальная форма теоремы об очистке обобщает теорему Дубовицкого–Милютина на произвольное число функций.Source: §1.6 · pp. 34–35

1.7 Дополнение по Шуру

  • При A ≻ 0 неотрицательная определённость блочной матрицы X эквивалентна неотрицательной определённости дополнения Шура S, а положительная — совместной положительности S и A.Дополнение Шура применяется к минимизации квадратичной формы и возникает также при исключении блоков переменных в линейных системах.Source: §1.7 · p. 36

1.8 Теорема о неявной функции

  • Теорема о неявной функции обеспечивает локальное представление y как функции x при выполнении условий регулярности и переносится на банаховы пространства.Она применяется к итеративным оптимизационным методам, регуляризации, принципу множителей Лагранжа и теореме Люстерника.Source: §1.8 · pp. 36–38

1.9 Экстремальные задачи и двойственность

  • Экстремальная задача задаётся целевой функцией и допустимым множеством; выпуклость упрощает теорию двойственности, условий экстремума и существования решений.Основные результаты далее рассматриваются преимущественно в конечномерных пространствах, но переносятся на бесконечномерные случаи.Source: §1.9 · pp. 38–39

1.9.1 Правило множителей Лагранжа для задачи с ограничениями типа равенств

  • Для гладкой задачи с равенствами линейная независимость градиентов ограничений в точке минимума приводит к существованию множителей Лагранжа и эквивалентным условиям для функции Лагранжа.Доказательство использует теорему о неявной функции и сводит задачу с ограничениями к безусловной минимизации; для выпуклых задач условия становятся достаточными.Source: §1.9.1 · pp. 40–42

1.9.2 Гладкие задачи с ограничениями типа равенств и неравенств

  • В гладких задачах с равенствами и неравенствами множители λ и ν связываются соответственно с равенственными и неравенственными ограничениями и образуют двойственные переменные.Неравенство h_i(·) ≤ 0 называется активным, если h_i(x′) = 0; задача предполагается имеющей непустую область допустимых точек.Source: §1.9.2 · pp. 42–43
  • Для каждой пары множителей с ν ⩾ 0 двойственная функция Лагранжа не превосходит оптимальное значение прямой задачи, а максимизация этой функции образует двойственную задачу.Двойственная функция вогнута, поэтому соответствующая задача является задачей выпуклого программирования.Source: §1.9.2 · pp. 43–44

1.9.3 Чувствительность в оптимизации

  • Множитель Лагранжа измеряет чувствительность оптимального значения целевой функции к изменению ограничения и интерпретируется как его цена.Для одного аффинного ограничения справедливо Δf = −λ*Δb с точностью до первого порядка; аналогичная интерпретация действует для нескольких ограничений и более общего вида g_i(x) = b.Source: §1.9.3 · pp. 45–47

1.9.4 Задачи выпуклого программирования

  • В выпуклой задаче локальный минимум глобален, а условия KKT необходимы; при ν_0 ≠ 0 они также достаточны для оптимальности допустимой точки.Условия включают минимум функции Лагранжа, дополняющую нежёсткость и неотрицательность множителей; их обоснование связывается с теоремами отделимости выпуклых множеств.Source: §1.9.4 · pp. 47, 48, 50, 51

1.9.5 Сильная и слабая двойственность

  • Слабая двойственность утверждает, что оптимальное значение двойственной задачи не превышает значение прямой даже в невыпуклом случае, а равенство определяет сильную двойственность.Разность этих оптимальных значений называется зазором двойственности; для невыпуклых задач сильная двойственность встречается редко.Source: §1.9.5 · p. 54
  • В задаче на единичном шаре оптимум задаётся нормированным собственным вектором симметричной матрицы, соответствующим её минимальному собственному значению.Такие задачи называют trust region problem и используют для оптимальных аппроксимаций второго порядка.Source: §1.9.5 · p. 55
  • Целочисленная задача разбиения с переменными x_i ∈ {−1,1} имеет 2^n допустимых точек и в общем случае является NP-трудной.Квадратичная функция интерпретируется как стоимость размещения элементов в одной или разных частях, а двойственная функция даёт нижнюю оценку оптимума.Source: §1.9.5 · pp. 55–56
  • Условие Слейтера гарантирует сильную двойственность выпуклой задачи, если существует строго допустимая точка; при аффинных ограничениях это условие можно ослабить.Строго допустимая точка удовлетворяет равенствам и строгим неравенствам для нелинейных ограничений; теорема Слейтера даёт нулевой двойственный зазор.Source: §1.9.5 · pp. 56–57

1.9.6 Задача линейного программирования

  • Линейное программирование оптимизирует линейную функцию на многограннике, заданном конечной системой линейных равенств и неравенств, и служит этапом алгоритмов нелинейной оптимизации.ЛП широко применялось для задач распределения ресурсов, производства и управления; его основателями считаются Канторович и другие исследователи.Source: §1.9.6 · pp. 57, 59
  • Симплекс-метод имеет полиномиальную сглаженную сложность: после небольших случайных возмущений входа он с высокой вероятностью работает за полиномиальное время.Это объясняет практическую быстроту метода несмотря на существование входов с экспоненциальным временем работы.Source: §1.9.6 · pp. 61–62
  • Для примера Кли–Минти при n=71 симплекс-методу требуется 2^n−1 ≈ 1.18 · 10^21 итераций, что при 1000 вершин в секунду составляет около 37 миллиардов лет.Этот пример показывает экспоненциальный худший случай метода Данцига, хотя рандомизированный симплекс-метод Келлнера и Спилмана имеет полиномиальное время работы.Source: §1.9.6 · pp. 63–64
  • Для линейного программирования слабая двойственность даёт c^T x* ≥ −b^T λ*, а при конечных оптимальных решениях сильная двойственность обеспечивает c^T x* = −b^T λ*.Переход к двойственной задаче может уменьшить размерность при числе ограничений, существенно меньшем числа переменных.Source: §1.9.6 · p. 65

1.9.7 Оценка на множители Лагранжа

  • При выполнении условий Слейтера можно получить верхнюю оценку на оптимальные множители Лагранжа.Такая оценка полезна при использовании штрафных функций или двойственного подхода.Source: §1.9.7 · p. 66

1.9.8 Геометрическая интерпретация

  • Геометрически сильная двойственность следует из существования невертикальной опорной гиперплоскости, а условия Слейтера гарантируют её существование через теорему отделимости.Без условий сильной двойственности зазор в общем случае может быть ненулевым; для возмущённых ограничений двойственные множители дают нижнюю оценку оптимума и характеризуют чувствительность к ужесточению или ослаблению ограничений.Source: §1.9.8 · pp. 67–72

1.9.9 Условия дополняющей нежёсткости

  • При сильной двойственности условия дополняющей нежёсткости означают, что множитель ν_i равен 0 для неактивного ограничения, а положительный ν_i возможен только при h_i(x*) = 0.Эти условия следуют из неположительности слагаемых, сумма которых достигает нулевого значения.Source: §1.9.9 · p. 73

1.9.10 Седловые точки

  • Седловая точка функции Лагранжа эквивалентна совпадению оптимальных значений прямой и двойственной задач, но может отсутствовать даже у простой функции.В приведённом примере оптимальные значения равны 1/4 и 0, поэтому функция Лагранжа не имеет седловых точек.Source: §1.9.10 · pp. 74–75
  • В задачах с седловыми точками функция выпукла по x при фиксированном ν и вогнута по ν при фиксированном x.Source: §1.9.10 · p. 76

1.10 Задача квадратичного программирования

  • При C≻0 оптимальные значения прямой и двойственной задач квадратичного программирования совпадают, то есть выполняется сильная двойственность.Квадратичное программирование сводится к минимизации квадратичной функции на положительном ортанте и часто возникает как этап численных методов оптимизации.Source: §1.10 · p. 78

1.11 Лемма Неймана–Пирсона

  • Лемма Неймана–Пирсона задаёт наиболее мощный критерий уровня значимости α через отношение правдоподобий двух простых гипотез.Наилучшая критическая область включает наблюдения, значительно более вероятные при H1, чем при H0.Source: §1.11 · p. 81

1.12 Лемма Фаркаша

  • Лемма Фаркаша–Минковского утверждает, что ровно одна из двух альтернативных систем имеет решение, а геометрически разделяющая гиперплоскость отделяет вектор от порождённого конуса.Для применения результата используется замкнутость конуса {c| c=Ax, x⩾0}; это также даёт критерий отсутствия решений задачи Ax=b, x⩾0.Source: §1.12 · pp. 83–85

1.12.1 Двойственность и лемма Фаркаша

  • В подразделе о двойственности вводится ещё одна формулировка леммы Фаркаша для альтернативных систем, предполагающая существование решения двойственной задачи.Эта версия подготавливает применение леммы к задачам двойственности.Source: §1.12.1 · p. 86

1.12.2 Связь теоремы Гильберта о нулях и леммы Фаркаша

  • Теорема Гильберта о нулях даёт альтернативу между существованием решения системы полиномиальных уравнений с R(x) ≠ 0 и представлением R^r через эти многочлены.Требование алгебраической замкнутости существенно; лемма Фаркаша аналогично описывает препятствия для линейных неравенств, а её следствия включают теоремы отделимости и Хелли.Source: §1.12.2 · pp. 87–88
  • Лемма Фаркаша утверждает, что единственным препятствием разрешимости системы линейных неравенств является существование неотрицательной комбинации, выводящей противоречие −1 ⩾ 0.Это связывает проверку разрешимости с сертификатом несовместности.Source: §1.12.2 · p. 89

1.12.3 Арбитражная теорема

  • В модели CRR справедливая цена европейского опциона определяется условием отсутствия арбитража, а на полном рынке однозначно задаётся единственной мартингальной мерой.Поиск арбитража сводится к системе Ax ⩾ 0, Ax ≠ 0 и через лемму Фаркаша — к условию y^T A = 0.Source: §1.12.3 · p. 92

1.12.4 Когда выгоден переход к двойственной задаче?

  • При сильной двойственности задачу с ограничениями можно заменить безусловной двойственной задачей и восстановить решение прямой задачи по формуле.Если матрица A не полноранговая, двойственное решение может быть неединственным, но восстановленные решения прямой задачи совпадают.Source: §1.12.4 · p. 93

1.13 Формулировка оптимизационных задач

  • Оптимизационная задача задаётся переменной x, допустимым множеством X и целевой функцией f, а выбор алгоритма зависит от выпуклости и доступности информации.Функция и множество могут описываться аналитически или через оракул; по их структуре выделяются LP, MILP и QP.Source: §1.13 · p. 94
  • Задачи классифицируют по форме функции и ограничений, преобразуют между эквивалентными классами или релаксируют, если стандартное эффективное решение недоступно.Полиномиальные задачи можно сводить к QCQP; выпуклый QCQP при положительно определённых матрицах и отсутствии квадратичных ограничений сводится к конично-квадратичной программе.Source: §1.13 · pp. 95–96, §1.14.2 · p. 99

1.14.1 Конические программы

  • Конические программы над симметричными конусами эквивалентны LP, CQP/SOCP или SDP, а их эффективное решение зависит главным образом от выбранного конуса.Любую выпуклую задачу можно переписать в конической форме; преобразование гарантирует эффективное решение, если размерность существенно не возрастает.Source: §1.14.1 · pp. 97–99

1.14.2 Преобразование и релаксации квадратичных задач

  • Полуопределённая релаксация QCQP получается удалением невыпуклого ограничения на ранг, задаёт нижнюю границу исходного оптимума и точна при единственном ограничении.Если релаксация имеет решение ранга 1, оно восстанавливает решение исходной задачи; при одном ограничении такая точность гарантирована.Source: §1.14.2 · pp. 100–101

1.14.3 Коническое представление множеств и функций

  • Коническое представление позволяет преобразовывать выпуклые задачи к стандартным программам, объединяя ограничения через прямые произведения конусов и используя lifting-переменные.Представимые множества замкнуты относительно конечных пересечений, аффинных сечений, аффинных образов и прообразов; представление функций сводится к представлению их надграфиков.Source: §1.14.3 · pp. 101–102
  • Коническое представление позволяет сводить многие нелинейные выпуклые задачи к стандартным коническим программам, решаемым пакетами вроде CVX.Для этого используют библиотеку стандартных функций с известными представлениями и правила их композиции для автоматического поиска представлений новых функций.Source: §1.14.3 · pp. 106–107

1.14.4 Преобразования конических программ

  • Конические программы можно преобразовывать через сечения и линейные проекции конусов, а оба подхода допускают комбинирование и являются двойственными.Сечение конуса задаёт эквивалентную программу над расширенным конусом; проекционное представление реализуется, в частности, введением дополнительных переменных.Source: §1.14.4 · pp. 107–108
  • Любой однородный конус является спектраэдральным, а симметрические конусы являются частным примером такого представления.Для ортантов и эрмитовых матричных конусов приведены соответствующие изоморфизмы с конусами неотрицательно определённых матриц.Source: §1.14.4 · p. 109

1.14.5 Программы над несимметричными конусами

  • Геометрическая программа после логарифмической замены и введения дополнительных переменных представляется как коническая программа над произведением экспоненциальных конусов.В результате целевая функция становится линейной, а нелинейность сосредотачивается в ограничениях над 3-мерными экспоненциальными конусами; такой солвер предлагается в MOSEK.Source: §1.14.5 · pp. 110–111

1.14.6 Теорема Яннакакиса и её обобщения

  • Минимальная размерность представления регулярного полиэдрального конуса через ортант равна неотрицательному рангу его матрицы невязок.Это следует из взаимного соответствия между ортантными представлениями и неотрицательными факторизациями матрицы невязок.Source: §1.14.6 · pp. 113–114
  • Факторизация оператора невязок регулярного конуса через K′ даёт представление K через K′, а обратное утверждение требует, чтобы L[V] пересекало int(K′).Это обобщает леммы Яннакакиса и явно выделяет дополнительное условие, необходимое для обратного направления.Source: §1.14.6 · pp. 115–116
  • Минимальный размер представления регулярного конуса K через матричный конус S_m равен полуопределённому рангу его оператора невязок.Следовательно, отсутствие факторизации оператора невязок через матричный конус исключает полуопределённую представимость; аналогичный результат действует для представлений через конусы Лоренца.Source: §1.14.6 · pp. 116–117

1.14.7 Аппроксимация полуопределённо представимыми конусами

  • Конус Лоренца можно аппроксимировать полиэдральным конусом, имеющим представление через ортант, используя аппроксимации правильными многогранниками.Конус над многогранником с N гранями представим через ортант размерности O(log N), а точность аппроксимации L_3 составляет ε = O(N^-1).Source: §1.14.7 · p. 117
  • Для MaxCut тригонометрическое множество T_A является внутренней аппроксимацией политопа MC, причём conv T_A = MC, а соответствующая константа не улучшается.Результат опирается на гауссовскую рандомизацию X и даёт субоптимальные решения квадратичной задачи; при A ⪰ 0 их ожидаемое значение не меньше 2/π оптимального.Source: §1.14.7 · pp. 118–119
  • Теорема Гёмaнса–Вильямсона гарантирует для полуопределённой релаксации MaxCut коэффициент γ, а при истинности Гипотезы Уникальных Игр его нельзя улучшить полиномиальным алгоритмом.Лемма 1.25 превращает релаксационное решение в случайное разбиение, ожидаемый вес которого не меньше γ веса максимального разреза.Source: §1.14.7 · pp. 119–120

1.14.8 Двойственные конические программы

  • Двойственная коническая программа максимизирует нижнюю оценку ⟨b, y⟩ на оптимум исходной задачи, а зазор между прямой и двойственной парами измеряет близость к решению.Для допустимых точек выполняется слабая двойственность, поэтому двойственная задача задаётся над K* и предоставляет проверяемую оценку.Source: §1.14.8 · pp. 120–121

1.15 Робастная оптимизация

  • Методология, учитывающая возможные неточности в данных, должна обеспечивать осмысленные ответы, согласованные с исходными неточностями, а интервальная модель описывает неопределённость границами возможных значений параметров.В вероятностно-статистической модели исходные данные считаются случайными величинами, но параметры распределения остаются неизвестными; интервальная модель в ряде прикладных задач оказывается наиболее предпочтительной.Source: §1.15 · p. 122
  • Робастная оптимизация выбирает лучшее решение среди удовлетворяющих ограничениям для всех наборов данных из заданной области неопределённости.При классической постановке целевой критерий минимизирует наихудшее значение; область неопределённости может задаваться, например, доверительным эллипсоидом.Source: §1.15 · pp. 122–123
  • При выпуклом множестве неопределённости робастная задача преобразуется в детерминированную коническую программу над конусом положительных отображений.Если точное преобразование невозможно, применяется аппроксимация; для матричного куба оценивается возникающая ошибка.Source: §1.15 · pp. 123–124

1.15.1 Робастная версия задачи конического программирования

  • Робастная версия конической задачи имеет смысл для неопределённых коэффициентов в неравенствах и при выпуклом компактном U с непустой внутренностью сама остаётся конической программой.Она требует выполнения конического ограничения для каждого набора коэффициентов из U.Source: §1.15.1 · pp. 124–125
  • Робастная версия формулируется над конусом положительных отображений Pos(K_U, K), поэтому её сложность определяется алгоритмической доступностью этого конуса и исходных конусов.Множество положительных отображений является регулярным выпуклым конусом.Source: §1.15.1 · p. 125

1.15.2 Конусы положительных отображений

  • Для полиэдрального K_U с N экстремальными лучами Pos(K_U, K) представим через K^N; поэтому при политопе U классы LP, SOCP и SDP сохраняются.При небольшом числе экстремальных точек сложность сопоставима с исходной, а при большом может существенно возрасти.Source: §1.15.2 · pp. 126–127
  • Эллипсоидальная неопределённость переводит робастную SOCP-задачу в SDP, тогда как для матричных конусов общего вида проверка положительности может быть сложной.Полуопределённые релаксации точны при размерах матричных блоков не более 3 или двумерном эллипсоиде неопределённости; иначе они могут быть консервативными.Source: §1.15.2 · pp. 127–129

1.15.3 Теорема о матричном кубе

  • Для матричного куба внутренняя SDP-релаксация заменяет экспоненциальное число 2^m условий проверкой совместимости 2^m+1 линейных матричных неравенств.Эта релаксация точна при размере матриц n=1; раздел также вводит величину для оценки ошибки релаксации.Source: §1.15.3 · pp. 129–130
  • Для матричного куба, не включённого в SR, используется элемент двойственного конуса, отделяющий его от SR.Это служит исходным условием формулировки теоремы 1.32.Source: §1.15.3 · pp. 131–132
  • Двойственный конус SR* представляется как сечение произведения соответствующих конусов.Source: §1.15.3 · p. 131
  • Граница внутренней аппроксимации SR близка к границе Pos(K_U, S_n^+) в точках, соответствующих матрицам B_1, ..., B_m малого ранга.Это наблюдение непосредственно предшествует теореме 1.32.Source: §1.15.3 · p. 132

Эффективность численных методов выпуклой оптимизации · 2.2 Методы выпуклой оптимизации для задач небольшой размерности

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

Эффективность численных методов выпуклой оптимизации

  • Эффективность метода измеряется числом обращений к оракулу для достижения заданной точности, а чёрный ящик использует только локальные ответы оракула.Эта концепция позволяет получать верхние и нижние оценки оракульной сложности для подклассов выпуклых функций; число обращений часто определяет число итераций и общую вычислительную сложность.Source: Эффективность численных методов… · pp. 134–135

Обозначения

  • Для рассматриваемых обозначений предполагается существование оптимального решения x*∈Q, а оптимальное значение функции обозначается f*=f(x*).Source: Обозначения · p. 139

2.2 Методы выпуклой оптимизации для задач небольшой размерности

  • Методы небольшой размерности решают выпуклую оптимизацию на компактном выпуклом теле Q, требуют отсекающего оракула и имеют линейную или квадратичную зависимость числа обращений к оракулу от n.Отсекающий оракул либо подтверждает x∈Q, либо строит гиперплоскость, отделяющую x от Q; поэтому методы применимы лишь к задачам не очень большой размерности.Source: §2.2 · pp. 139–140

2.2.1 Методы решения одномерных задач

  • В одномерной минимизации бисекция по знаку производной сужает интервал до длины не более ε и имеет линейную сходимость, тогда как золотое сечение при каждом шаге умножает длину интервала на α<1.Бисекция сначала расширяет интервал экспоненциальными шагами, а затем последовательно делит его пополам; золотое сечение использует значения функции в точках, включая симметричные внутренние точки.Source: §2.2.1 · pp. 140–142
  • Метод золотого сечения для одномерных задач имеет линейную сходимость.Source: §2.2.1 · p. 142

2.2.2 Метод центров тяжести

  • Метод центров тяжести требует O(nlog(C/ε)) обращений к оракулам первого и нулевого порядков и является оптимальным по порядку для широкого класса выпуклых функций.Его оценка не может быть улучшена методами, использующими оракул первого порядка, но для более узких классов функций могут существовать более эффективные методы.Source: §2.2.2 · pp. 144–146
  • Метод центров тяжести непрактичен при n>2, поскольку эффективной нерандомизированной процедуры вычисления центра тяжести многомерного множества не существует.Несмотря на это, метод представляет теоретический интерес, а его идея используется в методе эллипсоидов.Source: §2.2.2 · pp. 145–146

2.2.3 Метод эллипсоидов

  • Метод эллипсоидов заменяет вычисление центра тяжести нахождением центра описанного эллипсоида, требуя O(n^2) операций на итерацию и O(n^2 log(1/ε)) обращений к оракулу.При липшицевости f на евклидовом шаре радиуса R с константой M теорема 2.2 даёт не более 2n^2 log(MR/ε) обращений к оракулу.Source: §2.2.3 · pp. 146, 148
  • При условии существования оптимального решения в B_2(0,R) ε-приближенное решение находится за O((n+m)n^3 log(Rhn/ε)) арифметических операций.Вычисления выполняются над O(log(Rhn/ε))-разрядными двоичными числами.Source: §2.2.3 · p. 152
  • Каждый шаг метода строит эллипсоид меньшего объема, причем vol(E′) ≤ e^−1/(2(n+1)) vol(E) при O((n+m)n) операциях.Метод стартует с E_0 = B_2(0,R) и последовательно уточняет область поиска отсекающими гиперплоскостями.Source: §2.2.3 · pp. 152–153
  • Для целочисленной системы линейных неравенств точное решение восстанавливается из ε_0-допустимого решения за O(mn^2) операций.Процедура использует не более n итераций, каждая из которых требует не более O(mn^2) операций.Source: §2.2.3 · pp. 154–155
  • Для задачи ЛП с битовой длиной входа L метод эллипсоидов требует O(mn^3L) операций, используя точность порядка O(L) двоичных разрядов.В резюме также указаны параметры ε_1 = 1/(4n^(5/2)Δ^3(A)||c||) и R = n^(3/2)hΔ(A).Source: §2.2.3 · p. 155

2.3 Субградиентные методы

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

для задач выпуклой оптимизации

  • Для выпуклых негладких липшицевых функций обычный субградиентный метод Шора является оптимальным, а выбор параметров дает точность, оптимальную с точностью до константного множителя.Размерность итерационной оценки согласуется с числом итераций N = M^2R^2/ε^2.Source: для задач выпуклой оптимизации · pp. 155, 157, 158
  • Для задач с функциональным ограничением субградиентная схема с переключением использует целевой субградиент на продуктивных шагах и субградиент ограничения на непродуктивных.Предполагается, что целевая функция и ограничение липшицевы на Q с константами M_f и M_g; шаги выполняются с проекцией на замкнутое множество Q.Source: для задач выпуклой оптимизации · pp. 159–160
  • Теорема 2.5 устанавливает оценку после заданного числа итераций алгоритма переключения и тем самым гарантирует существование продуктивных шагов.Доказательство отдельно анализирует продуктивные и непродуктивные итерации, используя выпуклость, липшицевость и свойства оператора проектирования.Source: для задач выпуклой оптимизации · pp. 160–161
  • Для задач на компактном допустимом множестве алгоритм имеет прямо-двойственную интерпретацию: качество пары приближенных решений оценивается величиной зазора двойственности при выполнении условий Слейтера.Ограничение представляется как максимум нескольких функций, а двойственные множители восстанавливаются по работе алгоритма.Source: для задач выпуклой оптимизации · p. 162
  • При правильном выборе шага субградиентные методы оптимальны по нижним оценкам числа вызовов оракула для выпуклых задач с ограниченной константой Липшица,.Для функций с липшицевым градиентом ни один выбор шага в рассматриваемом классе градиентного спуска не дает оптимального метода.Source: для задач выпуклой оптимизации · p. 164

2.4 Методы типа градиентного спуска · 2.5 Оценка скорости сходимости градиентного спуска для задач гладкой выпуклой оптимизации

Раздел рассматривает градиентный спуск и его ускоренные варианты для гладких выпуклых и сильно выпуклых задач, включая выбор шага и оценку сходимости. Для точной оценки постоянного шага используется сведение к конечномерной полуопределённой релаксации, а оптимальный шаг зависит от числа итераций и при его увеличении стремится к 2/(L + μ).

2.4 Методы типа градиентного спуска

  • Метод Чебышёва оптимален на классе методов первого порядка для квадратичных задач с параметрами μ и L, а оценку градиентного спуска в общем случае улучшить нельзя.Лучший выбор постоянного шага требует знания μ; при μ=0 вместо сходимости по аргументу рассматривается сходимость по функции.Source: §2.4 · pp. 166–167
  • Метод сопряжённых градиентов достигает оптимальных оценок и не требует знания μ и L, тогда как метод Чебышёва сохраняет более близкую к градиентному спуску форму.Оба метода основаны на многочленах Чебышёва; методы типа Чебышёва проще обобщать на гладкие выпуклые задачи без вспомогательной маломерной оптимизации.Source: §2.4 · pp. 168–169
  • Ускоренные методы Тейлора–Дрори и Кима–Фесслера дают оптимальные оценки для классов соответственно μ-сильно выпуклых и выпуклых функций с L-липшицевым градиентом.Для обоих методов установлены соответствующие нижние оценки, ограничивающие улучшение скорости в рассматриваемых классах.Source: §2.4 · pp. 170–171

2.5 Оценка скорости сходимости градиентного спуска для задач гладкой выпуклой оптимизации

  • Точная оценка расстояния до оптимума после k итераций постоянного шага формулируется как невыпуклая бесконечномерная задача на классе F_μ,L.Рассматриваются начальные точки в шаре радиуса R вокруг оптимума и фиксированный шаг γ>0.Source: §2.5 · p. 172
  • Существование функции из F_μ,L с заданными значениями и градиентами в конечном наборе точек эквивалентно квадратичным условиям на эти скаляры и векторы.Это наблюдение переводит анализ бесконечномерного объекта в конечномерную постановку.Source: §2.5 · pp. 173–174
  • Полуопределённая релаксация полученной квадратичной задачи точна при d≥2k+1, поэтому в произвольной размерности можно численно находить оптимальный шаг для фиксированного числа итераций.Аналогичный анализ применим к переменным шагам и другим критериям сходимости; численный эксперимент указывает на одномерную наихудшую функцию для критерия по значению.Source: §2.5 · pp. 174–175
  • Полученный выбор шага приводит к оценке скорости сходимости, параметризованной числом обусловленности κ = μ/L.Source: §2.5 · p. 175
  • Оптимальная длина шага γ минимизирует максимум в правой части неравенства и определяется как функция числа итераций k.Максимум минимизируется, когда два выражения в фигурных скобках становятся равными.Source: §2.5 · p. 175
  • При k → ∞ оптимальная длина шага стремится к γ = 2/(L + μ).Source: §2.5 · p. 175

2.6 Метод условного градиента, или алгоритм Франк–Вульфа · 2.7 Ускоренный Мета-алгоритм

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

2.6 Метод условного градиента, или алгоритм Франк–Вульфа

  • Метод Франка–Вульфа линеаризует целевую функцию, минимизирует линейную аппроксимацию на Q и использует найденную точку для выбора направления.Он предполагает выпуклость и непрерывную дифференцируемость f, компактность и выпуклость Q, а также более простую линейную оптимизацию на Q.Source: §2.6 · p. 176
  • Отсутствие проекции, независимость от нормы и сохранение разреженности делают метод Франка–Вульфа эффективным для важных приложений.При политопном Q линейная подзадача является линейной программой, а для шаров простых норм и их проекций она может решаться явно.Source: §2.6 · p. 176
  • Метод Франка–Вульфа аффинно инвариантен, а величина f(x_k) − μ_k задаёт верхнюю границу двойственного зазора.μ_k является нижней границей оптимального значения задачи.Source: §2.6 · pp. 176–177
  • При старте из вершины политопа после k итераций результат является выпуклой комбинацией не более k вершин, что при k << n существенно меньше размерности пространства.Это следует из описания разреженности итераций и того, что скорость сходимости не зависит от размерности.Source: §2.6 · p. 178

2.7 Ускоренный Мета-алгоритм

  • Ускоренный Мета-алгоритм показывает, что одной ускоренной проксимальной оболочки достаточно для получения всех известных ускоренных методов гладкой выпуклой безусловной оптимизации.В ряде случаев он устраняет логарифмические зазоры в оценках сложности относительно нижних оценок.Source: §2.7 · p. 179

2.7.1 Основные результаты

  • Теорема 2.9 устанавливает сходимость Ускоренного Мета-алгоритма при p ≥ 1 и H ≥ (p + 1)L_p,f, а для p ≥ 2 задаёт условие достижения точности ε.Вспомогательную задачу можно решать неточно; такая модификация добавляет множитель 12/5 в правую часть (2.41).Source: §2.7.1 · pp. 180–181
  • УМ и его теорема сходимости распространяются на условную оптимизацию на выпуклых множествах простой структуры Q, включая неточное решение вспомогательных задач.Для негладкой g критерий точности такого решения может быть трудно обеспечить, поэтому предлагаются более удобные критерии.Source: §2.7.1 · p. 181
  • Оценка сходимости Ускоренного Мета-алгоритма оптимальна с точностью до числового множителя для выпуклых задач с липшицевой p-й производной.При равномерной выпуклости F оптимальный метод строится на базе УМ с помощью рестартов, а теорема 2.10 оценивает общее число вычислений вспомогательной задачи.Source: §2.7.1 · pp. 182–183

2.8 Приложения Ускоренного Мета-алгоритма

Раздел показывает, как Ускоренный Мета-алгоритм применяется к композитной, проксимальной, оракульной и седловой оптимизации. Он объединяет ускорение различных методов и достигает квазиоптимальных оценок с точностью до логарифмического множителя.

2.8.1 Ускоренные методы композитной оптимизации

  • Для композитной оптимизации Ускоренный Мета-алгоритм задаёт семейство ускоренных методов различных порядков и допускает негладкую функцию g [254].При p=1 поиск параметра λ_{k+1} не требуется, что упрощает метод.Source: §2.8.1 · p. 183

2.8.2 Ускоренные проксимальные методы. Каталист

  • Ускоренный проксимальный метод не требует очень точного решения вспомогательной задачи, поэтому её сложность может не зависеть от точности ε исходной задачи.Каталист получается как частный случай Ускоренного Мета-алгоритма и использует ускоренную проксимальную оболочку для неускоренных процедур.Source: §2.8.2 · pp. 183–184

2.8.3 Разделение оракульных сложностей

  • Разделение оракульных сложностей обеспечивает квазиоптимальное число вызовов оракулов для функций f и g, оптимальное с точностью до логарифмического множителя.Оракул вычисляет производные до порядка p включительно; при p=1 внутреннюю задачу также можно решать покомпонентными, безградиентными методами или методами редукции дисперсии.Source: §2.8.3 · p. 184

2.8.4 Ускоренные методы для седловых задач

  • Для гладких выпукло-вогнутых седловых задач Ускоренный Мета-алгоритм строит оптимальные градиентные методы на базе оптимальных ускоренных методов выпуклой оптимизации.Применение Каталиста улучшает схему из на логарифмический множитель и распространяет её на ненулевые f и h; возможны обобщения на невыпукло-сильно-вогнутые задачи [325].Source: §2.8.4 · p. 186
  • Универсальная схема ускорения позволяет «собрать как в конструкторе» оптимальный метод с точностью до логарифмического множителя по желаемой точности решения.При f≡0 и h≡0 такая оптимальность опирается на известные нижние оценки. Обратный переход от Mirror Prox к оптимальному методу гладкой выпуклой оптимизации указан в [127].Source: §2.8.4 · p. 186

2.9 Методы внутренней точки

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

2.9 Методы внутренней точки

  • Методы внутренней точки строят итерации во внутренности конуса, а их применимость определяется эффективно вычислимым самосогласованным барьером.Короткий шаг имеет полиномиальную сложность, а дополнительная структура, например симметрия конуса, может ускорить практическую работу длинным шагом.Source: §2.9 · pp. 186–187

2.9.1 Самосогласованные функции

  • Самосогласованные функции обеспечивают аффинно-инвариантный анализ метода Ньютона и контролируют изменение локальных норм, аппроксимации и ньютоновского декремента.Для сильно самосогласованных функций шаг Ньютона сохраняет принадлежность области при локальной норме градиента не более единицы, а декремент монотонно уменьшается.Source: §2.9.1 · pp. 187–190
  • Самосогласованность сохраняется при ограничении на аффинное подпространство, прибавлении линейной функции и сложении функций на прямом произведении.Эти свойства позволяют переносить самосогласованность между связанными выпуклыми конструкциями.Source: §2.9.1 · p. 189

2.9.2 Прямой метод внутренней точки с коротким шагом

  • Для прямого метода следования центральному пути центральный путь при τ→+∞ стремится к решению исходной задачи, а при неединственности — к относительной внутренности множества решений.Метод чередует шаг Ньютона и обновление параметра τ, сохраняя итерации в окрестности центрального пути и удовлетворяющими линейным ограничениям.Source: §2.9.2 · pp. 192–193
  • На каждом шаге короткий метод увеличивает log τ на величину порядка ν^-1/2, то есть умножает τ на 1+O(ν^-1/2), и сходится линейно.Меньший параметр барьера ν ускоряет сходимость; поэтому требуется эффективно вычислимый логарифмично однородный самосогласованный барьер с небольшим ν.Source: §2.9.2 · pp. 194–195

2.9.3 Двойственные барьеры

  • Для логарифмично однородного самосогласованного барьера на конусе двойственный барьер определяется преобразованием Лежандра на двойственном конусе.Для каждого s во внутренности двойственного конуса соответствующая точка x существует и единственна и удовлетворяет F′(x) = −s.Source: §2.9.3 · p. 196
  • Двойственный барьер F* также является логарифмично однородным самосогласованным барьером, а отображение L: x ↦ −F′(x) изометрически связывает внутренности K и K*.Кроме того, L переводит тензор третьих производных F′′′(x) в соответствующий тензор двойственного барьера.Source: §2.9.3 · p. 196

2.9.4 Примеры самосогласованных барьеров

  • Самосогласованные барьеры для LP, SOCP и SDP имеют совпадающие с двойственными исходные формы, оптимальный параметр и авто-шкалированность, что поддерживает эффективные методы с длинным шагом.Для экспоненциального конуса также рассматривается барьер, но он относится к несимметричному случаю.Source: §2.9.4 · p. 197

2.9.5 Универсальные конструкции барьеров

  • Универсальный барьер F(x)=log φ(x) существует на любом регулярном выпуклом конусе, имеет параметр ν=n, вычисляется через автоморфизмы на однородных конусах, но обычно труден для неоднородных.Канонический барьер задаётся уравнением в частных производных, также имеет параметр ν=n, дуален каноническому барьеру двойственного конуса и совпадает с универсальным на однородных конусах.Source: §2.9.5 · pp. 198–199

2.9.6 Другие варианты методов внутренней точки

  • Короткошаговое следование центральному пути достигает точности ϵ за O(√νlog ϵ) итераций, тогда как длинный шаг теоретически требует O(νlog ϵ), возвращаясь в узкую окрестность несколькими шагами Ньютона.Прямо-двойственные методы одновременно приближают центральные пути прямой и двойственной задач, а методы редукции потенциала монотонно уменьшают потенциал и сходятся к решениям.Source: §2.9.6 · pp. 199–200

2.9.7 Прямо-двойственные методы на симметричных конусах

  • На симметричных конусах точка шкалировки задаёт ближайшую к текущей прямо-двойственную пару на графе изометрии, а авто-шкалированные барьеры позволяют делать длинные шаги, поэтому на практике обычно достаточно нескольких десятков итераций.Направления Нестерова–Тодда сочетают улучшение целевых функций с центрированием; в SDP вычисление точки шкалировки требует порядка O(n^4) операций.Source: §2.9.7 · pp. 200–203

2.9.8 История методов внутренней точки

  • История методов внутренней точки прошла путь от метода Дикина и полиномиального метода Кармаркара к центральным путям, прямо-двойственным и потенциал-редуцирующим методам, обобщённым Нестеровым и Немировским на выпуклые конические ограничения.Теория авто-шкалированных барьеров и длинных шагов на симметричных конусах стала наиболее эффективной на практике и используется в современных солверах,.Source: §2.9.8 · pp. 204–206
  • Методы, использующие автошкалируемость, были обобщены на гиперболические и однородные конусы, а точки шкалировки — на произвольные самосогласованные барьеры.Source: §2.9.8 · p. 206
  • Новые универсальные самосогласованные барьеры появились для конусов и выпуклых множеств, линейного программирования [225, п. 6.3] и несимметричных конусов, включая экспоненциальный.Для построения алгоритмов также предлагалось использовать отрицательную кривизну вместо автошкалируемости, а следование центральному пути с энтропическим барьером связывалось с имитацией отжига.Source: §2.9.8 · p. 206
  • Параллельно методам внутренней точки развивались обобщения симплекс-метода на полуопределённое программирование, включая цикл работ В. Г. Жадана.Source: §2.9.8 · p. 206

2.10 Концепция неточной модели функции и методы градиентного типа для задач, допускающих существование таких моделей

This section develops inexact function models and gradient-type methods for convex and composite optimization, addressing inaccurate oracles, approximate subproblem solutions, relative smoothness, and model-specific structures. It examines adaptive and accelerated schemes, convergence guarantees, error trade-offs, universal conditional-gradient methods, and regularization with restarts.

2.10 Концепция неточной модели функции и методы градиентного типа для задач, допускающих существование таких моделей

  • The abstract (δ, L)-function model generalizes the Devolder–Glineur–Nesterov inexact oracle and supports gradient methods for inaccurate values, gradients, nonsmooth subgradients, lower-smoothness functions, and composite objectives.Without errors, the resulting dimension-independent rates are optimal; with oracle errors, acceleration may accumulate inaccuracies and underperform the ordinary method.Source: §2.10 · p. 207, §2.10.1 · p. 214

2.10.1 Неточный оракул и неточная модель целевой функции: понятия и базовые свойства

  • The model framework broadens first-order optimization to structured tasks, including LASSO and network-flow matrix recovery, while requiring explicit control of auxiliary-subproblem errors.A proposed error description can avoid error accumulation even for accelerated methods and connects model-based gradient methods with Frank–Wolfe methods.Source: §2.10 · p. 208, §2.10.1 · p. 215

2.10 Концепция неточной модели функции и методы градиентного типа для задач, допускающих существование таких моделей

  • Relative smoothness replaces the Lipschitz-gradient condition with a Bregman-divergence inequality, enabling gradient methods for functions such as x^4 that lack Lipschitz gradients.Prox-structures may be non-Euclidean, but the resulting auxiliary minimization problems become more difficult and may require solving nonlinear equations approximately.Source: §2.10 · pp. 210–211
  • Nonaccelerated gradient methods have optimal complexity on a broad class of convex relatively smooth problems, whereas accelerated methods require a 1-strongly convex prox-function to be optimal for ordinarily smooth problems.The weaker inequality suffices for nonaccelerated theory, while 1-strong convexity is essential for optimal acceleration on the standard smooth class.Source: §2.10 · p. 211

2.10.1 Неточный оракул и неточная модель целевой функции: понятия и базовые свойства

  • For composite convex optimization, the abstract model extends accelerated gradient methods and yields convergence estimates analogous to those for ordinary smooth convex problems.The composite objective combines a smooth convex function with Lipschitz gradient and a generally nonsmooth convex component.Source: §2.10.1 · pp. 214–215

2.10.2 О подходах к описанию погрешностей при решении вспомогательных подзадач, возникающих на итерациях численных методов

  • Точность по функции не всегда означает точность по аргументу, однако при липшицевости ψ по норме ε-решение по функции становится (M/L)-решением по определению 2.10.Это делает концепцию приближённого решения пригодной для описания ошибок вспомогательных подзадач градиентных методов.Source: §2.10.2 · pp. 219–220

2.10.3 Градиентный метод с оракулом, использующим на итерациях неточную модель функции

  • Адаптивный неускоренный градиентный метод подбирает локальные константы L_k, применим к относительно гладким задачам и не требует 1-сильной выпуклости прокс-функции.Адаптивность балансирует скорость и гарантированную точность; число обращений к вспомогательным задачам увеличивается в среднем менее чем в три раза.Source: §2.10.3 · pp. 221, 222, 224

2.10.1 Неточный оракул и неточная модель целевой функции: понятия и базовые свойства

  • Неточная модель функции задаётся через (δ, L, V)-модель относительно дивергенции V в точке y, причём такая модель предполагается существующей в каждой точке области Q.В евклидовом неограниченном случае при δ = eδ = 0 вспомогательная задача сводится к обычному градиентному шагу.Source: §2.10.3 · pp. 221–222

2.10.3 Градиентный метод с оракулом, использующим на итерациях неточную модель функции

  • Теорема 2.13 устанавливает оценку сходимости алгоритма 2.10 при наличии неточной (δ, L, V)-модели и ограничении на начальную дивергенцию Брэгмана.Метод применим при L_0 ≤ 2L, а точность вспомогательных подзадач задаётся параметром eδ.Source: §2.10.3 · pp. 221, 225

2.10.4 Примеры сильно выпуклых прокс-функций

  • Для ускоренного метода существенна 1-сильная выпуклость прокс-функции, а таблица примеров связывает такие проксы и дивергенции Брэгмана с p-нормами при 1 ≤ p ≤ 2.Масштабированная функция из (2.88) 1-сильно выпукла относительно 1-нормы; KL-прокси удобен явными формулами проекции на симплекс.Source: §2.10.4 · pp. 227–230
  • Неевклидовы прокс-функции могут улучшать оценку через константу L: для разреженных решений естественна 1-норма, а переход от 2-нормы к 1-норме способен существенно уменьшить L.Все прокс-функции из табл. 2.2 1-сильно выпуклы в соответствующих нормах на всём пространстве и применимы к неускоренным и ускоренным методам.Source: §2.10.4 · pp. 230–231
  • Теорема 2.14 задаёт оценки сходимости ускоренного метода для (δ, L)-модели при V(x*, x0) ≤ R^2 и L0 ≤ 2L.Метод использует 1-сильно выпуклую прокс-функцию, а расстояние до ближайшего решения измеряется дивергенцией Брэгмана.Source: §2.10.4 · pp. 230, 233, 237

2.10.6 Некоторые следствия из описанных теоретических результатов о сходимости градиентных методов в модельной общности

  • При δ = 0 и точном решении подзадач ускоренный метод оптимален на классе выпуклых функций с L-липшицевым градиентом, хотя его константа равна 8 вместо ≃1.В этом режиме ускоренные методы имеют лучшие оценки сходимости, чем неускоренные.Source: §2.10.6 · p. 238
  • Ускоренный метод устойчивее к ошибкам решения промежуточных подзадач, но может накапливать ошибку δ модели; неускоренный метод не накапливает δ, зато выигрывает у ускоренного лишь при δ = 0 или малом δ.Для ускоренного метода точность вспомогательной задачи становится труднее поддерживать с ростом номера итерации из-за роста обусловленности.Source: §2.10.6 · pp. 238–239
  • Универсальные методы адаптивно настраиваются на константу Липшица или Гёльдера и уровень гладкости, а для задачи Ферма–Торричелли–Штейнера экспериментально достигают O(1/ε) вместо гарантированного O(1/ε^2).Аналогичная скорость O(1/ε) наблюдалась для обобщённой задачи о расстояниях до выпуклых множеств и для равновесного распределения потоков.Source: §2.10.6 · pp. 239–240
  • Теорема 2.14 также обобщает метод условного градиента Франк–Вульфа, заменяя трудную оптимизационную модель более простой, когда промежуточные подзадачи нельзя решать за разумное время.Это связывает модельный анализ ускоренного метода с практической эффективностью условного градиента для некоторых классов задач.Source: §2.10.6 · pp. 242–243
  • Для ускоренного градиентного метода получена оценка сходимости, которая для методов типа Франка–Вульфа не может быть улучшена с точностью до числового множителя.Source: §2.10.6 · pp. 243–244

2.10.7 Универсальный метод условного градиента

  • Универсальный метод условного градиента требует ν > 0, поскольку при ν = 0 метод условного градиента может не сходиться.Алгоритм 2.12 адаптивно настраивается на оптимальный уровень и константу гладкости во время итераций, поэтому заранее вычислять N не требуется.Source: §2.10.7 · pp. 244–245

2.10.8 Регуляризация и рестарты

  • Регуляризация переводит решение невыпуклой задачи в решение регуляризованной сильно выпуклой задачи с μ = ε/(2R^2), а рестарты дают обратный переход к сильно выпуклым задачам.Описанный прием рестартов применим не только к алгоритму 2.12, но и к методам, чьи оценки зависят от начального расстояния, невязки функции или нормы градиента.Source: §2.10.8 · pp. 245–246
  • Для композитной задачи в 1-норме специальная прокс-функция обеспечивает R^2 = O(log n) и ω_n = O(log n), позволяя применить схему рестартов.При μ ≫ ε/(2 log n) итерации требуют вычисления градиента и решения вспомогательной композитной подзадачи через двойственную задачу и метод эллипсоидов.Source: §2.10.8 · p. 249
  • В типичных приложениях стоимость вычисления градиента обычно доминирует стоимость вспомогательной задачи, поэтому ее можно решать с высокой точностью без существенного влияния на общую сложность.Авторы отмечают, что описанная техника демонстрирует применимость методов выпуклой оптимизации в пространствах больших размерностей и является известным им способом учитывать сильную выпуклость в 1-норме ускоренным методом.Source: §2.10.8 · p. 250

2.11 Другие концепции неточного градиента

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

2.11.1 Основные результаты

  • Для концепции (2.115) даже на гладких сильно выпуклых задачах обычный градиентный метод без регуляризации или ранней остановки не гарантирует пренебрежимо малое влияние шума.В сильно выпуклом случае неускоренные методы могут сходиться в (1−α)^−1 раз медленнее, тогда как для ускоренных сохранение порядка скорости доказано при α≲(μ/L)^3/4; в вырожденном случае α_k≲k^−3/2.Source: §2.11.1 · pp. 251, 253
  • При ограниченном ˜R неускоренные и ускоренные методы достигают f(x_k)−f(x*)=ε при δ(2.115)≃ε/˜R за порядок итераций, сопоставимый с точным градиентом.В вырожденном режиме малое μ делает нижние оценки неблагоприятными; регуляризация с μ≃ε/R^2 или ранняя остановка [312] позволяют уменьшить ˜R, а при случайном шуме условия могут ослабляться.Source: §2.11.1 · pp. 251–253

2.11.2 Обратная задача для эллиптического уравнения на квадрате

  • В эллиптической обратной задаче вычисление ∇𝔍(q)(y) сводится к решению двух корректных начально-краевых задач — прямой (P) и сопряжённой (D).Градиент неточен неизбежно, поскольку задачи (P) и (D) решаются численно; техника применима также к другим обратным задачам.Source: §2.11.2 · pp. 253, 256, 257

Примеры задач

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

и их практическое решение

  • Раздел демонстрирует численные методы на барицентре Васерштейна, задачах Франка–Вульфа, субградиентном спуске и полуопределённом программировании.Для задач на симплексе дешёвые итерации Франка–Вульфа могут дать лучшее время работы, чем ускоренные методы для гладких выпуклых задач.Source: и их практическое решение · p. 258

3.1.1 Примеры. Задача Монжа

  • Задача Монжа моделирует минимизацию стоимости перемещения массы между областями, кластерами или производителями и потребителями, но некоторые исходные постановки могут не иметь решения.В дискретной форме она сводится к транспортной задаче, заданной отображением между пунктами производства и потребления.Source: §3.1.1 · p. 261

3.1.2 Релаксация Канторовича

  • Релаксация Канторовича разрешает расщеплять массу между несколькими пунктами назначения и при весьма общих предположениях гарантирует существование решения.В отличие от постановки Монжа, она допускает вероятностное распределение массы и интерпретируется как бесконечномерная задача линейного программирования.Source: §3.1.2 · p. 262

3.1.3 Оптимальный транспорт

  • Теория оптимального транспорта сравнивает вероятностные распределения с учётом геометрии пространств, а расстояние Васерштейна является оптимумом транспортной задачи.Эта теория применяется, в частности, к задачам машинного обучения, анализа и обработки изображений.Source: §3.1.3 · pp. 263, 265

3.1.4 Барицентры

  • Барицентр Васерштейна формулируется как выпуклая задача с доказанным существованием решения и допускает эффективное восстановление через двойственную гладкую оптимизацию.Энтропийное сглаживание и переход к двойственной задаче позволяют применять ускоренные градиентные методы; по двойственному решению восстанавливается исходный барицентр.Source: §3.1.4 · pp. 265, 268

3.2.1 Выпуклая формулировка общей задачи оптимизации

  • Произвольную задачу оптимизации с измеримым допустимым множеством и непрерывной функцией цены можно эквивалентно записать в виде выпуклой задачи.Эта формулировка вводит моментный подход к полуопределённым релаксациям полиномиальных задач.Source: §3.2.1 · p. 269
  • Общая выпуклая формулировка минимизирует линейный функционал по вероятностным мерам, но требует перехода от бесконечномерного конуса к конечномерным моментным описаниям и релаксациям.При полиномиальных X и f переход к моментам выполняется без дополнительных аппроксимаций; в ряде случаев релаксации точны.Source: §3.2.1 · p. 270

3.2.2 Положительные полиномы и суммы квадратов

  • Конус сумм квадратов Σ2d,n задаёт полуопределённо представимую внутреннюю аппроксимацию конуса неотрицательных полиномов, поскольку p∈Σ2d,n эквивалентно существованию A⪰0 с p(x)=x^TAx.Эта связь реализуется как линейная проекция матричного конуса, но размер матрицы быстро растёт с числом переменных и степенью.Source: §3.2.2 · p. 272
  • Релаксация суммами квадратов точна тогда и только тогда, когда min(d,n)≤2 или (d,n)=(4,3), а для разреженных полиномов проверка принадлежности часто сводится к матрицам меньшего размера.В общем случае принадлежность коположительному конусу является ко-NP-полной задачей.Source: §3.2.2 · pp. 271, 273, 274
  • Полином Моцкина неотрицателен, но не является суммой квадратов полиномов; после умножения на (x2+y2+z2)² он становится суммой квадратов и представим через рациональные функции.Это иллюстрирует 17-ю проблему Гильберта: любой неотрицательный полином представим как сумма квадратов рациональных функций.Source: §3.2.2 · p. 274

3.2.3 Релаксации типа сумм квадратов для полиномиальных задач

  • Для полиномиальной оптимизации на базовом полуалгебраическом множестве конус неотрицательных полиномов заменяется внутренним полуопределённо представимым конусом Σd,K, задаваемым конечным набором линейных и полуопределённых ограничений.Каждый полином из Σd,K неотрицателен на K, поэтому Σd,K⊂Pd,K.Source: §3.2.3 · p. 278
  • Для полиномиальной задачи релаксация типа сумм квадратов сводит исходную оптимизацию к полуопределённой программе, давшей оптимальное значение −1, совпадающее с исходным.В примере используется множество K={(x,y)|x≥0, x^2+y^2=1} и степень d=3.Source: §3.2.3 · pp. 278–280

3.2.4 Моментные релаксации

  • Моментные релаксации заменяют неэффективно описываемый конус моментов полуопределёнными и линейными необходимыми условиями, образующими внешнюю аппроксимацию и релаксацию исходной задачи; её оптимальное значение равно −1.Source: §3.2.4 · pp. 281–283

3.2.5 Релаксации типа сумм квадратов для верхних оценок

  • Релаксации с плотностью, представимой суммой квадратов, дают верхние оценки, асимптотически сходящиеся к оптимальному значению на компактных K, но применимы лишь при доступных моментах меры.Точность возрастает с максимальной степенью d; релаксация фиксированной степени может быть точной только при постоянной f_0 на K.Source: §3.2.5 · pp. 283–284

3.2.6 Тригонометрические полиномы

  • Неотрицательные скалярные и матрично-значные тригонометрические полиномы имеют полуопределённые представления через эрмитовы положительно полуопределённые матрицы и разложения в квадраты.Тригонометрические полиномы задаются через угол на [-π,π] или переменную z=e^{iφ} на единичном круге и применяются в обработке сигналов и управлении.Source: §3.2.6 · pp. 284–285

3.3.1 Оптимизация топологии фермы: подход на базе полуопределённого программирования

  • Для топологии фермы робастная полуопределённая постановка учитывает эллипсоид нагрузок, максимизирует жёсткость при ограниченной массе и решается с вычислительной сложностью, пропорциональной n^7.Эллипсоид одновременно учитывает конечное число сценариев и произвольные малые нагрузки, но делает решение консервативным; сложность следует из стоимости шага Ньютона O(n^6) и числа итераций O(n^2).Source: §3.3.1 · pp. 286–288
  • The dual reformulation reduces truss-topology complexity below O(n^7), because increased cone complexity is offset by fewer variables.The reformulation also permits recovery of arbitrarily accurate bar-mass estimates by tracking dual variables along the central path.Source: §3.3.1 · p. 289

3.3.2 Оптимизация топологии фермы: подход на базе прямо-двойственного субградиентного метода

  • The original problem (3.20) can be replaced by primal-dual problems (3.22),(3.23); under compact localization of y in Q⊂R3n, their solution is 2ε-approximate.The pair defined by (3.26) solves (3.20), and algorithm 2.4 substantially reduces per-iteration complexity through sparsity of vectors ai and f.Source: §3.3.2 · pp. 292–293

3.4 Идентификация систем

  • System identification seeks input-output information about a linear dynamical system, with optimal experiment design choosing the input to make collected data informative.The application concerns estimating parameters of systems ranging from mobile-telephone channels to aircraft from measured input and output signals.Source: §3.4 · pp. 294–295

3.4.1 Сигналы, спектры, передаточные функции

  • The modeled systems are causal, linear, time-invariant discrete-time operators, with spectra and transfer functions describing signals and additive noise.In feedback systems, a controller K is introduced, with S = (I + KG)^-1; open-loop inputs are independent of outputs and noise.Source: §3.4.1 · pp. 295–296

3.4.2 Оценка параметров

  • Parameter estimates minimize prediction error over finite input-output sequences, and under weak conditions are unbiased with covariance inverse to the Fisher information matrix.For the ARX example, the predictor is linear in (a,b), so estimation reduces to least squares.Source: §3.4.2 · pp. 296–297

3.4.3 Дизайн эксперимента

  • Maximizing the information-matrix trace under an input-energy constraint can be transformed into a finite-dimensional semidefinite program by introducing generalized trigonometric moments.The moment representation removes the original infinite-dimensional spectral variables because only finitely many moments enter the formulation.Source: §3.4.3 · pp. 298–299
  • Полуопределённое представление конуса моментов сводит задачи оптимального дизайна эксперимента с линейными целевой функцией и ограничениями к полуопределённой программе.Для совместной оптимизации по возмущению и регулятору линейные условия на моменты вместе с T(m_k) ⪰ 0 необходимы и достаточны; в частном примере программа становится линейной, а решение равно m_u,0 = −sgn a_0 · m_u,1 = c(1−|a_0|)^2N.Source: §3.4.3 · pp. 300–302

3.5.1 Максимальный вписанный в политоп эллипсоид

  • Максимальный вписанный в политоп эллипсоид находится максимизацией det C при конично-квадратичных ограничениях, представимых средствами полуопределённого программирования.Определитель заменяется геометрическим средним собственных значений матрицы C, после чего используются конично-квадратичные представления.Source: §3.5.1 · p. 302

3.5.2 Минимальный описанный вокруг политопа эллипсоид

  • Минимальный описанный вокруг политопа эллипсоид формулируется через максимизацию det D и достраивается до полуопределённой программы представлениями геометрического среднего и спектра.Политоп задан выпуклой оболочкой вершин, а эллипсоид задаётся квадратичным неравенством с положительно определённой матрицей D.Source: §3.5.2 · p. 303

3.5.3 Поиск функции Ляпунова

  • Для политопа матриц U поиск квадратичной функции Ляпунова сводится к полуопределённой программе, а строго положительное допустимое s гарантирует устойчивость.Соответствующая матрица X задаёт функцию Ляпунова; если строго положительного допустимого s нет, достаточное условие не выполняется.Source: §3.5.3 · pp. 304–305

3.5.4 Поиск линейного стабилизирующего регулятора

  • Поиск линейного стабилизирующего регулятора линеаризуется заменой Y = X^-1, после чего из допустимого решения восстанавливаются X = Y^-1 и K = Z X.Исходное условие нелинейно из-за произведения XBK; при строго положительном допустимом s найденные Y и Z дают функцию Ляпунова и управление.Source: §3.5.4 · p. 305

3.5.5 Задача о максимальной клике

  • Функция Ловаша ϑ(G) даёт верхнюю оценку кликового числа через полуопределённую программу, а более сильная релаксация использует матричное неравенство порядка n и O(n^2) линейных неравенств.Для клики мощности k строится допустимая матрица X с ценой k, поэтому k ≤ ϑ(G).Source: §3.5.5 · p. 306

3.6.1 Аппроксимация сигналов

  • Метод условного градиента решает задачу аппроксимации сигналов за O(k·p(n) + k^2) операций после k итераций при полиномиально разрешимой линейной подзадаче.Разреженность позволяет обновлять x за O(k) и z за O(n), а целевая функция имеет константу Липшица m^2 на множестве диаметра 2.Source: §3.6.1 · pp. 307–308

3.6.2 Выявление аномалий

  • Для выявления аномалий строится шар наименьшего радиуса, содержащий обучающие точки, а метод Франка–Вульфа сохраняет не более k + 1 ненулевых компонент двойственного вектора.При ограничении 2-нормы точек скорость сходимости аналогична полученной для аппроксимации сигналов.Source: §3.6.2 · pp. 308–309

3.7 Пример использования метода эллипсоидов для решения двойственной задачи малой размерности

  • В двумерной двойственной задаче метод эллипсоидов выполняет O(log(C/ε)) итераций со стоимостью O(nlog(nC/ε)) каждой.Прямо-двойственность и сильная выпуклость позволяют восстановить решение прямой задачи с точностью по функционалу порядка ε без существенных дополнительных затрат.Source: §3.7 · p. 312

3.8 Относительно гладкая оптимизационная задача

  • Для D-оптимального плана эксперимента функция является 1-гладкой относительно дивергенции Брэгмана, что обеспечивает линейную скорость сходимости неускоренного градиентного метода [232].Подход сохраняет оценку 𝑂(1/𝑁), а вычисление итерации сводится к выпуклой одномерной задаче.Source: §3.8 · pp. 313–315
  • Метод Хачияна выигрывает по общей стоимости за счёт более дешёвой итерации, хотя градиентный метод с относительной гладкостью требует меньше итераций.При близких m и n оценки сложности сопоставимы для не слишком малого ε; адаптивный вариант может улучшать качество решения.Source: §3.8 · pp. 316–317

3.9.1 Автоматическое дифференцирование

  • Автоматическое дифференцирование вычисляет аналитические производные компьютерно представленной функции, устраняя основные недостатки ручного и численного дифференцирования.Его методы используют вычислительный граф как композицию элементарных операций и правило цепочки.Source: §3.9.1 · pp. 318–319
  • Обратное автоматическое дифференцирование лежит в основе backpropagation и позволяет одним проходом вычислять градиент функции невязки по выходным переменным.В обратном режиме сначала вычисляются значения переменных графа, затем чувствительности распространяются от выходной вершины к входным.Source: §3.9.1 · pp. 320–322
  • Обратный режим автоматического дифференцирования выгоднее при большем числе входных переменных, а прямой — при большем числе выходных; обратный проход требует в 4–5 раз больше операций, чем вычисление функции.Прямой проход вычисляет один столбец матрицы Якоби, обратный — одну строку; обратный режим также требует сохранять значения всего вычислительного графа.Source: §3.9.1 · p. 321

3.9.2 Оптимизационные пакеты

  • CVX упрощает решение выпуклых задач через правила управляемого выпуклого программирования (DCP), но отвергает даже выпуклые формулировки, не распознаваемые этими достаточными условиями.Задачу иногда нужно переформулировать: например, выражение minimize sqrt(sum(x.^2)) CVX не принимает, тогда как эквивалентная запись через 2-норму допустима.Source: §3.9.2 · pp. 323–324
  • SeDuMi обычно решает задачи CVX быстрее SDPT3, тогда как SDPT3 надёжнее и поэтому используется по умолчанию; доступны также GLPK, MOSEK и Gurobi.Различия между солверами связаны с поддерживаемыми типами ограничений и производительностью.Source: §3.9.2 · p. 325
  • TensorFlow и PyTorch представляют вычисления нейронных сетей тензорами и графами, автоматически вычисляют производные и поддерживают оптимизацию многомиллионных параметров.TensorFlow поддерживает статические и динамические графы, тогда как PyTorch — только динамические, что является его недостатком; TorchScript частично компенсирует это ограничение.Source: §3.9.2 · pp. 325–328
  • Для оптимизации доступны SciPy.optimize, CPLEX, MOSEK, Gurobi и Local Solver, охватывающие задачи от линейного и квадратичного до невыпуклого программирования.SciPy.optimize также позволяет подключать собственные методы, а MOSEK, Gurobi и Local Solver предлагают академические версии.Source: §3.9.2 · pp. 330–331
  • Языки алгебраического моделирования переводят высокоуровневое описание целевой функции и ограничений в формат солвера; распространены AMPL, GAMS, AIMMS, LINGO и MPL.NEOS предоставляет бесплатный доступ более чем к 60 солверам, включая CPLEX, Gurobi и MOSEK.Source: §3.9.2 · pp. 331–332

3.9.3 Модель вычислений Блюм–Шуба–Смейла

  • Над полем рациональных чисел задача существования решения линейной системы решена Хачияном, но соответствующая проблема над вещественными числами остаётся открытой.Модель Блюма–Шуба–Смейла обобщает анализ вычислений над произвольными кольцами и полями, включая вещественные числа.Source: §3.9.3 · pp. 333–334
  • По гипотезе Шуба–Смейла полиномиального алгоритма проверки общего нуля системы полиномиальных уравнений над C не существует, а алгоритм Браунавелла работает за экспоненциальное время.Теорема Гильберта о нулях задаёт критерий существования общего нуля, а Браунавелл получил неулучшаемую оценку степеней соответствующих многочленов.Source: §3.9.3 · pp. 334–335

3.9.4 О машинной арифметике

  • 27 обращений к таблице умножения достаточно для перемножения двух 8-значных чисел методом Карацубы вместо 64 школьным способом; при удвоении разрядности трудоёмкость растёт втрое, а не вчетверо.Для чисел длины 2^m метод Карацубы требует 3^m обращений, поэтому выигрыш увеличивается с длиной сомножителей.Source: §3.9.4 · pp. 337–338
  • В двоичной системе запись чисел примерно в 3,3 раза длиннее десятичной, поэтому преимущество метода Карацубы проявляется при меньших значениях чисел.Современные компьютеры используют двоичную систему счисления.Source: §3.9.4 · p. 338
  • Умножение двух n-значных чисел ускорено до O(nlog n), а гипотеза о невозможности меньшей сложности остаётся недоказанной.Получение нижних оценок существенно труднее верхних, поскольку требует рассмотрения всех возможных способов вычисления.Source: §3.9.4 · p. 338
  • После трёх итераций уточнения обратного числа получены 8 верных цифр, причём трудоёмкость последнего шага превышает суммарную трудоёмкость предыдущих.Точность вычислений наращивается вместе с длиной используемых чисел; быстрые методы деления сводятся к операциям умножения.Source: §3.9.4 · pp. 339–340

3.9.5 Аппроксимация трансцендентных условий полуопределённо представимыми

  • Ограничение y≥e^x аппроксимируется коническими условиями над конусами Лоренца с r дополнительными переменными.Для относительной точности 10^-12 достаточно r=24 при |x|≤10 и r=29 при |x|≤100.Source: §3.9.5 · p. 341

Заключение

  • Пособие обновляет русскоязычное изложение современной оптимизации, но не охватывает стохастический градиентный спуск, распределённую и многие невыпуклые методы.Авторы рассматривают выпуклую оптимизацию как основу для последующего изучения более специализированных направлений.Source: Заключение · p. 342

Учебное издание

Учебное издание связано с Евгенией Алексеевной Воронцовой, Роландом Фальковичем Хильдебрандом и Александром Владимировичем Гасниковым; в выходных данных также указаны редакторы, технические сотрудники и параметры печати.

Учебное издание

  • Авторами учебного издания указаны Евгения Алексеевна Воронцова, Роланд Фалькович Хильдебранд и Александр Владимирович Гасников.Source: Учебное издание · p. 364

ВЫПУКЛАЯ ОПТИМИЗАЦИЯ

  • Над изданием работали редакторы В. А. Дружинина, И. А. Волкова и О. П. Котова, а корректором и специалистом по компьютерной вёрстке была Н. Е. Кобзева.Дизайн обложки выполнила Е. А. Казённова.Source: ВЫПУКЛАЯ ОПТИМИЗАЦИЯ · p. 364
  • Издание подписано в печать 11.06.2021; его тираж составил 250 экземпляров, формат — 60×84 1/16.Указаны также объёмы 22,75 условных печатных листа и 20,3 учётно-издательских листа, а также заказ №58.Source: ВЫПУКЛАЯ ОПТИМИЗАЦИЯ · p. 364
  • Печать выполнена ООО «Печатный салон ШАНС» в Москве в соответствии с предоставленным оригиналом-макетом.В выходных данных приведены адрес типографии на Ижорской улице и телефон.Source: ВЫПУКЛАЯ ОПТИМИЗАЦИЯ · p. 364

Related papers

Loading 2106.01946v4…