Имеет ли функция многих переменных локальные минимумы?

[dgwuqtj]

Missiir в сообщении #1610417 писал(а):

dgwuqtj в сообщении #1610406 писал(а):

Я не знаю насчёт нескольких локальных минимумов, но $\frac{x^2 - 1}y + y$ не является выпуклой при $y > 0$. У неё определитель матрицы Гессе равен $-\frac 4{y^4}$, ну и локальных минимумов вообще нет.

именно при y>0 она является выпуклой, так как в этой области она будет проходить ниже отрезка, соединяющего две её любые точки. Возможно, Гессиан отрицательный из-за разрыва в нуле.

Ничего, что эти утверждения друг другу противоречат? И гессиан зависит от функции локально, так что не имеет значения, что там в нуле. Я не знаю, как вы проверяли выпуклость по определению (это некоторое вычисление всё-таки), но гессиан считается легко и он именно отрицательный.

Если взять мой пример и ограничить $y > 10$, то там функция будет точно положительной, но не будет достигать минимума. Правда, минимум у неё будет на границе $y = 10$. А что вы вообще называете минимумом комплекснозначной функции? Точку, где обнуляется градиент?

-- 18.09.2023, 22:44 --

Missiir в сообщении #1610353 писал(а):

Для большей конкретики

$$f_k(x_1,...x_n, y_k)=\frac{g(x_1,...x_n)}{ y_k}+y_k$$

Если буквально так (то есть $g$ - это многочлен второй степени, не зависящий от $k$), то ваша функция точно достигает наименьшего значения, если её ограничить на множество $y_k \geq a_k$ для любых чисел $a_k > 0$. Если к тому же у $g$ однородная часть степени $2$ невырожденная (то есть это не что-то в духе $(x_1 - x_2)^2$), то минимум достигается только в одной точке. Там частные производные по $x_i$ должны обнуляться, то есть $x_i$ определены однозначно как точка минимума $g$, ну и $y_k = \mathrm{max}(a_k, \sqrt{g(x_{\mathrm{min}})})$.

[Missiir]

dgwuqtj в сообщении #1610428 писал(а):

ну и $y_k = \mathrm{max}(a_k, \sqrt{g(x_{\mathrm{min}})})$.

до этого я дошел уже давно, в смысле минимум так и нахожу

-- 18.09.2023, 22:55 --

dgwuqtj в сообщении #1610428 писал(а):

Missiir в сообщении #1610417 писал(а):

dgwuqtj в сообщении #1610406 писал(а):

Если буквально так (то есть $g$ - это многочлен второй степени, не зависящий от $k$), то ваша функция точно достигает наименьшего значения, если её ограничить на множество $y_k \geq a_k$ для любых чисел $a_k > 0$.

всё почти так, но от k он всё таки зависит, структура одинаковая, переменные одни и те же, но коэффициенты разные

-- 18.09.2023, 23:01 --

в этом случае она будет гарантированно достигать минимума, или уже нет?

-- 18.09.2023, 23:13 --

dgwuqtj в сообщении #1610428 писал(а):

Если к тому же у $g$ однородная часть степени $2$ невырожденная (то есть это не что-то в духе $(x_1 - x_2)^2$), то минимум достигается только в одной точке

если я правильно Вас понимаю, то однородная часть при степени $2$ у меня такая:

$$(a_1x_1+a_2x_2+...+a_nx_n)^2$$

это вырожденная, или нет?

[dgwuqtj]

Missiir в сообщении #1610430 писал(а):

dgwuqtj в сообщении #1610428 писал(а):

Если к тому же у $g$ однородная часть степени $2$ невырожденная (то есть это не что-то в духе $(x_1 - x_2)^2$), то минимум достигается только в одной точке

если я правильно Вас понимаю, то однородная часть при степени $2$ у меня такая:

$$(a_1x_1+a_2x_2+...+a_nx_n)^2$$

это вырожденная, или нет?

Если у вас матрица из $a_{ik}$ (они же ещё от $k$ зависят) ранга $n$, то всё нормально, иначе проблемы.

[Missiir]

dgwuqtj в сообщении #1610437 писал(а):

Если у вас матрица из $a_{ik}$ (они же ещё от $k$ зависят) ранга $n$, то всё нормально

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

[dgwuqtj]

Давайте вы напишете всё, что известно про эти $g_k$.

[dgwuqtj]

Если все $g_k$ всюду неотрицательны и ядра их однородных компонент степени 2 имеют нулевое пересечение, то вроде минимум существует и единственнн в области $y_k \geq a_k$ при $a_k > 0$. Существование следует из того, что снаружи некоторой ограниченной области функция будет слишком большой. Для единственности поищем сначала экстремумы не на границе, там можно сделать замену $y_k = \sqrt{g_k}$. Сама функция превратится в удвоенную сумму квадратных корней из неотрицательных многочленов второй степени, то есть после замены она станет выпуклой (каждое слагаемое аффинной заменой координат сводится к $\sqrt{x_1^2 + \ldots + x_{l_k}^2 + c_k}$). Тут только надо убедиться, что она строго выпуклая, но это наверняка следует из условия на старшие члены $g_k$.

