МНК - оптимизация с ограничениями на параметры

[Andrey_Kireew]

Уважаемые участники форума помогите пожалуйста разобраться
имеется нелинейная система
$\left\{ \begin{array}{rcl} &f_1(x_1,x_2,...x_n)=a_1& \\ &f_2(x_1,x_2,...x_n)=a_2& \\ &..................................& \\ &f_m(x_1,x_2,...x_n)=a_m& \\ \end{array} \right. $
имеется критерий оптимизации
$F[f_1(\cdot),f_2(\cdot),...f_m]\to max$

для этого критерия удалось вычислить градиент и матрицу Гёссе,
так, что можно использовать для оптимизации метод Ньютона (правда область сходимости оказалась очень узкой, но это решаемо),
классический алгоритм имеет вид
$X(k+1)=X(k)-H(k)\nabla(k)$,
где $k$ - номер итерации, $H$ - матрица Гёссе, $\nabla$ - вектор градиента, $X=(x_1,x_2,...x_n)^T$ - вектор оптимизируемых параметров.

В принципе алгоритм работает, но проблема в том, что все параметры $x_i$ по своей физической природе положительны, а в ходе оптимизации часть из них "вылетает" в область отрицательных чисел, что естественно не устраивает.
Единственное, что мне пока пришло в голову, то это наложить ограничения на параметры путём L2 регуляризации решения.
Опробовал несколько вариантов:
1) градиент модифицируется следующим образом: $\nabla=\nabla_0-q(X-h)$,
где $\nabla_0$ - градиент без регуляризации, $ h $ - априорное значение вектора $X$,
2) градиент модифицируется следующим образом: $\nabla=\nabla_0-q(X-max(X))$,
3) градиент модифицируется следующим образом: $\nabla=\nabla_0-q(X-\bar{X})$.

Матрица Гёссе во всех случаях модифицируется следующим образом: $ H=H_0-qE$, где $E$ - единичная матрица.

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

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

[dsge]

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

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

Условная оптимизация, множители Лагранжа, Кун-Таккер.

-- 27.02.2016, 12:34 --

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

имеется нелинейная система
$$\left\{ \begin{array}{rcl} &f_1(x_1,x_2,...x_n)=a_1& \\ &f_2(x_1,x_2,...x_n)=a_2& \\ &..................................& \\ &f_m(x_1,x_2,...x_n)=a_m& \\ \end{array} \right. $ $имеется критерий оптимизации
$F[f_1(\cdot),f_2(\cdot),...f_m]\to $

Вы уверены, что равенства точные, если это МНК?

[Andrey_Kireew]

dsge в сообщении #1102517 писал(а):

Вы уверены, что равенства точные, если это МНК?

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

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

Штрафные или барьерные функции?

[dsge]

Можно, также сделать замену переменных в параметрах, например, так:
$\phi =\exp( -\phi_1)$,
где $\phi $ - старые параметры, $\phi_1 $ - новые параметры.

[Andrey_Kireew]

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

Штрафные или барьерные функции?

А какие лучше в этом случае использовать?
сейчас у меня штраф $q(X-h)^T(X-h)$

-- 27.02.2016, 15:20 --

dsge в сообщении #1102527 писал(а):

Можно, также сделать замену переменных в параметрах, например, так:
$\phi =\exp( -\phi_1)$,
где $\phi $ - старые параметры, $\phi_1 $ - новые параметры.

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

[dsge]

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

Дело в том, что в функционале и так уже есть экспоненты,

Ну, не обязательно брать именно экспоненту, можно любую "хорошую" положительно-определенную функцию, например: $\phi =\frac{\phi_1^2}{1+\phi_1^2}$.

[Andrey_Kireew]

dsge в сообщении #1102533 писал(а):

Ну, не обязательно брать именно экспоненту, можно любую положительно-определенную функцию, например: $\phi =\frac{\phi_1^2}{1+\phi_1^2}$,

В принципе это идея, можно даже $x^2$ попробовать, чтобы проще алгоритм выводить, а потом найденные $x$ снова возвести в квадрат.
Спасибо! сейчас попробую это проработать

-- 27.02.2016, 15:56 --

Цитата:

Условная оптимизация, множители Лагранжа, Кун-Таккер.

Боюсь что с множителя Лагранжа и методом Куна-Такера придётся отказаться от метода Ньютона, чего мне бы очень не хотелось. Хотя я в этом не уверен, так как с этими методами незнаком.

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

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

[DeBill]

Andrey_Kireew
А не могли бы Вы явно указать, что у Вас за $F$ и $f$? А то так, в общем виде - мало что сказать можно.
А вот если бы задача возникала именно из ММП, да еще и распределения - нормальны, то, может, что-нить хорошее и проглянет...

[Andrey_Kireew]

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

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

Вообще наверно так и есть, квадрат не пойдёт, получается самое простое - это и есть экспонента.

[dsge]

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

квадрат не пойдёт,

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

[Andrey_Kireew]

dsge в сообщении #1103239 писал(а):

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

Звучит весьма убедительно, тогда попробую квадрат, с ним меньше всего переделывать придётся.
Спасибо!

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

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

[Andrey_Kireew]

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