Метод Лагранжа для неравенств

[MestnyBomzh]

Добрый день!
Столкнулся с задачей по поиску условного экстремума функции при ограничениях-неравенствах. Хотел бы уточнить на форуме алгоритм действий. Верно ли я понимаю, что он следующий (пусть, для определенности, ищем максимум функции):
1) Пусть $F$ - целевая функция, $g_1...g_n$ - ограничения вида неравенства, то есть $g_i \leq 0$
2) Сначала решаем задачу безусловной оптимизации $F \to \max$
3) Далее решаем $n$ задач Лагранжа, где $i$ - ая задача имеет следующий вид: $L = F + \lambda \cdot g_i$, то есть мы смотрим что происходит на одном из краёв, обращая неравенство в равенство: $g_i = 0$
4) Попарно обращаем все неравенства в равенства и проверяем что происходит на "стыках" у целевой функции. То есть тут всего будет $C_n^2$ проверок
4) Получили несколько подозрительных точек. Каждую из них подставляем в исходную задачу - проверяем что все неравенства выполнены. Если какое-либо не выполнено, то выбрасываем точку из рассмотрения. Из всех оставшихся точек выбирем ту, у которой значение $F$ бОльшее
---
Верно ли я описал алгоритм дейтсвий?

[ShMaxG]

Ну почти. Подозрительные точки являются лишь стационарными точками функции Лагранжа, максимум (или минимум) ее достигаться на них не обязан. Поэтому после того, как перебрали все возможные варианты активного множества и получили набор допустимых подозрительных точек, нужно воспользоваться либо достаточными условиями максимума, либо вручную пошевелить точки внутри допустимого множества и посмотреть, как меняется целевая функция.

-- Пн мар 26, 2018 22:07:35 --

Кроме того, вы неявно предположили, что градиенты функций-ограничений линейно независимы в точке максимума. Если же это вдруг не так, то необходимо добавить еще один параметр Лагранжа -- тот, который перед целевой функцией в лагранжиане ставится.

[MestnyBomzh]

ShMaxG
Так я в пунктах 2-4 нашел все возможные потенциальные точки, которые могут быть макисмум (иными словами, максимум 100% находится среди них). А дальше я тупо проверяю каждую из них, где больше - та и максимум. Вы имели в виду, что я нашел не все подозрительные точки?

[ShMaxG]

MestnyBomzh
Вы нашли все стационарные точки функции Лагранжа. А вдруг есть стационарная точка, которая не является точкой локального максимума целевой функции при ограничениях, но в ней целевая функция достигает наибольшего значения среди других найденных точек? Например есть один локальный максимум, и есть точка перегиба где-то там выше. Но перегиб это не локальный максимум. Наверное при более жестких ограничениях на функции и рассматриваемое множество поиска это не возможно, но у вас очень общая ситуация :)

[MestnyBomzh]

ShMaxG в сообщении #1299912 писал(а):

Например есть один локальный максимум, и есть точка перегиба где-то там выше. Но перегиб это не локальный максимум

Понял идею.. Давайте тогда изменим пункт 2) на такой:
2) Ищем все стационарные точки функции $F$
---
Тогда мы всё учтем?

[ShMaxG]

Просто стационарные точки функции $F$ -- это все точки, в которых производная $F$ равна нулю. А вы наверное имеете ввиду стационарные точки задачи на условный экстремум? Ну, если всюду градиенты функций-ограничений линейно независимы, то действуя как вы описали, вы по определению найдете все стационарные точки задачи на условный экстремум, ибо по определению они и есть стационарные точки функции Лагранжа в случаях, когда не все множители Лагранжа (включая тот, что перед целевой функцией) равны нулю.

[MestnyBomzh]

Да. Этого будет достаточно?

[ShMaxG]

MestnyBomzh в сообщении #1299914 писал(а):

ShMaxG в сообщении #1299912 писал(а):

Например есть один локальный максимум, и есть точка перегиба где-то там выше. Но перегиб это не локальный максимум

Понял идею.. Давайте тогда изменим пункт 2) на такой:
2) Ищем все стационарные точки функции $F$
---
Тогда мы всё учтем?

А, вы предложили изменить пункт 2, а я вас не совсем понял. Ну так да, вернее будет говорить, но опять же. Перебирая все возможные активные множества, вы найдете лишь стационарные точки Лагранжа (они же, по определению, стационарные точки задачи с условиями-ограничениями). Если же у вас цель получить именно точки локального максимума, то от процедуры проверки их на каких-нибудь достаточных условиях или учета специфики задачи вы не уйдете.

-- Пн мар 26, 2018 22:43:11 --

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

[Markiyan Hirnyk]

Посмотрите условия Каруша-Куна-Таккера. Мы в 21-ом веке, а не в 18-ом.

[ShMaxG]

Markiyan Hirnyk
Да нет, у нас тут тоже условия Каруша-Куна-Таккера. Речь-то идет об алгоритме поиска минимума, а он (алгоритм) как ни крути сводится сначала к комбинаторной проблеме поиска стационарных точек Лагранжа для различных активных множеств, а потом -- к отбору среди эти точек уже локальных минимумов (максимумов).

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