Если найденная точка минимума не попала в область (то есть какое-то $\sqrt{g_k}$ оказалось в $[0, a_k)$), то надо взять $y_k = a_k$ и искать так же минимум при меньшем числе переменных. Опять надо проверять строгую выпуклость, там кроме квадратных корней из многочленов 2 степени появятся просто многочлены 2 степени.

Если все $g_k$ строго положительны, то такие суммы точно строго выпуклые. Иначе может быть $\frac{x^2}y + y + \frac{(x - 1)^2}z + z$, у неё минимумов много (некий отрезок). Но в любом случае, если $g_k$ неотрицательны, локальные минимумы будут образовывать связное подмножество.

[Missiir]

dgwuqtj в сообщении #1610468 писал(а):

можно сделать замену $y_k = \sqrt{g_k}$. Сама функция превратится в удвоенную сумму квадратных корней из неотрицательных многочленов второй степени, то есть после замены она станет выпуклой (каждое слагаемое аффинной заменой координат сводится к $\sqrt{x_1^2 + \ldots + x_{l_k}^2 + c_k}$). Тут только надо убедиться, что она строго выпуклая, но это наверняка следует из условия на старшие члены $g_k$.

Здравствуйте! Сначала, мне хотелось бы поблагодарить Вас за просто неоценимую помощь,

да, действительно, раз при любом фиксированном $g_k(x)$ минимум, и причём единственный, достигается при $y_k = \sqrt{g_k}$, то $F()$ можно свести к сумме корней и исследовать на единственность минимума эту суму, а для этого все слагаемые просто должны быть строго выпуклыми. Раньше я этого не понимал.

dgwuqtj в сообщении #1610468 писал(а):

Тут только надо убедиться, что она строго выпуклая, но это наверняка следует из условия на старшие члены $g_k$.

не могли бы Вы уточнить, какое ограничение нужно наложить на старшие члены $g_k$, чтобы корень из них был строго выпуклым?

[dgwuqtj]

Missiir в сообщении #1610475 писал(а):

не могли бы Вы уточнить, какое ограничение нужно наложить на старшие члены $g_k$, чтобы корень из них был строго выпуклым?

