| Математический сборник |
|
|
|
|
|
Эта публикация цитируется в 5 научных статьях (всего в 5 статьях) Характеризация решения задач сильно-слабо выпуклого программирования С. И. Дудов, М. А. Осипцев Саратовский национальный исследовательский государственный университет им. Н. Г. Чернышевского
Англоязычная версия:
Sbornik: Mathematics, 2021, Volume 212, Issue 6, Pages DOI: https://doi.org/10.1070/SM9431 
Реферативные базы данных:
    § 1. Введение1.1.Параметрический выпуклый анализ – один из разделов негладкого анализа, активно развивающийся последние десятилетия. Важное место в нем отводится изучению свойств сильно и слабо выпуклых множеств и функций. Параметры сильной и слабой выпуклости позволили придать известным фактам “классического” выпуклого анализа, при надлежащей переформулировке, дополнительную количественную характеристику, а также получить и новые качественные результаты (см. [1]–[3]). Экстремальные задачи – важный и традиционный объект приложения негладкого анализа. В настоящей работе мы рассматриваем задачу где $D$ – сильно или слабо выпуклое замкнутое множество из конечномерного действительного пространства $\mathbb R^p$, а $f(x)$ – сильно или слабо выпуклая функция, заданная на некотором открытом выпуклом множестве $\Omega$, содержащем $D$.Отметим, что существуют различные варианты ослабления понятия выпуклого множества (см., например, [4]–[10]), а также понятия выпуклой функции (см., например, [11]–[13]). Часто эти понятия совпадают в конечномерном пространстве с теми, которые используются в [1]–[3] и настоящей работе. Цель работы – получить необходимые и достаточные условия решения задачи (1.1), учитывающие, в частности, параметры сильной или слабой выпуклости допустимого множества $D$ и целевой функции $f(x)$. Отдельные результаты в этом направлении получены в [1], [2], [14]–[16]. Так, в [1], [2] и [14] рассматривалась задача математического программирования со слабо и сильно выпуклыми функциями. В [15] получено достаточное условие минимума сильно выпуклой дифференцируемой функции на слабо выпуклом множестве, а в [16] – слабо выпуклой дифференцируемой функции на сильно выпуклом множестве. Конкретное сравнение результатов нашей работы с результатами упомянутых выше будет сделано далее в процессе изложения. 1.2.Напомним (см. [1]–[3]) определения сильно и слабо выпуклых множеств, их некоторые ключевые для нас свойства и введем необходимые обозначения. Пусть $r>0$ и точки $x_1$ и $x_2$ из $\mathbb R^p$ таковы, что $\|x_1-x_2\|\leqslant 2r$. Обозначим через $D_r(x_1,x_2)$ пересечение всех евклидовых шаров из $\mathbb R^p$ с радиусом $r$, содержащих точки $x_1$ и $x_2$ (сильно выпуклый отрезок с концами в точках $x_1$ и $x_2$). Определение 1.1. Множество $A\subset \mathbb R^p$ называется: a) сильно выпуклым с константой $r$ ($r$-сильно выпуклым), если с любой парой точек $x_1$ и $x_2$, таких что $\|x_1-x_2\|\leqslant 2r$, оно содержит и $D_r(x_1,x_2)$; b) слабо выпуклым с константой $r$ ($r$-слабо выпуклым), если для любой пары точек из $A$ таких, что $\|x_1-x_2\|<2r$ и $x_1\neq x_2$, пересечение $D_r(x_1,x_2)\cap A$ содержит еще хотя бы одну точку, отличную от $x_1$ и $x_2$. Применительно к множествам далее будем использовать обозначения: $\overline{A}$, $\operatorname{int} A$, $\operatorname{co} A$, $\mathbb{K}(A)$, $\partial A$ – соответственно замыкание, внутренность, выпуклая оболочка, коническая оболочка, граница множества $A$; $K^+=\{ w \colon \langle v, w \rangle\geqslant 0\ \forall \,v\in K\}$ – сопряженный конус для конуса $K$, где $\langle \,\cdot\,{,}\, \cdot \,\rangle$ – скалярное произведение; $\operatorname{Arg}\min_{x\in D}f(x)=\{y\in D\colon f(y)=\min_{x\in D}f(x)\}$; $B(x,r)$, $S(x,r)$ – замкнутый евклидов шар и сфера радиуса $r$ с центром в точке $x$ соответственно. Для точки $x_0\in A$ обозначим через $\Gamma(x_0,A)$ и $N(x_0,A)=-\Gamma^+(x_0,A)$ контингентный конус (конус Булигана) и нормальный конус множества $A$ в точке $x_0$ соответственно. Известно (см. [1], [3]), что слабо выпуклые замкнутые множества, как и выпуклые, являются регулярными. То есть контингентный конус таких множеств совпадает в любой точке с соответствующим касательным конусом Кларка (нормальный конус совпадает с нормальным конусом Кларка) и является, таким образом, не только замкнутым, но и выпуклым (см. [17]). Справедливы следующие критерии для сильно и слабо выпуклых множеств (см. [1]–[3], опорный принцип). Предложение 1.1. Пусть $r>0$. Замкнутое множество $A$ из $\mathbb R^p$ является $r$-сильно (слабо) выпуклым тогда и только тогда, когда для любых $x\in A$ и $w\in N(x,A)$ таких, что $\|w\|=1$, справедливо включение 1.3.Теперь напомним определение сильно и слабо выпуклых функций, а также их некоторые свойства, которые будем в дальнейшем использовать (см., например, [3]). Определение 1.2. Пусть $\Omega \subset \mathbb R^p$ – открытое выпуклое множество и $\rho>0$. Функция $f(\,\cdot\,)\colon \Omega\to \mathbb R$ называется сильно (слабо) выпуклой с константой $\rho$ ($\rho$-сильно (слабо) выпуклой) на множестве $\Omega$, если функция $f(\,\cdot\,)-{\rho}/{2}\|\cdot\|^2$ ($f(\,\cdot\,)+{\rho}/{2}\|\cdot\|^2$) – выпукла на $\Omega$. Как показано в [1], слабо выпуклые функции являются локально липшицевыми и регулярными. То есть они, как и выпуклые (и тем более сильно выпуклые) функции, дифференцируемы по всем направлениям в точках $x\in \Omega$. При этом производная по направлению
