Методы оптимизации.

[Anton_74]

Господа, подскажите, может кто сталкивался.

Имеется функция $f(t) = \sqrt{( (ex - px - t*pvx)^2 + (ey - py - t*pvy)^2 )} $. При определенных значениях параметров ex, ey, px, py производная функции становится разрывной. Необходимо находить минимум данной функции в общем случае, т.е. при различных значениях параметров.
Какой метод оптимизации лучше выбрать. Мне кажется что лучше использовать методы, которые не используют вычисление производной (метод Ньютона, наискорейшего спуска). Может подскажите литературный источник, где такие проблемы решаются?

[venco]

А что обозначают $pvx$ и $pvy$?
В любом случае минимум функции достигается при минимуме квадратичного полинома от $t$ под корнем. Вам надо, чтобы этот минимум был не равен нулю (отрицательным он быть не может). А для этого надо, чтобы нули первого квадрата и второго не совпадали.

[мат-ламер]

А Вы минимизируйте не исходную функцию, а её квадрат.

[Anton_74]

venco в сообщении #352835 писал(а):

А что обозначают $pvx$ и $pvy$?
В любом случае минимум функции достигается при минимуме квадратичного полинома от $t$ под корнем. Вам надо, чтобы этот минимум был не равен нулю (отрицательным он быть не может). А для этого надо, чтобы нули первого квадрата и второго не совпадали.

$pvx$ и $pvy$ будут какие то числа, т.е. не зависят от $t$. Да я это и имел в виду при совпадении выражений в скобках, функция становится негладкой. И это очень не удобно в общем случае.

-- Чт сен 16, 2010 05:01:45 --

мат-ламер в сообщении #352860 писал(а):

А Вы минимизируйте не исходную функцию, а её квадрат.

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

[alekcey]

Anton_74 в сообщении #352938 писал(а):

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

Посмотрите на сайте экспоненты http://forum.exponenta.ru/viewtopic.php?t=10004. Должно подойти…

[Алексей К.]

Anton_74 в сообщении #352826 писал(а):

Господа, подскажите, может кто сталкивался.

Имеется функция $f(t) = \sqrt{( (ex - px - t*pvx)^2 + (ey - py - t*pvy)^2 )} $. При определенных значениях параметров ex, ey, px, py производная функции становится разрывной.

Anton_74,

вероятно, Вы молча перенесли в математическую тему програмистскую фичу называть переменные именами, а не единственным символом. Ваше $vx$ есть, видимо, $v_x$; об этом следует явно заявить, дабы не заставлять здешнего читателя чесать репу.
Но главное --- "При определенных значениях параметров ex, px..." Нет. Ваша функция зависит только от разности $ex-px$. Полагаю, Вам следовало написать что-то вроде $f(t) = \sqrt{ (A+Bt)^2 + (C+Dt)^2 } $ (после чего сразу просится $\sqrt{ at^2 + bt+c } $). Остальное пудрит людям мозги и мешает правильному пониманию.

[Anton_74]

-- Чт сен 16, 2010 18:39:31 --

Алексей К. в сообщении #352994 писал(а):

Anton_74 в сообщении #352826 писал(а):

Господа, подскажите, может кто сталкивался.

Имеется функция $f(t) = \sqrt{( (ex - px - t*pvx)^2 + (ey - py - t*pvy)^2 )} $. При определенных значениях параметров ex, ey, px, py производная функции становится разрывной.

Anton_74,

вероятно, Вы молча перенесли в математическую тему програмистскую фичу называть переменные именами, а не единственным символом. Ваше $vx$ есть, видимо, $v_x$; об этом следует явно заявить, дабы не заставлять здешнего читателя чесать репу.
Но главное --- "При определенных значениях параметров ex, px..." Нет. Ваша функция зависит только от разности $ex-px$. Полагаю, Вам следовало написать что-то вроде $f(t) = \sqrt{ (A+Bt)^2 + (C+Dt)^2 } $ (после чего сразу просится $\sqrt{ at^2 + bt+c } $). Остальное пудрит людям мозги и мешает правильному пониманию.

Я как то даже и не подумал об этом. Тогда я сейчас попытаюсь изложить математически грамотно мою задачу полностью. Необходимо решить следующую задачу:

