Математика: темы
Оптимизация и исследование операций
Формулы и правила по теме «Оптимизация и исследование операций».
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 минимум штрафовой функции обычно остаётся немного недопустимым, поэтому метод использует последовательность растущих параметров. |