Минимизация квадратичной функции

[VivaKalman]

Доброго времени суток.
Имеется задача для безусловной минимизации квадратичной функции для 16 переменных. Предстоит реализовать алгоритм минимизации методом Флетчера-Ривса. Точнее, алгоритм уже реализован и считает правильно, одна проблема: в алгоритме на определенном шаге необходимо выполнить поиск локального минимума функции вида φ(tn) = f( xⁿ — tn * pⁿ) (здесь f - сама функция xⁿ - вектор прошлой итерации, pⁿ - градиентное направление (вектор), tn - параметр, который предстоит найти (при нем функция φ(tn)- минимальна)) у меня этот параметр находится методом дихотомии, однако, этот метод является приближенным и от меня требуют получить оптимальное t точно. Так как функция квадратична, то понятно, что этот параметр можно получить из следующего выражения: f ' ( xⁿ — tn * pⁿ) = 0, а как выразить его отсюда не могу понять... Так выглядит общий вид квадратичной функции f(x) = (1/2)xT Ax-bT x+c, если подставлять и решать систему, то получим вектор tn, а нужен параметр, к тому же это довольно муторно, мне намекнули, что он находится даже проще, чем методом дихотомии, чуть ли не в одно действие...
Часть целевой функции (сумма по m от 1 до 8, по этому 16 переменных (8 X и 8 Y), все остальное - параметры)
(xm sin((m − 1)k) + ym cos((m − 1)k)) − (k − t1) + (k − t2))^2
Подскажите формулу для поиска оптимального t, если таковая существует...
Спасибо.

[мат-ламер]

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

[alekcey]

Не знаю, кому и зачем вообще нужны градиентные методы, а в данном случае, неужели не хватает обычного метода Гаусса? Нашёл производные, решил линейную систему…

[AKM]

VivaKalman,
Здесь рассказано, как набирать формулы.

В частности, Ваше

VivaKalman в сообщении #315229 писал(а):

(xm sin((m − 1)k) + ym cos((m − 1)k)) − (k − t1) + (k − t2))^2

многим видится как
xm sin((m − 1)?k) + ym cos((m − 1)?k)) − (?k − t1) + (?k − t2))^2.

И этот деманд --- из Правил форума.

[VivaKalman]

Пардон,эт не очень важно, по этому не стал мучаться:
$ \left( x\sin \left( 2\,{\frac { \left( m-1 \right) \pi \, \left( k-1 \right) }{N-1}} \right) +y\cos \left( 2\,{\frac { \left( m-1 \right) \pi \, \left( k-1 \right) }{N-1}} \right) \right) ^{2} $
(почти тож самое)

Цитата:

Не знаю, кому и зачем вообще нужны градиентные методы, а в данном случае, неужели не хватает обычного метода Гаусса? Нашёл производные, решил линейную систему…

Ну, это принципиально важно, у меня в задании оговорено.

Цитата:

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

Я ищу, правда пока что ничего пока поддающегося алгоритмизации не нашел. Может, кто делал что-то подобное?

[мат-ламер]

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

[VivaKalman]

Градиент этой функции (16 переменных):
$\left[ \begin {array}{c} 0\\\noalign{\medskip} 0.0000000020951\,x_{{ 10}}+ 1023.0\,x_{{2}}- 312.56\\\noalign{\medskip}- 0.0000000047373\,x_ {{11}}- 156.36+ 1023.0\,x_{{3}}\\\noalign{\medskip}- 0.0000000066931\, x_{{12}}+ 138.35+ 1023.0\,x_{{4}}\\\noalign{\medskip}- 0.00000000023315\,x_{{13}}+ 129.54+ 1023.0\,x_{{5}} \\\noalign{\medskip} 0.0000000076376\,x_{{14}}- 6.6975+ 1023.0\,x_{{6} }\\\noalign{\medskip} 0.00000000083815\,x_{{15}}+ 0.98226+ 1023.0\,x_{ {7}}\\\noalign{\medskip}- 0.0000000042667\,x_{{16}}+ 21.972+ 1023.0\,x _{{8}}\\\noalign{\medskip}- 342.0+ 2048.0\,x_{{9}}\\\noalign{\medskip} 0.0000000020951\,x_{{2}}- 94.387+ 1025.0\,x_{{10}} \\\noalign{\medskip}- 0.0000000047373\,x_{{3}}+ 235.29+ 1025.0\,x_{{11 }}\\\noalign{\medskip}- 0.0000000066931\,x_{{4}}+ 1025.0\,x_{{12}}+ 167.29\\\noalign{\medskip}- 0.00000000023315\,x_{{5}}+ 1025.0\,x_{{13 }}- 54.415\\\noalign{\medskip} 0.0000000076376\,x_{{6}}- 63.911+ 1025.0\,x_{{14}}\\\noalign{\medskip} 0.00000000083815\,x_{{7}}+ 0.18775+ 1025.0\,x_{{15}}\\\noalign{\medskip}- 0.0000000042667\,x_{{8 }}+ 1025.0\,x_{{16}}- 41.984\end {array} \right] $
Правда, программно я могу посчитать его только численно(в подстановке)...