$ min \left( \left|| z_1(t) + z_2(t) t - z_3(t) \right|| - \mu t - f(t, \varepsilon) = 0 \right) $,
где минимум ищется по переменным $0 \leqslant t \leqslant T(t, \mu), \varepsilon' \leqslant \varepsilon $, $ T(t, \mu) = \frac{\varepsilon}{b}exp(\frac{\mu}{b}), \varepsilon', \mu, b $ - некоторые положительные числа,
$ f(t, \varepsilon) = \left\{ \begin{array}{l} \varepsilon - b t, 0 \leqslant t \leqslant \frac{\varepsilon}{b},\\ -ln(\frac{b}{\varepsilon}t) b t, \frac{\varepsilon}{b} \leqslant t. \end{array} \right. $

Функция $f(t, \varepsilon)$ вогнутая, производная которой не возрастает, гладкая, но вторая производная имеет разрыв.

Для решения метод Ньютона не подойдет, потому что вторая производная функции $f(t, \varepsilon)$ имеет разрыв, и что касается $\left|| z_1(t) + z_2(t) t - z_3(t) \right||$, то в общем случае она может быть не гладкой, поэтому метод градиентного спуска тоже не поможет. Может кто нибудь знает методы, которые используют только значения функции для нахождения ее минимума.

-- Чт сен 16, 2010 18:41:05 --

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

Anton_74 в сообщении #352938 писал(а):

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

Посмотрите на сайте экспоненты http://forum.exponenta.ru/viewtopic.php?t=10004. Должно подойти…

Решение нужно реализовать численно на компе, без сторонних пакетов.

[мат-ламер]

Anton_74. Вашу постановку я не понял, поскольку непонятно, что такое минимизация уравнения. От негладкости минимизируемой функции часто избавляются путём введения дополнительных переменных. Допустим корень (или норму) какого-то выражения взять за дополнительное переменное. К задаче оптимизации добавляем ограничение. Это определение этой переменной, возведённое в квадрат. Таким образом от негладкой задачи без ограничений переходим к гладкой задаче, но с ограничениями. Можно использовать непосредственно методы негладкой оптимизации. Можно посмотреть книгу Поляка Б.Т. "Введение в оптимизацию". Есть также книга Н. Шора. Название не помню. Если быстродействие Вас не волнует, можно использовать метод субградиента. Если надо быстродействие, то используйте метод Шора. Но его программировать труднее.

[Anton_74]

мат-ламер в сообщении #353155 писал(а):

Anton_74. Вашу постановку я не понял, поскольку непонятно, что такое минимизация уравнения. От негладкости минимизируемой функции часто избавляются путём введения дополнительных переменных. Допустим корень (или норму) какого-то выражения взять за дополнительное переменное. К задаче оптимизации добавляем ограничение. Это определение этой переменной, возведённое в квадрат. Таким образом от негладкой задачи без ограничений переходим к гладкой задаче, но с ограничениями. Можно использовать непосредственно методы негладкой оптимизации. Можно посмотреть книгу Поляка Б.Т. "Введение в оптимизацию". Есть также книга Н. Шора. Название не помню. Если быстродействие Вас не волнует, можно использовать метод субградиента. Если надо быстродействие, то используйте метод Шора. Но его программировать труднее.

Дело в то что нужно найти минимальные значения $\varepsilon, t$ при которых функция $\left|| z_1(t) + z_2(t) t - z_3(t) \right|| - \mu t - f(t, \varepsilon) = 0$. Дело в том при определенных условиях эта функция больше нуля. При увеличении параметра $\varepsilon$ функция при каком то значении $t$ станет равной нулю. Поскольку функция выпуклая, то это условие будет выполняться для некоторой точки экстремума $t^*$ функции $\left|| z_1(t) + z_2(t) t - z_3(t) \right|| - \mu t - f(t, \varepsilon^*) $, где $\varepsilon^*$ значение переменной $\varepsilon$ при котором минимум функции равен 0.

Я не могу найти в литературе ничего похожего. И придумал пока только способ похожий на метод перебора, потому что верхняя граница для переменной $\varepsilon$ неизвестна. Начинаю постепенно увеличивать параметр $\varepsilon$ и находить значение функции в точке экстремума. И делать это пока значение функции в точке экстремума не станет равной нулю с определенной погрешностью. Т.е. можно наверное выразить так F(t) = $\left|| z_1(t) + z_2(t) t - z_3(t) \right|| - \mu t - f(t, \varepsilon) $, $t^*$ - точка экстремума функции $F(t)$. При пошаговом увлечении параметра $\varepsilon$ найти такое $t^*$ чтобы $\left| F(t^*) \right| < \tau$, $\tau$ - заданная погрешность. Поэтому я сейчас ищу хороший метод для отыскания минимума функции, но желательно не использующий производных.

[мат-ламер]

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

[Anton_74]

мат-ламер в сообщении #353193 писал(а):

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

Шор, Н. З. "Методы минимизации недифференцируемых функций и их приложения"

Только в инете нет, может у тебя есть в электронном виде?

[мат-ламер]

Нет у меня такой книги.