Я умею только при $g_k \geq 0$. Обозначим через $G_k$ однородные компоненты $g_k$ степени 2, это квадратичные формы от $n$ переменных. Пусть $V_k$ - это ядро $G_k$, то есть $V_k = \{\vec x \mid G_k(\vec x + \vec x') = G_k(\vec x') \text{ для всех } \vec x'\}$. Наложим условие $\bigcap_k V_k = 0$ (если его не накладывать, то после замены переменных окажется, что какие-то $x_i$ вообще не участвуют в уравнениях, так что минимумов будет точно много). Например, при $g_k = (\sum_i a_{ki} x_i)^2 + c_k$ это в точности условие, что ранг $(a_{ik})_{ik}$ равен $n$.

Раз уж $g_k \geq 0$, то $\sqrt{g_k}$ является выпуклой функцией (как я писал, это можно проверить, приведя $g_k$ к каноническому виду). Если же $g_k > 0$ всюду, то $\sqrt{g_k}$ даже будет аналитической. Ясно, что функции вида $u = \sum_{k \in K} (\frac{g_k}{a_k} + a_k) + 2 \sum_{k \notin K} \sqrt{g_k}$ тоже являются выпуклыми (где $K \subseteq \{1, \ldots, m\}$), так что множество тех $\vec x$, где локальный минимум, является выпуклым (пустым или связным) множеством. В силу выпуклости значение $u$ во всех таких точках одинаково. В аналитическом случае (когда все $g_k > 0$) такое множество либо неограничено, либо является точкой, либо пусто.

Я утверждаю, что при условии $\bigcap_k V_k = 0$ функция $u$ возрастает с ростом $|\vec x|$, даже $u(\vec x) \geq C |\vec x| + C'$ для каких-то констант $C > 0$ и $C'$. Из этого будет следовать, что $u$ имеет локальный минимум на непустом и ограниченном множестве (причём локальный минимум совпадает с глобальным). Давайте писать $\alpha(\vec x) \succeq \beta(\vec x)$, если $\beta(\vec x) \geq 0$ и существуют константы $C > 0$, $C'$ такие, что $\alpha(\vec x) \geq C \beta(\vec x) + C'$ для всех $\vec x$. Легко видеть, что $g_k \succeq d(\vec x, V_k)^2 \succeq d(\vec x, V_k)$ и $\sqrt{g_k} \succeq d(\vec x, V_k)$, где $d(\vec x, V)$ - расстояние до подпространства. Так как $\bigcap_k V_k = 0$, то $\sum_k d(\vec x, V_k) \succeq |\vec x|$.

[Missiir]

dgwuqtj
Я конечно извиняюсь, но не могу разобраться в обозначениях. Не могли бы Вы разъяснить, что значит

dgwuqtj в сообщении #1610478 писал(а):

$\bigcap_k V_k = 0$

похоже не пересечение множеств, но смысл не совсем понятен
в выражении

dgwuqtj в сообщении #1610478 писал(а):

$V_k = \{\vec x \mid G_k(\vec x + \vec x') = G_k(\vec x') \text{ для всех } \vec x'\}$.

не понятно, что обозначает $\vec x'$, чем отличаются векторы $\vec x$ и $\vec x'$?

[dgwuqtj]

Вот возьмём произвольную квадратичную форму $Q$, например, $Q(\vec x) = x_1^2 + \ldots + x_l^2$ для некоторого $0 \leq l \leq n$. Ядро - это такие вектора $\vec x$, что значение $Q$ сохраняется при прибавлении $\vec x$ к аргументу. В примере с суммой квадратов ядро - это такие $\vec x$, что $(t_1 + x_1)^2 + \ldots + (t_l + x_l)^2 = t_1^2 + \ldots + t_l^2$ для всех $t_i$ одновременно (я вектор $\vec t$ выше обозначил через $\vec x'$). Другими словами, $x_1 = \ldots = x_l = 0$, тут ядро будет $(n - l)$-мерным. В общем случае это какое-то векторное подпространство $\mathbb R^n$. Пересечение означает, конечно же, именно пересечение множеств. Мы пересекаем векторные подпространства, так что в пересечении тоже будет подпространство. В правой части стоит нулевое подпространство, из одного нуля.

Если какая-то форма $G_k$ невырожденная (положительно определённая), то у неё ядро нулевое и пересечение всех ядер автоматически нулевое.

[Missiir]

т.е. проще говоря, ядро, в данном случае это набор переменных, входящих в $g_k$, но отсутствующих в её квадратичных членах?

[dgwuqtj]

Вообще я неправильно немного написал. Так как $g_k \geq 0$, функция $\frac{g_k}{\max(a_k, \sqrt{g_k})} + \max(a_k, \sqrt{g_k})$ заменой переменных сводится к $\frac{t^2 + c}{\max(a_k, \sqrt{t^2 + c})} + \max(a_k, \sqrt{t^2 + c})$, где $t^2 + c = g_k$. Эта функция выпуклая и возрастающая по $t \geq 0$ (можно проверить, посчитав производные), так что исходная функция тоже выпуклая из геометрических соображений. Сложив эти функции по всем $k$, получим, что исходная функция достигает минимума на выпуклом подмножестве. Независимо от условия на ядра $G_k$, это выпуклое подмножество непусто, и оно ограничено, если условие на ядра выполняется.

Если же все $g_k > 0$ и выполнено условие на ядра, то минимум достигается в единственной точке. Просто потому что иначе найдётся отрезок положительной длины в области, где достигается минимум, на котором все $\max$ раскрываются одинаковым образом (каждый максимум раскрывается одним способом на выпуклом замкнутом подмножестве и другим на замыкании его дополнения). После раскрытия максимумов получится аналитическая функция, а в силу условия на ядра её аналитическое продолжение на $\mathbb R^n$ возрастает на бесконечности, так что она не может быть константой на отрезке.

-- 19.09.2023, 13:18 --

Missiir в сообщении #1610492 писал(а):

т.е. проще говоря, ядро, в данном случае это набор переменных, входящих в $g_k$, но отсутствующих в её квадратичных членах?

Например, возьмём $g = (x_1 + x_2)^2 + 2(x_1 + x_2) + 2$. У неё ядро - это $\{\vec x \mid x_1 + x_2 = 0\}$. Что-то я тупанул, раз $G_k$ неотрицательно определено, то её ядро - это просто где $G_k$ обнуляется.

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

Мне что-то такое примерещилось:
$F(x_1,x_2,y)=(x_1^2+x_2^2)(y-1)^2+((x_1-1)^2+(x_2-1)^2)y^2$
Кажется, при фиксированных игреках квадратична, при фиксированных иксах квадратична, но два равных нулю минимума. При $x_1=x_2=y=0$ и $x_1=x_2=y=1$

[Missiir]

dgwuqtj
случай $y_k<a_k$ можно не рассматривать.

dgwuqtj в сообщении #1610501 писал(а):

где $t^2 + c = g_k$

$$g_k=(a_1x_1+a_2x_2+...+a_nx_c+b)^2$$

Вы уверены, что она может быть представлена в виде

$$g_k=t^2+c$$

[dgwuqtj]

Да, $t = \sum_i a_i x_i + b$, $c = 0$.

Имелось в виду, что сначала аффинной заменой $g_k$ сводится к виду $x_1^2 + \ldots + x_l^2 + c$, а потом берётся $t = \sqrt{x_1^2 + \ldots + x_l^2}$. Чтобы $c$ было наименьшим значением $g_k$.