<jupyter_start><jupyter_text>Тема 1 Введение 1. Обзор материала семестра 2. Общие постановки задач оптимизации 3. Примеры реальных задач 4. Общая схема решения 5. Сравнение методов оптимизации  Обзор материала весеннего семестра1. Введение и примеры задач2. Методы нулевого порядка3. Теория выпуклой оптимизации4. Методы первого порядка5. Метод Ньютона и квазиньютоновские методы6. Условная оптимизация с простыми ограничениями7. Методы внутренней точки8. Введение в теорию оптимального управления  Организация работы в семестре1. Две пары раз в неделю2. Домашнее задание почти каждую неделю: $\TeX$ или Jupyter Notebook3. Миниконтрольные в начале каждого занятия4. Промежуточная контрольная в середине семестра5. Устный зачёт в конце семестра6. Накопительная система выставления финальной оценки  Инструменты и литератураИнструменты:- $\TeX$- Python 3, CVXPy & Jupyter NotebookЛитература:- [Введение в оптимизацию, Б.Т. Поляк](http://elementy.ru/catalog/3461/Polyak_B_T_Vvedenie_v_optimizatsiyu_DjVu_6_Mb_premolab_ru_sites_default_files_polyak_optimizationintro_djvu)- [Методы выпуклой оптитмизации, <NAME>](http://premolab.ru/pub_files/pub5/MnexoB89z7.pdf)- [Convex Optimization by <NAME> & <NAME>](https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf)- [Numerical Optimization by <NAME> & <NAME>](http://www.深度学习.top/literature/Nocedal_Wright_Numerical_optimization_v2.pdf)- [Clever algorithms: nature-inspired programming recipes by <NAME>](https://doc.lagout.org/science/0_Computer%20Science/2_Algorithms/Clever%20Algorithms_%20Nature-Inspired%20Programming%20Recipes%20%5BBrownlee%202012-06-15%5D.pdf)  МетодологияОсновные этапы использования методов оптимизации при решении реальных задач:1. Определение целевой функции2. Определение допустимого множества решений3. Постановка и анализ оптимизационной задачи4. Выбор наилучшего алгоритма для решения поставленной задачи5. Реализация алгоритма и проверка его корректности  Постановка задачи "математического программирования"\begin{align*}& \min_{x \in S} f_0(x)\\\text{s.t. } & f_j(x) = 0, \; j = 1,\ldots,m\\& g_k(x) \leq 0, \; k = 1,\ldots,p\end{align*}где $S \subseteq \mathbb{R}^n$, $f_j: S \rightarrow \mathbb{R}, \; j = 0,\ldots,m$, $g_k: S \rightarrow \mathbb{R}, \; k=1,\ldots,p$Пример: выбор объектов для вложения денег и определение в какой объект сколько вкладывать- $x$ — размер инвестиций в каждый актив- $f_0$ — суммарный риск или вариация прибыли- $f_j, g_k$ — бюджетные ограничения, min/max вложения в актив, минимально допустимая прибыль  Основные определения1. Точка $x^*$ называется точкой **локального минимума** функции $f(x)$, если для некоторого $\varepsilon > 0$ выполнено $f(x^*) < f(y), y \in O_{\varepsilon}(x^*)$2. Дайте аналогично определение глобальному минимумуВезде далее рассматривается задача поиска локального минимума, если не оговорено обратное.  Важные частные случаи- Оптимизация на дискретном множестве (1-2 недели)- Безусловная оптимизация- Условная оптимизация с простыми ограничениями- Условная оптимизация общего вида  Нельзя так просто взять и решить задачу оптимизацииВ общем случае: - NP-полные- рандомизированные алгоритмы: время vs стабильность         НО определённые классы задач могут быть решены быстро!- Линейное программирование- Метод наименьших квадратов - Малоранговое приближение порядка $k$ - **Выпуклая оптимизация**  Задача выпуклой оптимизации- Минимизация выпуклой функции на выпуклом множестве- Формально\begin{align*}& \min_{x \in \mathbb{R}^n} f_0(x) \\\text{s.t. } & Ax = b\\& f_j(x) \leq 0, \; j = 1,\ldots, m,\end{align*}где $f_0$ и $f_j$ выпуклые функции- Функция называется выпуклой, если она определена на выпуклом множестве и отрезок, соединяющий любые две точки графика, расположен выше самого графика- Упражнение: запишите это определение формально  "The great watershed in optimization is not between linearity and non-linearity, but convexity and non-convexity"Причины:- Локальный оптимум является глобальным- Необходимое условие оптимальности является достаточнымВопросы:- Любую ли задачу выпуклой оптимизации можно эффективно решить?- Можно ли эффективно решить невыпуклые задачи оптимизации?  Примеры реальных задач и их формализация- Аппроксимация функции по известным точкам (см. лабораторные работы по физике)- Поиск круга (или эллипса) минимальной площади, покрывающего заданные точки- Определение пространственной конфигурации аминокислот для минимизации общей энергии белка- Сглаживание и очистка от шума заданного сигнала или изображения  Аналитические результаты для дифференцируемых функций: анонс- Необходимое условие первого порядка: если $x^*$ точка локального минимума дифференцируемой функции $f(x)$, тогда $$f'(x^*) = 0$$- Необходимое условие второго порядка: если $x^*$ точка локального минимума дважды дифференцируемой функции $f(x)$, тогда $$f'(x^*) = 0 \quad \text{и} \quad f''(x^*) \succeq 0$$- Достаточное условие: пусть $f(x)$ дважды дифференцируемая функция, и пусть точка $x^*$ удовлетворяет условиям$$f'(x^*) = 0 \quad f''(x^*) \succ 0,$$тогда $x^*$ является точкой строго локального минимума функции $f(x)$.  Особенности численного решения1. Точно решить задачу принципиально невозможно из-за погрешности машинной арифметики2. Необходимо задать критерий обнаружения решения3. Необходимо определить, какую информацию о задаче использовать  Общая итеративная схемаДано: начальное приближение $x$, требуемая точность $\varepsilon$.```pythondef GeneralScheme(x, epsilon):        while StopCriterion(x) > epsilon:                OracleResponse = RequestOracle(x)                UpdateInformation(I, x, OracleResponse)                x = NextPoint(I, x)            return x```  Вопросы1. Какие критерии остановки могут быть?2. Что такое оракул и зачем он нужен?3. Что такое информационная модель?4. Как вычисляется новая точка?  Критерии остановки1. Сходимость по аргументу: $$\| x_k - x^*  \|_2 < \varepsilon$$ 2. Сходимость по функционалу: $$\| f_k - f^* \|_2 < \varepsilon$$ 3. Выполнение необходимого условия для дифференцируемой функции $$\| f'(x_k) \|_2 < \varepsilon$$Но ведь $x^*$ неизвестна!Тогда\begin{align*}& \|x_{k+1} - x_k \| = \|x_{k+1} - x_k + x^* - x^* \| \\& \leq \|x_{k+1} - x^* \| + \| x_k - x^* \| \leq 2\varepsilon\end{align*}**Замечание**: лучше использовать относительные изменения этих величин! Например $\dfrac{\|x_{k+1} - x_k \|_2}{\| x_k \|_2}$  Что такое оракул?**Определение**: оракулом называют некоторое абстрактное устройство,которое отвечает на последовательные вопросы метода**Концепция чёрного ящика**1. Единственной информацией, получаемой в ходе работы итеративного метода, являются ответы оракула2. Ответы оракула являются *локальными*  Информация о задаче1. Каждый ответ оракула даёт локальную информацию о поведении функции в точке2. Агрегируя все полученные ответы оракула, обновляем информацию о глобальном виде целевой функции:    - кривизна    - направление убывания    - etc  Вычисление следующей точки$$x_{k+1} = x_{k} + \alpha_k h_k$$- **Линейный поиск**: фиксируется направление $h_k$ и производится поиск по этому направлению "оптимального" значения  $\alpha_k$- **Метод доверительных областей**:     - фиксируется допустимый размер *области* по некоторой норме $\| \cdot  \| \leq \alpha$ и *модель* целевой функции, которая хорошо её аппроксимирует в выбранной области.     - далее производится поиск направления $h_k$, минимизирующего модель целевой функции и не выводящего точку $x_k + h_k$ за пределы доверительной областиВопросы:1. Как выбрать $\alpha_k$?2. Как выбрать $h_k$?3. Как выбрать модель?4. Как выбрать область?5. Как выбрать размер области?   Как сравнивать методы оптимизации?Для заданного класса задач сравнивают следующие величины:1. Сложность    - аналитическая: число обращений к оракулу для решения задачи с точностью $\varepsilon$    - арифметическая: общее число всех вычислений, необходимых для решения задачи с точностью $\varepsilon$2. Скорость сходимости3. Эксперименты  Скорости сходимости 1. Сублинейная$$\| x_{k+1} - x^* \|_2 \leq C k^{\alpha},$$где $\alpha < 0$ и $ 0 < C < \infty$2. Линейная (геометрическая прогрессия)$$\| x_{k+1} - x^* \|_2 \leq Cq^k, $$где $q \in (0, 1)$ и $ 0 < C < \infty$3. Сверхлинейная $$\| x_{k+1} - x^* \|_2 \leq Cq^{k^2}, $$где $q \in (0, 1)$ и $ 0 < C < \infty$4. Квадратичная$$\| x_{k+1} - x^* \|_2 \leq C\| x_k - x^* \|^2_2, \qquad \text{или} \qquad \| x_{k+1} - x^* \|_2 \leq C q^{2^k}$$где $q \in (0, 1)$ и $ 0 < C < \infty$  Оптимальные методы: can we do better?- Доказывают нижние оценки скоростей сходимости для класса задач и методов фиксированного порядка- Предлагают методы, на которых эти нижние оценки достигаются $\Rightarrow$ доказана оптимальность - Ниже про значение теорем сходимостиОптимальным методам и нижним оценкам будет, возможно, посвящён отдельный семинар.<jupyter_code>%matplotlib inline
import matplotlib.pyplot as plt
import numpy as np
C = 10
alpha = -0.5
q = 0.9
num_iter = 20
sublinear = np.array([C * k**alpha for k in range(1, num_iter + 1)])
linear = np.array([C * q**k for k in range(1, num_iter + 1)])
superlinear = np.array([C * q**(k**2) for k in range(1, num_iter + 1)])
quadratic = np.array([C * q**(2**k) for k in range(1, num_iter + 1)])
plt.figure(figsize=(12,8))
plt.semilogy(np.arange(1, num_iter+1), sublinear, 
             label=r"Sublinear, $\alpha = -0.5$")
plt.semilogy(np.arange(1, num_iter+1), superlinear, 
             label=r"Superlinear, $q = 0.5$")
plt.semilogy(np.arange(1, num_iter+1), linear, 
             label=r"Linear, $q = 0.5$")
# plt.semilogy(np.arange(1, num_iter+1), quadratic, 
#              label=r"Quadratic, $q = 0.5$")
plt.xlabel("Number of iteration, $k$", fontsize=24)
plt.ylabel("Error rate upper bound", fontsize=24)
plt.legend(loc="best", fontsize=20)
plt.xticks(fontsize = 20)
_ = plt.yticks(fontsize = 20)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11400551639595465, 'fraction_numerical': 0.019716007763816528, 'mean_word_length': 4.944140862173649, 'pattern_counts': {'":': 0, '<': 24, '<?xml version=': 0, '>': 13, 'https://': 2, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '105814', 'license': 'MIT', 'n_tokens_mistral': 4136, 'n_tokens_neox': 4731, 'n_words': 1041, 'path': '01-Intro/01-Intro.ipynb', 'repo_name': 'amkatrutsa/cet_opt_met', 'size': '9819'}