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

[hollo]

Есть вопрос по минимизации функции $F(x_1,x_2,x_3,x_4)$ с ограничением $x_1+x_2+x_3+x_4=1$.

Насколько я понял, можно к начальным $[0,0,0,0]$ прибавлять антиградиент $-\nabla F(x_1,x_2,x_3,x_4)$, умноженный на шаг. И делать это, пока выполняется ограничение.

Далее "Нужно идти вдоль проекции градиента на плоскость ограничений, пока выполняется ограничение". Но не совсем понятно, что такое проекция градиента на плоскость ограничений в практическом плане. Как ее можно получить?

[ilghiz]

Если делать, как Вы написали с антиградиентом, то обычно это должно работать, чтобь формулы проще вывести надо в лагранжевом виде минимизацию записать:

$$\min_{x_1,x_2,x_3,x_4} F(x_1,x_2,x_3,x_4) + \lambda(x_1+x_2+x_3+x_4-1)$$

другое дело, чем вы будете искать минимум, BFGS, сопряженные направлениия, обычный градиентный спуск?

Если у Вас метод будет хорошо работать на градиентном спуске, то с лагранжевыми множителями тоже все работать будет, а если только BFGS хорошо будет сходиться?

Яб на Вашем месте попробовал взять

$$\min_{x_1,x_2,x_3,x_4} F(x_1,x_2,x_3,x_4) + \alpha(x_1+x_2+x_3+x_4-1)^2$$

фиксировать $\alpha$ в начале итераций чем меньше, тем лучше, а потом медленно ее увеличивать. Я знаю, что есть целая теория как это делать, но быстро найти не смог ссылки.

[Sicker]

hollo в сообщении #1441525 писал(а):

И делать это, пока выполняется ограничение.

Если вы сделаете градиентный шаг, оно уже не выполнится (почти всегда)

hollo в сообщении #1441525 писал(а):

Но не совсем понятно, что такое проекция градиента на плоскость ограничений в практическом плане. Как ее можно получить?

Вы должны из вашего вектора градиента $\frac{dF_i}{dx_i}$ вычесть вектор нормали к плоскости, заданной этим ограничением (в данном случае это просто $[1,1,1,1]$), умноженный на какой-то коэффициент $a$ такой, чтобы полученный вектор лежал в плоскости нашего ограничения

-- 26.02.2020, 05:04 --

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

Яб на Вашем месте попробовал взять

$$\min_{x_1,x_2,x_3,x_4} F(x_1,x_2,x_3,x_4) + \alpha(x_1+x_2+x_3+x_4-1)^2$$

фиксировать $\alpha$ в начале итераций чем меньше, тем лучше, а потом медленно ее увеличивать. Я знаю, что есть целая теория как это делать, но быстро найти не смог ссылки.

Так решение будет тем же самым, смысл в этом?

[hollo]

Sicker
Таким образом:
1) Сначала прибавляю антиградиент, умноженный на шаг.
2) Как только перестанет выполняться ограничение, вычитаю $a [1,1,1,1]$ (Можно взять $a$ фиксированное маленькое и повторять, пока не начнет выполняться ограничение?)

Это и будет локальным минимумом? Или нужно повторять процедуру и дальше?

[Sicker]

hollo в сообщении #1441586 писал(а):

вычитаю $a [1,1,1,1]$ (Можно взять $a$ фиксированное маленькое и повторять, пока не начнет выполняться ограничение?)

Вы должны выразить это $a$ через компоненты вектора градиента

-- 26.02.2020, 08:56 --

hollo в сообщении #1441586 писал(а):

Это и будет локальным минимумом? Или нужно повторять процедуру и дальше?

Конечно нет, дальше делаете шаги.

[hollo]

Sicker в сообщении #1441588 писал(а):

Вы должны выразить это $a$ через компоненты вектора градиента

А можно где-то почитать об этом поподробнее? Пока не понятно как это делать.

[Sicker]

hollo в сообщении #1441592 писал(а):

А можно где-то почитать об этом поподробнее? Пока не понятно как это делать.

У вас сумма компонент измененного вектора градиента должна быть ноль

[hollo]

Sicker в сообщении #1441593 писал(а):

У вас сумма компонент измененного вектора градиента должна быть ноль

Измененный вектор градиента? То есть $\nabla F(x_1,x_2,x_3,x_4)-a[1,1,1,1] $

[Sicker]

hollo
Да

-- 26.02.2020, 12:33 --

Ну а шаг делаете в антиградиенте

[ilghiz]

Sicker в сообщении #1441581 писал(а):

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

Яб на Вашем месте попробовал взять

$$\min_{x_1,x_2,x_3,x_4} F(x_1,x_2,x_3,x_4) + \alpha(x_1+x_2+x_3+x_4-1)^2$$

фиксировать $\alpha$ в начале итераций чем меньше, тем лучше, а потом медленно ее увеличивать. Я знаю, что есть целая теория как это делать, но быстро найти не смог ссылки.

Так решение будет тем же самым, смысл в этом?

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

[madschumacher]

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

фиксировать $\alpha$ в начале итераций чем меньше, тем лучше, а потом медленно ее увеличивать. Я знаю, что есть целая теория как это делать, но быстро найти не смог ссылки.

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

[feedinglight]

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

[svv]

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

[feedinglight]

Тогда метод штрафа, метод Лагранжа. Это выше уже обсуждали.

(Оффтоп)

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

[ilghiz]

madschumacher в сообщении #1441634 писал(а):

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

фиксировать $\alpha$ в начале итераций чем меньше, тем лучше, а потом медленно ее увеличивать. Я знаю, что есть целая теория как это делать, но быстро найти не смог ссылки.

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

Не, не про регуляризацию, а про сходимость.

ТС ничего про гессиан не сказал, значит его у него скорей всего нет. Чем будем минимизировать? Квазиньютоном? Если да, то я не сильно представляю как записать множители Лагранжа в квазиньютонах, ну скажем, в BFGSе. Поправьте меня, если я отстал от переднего края науки в этом направлении.

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

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

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