Субградиентные методы оптимизации

[andreso]

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

[мат-ламер]

Предлагаю попробовать вычислить субдифференциал от нормы в нуле.

[andreso]

Вы имеете ввиду функцию
$f(x)=|x|$? Это мне известно: [-1;1]. Мне интересен конкретный алгоритм оптимизации с примером.

[andreso]

И еще добавлю. Зачем заморачиваться с какими-то субградиентами на практике, если функция недифференцируема только в местах разрывов. Я здесь имею ввиду ломанные выпуклые функции.

[мат-ламер]

andreso в сообщении #1079861 писал(а):

Мне непонятно как на практике вычислять его,

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

-- Пн дек 07, 2015 20:52:05 --

andreso в сообщении #1080263 писал(а):

Зачем заморачиваться с какими-то субградиентами на практике, если функция недифференцируема только в местах разрывов

А вот тут любопытно будет рассмотреть, как ведёт себя допустим метод наискорейшего спуска для такой функции.

[andreso]

Вот программа на языке MatLab для $|X|$.

function [] = optimization()
K=0.1;
eps=1e-8;
xkm1=2;
xk=1;

k=0;
while (abs(xk-xkm1)>eps)
xkm1=xk;
xk=xk-K*dfdx(xk);
k=k+1
K=K/2;
end;
xk
end

%Градиент
function res = dfdx(x)
if (x>0)
res=1;
end;

if (x<0)
res=-1;
end;

if (x==0)
res=-0.01;
end;
end

%Функция
function res = f(x)
res=abs(x);
end

Собственно в точке 0 имеется разрыв функции. Метод наискорейшего спуска не сходится. субдифференциал в точке 0 [-1;1]. Из этого диапазона выбираю произвольный (напр. -0.01),
при этом метод сходится к точке 0,8, что не верно. Параметр K пока по мере итераций уменьшаю в два раза.

[мат-ламер]

andreso
То, что вы запрограммировали, никакого отношения не имеет ни к методу наискорейшего спуска, ни к субградиентному алгоритму. Ваш метод может продвинуться от начальной точки на расстояние не более, чем $2K$ (если минимизируется функция модуля) и сходиться не будет.

[andreso]

Тогда так.

function [] = optimization()

eps=1e-8;

xkm1=3;
xk=2;

fmin=0; %значение функции в точке минимума
gamma=0.5;

k=0;
while (abs(xk-xkm1)>eps)
xkm1=xk;
%Фейеровский шаг
hk=gamma*(f(xk)-fmin)/abs(dfdx(xk)); %abs(f(xk)) - норма dfdx
xk=xk-hk*(dfdx(xk)/abs(dfdx(xk)));
k=k+1
end;
xk
end

%Градиент
function res = dfdx(x)
if (x>0)
res=1;
end;

if (x<0)
res=-1;
end;

if (x==0)
res=-0.5;
end;
end

%Функция
function res = f(x)
res=abs(x);
end

В этом случае процесс сходится куда нужно, но теперь более сложная задача, которая у меня изначально стояла.
У меня есть функция нескольких переменных (для начала двух), вид которой заранее неизвестен, равно как неизвестно где происходит излом поверхности, также неизвестно fmin.
Как в этом случае рассчитывать субградиент? Или во всяком случае как узнать, что попали на линию излома поверхности? Я понимаю, что вероятность попасть туда стремится к нулю, но тем не менее. Получается на практике субградиент можно считать равным градиенту и не заморачиваться. Однако открытым остается вопрос с fmin.

[мат-ламер]

andreso в сообщении #1084407 писал(а):

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

Для начала почитайте теорию. Например, Магарил-Ильяев, Тихомиров. Выпуклый анализ и его приложения. Параграф. 1.1.5. Субдифференциальное исчисление. Но лучше теория усваивается на конкретных примерах. Если у вас есть функция, то выпишите её здесь. Разберёмся. Только не выкладывайте здесь программы. Вряд ли их будет кто-то читать. Любую идею можно выразить словами и LaTeXом.

-- Вт дек 22, 2015 15:52:24 --

andreso в сообщении #1084407 писал(а):

Или во всяком случае как узнать, что попали на линию излома поверхности?

Вот на конкретном примере и посмотрим.

-- Вт дек 22, 2015 15:53:30 --

andreso в сообщении #1084407 писал(а):

Однако открытым остается вопрос с fmin.

А вот это вопрос сложный и принципиальный. Для начала распишите фомулами, какой метод вы испоьзуйте.