[VivaKalman]

Задача состоит не в том, что бы минимизировать квадратичную функцию (алгоритм у меня есть и работает), а решение подзадачи min->φ(tn)= argmin ( f( xⁿ — tn * pⁿ) ) , нахождение оптимального параметра t отсюда:
f ' ( xⁿ — t * pⁿ) = 0
Без вариантов, потому, как условие задачи сформулировано точно.

[мат-ламер]

Цитата:

то для начала выпишите тут её градиент. (Только в обобщённом виде - через матрицы. Подробности ... - не нужно) .

Я наверное неправильно выразился. Пусть стоит задача минимизации квадратичной функции $(Ax,x)/2+(b,x)$ на отрезке $x^n+tp^n$. Градиент квадратичной функции на всём пространсве - $Ax+b$, а на отрезке - $A(x^n+tp^n)+b$.

Цитата:

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

Условие перпендикулярности даёт уравнение $(A(x^n+tp^n),p^n)=0$. Теперь решаем это уравнение относительно $t$. Продолжить сможете?

[alekcey]

VivaKalman в сообщении #315731 писал(а):

Задача состоит не в том, что бы минимизировать квадратичную функцию (алгоритм у меня есть и работает), а решение подзадачи min->φ(tn)= argmin ( f( xⁿ — tn * pⁿ) ) , нахождение оптимального параметра t отсюда:
f ' ( xⁿ — t * pⁿ) = 0
Без вариантов, потому, как условие задачи сформулировано точно.

Так минимум на отрезке, это условная оптимизация или как в первом сообщении?...

[VivaKalman]

alekcey в сообщении #316085 писал(а):

VivaKalman в сообщении #315731 писал(а):

Задача состоит не в том, что бы минимизировать квадратичную функцию (алгоритм у меня есть и работает), а решение подзадачи min->φ(tn)= argmin ( f( xⁿ — tn * pⁿ) ) , нахождение оптимального параметра t отсюда:
f ' ( xⁿ — t * pⁿ) = 0
Без вариантов, потому, как условие задачи сформулировано точно.

Так минимум на отрезке, это условная оптимизация или как в первом сообщении?...

Ну это кусок алгоритма флетчера ривза (9 шаг):
http://webcache.googleusercontent.com/search?q=cache:JcYAW9nyAE4J:www.matmetod.ru/fletcher_rivs_algorithm+%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC+%D1%84%D0%BB%D0%B5%D1%82%D1%87%D0%B5%D1%80%D0%B0&cd=6&hl=ru&ct=clnk&gl=ru&client=firefox
Он подразумевает решение этой задачи, правда вариантов ее решения довольно много...

Цитата:

Цитата:
то для начала выпишите тут её градиент. (Только в обобщённом виде - через матрицы. Подробности ... - не нужно) .

Я наверное неправильно выразился. Пусть стоит задача минимизации квадратичной функции $(Ax,x)/2+(b,x)$ на отрезке $x^n+tp^n$. Градиент квадратичной функции на всём пространсве - $Ax+b$, а на отрезке - $A(x^n+tp^n)+b$.
Цитата:
Можно подсчитать градиент для точек, расположенных на прямой поиска, и посмотреть, где этот градиент перпендикулярен направлению поиска.
Условие перпендикулярности даёт уравнение $(A(x^n+tp^n),p^n)=0$. Теперь решаем это уравнение относительно $t$. Продолжить сможете?

Ну кажется понял о чем речь, вот нашел в википедии: должно получиться примерно так $a_{{k}}={\frac {r_{{k}}\cdot r_{{{\it k}}}}{Ap_{{k}}\cdot p_{{k}}}}$ тут a - искомое t, а $r_{{k}}=b-{\it Ax}_{{k}}=-{\frac {d}{dx}}f \left( x \right) $.
Я сейчас решил эту задачу через матрицу Гессе по вот этой статейке: http://www.basegroup.ru/library/analysis/neural/conjugate/, думаю это то, что от меня требовали, отпишусь если возникнут какие-нибудь вопросы.
Всем спасибо за помощь.