Когда задача оптимизации не имеет решений?

[ShMaxG]

Долгое время мучает один вопрос, никак не могу разрешить. Пусть решается задача оптимизации $f(x,y)=\sqrt{x^2+y^2}\to\min$ с некоторым скалярным ограничением $g(x,y)=C$ и на квадрате $-1\le x,y \le 1$. Может ли быть так, что решение этой задачи не существует? Я перебирал разные функции, рисовал картинки, всегда решение существует. Наверное потому что я перебирал "хорошие" функции $g(x,y)$, такие, что сужение функционала на них представляло собой непрерывную функцию на компакте, а такие функции всегда имеют где-то минимум. У меня не получается представить себе такую функцию, чтобы минимума не существовало, ну так, чтобы не совсем изощренная экзотика. (Решаю реальную задачу в пространстве большей размерности, с вроде бы "хорошей" функцией $g(x,y)$, но ни один решатель оптимизационных задач (хоть градиентные, хоть неградиентные) не могут найти решение).

[meshok]

А разве не проходят такие стандартные рассуждения?
Пусть функция $g$ непрерывна, тогда $g^{-1}(C)$ -- замкнутое множество (как прообраз замкнутого множества), а поскольку мы рассматриваем еще его сужение на квадрат, то получаем компакт. И далее как вы упомянули: непрерывная функция на компакте достигает своего минимума.
Если допускается, что $g$ может быть разрывной, то можно рассмотреть такую функцию $g(x,y)=Ind_{x=y\ne 0}(x,y)$. Тогда в задаче $f(x,y)=\sqrt{x^2+y^2}\to \min,\quad g(x,y)=1, -1\leq x,y\leq 1$ инфимум равен нулю, но он не достигается.

[vpb]

С точки зрения чистого матана Вам уже всё объяснили, добавить, в принципе, нечего.

ShMaxG в сообщении #1637923 писал(а):

но ни один решатель оптимизационных задач (хоть градиентные, хоть неградиентные) не могут найти решение).

А вот с практикой всё гораздо хуже. Например, метод наискорейшего спуска, даже если его применить всего лишь к квадратичной, положительно определенной, функции, сходится и даже экспоненциально. Но какова скорость сходимости, спрашивается ? Показатель в экспоненте будет $-\mu/M$, где $\mu$ и $M$ --- наименьшее и наибольшее собственные значения. А это отношение, вполне может быть очень мало. Оттого и скорость маленькая. А если функция весьма невыпуклая ? А влияние численных ошибок (округления) ? Опять же, если размерность большая, то пойдет время на матричные вычисления. Короче, в реальности даже локальная задача оптимизации (в "области притяжения" одного конкретного минимума) решается очень плохо.
(Но это по моим личным понятиям и моему опыту, которые достаточно скромные, т.е. имхо).

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

Мне кажется, что "не существует" тут даже при разрывной функции в том смысле, что можно сколь угодно близко приблизиться к оптимуму, но точка, к которой приближаемся, вне области, заданной ограничениями (как в примере meshok). То есть решатель должен бы выдать ответ в пределах заданной погрешности.
Может, тут более частная проблема, связанная с функцией ограничений и её заданием решателю. Может быть, тут ограничения разбивают допустимую область на несколько несвязных, и надо проводить поиск в каждой по отдельности.
Ну и в качестве мелкого совета - возвести ЦФ в квадрат, на положение оптимума не повлияет, а с производными проще будет.

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

И, кстати, как понимать "решатель не может найти решение"?
Зависает надолго, или выдаёт ответ, а он явно не оптимален, или вылетает по какой-то причине?

[ShMaxG]

Большое спасибо за ответы, немного прояснилось. Значит просто непрерывности $g(x,y)$ достаточно для существования решения, а проблемы скорее всего связаны с численными методами оптимизации. Поясню проблему более конкретно. Решается задача

$$f(\mathbf{x}_1,\mathbf{x}_2,\mathbf{x}_3)=|\mathbf{x}_1| + |\mathbf{x}_2| + |\mathbf{x}_3|\to\min, \ \mathbf{g}(\mathbf{x}_1,\mathbf{x}_2,\mathbf{x}_3)=0.$$

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

$$L=f(\mathbf{x}_1,\mathbf{x}_2,\mathbf{x}_3) + \mathbf{p}^T \mathbf{g}(\mathbf{x}_1,\mathbf{x}_2,\mathbf{x}_3)$$

не обнуляется, а осциллирует вокруг большого значения. Я проверил, действительно, градиент целевой функции не лежит в пространстве градиентов ограничений, множители Лагранжа $\mathbf{p}$ подходящие не находятся. Если я возьму функцию $f=|\mathbf{x}_1|^2 + |\mathbf{x}_2|^2 + |\mathbf{x}_3|^2$, то решение находится очень быстро. Мой функционал (сумма норм) не дифференцируема в нуле. Поэкспериментировав, я выяснил, что один из векторов стремится к нулю, а производная функционала там терпит разрыв, видимо это и мешает оптимизационной процедуре, основанной на непрерывности градиентов, сойтись.

