Оптимизация функции нескольких переменных

[embi]

Добрый день!
Существует функция шести переменных следующего вида:

F(\theta)=C_1\cdot\exp(\theta)+\dots+C_N\cdot\exp(\theta),

\theta=\theta(x_1,\dots,x_6).

В каждом слагаемом \theta принимает разные значения, поэтому сгруппировать в общем виде не представляется возможным.

Задание: требуется найти безусловный минимум функции F.

Если использовать метод Ньютона

\theta_{t+1}=\theta_{t} - H^{-1}(F(\theta_{t})) \cdot \nabla (F(\theta_{t})),

где H(F(\theta_{t})) - гессиан функции F, а \nabla (F(\theta_{t})) - градиент функции F, то последовательность \theta_{1}, \theta_{2},\dots не приводит к стабильному убыванию значения функции F. Более того, в отдельных случаях переход с \theta_{t} на \theta_{t+1} приводит к росту значения функции F.

При этом, если минимизировать функцию F покоординатно с использованием одномерного метода Ньютона (ниже - пример для фукнции, зависящей только от первой переменной):

\theta_{t+1}^{(1)}=\theta_{t}^{(1)} - (\frac{\partial^2 F}{\partial x_1^2})^{-1} \cdot \frac{\partial F}{\partial x_1}

сначала для первой переменной, затем для второй и т.д., то результаты получаются принципиально лучше. Последовательность \theta_{1}, \theta_{2},\dots приводит к стабильному убыванию значения функции F.

Вопрос: чем объясняется такое различие в результатах оптимизации?

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

[Xaositect]

При реализации метода Ньютона, если новое значение больше предыдущего, то шаг уменьшают, сохраняя направление, т.е. $\theta_{t+1}=\theta_{t} - \alpha H^{-1}(F(\theta_{t})) \cdot \nabla (F(\theta_{t}))$, где $\alpha$ подбирается (обычно проверяют, уменьшается ли значение, и если нет, то умножают $\alpha$ на фиксированную константу меньше 1).
У Вас специфика функций, видимо, такая, что покоординатный метод работает лучше. Можно придумать примеры, когда покоординатный метод тоже будет промахиваться

[svv]

embi в сообщении #1158167 писал(а):

Существует функция шести переменных следующего вида:
$F(\theta)=C_1\cdot\exp(\theta)+\dots+C_N\cdot\exp(\theta),$
$\theta=\theta(x_1,\dots,x_6).$

В каждом слагаемом $\theta$ принимает разные значения

Я правильно понял, что у Вас $N$ различных функций $\theta_i$, каждая от шести переменных $x_k$ ?
$F(x_1,\ldots,x_6)=C_1 e^{\theta_1(x_1,\ldots,x_6)}+C_2e^{\theta_2(x_1,\ldots,x_6)}+\dots+C_Ne^{\theta_N(x_1,\ldots,x_6)}$

[embi]

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

Я правильно понял, что у Вас $N$ различных функций $\theta_i$, каждая от шести переменных $x_k$ ?

Да, функция $F$ состоит из $N$ слагаемых, каждое из которых - произведение константы (C_i) на экспоненту. В свою очередь, экспонента зависит от шести переменных. Набор шести переменных не меняется, но \theta_i может принимать разные значения для каждого из слагаемых.

Xaositect в сообщении #1158169 писал(а):

При реализации метода Ньютона, если новое значение больше предыдущего, то шаг уменьшают, сохраняя направление, т.е. $\theta_{t+1}=\theta_{t} - \alpha H^{-1}(F(\theta_{t})) \cdot \nabla (F(\theta_{t}))$, где $\alpha$ подбирается (обычно проверяют, уменьшается ли значение, и если нет, то умножают $\alpha$ на фиксированную константу меньше 1).

Действительно, на всех итерациях \alpha=1, т.е. значение не менялось. Получается, необходимо ввести промежуточную стадию, скажем, $\theta'_{t+1}, на которой будет проверятся, новое значение больше или меньше предыдущего. Если больше, то корректируем шаг \alpha до тех пор, пока новое значение не станет меньше предыдущего. Если меньше, то $\theta_{t+1}=$\theta'_{t+1}.

Вы можете подтвердить, что такой алгоритм корректен?
Есть ли практические рекомендации по подбору \alpha?

[svv]

embi в сообщении #1158492 писал(а):

Набор шести переменных не меняется, но $\theta_i$ может принимать разные значения для каждого из слагаемых.

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

[Xaositect]

embi в сообщении #1158492 писал(а):

Действительно, на всех итерациях \alpha=1, т.е. значение не менялось. Получается, необходимо ввести промежуточную стадию, скажем, $\theta'_{t+1}, на которой будет проверятся, новое значение больше или меньше предыдущего. Если больше, то корректируем шаг \alpha до тех пор, пока новое значение не станет меньше предыдущего. Если меньше, то $\theta_{t+1}=$\theta'_{t+1}.

Вы можете подтвердить, что такой алгоритм корректен?
Есть ли практические рекомендации по подбору \alpha?

Извините, я немного соврал, давно занимался оптимизацией. Такой подход работает, но в некоторых случаях сходимость будет медленной.
Нужны условия чуть сложнее. Посмотрите https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf, параграф 9.2, раздел "backtracking line search".

[embi]

Спасибо за ссылку. Интересный вариант. Постараюсь реализовать. Еще раз спасибо!

[Markiyan Hirnyk]

Зачем изобретать велосипед? Современные математические пакеты (Maple и Mathematica) имеют мощные средства для нахождения глобальных экстремумов. Пожалуйста, представьте на форуме формулу целевой функции (желательно в записи Maple/Mathematica) и ограничения на абсолютные величины переменных $x_1,\dots,x_6$ и я попытаюсь решить Вашу задачу.