Вопрос по оптимизации

[Verbery]

Всем привет! Хочу решить такую задачу:

$$\text{argmin}_{x \in B_{2}(r)} \{ h(x) + c^\top x\}$$

Теперь вопрос. Можно ли утверждать, что если я заменю константу $c$ таким образом $c = \frac{c}{\| c \|_2 } \cdot r$ (то есть сделал вектор единичным и затем умножил на радиус шара, в котором заключена область определения), то решение этой задачи не изменится?

[svv]

Изменится. Возьмите для примера простейшую функцию $h(x)=x^\top x=\|x\|^2$, обеспечивающую существование минимума. Тогда при заданном $c$ минимум выражения
$x^\top x+c^\top x=(x^\top\!\!+\frac 1 2 c^\top)(x+\frac 1 2 c)-\frac 1 4 c^\top c=\|x+\frac 1 2c\|^2-\|\frac 1 2 c\|^2$
достигается при $x=-\frac 1 2 c$. Изменение $c$ сразу повлияет на результат.

Тут мы игнорировали ограничение, что $x$ принадлежит шару, но и с ним ответ будет — «в общем случае, изменится».
Советую Вам немного исследовать этот пример (сначала без ограничения $x\in B$, потом с ним). Хоть он и игрушечный, но полезный опыт даст. Даже в одномерном случае.

-- Пн июн 24, 2024 14:51:48 --

Verbery в сообщении #1643849 писал(а):

$c = \frac{c}{\| c \|_2 } \cdot r$

В С++, Java и подобных языках можно написать что-то вроде c=c/norm(c)*r, где знак = означает присваивание. Тут лучше писать «заменю константу $c$ на $\frac{c}{\| c \|}r$ », не приравнивая их.

[Verbery]

svv
Да, спасибо! Увидел, что в общем случае ответ изменится, т.к. есть Ваш контрпример

[svv]

Verbery
Вот, знаете, есть такие утверждения, которые кажутся справедливыми, а через 20 лет кто-то находит хитрую ситуацию, когда это утверждение неверно. (Есть целая книга: Геллбаум, Олмстед. Контрпримеры в анализе.)

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