СНАУ с огранмчениями

[Andrey_Kireew]

Имеется система нелинейных уравнений с линейными ограничениями:

$$\left\{ \begin{array}{rcl} F_1(x_1,x_2,...x_n) &=&0 \\ F_2(x_1,x_2,...x_n) &=&0 \\ ............ \\ F_m(x_1,x_2,...x_n) &=&0 \\ x_1 &>&0 \\ x_2 &>&0 \\ .......... \\ x_n &>&0 \\ \end{array} \right.$$

Для её решения использую следующий алгоритм

$$\bold x[k+1]=\left\lvert \bold x[k]-\mu \bold J^+ \cdot \bold \delta \right\rvert,$$

где $\bold J $ - иатрица Якоби, $\bold \delta $ - вектор невязок, $\mu\in (0, 1] $ - шаг, подбираемый на каждой итерации так, чтобы норма невязок уменьшалась.

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

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

На сколько вообще корректен этот алгоритм?

[vpb]

Позвольте спросить, а откуда Вы этот алгоритм взяли ? Прочитали где-то, или сами придумали ? (Я не в курсе, как выглядит метод Ньютона для задач с ограничениями, если что). А застревание в локальных экстремумах --- насколько я понимаю, совершенно обычное явление. Тем более для задач с ограничениями. Если задача не одноэкстремальна, то, ясен пень, при каких-то начальных условиях итерации непременно сойдутся "не туда".

[feedinglight]

Ньютон наверно может показывать не то направление шага, он же не знает про ограничения..

[Andrey_Kireew]

Видимо, получается так:

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

[Евгений Машеров]

Andrey_Kireew в сообщении #1393820 писал(а):

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

По-моему, это худшее решение из возможных.
Может быть, Вам попробовать штрафные или барьерные функции? А ещё можно попробовать перепараметризовать, взяв $y_i=\ln x_i$

[feedinglight]

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

-- 20.05.2019, 15:18 --

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

[Andrey_Kireew]

Евгений Машеров в сообщении #1394157 писал(а):

По-моему, это худшее решение из возможных

я и сам думаю, что не лучшее, поэтому и создал тему

Евгений Машеров в сообщении #1394157 писал(а):

А ещё можно попробовать перепараметризовать, взяв $y_i=\ln x_i$

это заманчиво ... просто сделать замену $x_i=e^{y_i}$ и все ненужные решения исчезнут сами собой, алгоритм застревать нигде не будет и сразу сойдётся к допустимому решению. Правильно ли я понимаю?

[feedinglight]

На $y^2$ хотя бы нельзя заменить? А то с экспонентой слишком жёстко может получиться.

[Andrey_Kireew]

Спасибо Евгений Машеров
В общем, получается неплохо. Оказалось, что для этого нужны минимальные изменения в алгоритме. Теперь сходимость всегда квадратичная (шаг быстро устанавливается в 1 и остаётся таким до конца). Характер убывания невязки, во всех испытаниях, оказался примерно одинаковым. Как на рисунке:

-- 20.05.2019, 18:32 --

Да feedinglight, наверное можно и квадрат. Тогда вычисления упростятся.

[feedinglight]

Andrey_Kireew в сообщении #1394206 писал(а):

получается неплохо

Я думал что не получится, т.к. $y$ должен стремиться к минус бесконечности, когда решение на границе, но, видимо, в реальности до переполнения не добирается..

(Оффтоп)

Соблазнительно было бы просто на границах поискать, если обычный Ньютон нарушает ограничения..

[Andrey_Kireew]

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

Соблазнительно было бы просто на границах поискать, если обычный Ньютон нарушает ограничения..

такой алгоритм не найдёт решения на границах, как Вы правильно заметили, для этого $y$ должен уйти в бесконечность. Но мне кажется, в модифицированном функционале, точки выходящие за ОДЗ вообще ни на что не влияют. И это очень хорошо, т.к. алгоритм теперь не должен застревать в локальных минимумах, которые как раз и появляются на границе. Решениями исходной задачи они не являются, т.к. в ограничениях стоят строгие неравенства.
P.S.: но это всего лишь догадки, подкреплённые несколькими численными экспериментами. Возможно, всё не так хорошо, как мне кажется.

[vpb]

Andrey_Kireew в сообщении #1394175 писал(а):

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

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

-- 20.05.2019, 17:22 --

Andrey_Kireew в сообщении #1394224 писал(а):

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

Ну дык, если Вы делаете замену с экспонентой, у Вас точка будет переть на бесконечность (точнее, некоторые ее координаты будут уходить в минус бесконечность).

[Andrey_Kireew]

vpb в сообщении #1394225 писал(а):

От замены переменной это не зависит, как легко понять

Мне это понять совсем не легко, если Вам не составит большого труда, пожалуйста объясните почему? Ведь эти отрицательные решения после перепараметризации не могут быть достигнуты, т.к. для них не существует отображения $x\to y\in R$. Как они тогда могут проявляться?

[vpb]

Пример: переменная одна, $F(x)=1+1/(1+(x-1)^2)$, ищете точку, где $F(x)=3/2$, начальная точка $x=1/2$, замена $x=e^y$, ограничение $x>0$ .... и что получится ?

[feedinglight]

Andrey_Kireew в сообщении #1394224 писал(а):

Решениями исходной задачи они не являются, т.к. в ограничениях стоят строгие неравенства.

Можно прибавить $10^{-100}$ и будет уже не строгое, какая разница.. Если $n$ не большое, то вполне можно поискать на границах.

-- 20.05.2019, 19:42 --

А если минимум не на границе, то его найдёт обычный метод Ньютона.