$$
\begin{equation*}
f'(x,g)=\lim_{\alpha\downarrow 0}\frac{f(x+\alpha g)-f(x)}{\alpha}
\end{equation*}
\notag
$$
для любых $g\in \mathbb R^p$ совпадает с обобщенной производной по направлению (Кларка (см. [17]):
$$
\begin{equation*}
f'(x,g)=f^o(x,g)\equiv\lim_{\substack{y\to x\\ \alpha\downarrow 0}}\sup \frac{f(y+\alpha g)-f(y)}{\alpha}.
\end{equation*}
\notag
$$
Следовательно, справедлива формула
$$
\begin{equation*}
f'(x,g)=\max_{v\in \partial f(x)}\langle v,g \rangle \quad \forall\, g\in \mathbb R^p,
\end{equation*}
\notag
$$
где $\partial f(x)$ – субдифференциал Кларка функции $f(\,\cdot\,)$ в точке $x$:
$$
\begin{equation*}
\partial f(x)\equiv \{v\in \mathbb R^p\colon f^o(x,g)\geqslant \langle v,g \rangle \quad \forall\, g \in\mathbb R^p \}.
\end{equation*}
\notag
$$
Сказанное выше также говорит о том, что слабо выпуклые функции являются субдифференцируемыми и субдифференциал Кларка для них совпадает с субдифференциалом В. Ф. Демьянова – А. М. Рубинова (см. [18], [19]). В [1] (см. также [3]) доказаны следующие факты. Предложение 1.2. Пусть $\Omega\,{\subset}\, \mathbb R^p$ – открытое выпуклое множество, $\rho\,{>}\,0$ и функция $f(\,\cdot\,)\colon \Omega\to \mathbb R$ является $\rho$-сильно (слабо) выпуклой на $\Omega$. Тогда вектор $v\in \mathbb R^p$ является элементом субдифференциала $\partial f(x_0)$ в точке $x_0\in \Omega$ тогда и только тогда, когда для всех $x\in \Omega$ справедливо неравенство Обозначим через $G(\alpha)=\{ x\in \Omega \colon f(x)\leqslant \alpha\}$. Предложение 1.3. Пусть $\Omega \subset \mathbb R^p$ – открытое выпуклое множество, $f(\,\cdot\,)\colon \Omega\to \mathbb R$, $\rho>0$, $x_0\in \Omega$, $\alpha=f(x_0)$. Тогда если a) функция $f(\,\cdot\,)$ является $\rho$-сильно выпуклой, то для любого $v\in \partial f(x_0)$ справедливо включение
$$
\begin{equation*}
G(\alpha)\subset B\biggl(x_0-\frac{v}{\rho},\frac{\|v\|}{\rho}\biggr);
\end{equation*}
\notag
$$
b) функция $f(\,\cdot\,)$ является $\rho$-слабо выпуклой, то для любого $v\in \partial f(x_0)$ выполняется План изложения таков. В § 2 мы получим необходимое условие решения задачи сильно-слабо выпуклого программирования (ССВП) в виде обычного в выпуклом программировании условия стационарности, к которому добавляется оценка поведения целевой функции на допустимом множестве, отражающая, в частности, параметры сильной и слабой выпуклости. На основе этой оценки получены затем достаточные условия глобального решения задачи СВВП в различных сочетаниях сильной и слабой выпуклости множества $D$ и функции $f(\,\cdot\,)$, за исключением их одновременной слабой выпуклости. В § 3 на основе результатов § 2 получены необходимые и достаточные условия решения задачи математического программирования для сильно и слабо выпуклых функций. В § 4, используя “сильное” условие стационарности для случая дифференцируемой целевой функции, будут получены достаточные условия глобального решения, а также и локального решения, с указанием радиуса окрестности точки, в которой она является локальным решением задачи. § 2. Общая задача ССВППусть $\Omega \subset \mathbb R^p$ – некоторое открытое выпуклое множество, на котором задана функция $f(\,\cdot\,)\colon \Omega\to\mathbb R$, и $D\subset \Omega$ – замкнутое множество. Везде далее считаем, что $r>0$, $\rho>0$. 2.1. Необходимые условия решенияИз известного факта (см. [17; п. 2.4.3]) следует Предложение 2.1. Если множество $D$ регулярно в точке $x_0\in D$, а в ее окрестности функция $f(\,\cdot\,)$ липшицева и в ней достигает наименьшего на $D$ значения, то Поскольку сильно и слабо выпуклые функции являются локально липшицевыми, то вопрос заключается в следующем. Что при таком условии на целевую функцию и требовании сильной или слабой выпуклости множества $D$ можно добавить к (2.1) в качестве необходимого условия решения? Лемма 2.1. Пусть множество $D$ является $r$-сильно (слабо) выпуклым и $x_0\in D$. Тогда для всех $v\in -N(x_0,D)$ и $x\in D$ выполняется неравенство Доказательство. Пусть $v\in -N(x_0,D)$ и $v\neq 0_p$. Поскольку $D$ – $r$-сильно (слабо) выпуклое множество, то в соответствии с предложением 1.1 имеем
$$
\begin{equation*}
D\subset B\biggl(x_0+r\frac{v}{\|v\|}, r\biggr)\qquad \biggl(D\subset \mathbb R^p\setminus \operatorname{int}B\biggl(x_0-r\frac{v}{\|v\|}, r\biggr)\biggr).
\end{equation*}
\notag
$$
Неравенства (2.2) являются очевидным следствием этих включений. Лемма доказана. Отметим, выполнение соотношения (2.1) означает, что множество
$$
\begin{equation*}
A(x_0)\equiv\partial f(x_0)\cap \{-N(x_0, D)\} \neq \varnothing.
\end{equation*}
\notag
$$
Далее понимаем под
$$
\begin{equation*}
M=\max_{v\in A(x_0)} \|v\|, \qquad m=\min_{v\in A(x_0)} \|v\|.
\end{equation*}
\notag
$$
Из предложения 1.2 и леммы 2.1 следует справедливость следующего факта. Лемма 2.2. Пусть выполняются условия: 1) $D$ – $r$-сильно (слабо) выпуклое множество; 2) $f(\,\cdot\,)$ – $\rho$-сильно (слабо) выпуклая функция; 3) в точке $x_0\in D$ имеет место включение (2.1). Тогда для всех $x\in D$ выполняется неравенство
$$
\begin{equation}
\begin{aligned} \, &f(x)-f(x_0) \nonumber \\ &\geqslant \begin{cases} \dfrac{1}{2}\biggl(\dfrac{M}{r}\pm \rho\biggr)\|x-x_0\|^2, &D\textit{ сильно выпуклое}; \\ \dfrac{1}{2}\biggl(-\dfrac{m}{r}\pm \rho\biggr)\|x-x_0\|^2, &D\textit{ слабо выпуклое и $\|x-x_0\|< 2r$}; \\ -m \|x-x_0\| \pm \dfrac{\rho}{2} \|x-x_0\|^2, &D\textit{ слабо выпуклое и $\|x-x_0\|\geqslant 2r$}. \end{cases} \end{aligned}
\end{equation}
\tag{2.3}
$$
Знак “$+$” в правой части (2.3) соответствует случаю сильной выпуклости функции $f(\,\cdot\,)$, а знак “$-$” – случаю слабой выпуклости. Теперь из предложения 2.1 и леммы 2.2 следует Теорема 2.1. Пусть выполняются условия: 1) $D$ – $r$-сильно (слабо) выпуклое множество; 2) $f(\,\cdot\,)$ – $\rho$-сильно (слабо) выпуклая функция; 3) $x_0\in \operatorname{Arg}\min_{x\in D}f(x)$. Тогда выполняются включение (2.1) и для всех $x\in D$ неравенство (2.3). Замечание 2.1. Точность оценок (2.3) (т.е. достижение равенств) можно увидеть на примере дифференцируемых функций вида $f(x)=f(x_0)\,{+} \langle f'(x_0),x-x_0 \rangle \pm ({\rho}/{2}) \|x-x_0\|^2$ и сильно выпуклого множества $D=B(x_0+ r{f'(x_0)}/{\|f'(x_0)\|},r)$ или слабо выпуклого множества $D=\mathbb R^p \setminus \operatorname{int}B(x_0- r{f'(x_0)}/{\|f'(x_0)\|},r)$. Здесь, конечно, предполагается $f'(x_0)\neq 0_p$. Очевидно, при этом включение (2.1) выполняется и $M=m= \|f'(x_0)\|$. Правая часть неравенства (2.3), за исключением одновременно сильной выпуклости множества $D$ и функции $f(\,\cdot\,)$, может принимать отрицательные значения. Поэтому точность оценок говорит о том, что включение (2.1) не является достаточным условием даже локального решения, если $D$ – слабо выпуклое множество или $f(\,\cdot\,)$ – слабо выпуклая функция. Однако неравенство (2.3), вытекающее из (2.1) при прочих условиях, дает очевидный подход к получению достаточных условий решения. 2.2. Достаточные условия решенияОчевидным следствием леммы 2.2 являются нижеследующие теоремы 2.2–2.4. Теорема 2.2. Пусть выполняются условия: 1) $D$ – $r$-сильно выпуклое множество; 2) $f(\,\cdot\,)$ – $\rho$-сильно выпуклая функция; 3) в точке $x_0\in D$ имеет место включение (2.1). Тогда $x_0\in \operatorname{Arg}\min_{x\in D} f(x)$, причем если $r\neq \infty$ или $\rho>0$, то Кроме того, для всех $x\in D$ выполняетсяЗамечание 2.2. Как известно (см. [20; гл. 4, § 2], [18; гл. 4, § 1]), включение (2.1) является необходимым и достаточным условием решения общей задачи выпуклого программирования (можно рассматривать, как случай $r=\infty$, $\rho=0$). Поэтому здесь интересной является лишь оценка (2.4), отражающая роль параметров $r$ и $\rho$ и $M$. Теорема 2.3. Пусть выполняются условия: 1) $D$ – $r$-слабо выпуклое множество; 2) $f(\,\cdot\,)$ – $\rho$-сильно выпуклая функция; 3) в точке $x_0\in D$ имеет место включение (2.1); 4) $\rho\geqslant {m}/{r}$. Тогда $x_0\in \operatorname{Arg}\min_{x\in D} f(x)$ и для всех $x\in D$ выполняется Пример 2.1. Пусть $p=2$, $x=(x^{(1)}, x^{(2)}) \in \mathbb R^2$, $D=\mathbb R^2 \setminus \operatorname{int} B(x_0, 2)$, $f(x)=\|x\|^2$, $x_0=(1,0)$. Очевидно, $D$ – слабо выпуклое множество с константой $r=2$, а функция $f(\,\cdot\,)$ является сильно выпуклой с константой $\rho=2$. Поскольку функция $f(\,\cdot\,)$ липшицева, дифференцируема и регулярна (см. [17; п. 2.3.6]), то $\partial f(x_0)=\{f'(x_0)\}$. Так как
$$
\begin{equation*}
f'(x)=2x,\, N(x,D)= \begin{cases} 0_p, &x\in \operatorname{int}D, \\ \{v \in \mathbb R^2\colon v=\lambda(x_0-x),\, \lambda\geqslant 0\}, &x\in \partial D=S(x_0,2), \end{cases}
\end{equation*}
\notag
$$
то нетрудно видеть, что включение (2.1) выполняется только в точках $x_1=(-1,0)$ и $x_2=(3,0)$. Тогда по теореме 2.1 имеем $\operatorname{Arg}\min_{x\in D}f(x)\subset \{x_1, x_2\}$. При этом $A(x_1)\,{=}\,f'(x_1)$, $A(x_2)\,{=}\,f'(x_2)$, для точки $x_1$ величина $m\,{=}\,\|f'(x_1)\|\,{=}\,2$, а для точки $x_2$, соответственно, $m= \|f'(x_2)\|=6$. Теперь легко убедиться, что все условия теоремы 2.3 в точке $x_1$ выполняются, а в точке $x_2$ не выполняется условие 4), а именно $\rho-{m}/{r}=-1<0$. Также нетрудно видеть, что $f(x)<f(x_2)$ в любой точке $x\in S(x_0,2)\subset D$, $x\neq x_2$. То есть точка $x_2$ не является даже локальным решением. Итак, получили $\operatorname{Arg}\min_{x\in D}f(x)=\{x_1\}$. К теореме 2.3 можно добавить некоторые уточнения. Следствие 2.1. Если выполняются условия теоремы 2.3, причем $\rho>{m}/{r}$, то Следствие 2.2. Если выполняются условия теоремы 2.3, причем $\rho={m}/{r}$, то Доказательство. Поскольку $x_0\in \operatorname{Arg}\min_{x\in D}f(x)$, то
$$
\begin{equation}
\operatorname{Arg}\min_{x\in D}f(x)=G(\alpha)\cap D, \qquad \alpha=f(x_0).
\end{equation}
\tag{2.7}
$$
В соответствии с предложениями 1.1 и 1.3 имеем Так как выполняется (2.1), то множество $A(x_0)$ не пусто и, очевидно, выпукло и замкнуто. Следовательно, элемент $v_m\in A(x_0)$ определяется однозначно. Учитывая $\|v_m\|=m$ и $\rho={m}/{r}$, множества $C_1$ и $C_2$ можно формально представить как
$$
\begin{equation*}
\begin{aligned} \, C_1&=B\biggl( x_0-\frac{v_m}{\rho}, r\biggr)\cap C_1, \\ C_2&= \biggl\{\mathbb R^p\setminus \operatorname{int} B\biggl(x_0-\frac{v_m}{\rho}, r \biggr)\biggr\}\cap C_2. \end{aligned}
\end{equation*}
\notag
$$
Тогда из (2.7) и (2.8) получаем включение (2.6), подчеркивающее роль элемента $v_m$. Следствие доказано. Также несложно получить и следующее геометрически очевидное Следствие 2.3. Если выполняются условия теоремы 2.3, причем $\rho={m}/{r}$ и при этом $v_m\,{\in}\,{-}\operatorname{int} N(x_0,D)$, то Замечание 2.4. В [15; лемма 2.1] при аналогичных требованиях слабой выпуклости (проксимальной гладкости) множества $D$ и сильной выпуклости функции $f(\,\cdot\,)$ получены достаточные условия для $\operatorname{Arg}\min_{x\in D}f(x)=\{x_0\}$. Автор предполагает дифференцируемость функции $f(\,\cdot\,)$, $f'(x_0)\neq 0_p$, выполнение (2.1) в форме $-f'(x_0)\in N(x_0,D)$ и неравенство $\rho>{m_B}/{r}$, где $m_B=\sup_{x\in G(\alpha)} \|f'(x)\|$ для $\alpha\geqslant f(x_0)$. Для сравнения с теоремой 2.3, учитывая $\partial f(x_0)=\{f'(x_0)\}$, остается отметить, что $m_B\geqslant m= \|f'(x_0)\|$. Теорема 2.4. Пусть выполняются условия: 1) $D$ – $r$-сильно выпуклое множество; 2) $f(\,\cdot\,)$ – $\rho$-слабо выпуклая функция; 3) в точке $x_0\in D$ имеет место включение (2.1); 4) ${M}/{r}\geqslant \rho$. Тогда $x_0\in \operatorname{Arg}\min_{x\in D} f(x)$ и для всех $x\in D$ выполняется неравенство Пример 2.2. Пусть $p=2$, $x=(x^{(1)}, x^{(2)}) \in \mathbb R^2$, $D=B(x_0,2)$, $f(x)=-\|x\|^2$, $x_0=(1,0)$. В данном случае $D$ – сильно выпуклое множество с константой $r=2$, а функция $f(\,\cdot\,)$ является слабо выпуклой с константой $\rho=2$. Как и в примере 2.1, имеем $\partial f(x)=\{f'(x)\}$, и так как Следствие 2.4. Если выполняются условия теоремы 2.4, причем ${M}/{r}>\rho$, то $\operatorname{Arg}\min_{x\in D}f(x)=\{x_0\}$. По аналогии со следствием 2.2, используя предложения 1.1 и 1.3, нетрудно доказать Следствие 2.5. Если выполняются условия теоремы 2.4, причем $\rho={M}/{r}$, то Замечание 2.5. В [16; теорема 5] при исходном требовании $r$-сильной выпуклости множества $D$, дифференцируемости функции $f(\,\cdot\,)$ и липшицевости ее градиента с константой $\rho$ (отсюда следует (см. [3; п. 2.1]) $\rho$-слабая выпуклость функции $f(\,\cdot\,)$) получены достаточные условия для $\operatorname{Arg}\min_{x\in D}f(x)=\{x_0\}$. Они также включают выполнение $-f'(x_0)\in N(x_0,D)$ и неравенство ${\|f'(x_0)\|}/{r}>\rho$. Для сравнения с теоремой 2.4 остается заметить, что в данном случае $M= \|f'(x_0)\|$. Следствие 2.6. Если выполняются условия теоремы 2.4, причем $\rho={M}/{r}$ и при этом $v_M \in \operatorname{int} \mathbb{K}(\partial f(x_0))$, то § 3. Сильно-слабо выпуклая задача математического программированияПусть $\Omega\subset \mathbb R^p$ – некоторое открытое выпуклое множество, на котором заданы функции
$$
\begin{equation*}
f(\,\cdot\,),\, g_i(\,\cdot\,),\, h_j(\,\cdot\,)\colon \Omega\to \mathbb R, \qquad i=1,\dots,m, \quad j=1,\dots,k,
\end{equation*}
\notag
$$
и $A\subset \Omega$ – замкнутое множество. Рассмотрим задачу
$$
\begin{equation}
D=\{ x\in \Omega \colon g_i(x)\leqslant 0,\, i=1,\dots,m;\, h_j(x)=0, \, j=1,\dots,k\}\cap A.
\end{equation}
\tag{3.2}
$$
Обозначим через
$$
\begin{equation}
L(x,\lambda,\mu)=\lambda_0 f(x)+\sum_{i=1}^m \lambda_i g_i(x)+\sum_{j=1}^k \mu_j h_j(x)
\end{equation}
\tag{3.3}
$$
функцию Лагранжа, $\lambda=(\lambda_0,\,\lambda_1, \dots,\lambda_m)$, $\mu=(\mu_1,\dots,\mu_k)$. Из известной теоремы Кларка (см. [17; п. 6.1.1]) следует Предложение 3.1. Пусть $A$ – регулярное в точке $x_0\in D$ множество, функции $f(\,\cdot\,)$, $g_i(\,\cdot\,)$, $h_j(\,\cdot\,)$ локально липшицевы при $i=1,\dots,m$, $j=1,\dots,k$. Если в точке $x_0$ функция $f(\,\cdot\,)$ достигает наименьшего на $D$ значения, то существуют ненулевые одновременно $\lambda \in \mathbb R^{m+1}_{+}$ и $\mu\in \mathbb R^k$ такие, что Замечание 3.1. Справедливость предложения следует из известной теоремы Кларка (см. [17; п. 6.1.1]) с учетом регулярности множества $A$ в точке $x_0$. При этом отметим, что функция Лагранжа в [17; п. 6.1.1] имела дополнительное, по сравнению с (3.3), слагаемое, отражающее множество $A$. Мы выбрали ее в форме (3.3), чтобы использовать результаты § 2. Далее, для краткости будем говорить, например, “функция $f(\,\cdot\,)$ $\alpha$-выпукла”, понимая под этим ее сильную выпуклость с константой $\alpha$, если $\alpha>0$, и ее слабую выпуклость с константой $|\alpha|$, если $\alpha<0$. По аналогии будем понимать, что означает “множество $A$ $r$-выпукло”. Лемма 3.1. Пусть при некоторых $\lambda \in \mathbb R^{m+1}_+$ с $\lambda_0=1$, $\mu \in\mathbb R^k$ функция $L(x,\lambda,\mu)$ является $\rho_{\lambda,\mu}$-выпуклой по $x$ на $\Omega$, множество $A$ $r$-выпукло. Если в точке $x_0\in D$ выполняются соотношения (3.4), (3.5), то для всех $x\in D$ выполняется неравенство Доказательство. Для точек $x\in D$ из условия (3.5) следует
$$
\begin{equation*}
f(x)-f(x_0)\geqslant L(x,\lambda,\mu)-L(x_0,\lambda,\mu).
\end{equation*}
\notag
$$
Отсюда, используя (3.4) и лемму 2.2, получаем (3.6). Лемма доказана. Теорема 3.1. Пусть выполняются условия: 1) множество $A$ $r$-выпукло; 2) функция $f(\,\cdot\,)$ является $\alpha$-выпуклой, функции $g_i(\,\cdot\,)$ $\beta_i$-выпуклы для $i=1,\dots,m$, функции $h_j(\,\cdot\,)$ являются $\gamma_j$-выпуклыми, функции $-h_j(\,\cdot\,)$ $\delta_j$-выпуклы для $j=1,\dots,k$; 3) $x_0\in \operatorname{Arg}\min_{x\in D}f(x)$. Тогда существуют ненулевые одновременно $\lambda \in \mathbb R^{m+1}_+$ и $\mu \in \mathbb R^k$, для которых выполняются соотношения (3.4), (3.5). Если при этом $\lambda_0=1$, то для всех $x\in D$ выполняется неравенство (3.6), где Доказательство. Поскольку множество $A$ регулярно, а сильно и слабо выпуклые функции являются локально липшицевыми, то выполнение соотношений (3.4), (3.5) следует из предложения 1.1. Учитывая неотрицательность множителей $\lambda_i$, $\mu^+_j$ и $\mu^-_j$, нетрудно сделать вывод о том, что функция Лагранжа (3.3) является $\rho_{\lambda,\mu}$-выпуклой. Поэтому по лемме 3.1 выполняется неравенство (3.6). Теорема доказана. Замечание 3.2. Одновременная слабая выпуклость функций $h_j(\,\cdot\,)$, $-h_j(\,\cdot\,)$ для $j=1,\dots,k$ влечет (см. [1]) дифференцируемость по Фреше этих функций. Тогда, учитывая также их регулярность (см. [17; п. 2.3.6]), получаем $\partial h_j(x)=\{h'_j(x)\}$. Поэтому, с учетом регулярности остальных функций, вытекающей из условия 2) теоремы 3.1, соотношение (3.4) принимает вид Теорема 3.2. Пусть выполняются условия: 1) множество $A$ $r$-выпукло; 2) для точки $x_0\in D$ при некоторых $\lambda \in \mathbb R^{m+1}_+$ с $\lambda_0=1$, $\mu\in \mathbb R^k$ выполняются соотношения (3.4), (3.5) и функция $L(x,\lambda,\mu)$ $\rho_{\lambda,\mu}$-выпукла по $x$ на $\Omega$; 3) выполняются неравенства
$$
\begin{equation}
{\rm a)}\quad\frac{M_{\lambda,\mu}}{r}+\rho_{\lambda,\mu}\geqslant 0 \quad\textit{в случае }\ r>0,
\end{equation}
\tag{3.10}
$$
$$
\begin{equation}
{\rm b)}\quad\frac{m_{\lambda,\mu}}{r}+\rho_{\lambda,\mu}\geqslant 0 \quad\textit{в случае }\ r<0.
\end{equation}
\tag{3.11}
$$
Тогда $x_0\in \operatorname{Arg}\min_{x\in D}f(x)$, причем если в (3.10) или (3.11) неравенство выполняется строго, то $\operatorname{Arg}\min_{x\in D}f(x)=\{x_0\}$. Справедливость теоремы, очевидно, вытекает из леммы 3.1 ($M_{\lambda,\mu}$, $m_{\lambda,\mu}$, подразумевается, определены в (3.7)). Замечание 3.3. Если выполняется условие 2) теоремы 3.1, то значение $\rho_{\lambda,\mu}$ в (3.10), (3.11) можно выразить через (3.8), (3.9). Замечание 3.4. Нетрудно сформулировать соответствующие уточнения теоремы 3.2, по аналогии со следствиями 2.1–2.6, в случае, когда в (3.10) при $r>0$ или в (3.11) при $r<0$ имеет место знак равенства. Замечание 3.5. 1) Если в задаче (3.1), (3.2) множество $A=\mathbb R^p$, мы можем его считать $r$-выпуклым с любым значением $r<0$. Поскольку в этом случае $x_0\in \operatorname{int}A$, то $N(x_0,A)=\{0_p\}$ и, следовательно, $m_{\lambda,\mu}=0$. Тогда неравенство (3.11) принимает вид $\rho_{\lambda,\mu}\geqslant 0$. Это соответствует достаточным условиям решения, приведенным в [1; теорема 5.2], где также предполагается выполненным условие 2) теоремы 3.1. 2) В [2] (дополнение 1) задача (3.1), (3.2) рассматривалась в случае $A=\mathbb R^p$ и отсутствия ограничений типа равенств. Полученные там необходимые и достаточные условия решения задачи соответствуют теоремам 3.1 и 3.2, но вместо условия $\lambda_0=1$ теоремы 3.2 в [2] используется “усиленное” условие Слейтера. 3) В [14] для получения достаточных условий решения экстремальной задачи использован подход на основе абстрактно выпуклого анализа [21]–[23]. В качестве приложения рассматривалась, в частности, задача (3.1), (3.2) как с ограничениями в виде равенств, так и без них. При этом предполагалась сильная или слабая выпуклость соответствующих функций и их дифференцируемость, а также $A=\mathbb R^p$. Полученные при этом достаточные условия решения можно получить как следствие теоремы 3.2. Приведем один из результатов. Следствие 3.1 (см. [14; предложение 4.1]). Пусть выполняются условия: 1) $A=\mathbb R^p$; 2) выполняется условие 2) теоремы 3.1 и все функции $f(\,\cdot\,)$, $g_i(\,\cdot\,)$, $h_j(\,\cdot\,)$, $i=1,\dots,m$, $j=1,\dots,k$, дифференцируемы по Гато в точке $x_0\in D$; 3) для точки $x_0\in D$ при некоторых $\lambda \in \mathbb R_+^{m+1}$ с $\lambda_0=1$, $\mu\in \mathbb R^k$ выполняется $\lambda_i g_i(x_0)=0$, $i=1,\dots,m$, и
$$
\begin{equation}
f'(x_0)+\sum_{i=1}^m \lambda_i g'_i(x_0) + \sum_{j=1}^k\mu_j h'_j(x_0)=0_p.
\end{equation}
\tag{3.12}
$$
Если при этом определенное через (3.8), (3.9) значение $\rho_{\lambda,\mu}\geqslant 0$, то $x_0\in \operatorname{Arg}\min_{x\in D}f(x)$. Доказательство. Так как $N(x_0,A)=\{0_p\}$, то ввиду регулярности и дифференцируемости по Гато функций в точке $x_0$ (см. [17; пп. 2.3.3, 2.3.4, 2.3.6]) включение (3.4) принимает вид (3.12). Как отмечено выше, из $N(x_0,A)=\{0_p\}$ следует $m_{\lambda, \mu}=0$, и тогда неравенству (3.11) соответствует $\rho_{\lambda, \mu}\geqslant 0$. Таким образом, все условия теоремы 3.2 выполнены. Следствие доказано.
§ 4. Задача ССВП с дифференцируемой целевой функциейИсточником получения достаточных условий решения задачи (1.1) в § 2, 3 было неравенство (2.3), вытекающее из условия стационарности (2.1) при учете параметров сильной и слабой выпуклости $D$ и $f(\,\cdot\,)$. Как видно из (2.3), если использовать только эти параметры, а также $\partial f(\,\cdot\,)$ и $N(\,\cdot\,,D)$ как локальные характеристики объектов, то исключается возможность получения достаточных условий решения в случае, если $D$ – слабо выпуклое множество и $f(\,\cdot\,)$ – слабо выпуклая функция одновременно (ввиду отрицательного знака правой части неравенства (2.3)). Это стало причиной исследования случая, когда вместо (2.1) выполняется “сильное” условие стационарности и при этом функция $f(\,\cdot\,)$ дифференцируема в точке $x_0$, подозреваемой на экстремум, а именно
$$
\begin{equation}
B(0_p,\delta)\subset f'(x_0)+N(x_0,D), \qquad \delta\geqslant 0.
\end{equation}
\tag{4.1}
$$
Как мы в итоге увидим, выполнение (4.1) при некотором $\delta>0$, с одной стороны, позволит в некоторых случаях ослабить другое условие на сочетание значений параметров, при которых достигается глобальное решение. С другой стороны, появится возможность при нарушении условий теорем 2.3 и 2.4 получить достаточные условия локального решения с указанием соответствующего радиуса окрестности. Кроме этого мы получим достаточные условия локального решения даже в случае, когда $D$ – слабо выпуклое множество и одновременно $f(\,\cdot\,)$ – слабо выпуклая функция. 4.1. Вспомогательные фактыВ [18; гл. 1, § 6] фактически доказано следующее Предложение 4.1. Пусть $C$ – выпуклый компакт, а $\Gamma$ – выпуклый конус из $\mathbb R^p$ и $\delta\geqslant 0$. Тогда эквивалентны соотношения: (1) $B(0_p,\delta)\subset C-\Gamma^+$; (2) $\max_{v\in C}\langle v,g \rangle\geqslant \delta$ $\forall\, g\in \Gamma$, $\|g\|=1$. В [3; § 1.2] доказан следующий факт. Предложение 4.2. Если $x_0$ и $x_1$ из $\mathbb R^p$ таковы, что $\|x_0-x_1\|\leqslant 2r$ и $x\in D_r(x_0,x_1)$, то Нетрудно видеть, что из предложения 4.2 вытекает Следствие 4.1. Если $x_0\neq x_1$, $\|x_0-x_1\|\leqslant 2r$, то Лемма 4.1. Пусть $A$ – $r$-сильно выпуклое множество, $x_0\in A$ и где $\|x_0-x_1\|\leqslant 2r$. Тогда справедливо включение Доказательство. Обозначим через
$$
\begin{equation*}
C=\{x\in \mathbb R^p \colon \|x_0-x\|= \|x_1-x\|=r\}.
\end{equation*}
\notag
$$
Нетрудно видеть, что наряду с известными формами представления сильно выпуклого отрезка (см. [2; т. 3.2.2], [3; § 1.2]) имеет также место Используя равенство
$$
\begin{equation*}
\|x_1-x\|^2= \|x_1-x_0\|^2 + \|x_0-x\|^2- 2 \langle x_1-x_0,x-x_0 \rangle,
\end{equation*}
\notag
$$
для $x\in C$ имеем
$$
\begin{equation*}
\biggl\langle \frac{x_1-x_0}{\|x_1-x_0\|},x-x_0 \biggr\rangle = \frac{\|x_1-x_0\|}{2r}\|x-x_0\|.
\end{equation*}
\notag
$$
Следовательно, ввиду (4.3) $x_0-x\in N(x_0, D_r(x_0,x_1))$, и теперь, используя (4.4), получаем $x_0-x\in N(x_0, A)$ для всех $x\in C$. Тогда в соответствии с предложением 1.1
$$
\begin{equation*}
A\subset \bigcap_{x\in C}B\biggl( x_0- \frac{x_0-x}{\|x_0-x\|}r,r\biggr)=\bigcap_{x\in C}B(x,r).
\end{equation*}
\notag
$$
Тем самым (см. (4.5)) лемма доказана. Лемма 4.2. Пусть $\|x_1-x_0\|\leqslant 2r$, $0 \leqslant d \leqslant \|x_1-x_0\|$. Тогда справедливо равенство Доказательство. Пусть $x^*\in D_r(x_0,x_1)$, $\|x^*-x_0\|=d$ и
$$
\begin{equation*}
\langle x_1-x_0,x^*-x_0 \rangle =\min_{\substack{x\in D_r(x_0,x_1)\\ \|x-x_0\|=d}} \langle x_1-x_0,x-x_0 \rangle.
\end{equation*}
\notag
$$
В соответствии с представлением (4.5) нетрудно видеть, что в двумерной плоскости $\pi$, содержащей точки $x_0$, $x_1$ и $x^*$, точка $x^*$ находится на окружности радиуса $r$ с центром в некоторой точке $y_0\in C\cap \pi$, т.е. С одной стороны, имеем представление
$$
\begin{equation}
\begin{aligned} \, \notag \|x_1-x^*\|^2 &= \|x_1-x_0\|^2+ \|x_0-x^*\|^2- 2 \langle x_1-x_0,x^*-x_0 \rangle \\ & = \|x_1-x_0\|^2+ d^2 -2d \|x_1-x_0\|\cos(\gamma), \end{aligned}
\end{equation}
\tag{4.8}
$$
где $\gamma=\angle x_1 x_0 x^*$ – угол в треугольнике $\Delta x_0 x_1 x^*$ с вершиной в точке $x_0$. А с другой стороны, учитывая (4.7), получаем где $\beta=\angle x_1 y_0 x^*$ – угол в треугольнике $\Delta x_1 y_0 x^*$ с вершиной в точке $y_0$.
Углы $\gamma$ и $\beta$ опираются на одну и туже дугу окружности $S(y_0,r)\cap \pi$. Так как $\beta$ – центральный угол, а $\gamma$ – вписанный угол, то $\beta = 2\gamma$ и $\cos(\beta)=2 \cos^2(\gamma)-1$. Тогда из (4.8) и (4.9) получаем уравнение относительно $\cos(\gamma)$:
$$
\begin{equation*}
\|x_1-x_0\|^2+ d^2 -2d \|x_1-x_0\|\cos(\gamma)=2r^2-2r^2(2 \cos^2(\gamma)-1).
\end{equation*}
\notag
$$
Выбирая в его решении соответствующее значение корня, после подстановки в $\langle x_1-x_0,x^*-x_0 \rangle= \|x_1-x_0\|d\cos(\gamma)$ получаем (4.6). Лемма доказана. Замечание 4.1. Можно убедиться, что при $d>0$ справедливо неравенство Лемма 4.3. Пусть конус $\Gamma$ имеет вид Доказательство. Из (4.10) следует
$$
\begin{equation}
-\Gamma^+=\Bigl\{w\colon \langle v, w \rangle \leqslant - \|w\|\sqrt{\|v\|^2-\delta^2}\Bigr\}.
\end{equation}
\tag{4.13}
$$
1) Пусть $x \in \mathbb R^p$ удовлетворяет неравенствам
$$
\begin{equation}
\|x-x_0\|<2r,\qquad \langle v,x-x_0 \rangle \leqslant - \|x-x_0\|\sqrt{\|v\|^2-\delta^2}.
\end{equation}
\tag{4.14}
$$
Из (4.13) и (4.14) следует $w=(x-x_0)/{\|x-x_0\|}\in - \Gamma^+$, $\|w\|=1$, и поскольку $\|x-x_0\|<2r$, то
$$
\begin{equation}
x=x_0+ \|x-x_0\|w \in \operatorname{int}B(x_0+rw,r).
\end{equation}
\tag{4.15}
$$
Из (4.15) и (4.11) следует $x\notin A$. Тем самым мы доказали, что
$$
\begin{equation}
A\cap\Bigl \{x\in \mathbb R^p\colon \langle v,x-x_0 \rangle \leqslant - \|x-x_0\|\sqrt{\|v\|^2-\delta^2},\, \|x-x_0\|<2r\Bigr\}=\varnothing.
\end{equation}
\tag{4.16}
$$
2) Возьмем произвольную точку $x\in A$, $\|x-x_0\|<2r$. Для нее в силу (4.16) выполняется Рассмотрим двумерную плоскость $\pi$, содержащую точки $x_0$, $x_0+v$, $x$. Пусть $w_0\in -\Gamma^+$, причем
Очевидно, имеется две точки, удовлетворяющие данным условиям. На рис. 1 эти точки $w_0$ и $w_1$ (изображения $\Gamma$ и $-\Gamma^+$ на рис. 1 соответствуют случаю $p=2$, $x_0=0_2$). Будем считать, что $w_0$ – та из них, для которой точка $x$ лежит в тупом угле с вершиной $x_0$, на одной стороне которого находится точка $x_0+v$, а на другой – точка $x_0+w_0$. Этот тупой угол обозначим через $\alpha=\angle (x_0+w_0)x_0(x_0+v)$. Рассмотрим также углы $\beta = \angle (x_0+w_0)x_0 x$, $\gamma= \angle (x_0+v)x_0 x$. В соответствии с построением имеем В треугольнике $\Delta x_0(x_0+2rw_0)x$ угол $\angle (x_0+2rw_0)x_0x=\beta$ и поскольку $x\in A$ и, по условию леммы, $\operatorname{int}B(x_0+rw_0,r)\cap A=\varnothing$, то угол $\angle x_0 x (x_0+2rw_0)\leqslant {\pi}/{2}$. Следовательно, выполняется С другой стороны, в соответствии с (4.18) Теперь из (4.19), (4.20) и (4.21) получаем
$$
\begin{equation}
\cos(\gamma)=\cos(\alpha-\beta)\geqslant -\frac{\|x-x_0\|}{2r}\sqrt{1-\frac{\delta^2}{\|v\|^2}}+ \frac{\delta}{\|v\|}\sqrt{1-\frac{\|x-x_0\|^2}{4r^2}}.
\end{equation}
\tag{4.22}
$$
Подставляя оценку (4.22) в $\langle v,x-x_0 \rangle= \|v\|\, \|x-x_0\|\cos(\gamma)$, мы получаем итоговое неравенство (4.12). Лемма 4.3 доказана. Лемма 4.4. Пусть $A$ является сильно (слабо) выпуклым множеством с константой $r\,{>}\,0$ и для некоторых $v_0\neq 0_p$ и $\delta \geqslant 0$ в точке $x_0 \in A$ выполняется включение Тогда для всех $x\in A$ (удовлетворяющих условию $\|x-x_0\|<2r$) справедливо неравенство Доказательство. Как отмечалось в п. 1.2, конус $\Gamma(x_0,A)$ является выпуклым, даже если $A$ – слабо выпуклое множество. Поэтому в соответствии с предложением 4.1 включение (4.23) эквивалентно неравенству
$$
\begin{equation}
\min_{\substack{g\in \Gamma(x_0,A) \\ \|g\|=1}} \langle v_0,g \rangle \geqslant \delta.
\end{equation}
\tag{4.25}
$$
Отметим, что $\delta \leqslant \|v_0\|$ и из (4.25) следует
1) Пусть $A$ – $r$-сильно выпуклое множество. Рассмотрим точку
$$
\begin{equation}
x_1=x_0+\frac{2r v_0}{\|v_0\|}\sqrt{1-\frac{\delta^2}{\|v_0\|^2}}.
\end{equation}
\tag{4.27}
$$
Поскольку $\|x_1-x_0\|\leqslant 2r$, то, используя следствие 4.1 при подстановке (4.27) в (4.2), получаем
$$
\begin{equation}
\Gamma(x_0, D_r(x_0,x_1))=\{ g \in \mathbb R^p\colon \langle v_0,g \rangle \geqslant \delta \|g\|\}.
\end{equation}
\tag{4.28}
$$
Из (4.26) и (4.28) следует $\Gamma(x_0,A)\subset \Gamma(x_0,D_r(x_0,x_1))$, и тогда по лемме 4.1 получаем Теперь из (4.29) и леммы 4.2 для всех $x\in A$ следует справедливость неравенства
$$
\begin{equation*}
\begin{aligned} \, &\langle x_1-x_0,x-x_0 \rangle \\ &\qquad \geqslant \frac{1}{4r^2}\|x-x_0\|\, \|x_1-x_0\| +\sqrt{(4r^2- \|x-x_0\|^2)(4r^2- \|x_1-x_0\|^2)}). \end{aligned}
\end{equation*}
\notag
$$
Подстановка сюда (4.27) и дальнейшие несложные преобразования дают (4.24) в рассматриваемом случае.
2) Пусть теперь множество $A$ является слабо выпуклым с константой $r\,{>}\,0$. Из (4.26) следует, что $-\Gamma_0^+\subset N(x_0,A)$. Тогда в силу предложения 1.1 выполняется включение
$$
\begin{equation*}
A\subset \bigcap_{\substack{w\in -\Gamma_0^+\\ \|w\|=1}}\{ \mathbb R^p \setminus \operatorname{int}B(x_0+rw,r)\}.
\end{equation*}
\notag
$$
Теперь, применяя лемму 4.3, для всех $x\in A$, удовлетворяющих $\|x-x_0\|<2r$, получаем (4.24). Лемма доказана. 4.2. Случай сильно выпуклого допустимого множества и сильно выпуклой целевой функцииВезде далее в пп. 4.2–4.5 будем считать, если не оговаривается большее, что $r >0$, $ \rho \geqslant 0$, $\delta \geqslant 0$. Теорема 4.1. Пусть выполняются условия: 1) $D$ – $r$-сильно выпуклое множество; 2) $f(\,\cdot\,)$ – $\rho$-сильно выпуклая функция, дифференцируемая по Гато в точке $x_0 \in D$; 3) выполняется включение (4.1). Тогда $x_0 \in \operatorname{Arg}\min_{x \in D} f(x)$, причем если $r \neq \infty$ или $\rho >0$, то При этом для всех $x \in D$ выполняется неравенство Доказательство. Как известно (см. [17; § 2.3]), из регулярности функции $f(\,\cdot\,)$ и ее дифференцируемости по Гато в точке $x_0$ следует $\partial f(x_0)=\{f'(x_0)\}$. Тогда в соответствии с предложением 1.2 для всех $x \in \Omega$ выполняется неравенство
$$
\begin{equation*}
f(x)-f(x_0) \geqslant \langle f'(x_0), x-x_0 \rangle + \frac{\rho}{2} \|x-x_0\|^2.
\end{equation*}
\notag
$$
Теперь, используя (4.1) и лемму 4.4, получаем для всех $x\,{\in}\,D$ неравенство (4.30), а из него и остальные утверждения теоремы. Замечание 4.2. Новое в теореме, по сравнению с давно известными в выпуклом программировании фактами, заключается лишь в полезном для приложений неравенстве (4.30), отражающем влияние параметров сильной выпуклости. В частности, оно может отразиться на улучшении оценки скорости сходимости численных методов решения задачи (1.1) в рассматриваемом случае. Приведем некоторые сравнения. Для этого обозначим скобку $({\dots})$ в правой части (4.30) через $\varphi(\delta, r)$. Используя (4.1) вместо (4.23) и повторяя рассуждения, приведенные при доказательстве леммы 4.4, для случая $A$-сильно выпуклого множества (берем $A=D$ и $v_0=f'(x_0)$), получаем при $f'(x_0) \neq 0_p$
$$
\begin{equation*}
D \subset D_r(x_0, x_1), \qquad x_1=x_0 + \frac{2r f'(x_0)}{\|f'(x_0)\|} \sqrt{1-\frac{\delta^2}{\|f'(x_0)\|^2}}.
\end{equation*}
\notag
$$
Отсюда следует
$$
\begin{equation}
\|x-x_0\| \leqslant 2 r \sqrt{1-\frac{\delta^2}{\|f'(x_0)\|^2}} \quad \forall\, x \in D.
\end{equation}
\tag{4.31}
$$
Используя (4.31), нетрудно убедиться, что В то же время, для просто выпуклого множества $D$ (случай $r = \infty$) имеем $\varphi (\delta, \infty) = \delta$. Отметим также, что и при $\delta = 0$ сильная выпуклость множества дает положительный эффект, поскольку 4.3. Случай слабо выпуклого допустимого множества и сильно выпуклой целевой функцииИз предложения 1.2 и леммы 4.4 следует справедливость следующего утверждения. Лемма 4.5. Пусть выполняются условия: 1) $D$ – $r$-слабо выпуклое множество; 2) $f(\,\cdot\,)$ – $\rho$-сильно выпуклая функция, дифференцируемая по Гато в точке $x_0 \in D$; 3) выполняется включение (4.1). Тогда для всех $x \in D$ выполняется неравенство
$$
\begin{equation}
f(x)-f(x_0) \geqslant \begin{cases} \biggl( \delta \sqrt{1-\dfrac{\|x-x_0\|^2}{4 r^2}} \\ \ \ {-}\dfrac{\|x-x_0\|}{2 r} \sqrt{\|f'(x_0)\|^2-\delta^2}\biggr) \|x-x_0\| \\ \ \ {+}\dfrac{\rho}{2} \|x-x_0\|^2, & \|x-x_0\| < 2r, \\ \dfrac{\rho}{2} \|x-x_0\|^2-\|f'(x_0)\|\, \|x-x_0\|, & \|x-x_0\| \geqslant 2 r. \end{cases}
\end{equation}
\tag{4.32}
$$
Замечание 4.3. Можно убедиться, что равенство в (4.32) при каждом фиксированном значении $\|x-x_0\|$ достигается для функции вида Приведем для рассматриваемого случая достаточные условия глобального решения задачи. Теорема 4.2. Пусть выполняются условия 1)–3) леммы 4.5. Если при этом $\rho >0$ и 4) $r \geqslant {\|f'(x_0)\|}/{\rho}$, то $x_0 \in \operatorname{Arg} \min_{x \in D} f(x)$ и для всех $x \in D$ выполняется неравенство (4.32). Доказательство. Неравенство (4.32) следует из леммы 4.5. Нетрудно убедиться, что неотрицательность его правой части обеспечивается условием 4). Теорема доказана. Следствия 2.1–2.3 принимают в данном случае следующий вид. Следствие 4.2. Если выполняются условия теоремы 4.2, причем то $\operatorname{Arg} \min_{x \in D} f(x)=\{x_0\}$. Следствие 4.3. Если выполняются условия теоремы 4.2, причем то Доказательство. Пояснить, видимо, надо только (4.36). Действительно, при $\delta >0$ из (4.1) следует $-f'(x_0) \in \operatorname{int} N(x_0, D)$. Таким образом, (4.36) получаем из следствия 2.3. Следствие доказано. Элементарное исследование знака правой части неравенства (4.32) в зависимости от соотношения величин $\delta$, $r$, $\rho$, $\|f'(x_0)\|$ и $\|x- x_0\|$ позволяет выявить условия ее неотрицательности. Тем самым мы получаем не только достаточные условия локального решения задачи, но и соответствующее значение радиуса окрестности локального минимума. Далее при $\lambda>0$ понимаем под $D(\lambda)=\{x\in D\colon \|x-x_0\|<\lambda\}$. Теорема 4.3. Пусть выполняются условия 1)–3) леммы 4.5. Если при этом 4) $\delta >0$, $\rho=0$ или $\rho>0$ и $r<{\|f'(x_0)\|}/{\rho}$, то $\operatorname{Arg} \min_{x \in D(\lambda(\delta))} f(x)=\{x_0\}$, где
$$
\begin{equation*}
\lambda(\delta)= \begin{cases} 2 r, &\rho\,{>}\,0,\, \dfrac{\sqrt{\|f'(x_0)\|^2\,{-}\,\delta^2}}{\rho}\,{\leqslant}\, r\,{<}\, \dfrac{\|f'(x_0)\|}{\rho}, \\ \dfrac{2 r \delta}{\sqrt{\delta^2\,{+}\bigl( \sqrt{\|f'(x_0)\|^2{\kern1pt}{-}{\kern1pt}\delta^2}{\kern1pt}{-}{\kern1pt}\rho r \bigr)^2}}, &\rho>0,\, r<\dfrac{\sqrt{\|f'(x_0)\|^2 - \delta^2}}{\rho}, \\ \dfrac{2 r \delta}{\|f'(x_0)\|},&\rho=0. \end{cases}
\end{equation*}
\notag
$$
Пример 4.1. Пусть $p=2$, $x=(x^{(1)}, x^{(2)}) \in \mathbb R^2$, $f(x)= \|x\|^2$, $D=\bigcap_{i=1,2}\{\mathbb R^2 \setminus \operatorname{int} B(z_i, 2\sqrt{2})\}$, $z_1=(1,2)$, $z_2=(1,-2)$. В данном случае $D$ – слабо выпуклое множество с константой $r=2$ (но слабо выпукло по Ефимову–Стечкину (см. [5]) c константой $2\sqrt{2}$), а $f(\,\cdot\,)$ – сильно выпуклая функция с константой $\rho=2$ и $\partial f(x)=\{f'(x)\}$. Геометрически очевидно, что включение (2.1) выполняется только в точках $x_1=(-1,0)$, $x_2=(3,0)$, а также в точках $x_3=(1+2\sqrt{{2}/{5}},2+4\sqrt{{2}/{5}})$, $x_4=(1+2\sqrt{{2}/{5}},-2-4\sqrt{{2}/{5}})$, находящихся на пересечении окружностей $S(z_i,2\sqrt{2})$ с прямыми, проходящими через $z_i$ и $0_2$ для $i=1,2$ соответственно. Тогда в соответствии с теоремой 2.1 $\operatorname{Arg}\min_{x\in D}f(x)\subset \{ x_i\}$, $i=1,\dots, 4$. Нетрудно видеть, что После этого можно сделать выводы. 1) Так как ${\|f'(x)\|}/{\rho}=1$, а $r=2$, то все условия теоремы 4.2 выполняются и, следовательно, $x_1 \in \operatorname{Arg}\min_{x\in D}f(x)$. 2) Для точки $x_2$ имеем $f(x_2)>f(x_1)$, ${\sqrt{\|f'(x_2)\|^2-\delta^2}}/{\rho}={3}/{\sqrt{2}}>r$, т.е. условие 4) теоремы 4.2 не выполняется. Но поскольку $\delta>0$, мы по формуле из теоремы 4.3 можем подсчитать значение $\lambda(\delta)$ – радиуса окрестности точки $x_2$, в которой она является локальным решением задачи. 3) В точках $x_3$ и $x_4$ условие 4) теоремы 4.2 также не выполняется и $f(x_3)=f(x_4)>f(x_1)$. Так как $\delta=0$, то не выполняется соответствующее условие теоремы 4.3. Можно показать, что эти точки не являются даже локальными решениями задачи. Замечание 4.5. Нетрудно убедиться, что для примера (4.33)–(4.35) при $r={\|f'(x_0)\|}/{\rho}$ и $\delta=0$ получаем а при $r={\|f'(x_0)\|}/{\rho}$ и $\delta >0$ имеем Кроме того, на этом же примере можно убедиться в точности значений радиуса локального минимума в теореме 4.3. 4.4. Случай сильно выпуклого допустимого множества и слабо выпуклой целевой функцииИз предложения 1.2 и леммы 4.4 следует Лемма 4.6. Пусть выполняются условия: 1) $D$ – $r$-сильно выпуклое множество; 2) $f (\,\cdot\,)$ – $\rho$-слабо выпуклая функция, дифференцируемая по Гато в точке $x_0 \in D$; 3) выполняется включение (4.1). Тогда для всех $x \in D$ выполняется неравенство Достаточные условия глобального решения задачи выражает Теорема 4.4. Пусть выполняются условия 1)–3) леммы 4.6. Если также выполняется условие 4) $\rho=0$ или $\rho>0$, $f'(x_0)\neq 0_p$ и $r \sqrt{1-{\delta^2}/{\|f'(x_0)\|^2}} \leqslant {\|f'(x_0)\|}/{\rho}$, то $x_0 \in \operatorname{Arg} \min_{x \in D} f(x)$ и для всех $x\in D$ выполняется неравенство (4.37). Доказательство. Неравенство (4.37) имеет место в соответствии с леммой 4.6. Остается сказать, что условие 4) обеспечивает неотрицательность правой части этого неравенства. Теорема доказана. Приведем некоторые уточнения теоремы 4.4. Следствие 4.4. Если выполняются условия теоремы 4.4, причем $\rho >0$, $f'(x_0)\neq 0_p$ и $r \sqrt{1-{\delta^2}/{\|f'(x_0)\|^2}} <{\|f'(x_0)\|}/{\rho}$, то $\operatorname{Arg} \min_{x \in D} f(x) = \{x_0\}$. Следствие 4.5. Если выполняются условия теоремы 4.4, причем $\rho>0$, $f'(x_0)\neq 0_p$ и $r \sqrt{1-{\delta^2}/{\|f'(x_0)\|^2}}={\|f'(x_0)\|}/{\rho}$, то Доказательство. Из включения (4.1), используя предложение 4.1, получаем
$$
\begin{equation}
\Gamma(x_0, D) \subset K=\{g \in \mathbb R^p\colon \langle f'(x_0), g \rangle \geqslant \delta \|g\| \}.
\end{equation}
\tag{4.38}
$$
Возьмем точку
$$
\begin{equation}
x_1 = x_0 + 2 r \sqrt{1-\frac{\delta^2}{\|f'(x_0)\|^2} \, \frac{f'(x_0)}{\|f'(x_0)\|}}.
\end{equation}
\tag{4.39}
$$
Подстановкой этой точки в (4.2) можно убедиться, что Тогда по лемме 4.1 из (4.38)–(4.40) следует В соответствии с предложением 1.3, учитывая $\partial f(x_0) = \{f'(x_0)\}$, при $\alpha = f(x_0)$ имеем
$$
\begin{equation}
G(\alpha) \subset \mathbb R^p \setminus \operatorname{int} B \biggl ( x_0 + \frac{f'(x_0)}{\rho}, \frac{\|f'(x_0)\|}{\rho} \biggr).
\end{equation}
\tag{4.42}
$$
С другой стороны, учитывая ${\|f'(x_0)\|}/{\rho} = r \sqrt{1 - {\delta^2}/{\|f'(x_0)\|^2}}$, имеем $x_1 = x_0 +{2 f'(x_0)}/{\rho}$ и тогда
$$
\begin{equation}
D_r(x_0, x_1) = B \biggl( x_0 + \frac{f'(x_0)}{\rho}, \frac{\|f'(x_0)\|}{\rho} \biggr), \qquad \delta=0,
\end{equation}
\tag{4.43}
$$
$$
\begin{equation}
D_r(x_0, x_1) \cap B \biggl( x_0 + \frac{f'(x_0)}{\rho}, \frac{\|f'(x_0)\|}{\rho} \biggr)=\{x_0, x_1\}, \qquad \delta>0.
\end{equation}
\tag{4.44}
$$
Теперь, поскольку в соответствии с предложением 1.1 выполняется $D \subset C_4$, из (4.41)–(4.44) получаем
$$
\begin{equation*}
\begin{aligned} \, \operatorname{Arg}\min_{x \in D}f(x) &= G(\alpha)\,{\cap}{\kern1pt}D\,{\subset}\biggl\{ \mathbb R^p\,{\setminus}\operatorname{int} B \biggl( x_0\,{+}\,\frac{f'(x_0)}{\rho}, \frac{\|f'(x_0)\|}{\rho} \biggr)\biggr\}\,{\cap}\, D_r(x_0, x_1)\,{\cap}\, C_4 \\ &=\begin{cases} S \biggl( x_0 + \dfrac{f'(x_0)}{\rho}, \dfrac{\|f'(x_0)\|}{\rho} \biggr) \cap C_4, &\delta=0, \\ \{x_0, x_1\}, &\delta >0. \end{cases} \end{aligned}
\end{equation*}
\notag
$$
Следствие доказано. Теперь приведем достаточные условия локального решения и соответствующее значение радиуса локального минимума, которые также вытекают из простого исследования знака правой части неравенства (4.37). Теорема 4.5. Пусть выполняются условия 1)–3) леммы 4.6, а также 4) $\rho>0$, $f'(x_0)\neq 0_p$ и $r \sqrt{1-{\delta^2}/{\|f'(x_0)\|^2}}>{\|f'(x_0)\|}/{\rho}$. Тогда $\operatorname{Arg}\min_{x \in D(\lambda(\delta))} f(x)=\{x_0\}$, где Пример 4.2. Пусть $p\,{=}\,2$, $x\,{=}\,(x^{(1)}, x^{(2)})\,{\in}\,\mathbb R^2$, $f(x)\,{=}\,{-}\|x\|^2$, $D\,{=}\,B(z_1, 2 \sqrt 2) \cap B(z_2, 2 \sqrt 2)$, $z_1=(1, 2)$, $z_2(1, -2)$. В данном случае $D$ – сильно выпуклое множество с константой $r=2 \sqrt 2$, а $f(\,\cdot\,)$ – слабо выпуклая функция с константой $\rho=2$. Можно проверить, что включение (2.1) выполняется только в точках $x_1=(-1,0)$, $x_2=(3, 0)$, а также в точках $x_3=(1-2\sqrt{{2}/{5}},2-4\sqrt{{2}/{5}})$, $x_4=(1-2\sqrt{{2}/{5}},-2+4\sqrt{{2}/{5}})$, находящихся на пересечении окружностей $S(z_i,2\sqrt{2})$ с прямыми, проходящими через $z_i$ и $0_2$ для $i=1,2$ соответственно. Тогда в соответствии с теоремой 2.1 $\operatorname{Arg}\min_{x\in D}f(x)\subset \{ x_i\}$, $i=1,\dots, 4$. Нетрудно видеть, что Далее делаем следующие выводы. 1) В точке $x_1$ имеем
$$
\begin{equation*}
\frac{\|f'(x_1)\|}{\rho}=1, \qquad r\sqrt{1-\frac{\delta^2}{\|f'(x_1)\|^2}}=2,
\end{equation*}
\notag
$$
т.е. условие 4) теоремы 4.4 не выполняется, но выполняются условия теоремы 4.5. А следовательно, данная точка является локальным решением задачи в радиусе
$$
\begin{equation*}
\lambda(\delta)=\frac{2r \delta}{\sqrt{\delta^2+(\rho r-\sqrt{\|f'(x_1)\|^2-\delta^2})^2}}=\frac{4}{\sqrt 5},
\end{equation*}
\notag
$$
причем это точный радиус локального решения. 2) В точках $x_3$ и $x_4$ условие 4) теоремы 4.5 не выполняется и $f(x_3)=f(x_4)>f(x_2)$. Теорема 4.6 неприменима, поскольку $\delta=0$. Нетрудно показать, что эти точки не являются даже локальными решениями задачи. 3) В точке $x_2$ имеем
$$
\begin{equation*}
\frac{\|f'(x_2)\|}{\rho}=3, \qquad r \sqrt{1-\frac{\delta^2}{\|f'(x_2)\|^2}}=2.
\end{equation*}
\notag
$$
Таким образом, все условия теоремы 4.4 выполняются, а значит, в итоге $\operatorname{Arg}\min_{x \in D}f(x)=\{x_2\}$. Замечание 4.6. Для множества $D=D_r(x_0, x_1)$, где точка $x_1$ определена через (4.39), и функции 4.5. Случай слабо выпуклого допустимого множества и слабо выпуклой целевой функцииИз предложения 1.2 и леммы 4.4 следует Лемма 4.7. Пусть выполняются условия: 1) $D$ – $r$-слабо выпуклое множество; 2) $f(\,\cdot\,)$ – $\rho$-слабо выпуклая функция, дифференцируемая по Гато в точке $x_0 \in D$; 3) выполняется включение (4.1). Тогда для всех $x \in D$ выполняется неравенство
$$
\begin{equation}
f(x)-f(x_0) \geqslant \begin{cases} \biggl ( \delta \sqrt{1- \dfrac{\|x-x_0\|^2}{4r^2}} \\ \ \ -\dfrac{\|x-x_0\|}{2r} \sqrt{\|f'(x_0)\|^2 - \delta^2} \biggr) \|x-x_0\| \\ \ \ -\dfrac{\rho}{2} \|x-x_0\|^2, &\|x-x_0\| < 2r, \\ -\|f'(x_0)\|\, \|x-x_0\| - \dfrac{\rho}{2} \|x-x_0\|^2, &\|x-x_0\| \geqslant 2r. \end{cases}
\end{equation}
\tag{4.47}
$$
Исследование знака правой части неравенства (4.47) приводит к справедливости следующего утверждения. Теорема 4.6. Пусть выполняются условия 1)–3) леммы 4.7 и $\delta>0$. Тогда $\operatorname{Arg}\min_{x \in D(\lambda(\delta))}f(x)=\{x_0\}$, где Пример 4.3. Пусть $p=2$, $x=(x^{(1)}, x^{(2)}) \in \mathbb R^2$, $f(x)=-\|x\|^2$, Замечание 4.7. Пример множества $D$, заданного в виде (4.34), и функции вида (4.46) позволяет убедиться в достижении равенства в (4.47), выполнении (4.1) и точности радиуса локального минимума (4.48). § 5. Заключение5.1.Полученные в § 2 и § 3 достаточные условия решения задачи (1.1) дополнительно дают информацию о квадратичном росте (см. [24], [25]) целевой функции по мере удаления аргумента от точки минимума на всем допустимом множестве или в указанной окрестности (см. (2.4), (2.5), (2.10) и (3.10)), т.е. при конкретном $\alpha\geqslant 0$. Эти достаточные условия включают в себя условие стационарности (2.1). Его замена в § 4 на условие (4.1) для случая дифференцируемой функции $f(\,\cdot\,)$ при $\delta>0$ дает более сильные локально, чем (5.1), оценки роста (4.30), (4.32), (4.37) и (4.47). А именно, из них следует, что при некотором $\beta >0$ на всем допустимом множестве $D$ или на $D\cap B(x_0, \gamma)$ при некотором $\gamma >0$ выполняется5.2.Эти $\beta$ и $\gamma$ можно указать в каждом из рассматриваемых случаев. Например, при выполнении неравенства (4.47) имеем
$$
\begin{equation*}
\begin{gathered} \, f(x)-f(x_0)\geqslant \phi(t)\|x-x_0\|, \qquad t=\|x-x_0\|, \qquad \|x-x_0\|<2r, \\ \phi(t)=\delta \sqrt{1-\frac{t^2}{4r^2}}-\biggl(\frac{\rho}{2}+\sqrt{\frac{\|f'(x_0)\|^2-\delta^2}{2r}}\biggr)t. \end{gathered}
\end{equation*}
\notag
$$
Функция $\phi(t)$ убывает на $[0,2r)$ и $\phi(0)=\delta$. Поэтому можно выбрать любое $\beta \in (0, \delta)$ и указать в качестве $\gamma$ корень простого уравнения $\phi(t)= \beta$ на $[0,2r)$. 5.3.Условие (5.2) дает сходимость градиентных методов в выпуклом негладком случае (см. [26]), а также и при условии слабой выпуклости функции $f(\,\cdot\,)$ (см. [27], [28]). Его называют условием остроты или говорят, что $x_0$ – точка острого минимума. Преимущества оценок роста функции (4.30), (4.32), (4.37) и (4.47) перед (5.2) в рассматриваемых случаях очевидны. В частности, они позволили нам получить радиусы окрестности локального решения задачи (1.1) в случаях, когда достаточные условия решения в теоремах 4.2 и 4.4 нарушаются, или в случае когда целевая функция и допустимое множество слабо выпуклы. 5.4.Надо сказать, что ключевое в § 4 условие (4.1) при $\delta>0$ становится невыполнимым, если $f'(x_0)=0_p$, или $x_0\in \operatorname{int}D$, или $x_0$ – точка гладкости $D$. Поэтому встает насущный вопрос обобщения результатов § 4 на случай недифференцируемой функции $f(\,\cdot\,)$ с соответствующей заменой условия (4.1) на
$$
\begin{equation*}
B(0_p,\delta)\subset \partial f(x_0)+N(x_0,D), \qquad \delta>0.
\end{equation*}
\notag
$$
5.5.Полученные результаты могут быть использованы при исследовании других свойств решения задач ССВП и разработке методов их численного решения. В частности, они могут отразиться на улучшении оценки скорости сходимости используемых численных методов (например, в задачах со слабо выпуклыми целевыми функциями (см. [27]–[29])). Возможно, их также можно применить для исследования задач по шаровым оценкам слабо выпуклых компактов на пути обобщения давно известных и новых задач по оценкам выпуклых компактов (см., например, [30]–[33]). Авторы выражают глубокую признательность рецензентам за конструктивные замечания.
Цитирование в формате AMSBIB
\RBibitem{DudOsi21} |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|