Градиентный метод с линейным ограничением

[madschumacher]

ilghiz в сообщении #1441734 писал(а):

С радостью услышу более правильную теорию,

Ох, по мне это извращение для учебной задачки.

ilghiz в сообщении #1441734 писал(а):

ТС ничего про гессиан не сказал, значит его у него скорей всего нет. Чем будем минимизировать? Квазиньютоном?

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

[B@R5uk]

Я вот не пойму: ограничение линейное, в чём проблема выразить одну из координат и решать задачу с размерностью на единицу меньше?

[madschumacher]

B@R5uk в сообщении #1441781 писал(а):

Я вот не пойму: ограничение линейное, в чём проблема выразить одну из координат и решать задачу с размерностью на единицу меньше?

feedinglight в сообщении #1441638 писал(а):

а нельзя в данном случае из ограничения выразить одну из переменных и подставить в минимизируемую функцию?

Уже предлагали, и вроде предположил, что в задаче подразумевалось нечто иное.

[B@R5uk]

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

-- 27.02.2020, 10:30 --

svv в сообщении #1441651 писал(а):

Тут выразить можно, а что делать, если ни одна переменная явно не выражается?

В случае поверхностей второго порядка всегда можно ввести параметризацию, например. Что опять же снизит размерность на единицу.

Я не утверждаю, что снижение размерности — это универсальный рецепт на все времена. Просто если можно упростить себе жизнь, то нужно упростить себе жизнь.

[svv]

feedinglight в сообщении #1441660 писал(а):

Всегда раздражает "методичность" задания, когда нужно искать скрытый смысл, чтобы "правильно" его решить. Придумывать постановку задачи, для решения которой самый оптимальный путь - это путь, который методически подразумевается, естественно, некоторые ленятся.

B@R5uk в сообщении #1441784 писал(а):

Просто если можно упростить себе жизнь, то нужно упростить себе жизнь.

Я, наоборот, думаю, что более универсальные и «высокоуровневые» методы удобно изучать на таких задачах, в которых с проблемой в принципе можно справиться и кустарным способом (причём в конкретном случае это может быть и проще). Для сравнения, для лучшего понимания, для проверки.

[B@R5uk]

svv в сообщении #1441785 писал(а):

для проверки

Разве только это.

svv в сообщении #1441785 писал(а):

в которых с проблемой в принципе можно справиться и кустарным способом

Что же здесь кустарно?! В самом общем случае, если есть N-мерная функция, подлежащая оптимизации, и есть M линейных ограничений на её координаты (совместные и линейно независимые, разумеется), то можно построить преобразование $(N-M)$-мерного пространства в N-мерное и решать задачу с меньшей размерностью. Это всегда предпочтительней наращиванию размерности, как в методе множителей Лагранжа. Плюс, если напрячься, то можно поставить дополнительное условие (и удовлетворить ему) на линейное преобразование пространства свободных координат в пространство координат функции и ограничений. А именно: чтобы линейное преобразование было максимально хорошо обусловлено.

Самому мне никогда не приходилось решать задачу построения такого преобразования, но поскольку это простая тема линейной алгебры, наверняка вопрос уже давно кем-то решён. Просто я не в курсе на что сослаться.

[B@R5uk]

ilghiz в сообщении #1441734 писал(а):

С радостью услышу более правильную теорию, хорошо проверенную на практике, как такое можно решать.

Один из лучших алгоритмов для оптимизации "овражистой" функции — метод Нелдера-Мида. Кроме всего прочего, он ещё и не требует знания производных, так как работает только со значениями целевой функции. К сожалению, чтобы воспользоваться им, задачу с ограничениями придётся "допилить". Лучший способ — это ввести параметризацию, которая сразу удовлетворит граничным условиям и за одно понизит размерность задачи. Но это работает не всегда.

-- 27.02.2020, 17:21 --

feedinglight в сообщении #1441660 писал(а):

метод Лагранжа

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

А в лоб найти численно экстремум у функции Лагранжа не получится. Просто потому, что его нет: по множителям Лагранжа функция не ограничена в обе стороны (они входят в виде линейных множителей, на то и множители), соответственно не имеет экстремума. Можно, конечно, взять эти множители в виде квадратов, но тогда надо угадать со знаком каждого множителя (вернее, даже перебрать все $2^m$ вариантов), так как множители Лагранжа в сущности — это коэффициенты линейной комбинации, и могут быть любых знаков. Если потребовать знакоопределённость, то решения будут теряться.

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

[feedinglight]

svv в сообщении #1441785 писал(а):

более универсальные и «высокоуровневые» методы удобно изучать на таких задачах

svv в сообщении #1441785 писал(а):

Для сравнения, для лучшего понимания, для проверки

Ну да, если это явно сказано в условии(какие методы можно применять)

B@R5uk в сообщении #1441822 писал(а):

как его использовать на практике для численных вычислений

Метод множителей Лагранжа вполне применяется, например, в контактных задачах механики [Коробейников С.Н. Нелинейное деформирование твердых тел, 2000, стр. 153] но я его не реализовывал

(Оффтоп)

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

Хотя, это немного другая задача.

Открыл википедию, вроде есть готовый алгоритм для случая из сабжа.

[dmd]

B@R5uk в сообщении #1441781 писал(а):

Я вот не пойму: ограничение линейное, в чём проблема выразить одну из координат и решать задачу с размерностью на единицу меньше?

В мат.программировании так не бывает, это же не алгебра.
Если из ограничения $x_1+x_2+x_3+x_4=1$ Вы выразили, допустим, $x_4 \to 1-x_1-x_2-x_3$ и подставили в $F(x_1,x_2,x_3,x_4)$, то в итоге получили новую задачу мат.программирования для оптимизации некой новой целевой функции $G(x_1,x_2,x_3)$, связанную с первоначальной $F(x_1,x_2,x_3,x_4)$ тем же самым первоначальным ограничением $x_1+x_2+x_3+x_4=1$. Т.е. вычислительно ничего не изменилось, оптимизировав $G(x_1,x_2,x_3)$ и получив некие якобы оптимальные $(x_1,x_2,x_3)$, нужно дополнительным шагом проверить ограничение $x_1+x_2+x_3+x_4=1$, которое может и не выполниться при формально оптимальной цели $G(x_1,x_2,x_3)$. Ведь значение $x_4 = 1-x_1-x_2-x_3$ может оказаться за пределами его допустимого диапазона.

[B@R5uk]

dmd в сообщении #1442713 писал(а):

...нужно дополнительным шагом проверить ограничение $x_1+x_2+x_3+x_4=1$, которое может и не выполниться...

Вот это вы чушь написали.

dmd в сообщении #1442713 писал(а):

Ведь значение $x_4 = 1-x_1-x_2-x_3$ может оказаться за пределами его допустимого диапазона.

Сдаётся мне вы пытаетесь решать совсем другую задачу.