Математика: темы

Оптимизация и исследование операций

Формулы и правила по теме «Оптимизация и исследование операций».

13 формул

Таблица формул

Формула Запись Тема Для чего нужна
Производная по направлению через градиент $D_{\mathbf u}f(\mathbf a)=\nabla f(\mathbf a)\cdot \mathbf u,\quad \|\mathbf u\|=1$ Математический анализ Производная по направлению равна скалярному произведению градиента на единичный вектор направления. Она измеряет мгновенную скорость изменения функции вдоль выбранного луча.
Экстремумы квадратичной формы на сфере $\lambda_{\min} \le \frac{x^T A x}{x^T x} \le \lambda_{\max}, \quad A=A^T.$ Линейная алгебра На единичной сфере максимум и минимум квадратичной формы достигаются на собственных векторах, соответствующих λ_max и λ_min.
Критерий наименьших квадратов $\hat x_{\mathrm{LS}}=\arg\min_{x\in\mathbb R^n} \|Ax-b\|_2^2 = \arg\min_x (Ax-b)^\top (Ax-b).$ Линейная алгебра Критерий наименьших квадратов измеряет суммарную квадратичную ошибку между наблюдаемым вектором b и моделью Ax, поэтому превращает переопределенную систему в задачу минимизации.
Метод золотого сечения: сужение интервала минимума $\tau=\frac{\sqrt5-1}{2},\quad u=a+(1-\tau)(b-a),\quad v=a+\tau(b-a),\quad L_n=\tau^nL_0$ Численная оптимизация Золотое сечение находит минимум унимодальной функции без производных. Два внутренних значения позволяют отбросить часть интервала, а удачное отношение длин сохраняет одно вычисление для следующего шага.
Тернарный поиск минимума непрерывной унимодальной функции $u=a+\frac{b-a}{3},\quad v=b-\frac{b-a}{3},\quad [a,b]\leftarrow\begin{cases}\left[u,b\right],&f(u)>f(v),\\\left[a,v\right],&f(u)\le f(v),\end{cases}\quad L_n=(2/3)^nL_0$ Численная оптимизация Тернарный поиск сравнивает функцию в двух точках, делящих интервал на трети. При унимодальности одно сравнение позволяет удалить крайнюю треть и сохранить интервал, содержащий минимум.
Параболическая интерполяция для поиска минимума функции $A=\frac{(f_3-f_2)/(x_3-x_2)-(f_2-f_1)/(x_2-x_1)}{x_3-x_1},\quad B=\frac{f_2-f_1}{x_2-x_1}-A(x_1+x_2),\quad x_p=-\frac{B}{2A}$ Численная оптимизация Через три значения функции строят квадратичный интерполянт и используют его вершину как новую пробную точку минимума. В отличие от деления интервала схема учитывает высоты всех трёх точек.
Градиентный спуск с постоянным шагом: условие убывания $x_{k+1}=x_k-\alpha\nabla f(x_k),\quad 0<\alpha<2/L,\quad f(x_{k+1})\le f(x_k)-\alpha(1-L\alpha/2)\|\nabla f(x_k)\|^2$ Численная оптимизация Постоянный шаг градиентного спуска смещает точку против градиента. При липшицевом градиенте известная граница шага обеспечивает уменьшение функции и объясняет, почему слишком крупный шаг вызывает расходимость.
Правило Армихо: обратный поиск длины шага спуска $f(x+\alpha p)\le f(x)+c\alpha\nabla f(x)^Tp,\quad \nabla f(x)^Tp<0,\quad \alpha\leftarrow\beta\alpha,\quad 0<c<1,\ 0<\beta<1$ Численная оптимизация Обратный поиск по правилу Армихо уменьшает пробный шаг, пока функция не снизится на заданную долю линейного прогноза. Он выбирает длину движения вдоль уже найденного направления спуска.
Отражение в методе Нелдера—Мида $x_r=\bar x+\alpha(\bar x-x_w),\quad\alpha=1$ Численная оптимизация Отражение в методе Нелдера—Мида даёт не только вычислительную запись, но и правило, какие данные определяют результат и как проверить его численно. Формула применяется к строго указанной модели; ниже разобраны предпосылки, два решённых задания и границы корректной интерпретации.
Обновление BFGS для обратной матрицы Гессе $H_{k+1}=(I-\rho sy^T)H_k(I-\rho ys^T)+\rho ss^T,\quad\rho=(y^Ts)^{-1}$ Численная оптимизация Обновление BFGS для обратной матрицы Гессе даёт не только вычислительную запись, но и правило, какие данные определяют результат и как проверить его численно. Формула применяется к строго указанной модели; ниже разобраны предпосылки, два решённых задания и границы корректной интерпретации.
Условия Каруша—Куна—Таккера: комплементарная нежёсткость $\lambda_i g_i(x)=0,\quad\lambda_i\ge0,\quad g_i(x)\le0$ Численная оптимизация Условия Каруша—Куна—Таккера: дополнительная нежёсткость даёт не только вычислительную запись, но и правило, какие данные определяют результат и как проверить его численно. Формула применяется к строго указанной модели; ниже разобраны предпосылки, два решённых задания и границы корректной интерпретации.
Симплекс-метод: правило минимального отношения $\theta^*=\min_{i:a_{ij}>0}\frac{b_i}{a_{ij}}$ Численная оптимизация Симплекс-метод: правило минимального отношения даёт не только вычислительную запись, но и правило, какие данные определяют результат и как проверить его численно. Формула применяется к строго указанной модели; ниже разобраны предпосылки, два решённых задания и границы корректной интерпретации.
Квадратичный штраф за нарушение равенства $\Phi_\mu(x)=f(x)+\frac{\mu}{2}h(x)^2$ Численная оптимизация Квадратичный штраф заменяет равенство h(x)=0 добавкой mu h(x)^2/2 к цели. При конечном mu минимум штрафовой функции обычно остаётся немного недопустимым, поэтому метод использует последовательность растущих параметров.