Изменения

* '''Т.''' (сильно вып. Вейерштрасса) J(u) сильно выпукла и п.н. снизу на выпуклом и замкнутом U из Гильбертова H => &rArr; достигает inf, Argmin={argmin}, <m>\frac{k}{2}|u-u_*|² \le J(u)-J(u_*)</m>.

* [[rupedia:Метод множителей Лагранжа]] относится к методам снятия ограничений. * '''Задача - .''' J(u) &rarr; min при огр. g_i &le; 0.* А мы будем минимизировать L(u,λ) = λ₀J(u) + сумма λ_ig_i, λ_i -  — множители Лагранжа.

* '''Т.''' (Куна-Таккера) (обоснование метода Лагранжа) -  — всё существует, λ_i неотрицательно, λ_ig_i=0 (усл.доп.нежёсткости). Для достаточности ещё λ_i &ne; 0.* '''Опр.''' Двойственная задача: <m>(\psi(\lambda) = inf_{u \in U_0} L(u, \lambda)) \to sup_{\lambda \in \Lambda_0}</m>* '''Т.''' (свойства дв.задачи). <m>\psi \le \psi^* \le \phi_* = J_* \le \phi(u)</m>. '''=''' только если L имеет седловую точку. === Метод проекции градиента (в ''Е^N'', в гильбертовом пространстве) === * Условный минимум — минимизируем J(u) на множестве U. В лоб — метод град. спуска проецируем на U = pr_U(u_k-a_kJ'(u_k)).* '''Т.''' (скорость сходимости) <m>\le |u_0 — u_*|_H q^k(\alpha), q(\alpha) = \sqrt{1-2k\alpha+\alpha² L²}</m> === Метод Ньютона === * Идея — градиентный (или скорейший) спуск по квадратичной аппроксимации функции J(u) в окрестности u_k.* '''Т.''' (скорость сходимости) <m>\le \frac{2k}{L}q^{2^k}(1-q^{2^k})^{-1}</m> === Метод покоординатного спуска === * Сдвигаемся на a_k в одну из сторон по одной координате по очереди, пока удаётся. Потом переходим к следующей. Потом дробим a.* '''Т.''' (обоснование сходимости) === Метод штрафных функций === * Можно также почитать [[mlwiki:Метод штрафных функций]].* Относится к методам снятия ограничений.* '''Задача.''' J(u) &rarr; min при огр. g_i &le; 0 либо = 0 начиная с g_m+1-ой.* От задачи переходим к последовательности задач <m>J(u)+A_k P(u) \to min</m>. P(u) — штраф, <m>A_k \to +\inf</m>.* '''Т.''' (обоснование) индив. штрафы должны давать огран. множество &rArr; всё сходится. === Метод барьерных функций === * Можно почитать [[mlwiki:Метод штрафных функций#Метод барьерных функций]].* По сути то же, что и метод штрафных функций, только штраф другого вида. === Метод динамического программирования === * Нет в МетОптах.* Можно почитать книжку {{Скачать|Пападимитриу, Стайглиц - Комбинаторная оптимизация.djvu}}, страницы 461—464.* Или просто [[rupedia:Динамическое программирование|Википедию]].* Идея — поиск пути по минному полю с конца к началу, ибо любой конец оптимальной траектории оптимален (принцип оптимальности Беллмана).* Вообще-то ещё есть непрерывный аналог, идея та же, реализация на дифф.исчислении и ощутимо мохнатее. === Устойчивость задач оптимизации. Метод стабилизации (регуляризация по Тихонову) === * '''Опр.''' корректно пост.задача: 1) существует, 2) единственно, 3) из сходимости значений следует сходимость аргументов.* Суть метода — в отсутствие (3) добавить к J(u) <m>+ \alpha |u|²</m> и минимизировать полученный ''функционал Тихонова''.* '''Т.''' (обоснование метода). === Линейное программирование. Симплекс-метод. Двойственные задачи линейного программирования ===

# Метод проекции градиента (в * ''Е^N'Опр.''' ЗЛП, в гильбертовом пространствеканоническая ЗЛП (u &ge; 0), угловая точка, невырожденная угловая точка, невырожденная задача.# Метод Ньютона* '''Т.# Метод покоординатного спуска.# Метод штрафных функций.# Метод барьерных функций.# Метод динамического программирования.# Устойчивость задач оптимизации. Метод стабилизации ''' (регуляризация по Тихоновукритерий угловой точки) (про линейную комбинацию r столбцов матрицы A).# Линейное программирование. * Симплекс-метод. Двойственные задачи линейного программированияметод — идея перебора угловых точек в направлении минимизации функции.