[мат-ламер]

ShMaxG в сообщении #1637943 писал(а):

Мой функционал (сумма норм) не дифференцируема в нуле.

И не только в нуле. Вы правильно поняли, что градиентный метод может не работать для функции, у которой нет градиента (в обычном смысле слова). Для минимизации таких функций, как у вас, придуманы разные методы. Как вариант, можно ввести три вспомогательных переменных $y_i^2=x_i$ . И тогда мы получаем задачу минимизации гладкой функции $\sum y_i^2$ с четырьмя ограничениями. К старому ограничению добавились три новые (определения новых переменных).

ShMaxG в сообщении #1637943 писал(а):

Процесс нормально не заканчивается, потому что норма градиента функции Лагранжа ... не обнуляется

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

[Alex Krylov]

Все вот это $\left\lvert...\right\rvert$, $\left\lVert...\right\rVert_p, p=1,\infty$ сводимо к эквивалентным линейным ограничениям. Если при этом в задаче отсутствуют нелинейные ограничения, то исходная задача (явным образом) переформулируется в виде задачи ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.

Как пример:

$\min\limits_{} \sum\limits_{j=1}^{N} c_j\left\lvert x_j \right\rvert, c_j>0$
$Ax>b$

Замечаем, что $x_j = u_j - t_j; u_j\geqslant0, t_j\geqslant0 \Rightarrow \left\lvert x_j \right\rvert = u_j + t_j$
Далее все это подставляется в исходную задачу и добавляются дополнительные ограничения $u_j\geqslant0, t_j\geqslant0$

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

Ещё бы про ограничения узнать...

[svv]

ShMaxG в сообщении #1637943 писал(а):

Решается задача

$$f(\mathbf{x}_1,\mathbf{x}_2,\mathbf{x}_3)=|\mathbf{x}_1| + |\mathbf{x}_2| + |\mathbf{x}_3|\to\min, \ \mathbf{g}(\mathbf{x}_1,\mathbf{x}_2,\mathbf{x}_3)=0.$$

А мне интересно, здесь $\mathbf{x}_1,\mathbf{x}_2,\mathbf{x}_3$ — это скалярные переменные (тогда почему полужирным?), или всё ж таки векторные?

[ShMaxG]

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

Ещё бы про ограничения узнать...

Это нелинейные всюду гладкие функции переменных.

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

А мне интересно, здесь $\mathbf{x}_1,\mathbf{x}_2,\mathbf{x}_3$ — это скалярные переменные (тогда почему полужирным?), или всё ж таки векторные?

Здесь это векторы, каждый размерности 3. Всего получается 9 переменных оптимизации. Вектор $\mathbf{g}$ имеет размерность 6.

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

А область, удовлетворяющая ограничениям, односвязная?
И мне кажется, что, если минимизировать сумму квадратов, содержательно изменится мало, а считать может лучше.

[ShMaxG]

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

А область, удовлетворяющая ограничениям, односвязная?

Да, и более того, я поисследовал ее численно, оказывается множество значений $\mathbf{g}$ еще и выпукло, к моему удивлению. Так что со стороны этой функции и ограничений все даже очень хорошо.

На данный момент я сталкиваюсь с проблемами сходимости даже в случаях, когда ни один из иксов не идет к нулю или к границе. Однако, посидев с ручкой, я выяснил, что матрица вторых происходных моего функционала необходимо вырождена всюду. Это значит, что функционал даже локально не квадратичный, видимо это проблема для методов оптимизации, ориентированных на положительно определенную матрицу вторых производных функции Лагранжа. Хотя матрица вторых производных функции Лагражна и целевой функции не совпадают, но возможно это какое-то влияние оказывает. Повторюсь, что если функционал брать квадратичным, сходимость наблюдается очень быстрая. К сожалению, выбор функционала именно как суммы норм, а не квадратов, делает задачу содержательной предметно.

Из ответов в теме я также понял, что нужно активно смотреть в сторону регуляризации задачи. Раз в квадратичном смысле все сходится, значит надо переходить в переменные $\mathbf{y}$ такие, что $|\mathbf{x}|=|\mathbf{y}|^2$. То есть преобразования типа Леви-Чивита. Вообще было бы здорово иметь обзор регуляризационных методов, вдруг у кого-то есть, был бы признателен за ссылку. Но опять же, одно дело решить, а другое -- все же разобраться на фундаментальном уровне, в чем проблема.

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

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

[мат-ламер]

ShMaxG в сообщении #1638087 писал(а):

значит надо переходить в переменные $\mathbf{y}$ такие, что $|\mathbf{x}|=|\mathbf{y}|^2$.

Наверное так: $y_i^4=x_{i1}^2+x_{i2}^2+x_{i3}^2$ . И задача сводится к минимизации приятной функции $f=y_1^2+y_2^2+y_3^2$ . Правда, добавляются три новых ограничения, причём с четвёртой степенью, что может быть неприятно.

-- Пн май 06, 2024 18:28:06 --

ShMaxG в сообщении #1638087 писал(а):

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

Ссылки нет, но поищите в Академии Google по proximal algorithms .