Журнал вычислительной математики и математической физики, 2022, T. 62, № 12, стр. 2018-2025

ВВЕДЕНИЕ

Один из подходов к решению задачи вида $\varphi (x) \to \min $, $x \in X \subset {{E}^{n}}$, в случае выпуклой негладкой функции $\varphi (x)$ и невыпуклого замкнутого множества Х состоит в сведении исходной задачи минимизации к последовательности задач выпуклого программирования. В [1] был рассмотрен случай, когда Х представляет собой гладкую поверхность произвольного вида, а в [2] – пересечение гладкой поверхности с выпуклым компактом. При реализации алгоритмов, предлагаемых в указанных работах, на каждой итерации решается задача минимизации $\varphi (x)$ на выпуклом компактном подмножестве точек некоторой вспомогательной гиперплоскости. Сходимость алгоритмов не зависит от выбора метода решения вспомогательных задач выпуклого программирования, поэтому удачный выбор соответствующего метода может повысить эффективность вычислений.

При реализации ряда методов решения вычислительных задач, особенно при поиске экстремумов функций, существенно используется аппарат проектирования точки на множество. Среди работ, посвященных таким методам, можно отметить, например, [3]–[14]. В тех ситуациях, когда поиск проекций не удается осуществлять точными методами, используются итерационные процедуры. Последнее обстоятельство существенно снижает эффективность метода решения исходной вычислительной задачи, однако на практике такой подход иногда оказывается наиболее целесообразным, поскольку методы непроекционного типа могут иметь свои существенные недостатки и ограничения в использовании.

В настоящей работе изучается задача минимизации выпуклой негладкой функции $\varphi (х)$ на множестве $X \subset {{E}^{n}}$, представимом в виде теоретико-множественной разности множества точек гладкой поверхности S и объединения конечного числа выпуклых открытых множеств $\operatorname{int} {{G}_{i}},$ $\,i = 1,2,...,l$, где каждое из замкнутых множеств ${{G}_{i}}$ в любой своей граничной точке имеет единственную опорную гиперплоскость.

В процессе использования алгоритма на каждой итерации приходится находить решение $z({{x}_{k}})$ вспомогательной задачи минимизации $\varphi (x)$ на компактном пересечении конечного числа замкнутых полупространств, содержащих точку ${{x}_{k}}$, и касательной гиперплоскости к поверхности S, построенной в точке ${{x}_{k}}$. В силу выпуклости гиперплоскости, полупространств и функции $\varphi (x)$, эта задача может быть приближенно решена с помощью одного из итерационных методов выпуклого программирования. При использовании метода проекции субградиента, рассмотренного в [15, с. 281–287], на каждой итерации необходимо вычислять произвольный субградиент функции $\varphi (x)$ в точке ${{x}_{k}}$ и находить проекцию некоторой точки на соответствующее выпуклое множество. Поскольку это множество задается линейными неравенствами и линейным равенством, то задача проектирования точки на него сводится к задаче квадратичного программирования и может быть решена с помощью конечношаговых алгоритмов. Отметим, что число неравенств с ростом n и l возрастает; при малых значениях n и l (например, при $n = 2$ и $l = 1$) оно становится небольшим, и тогда для поиска проекции вместо решения задачи квадратичного программирования возможно использование более простых частных приемов.

Наиболее сложной при реализации предлагаемого алгоритма является вспомогательная задача нахождения проекции точки на пересечение гладкой поверхности S и l полупространств, которое в общем случае является невыпуклым. В работе [16] и библиографии к ней предлагаются итерационные алгоритмы нахождения проекции точки на множество вида $\{ x \in А\,:g(x) = 0\} $, где А – выпуклый компакт, а $g(x)$ удовлетворяет тому или иному условию подчинения. Одним из таких условий является липшицевость $g(x)$ на А. При реализации метода, предлагаемого в настоящей работе, на каждой итерации требуется проектировать различные точки отрезка $[{{x}_{k}},z({{x}_{k}})]$, при этом расстояние от проектируемой точки до ее проекции не может превосходить величину $\left\| {{{x}_{k}} - z({{x}_{k}})} \right\|$, поэтому в качестве А можно брать соответствующее пересечение l полупространств и замкнутого шара с центром в проектируемой точке и радиусом, не меньшим величины $\left\| {{{x}_{k}} - z({{x}_{k}})} \right\|$. Поскольку гладкая поверхность может быть задана в виде $S = \{ x \in {{E}^{n}}\,:g(x) = 0\} $, где $g(x) \in {{C}^{1}}({{E}^{n}})$, то $g(x)$ на любом компакте, очевидно, является липшицевой.

1. ПОСТАНОВКА ЗАДАЧИ И АЛГОРИТМ

Рассмотрим задачу вида $\varphi (x) \to \min $, $x = ({{x}^{{(1)}}},...,{{x}^{{(n)}}}) \in X \subset {{Е}^{n}}$, в которой $\varphi (х)$ выпукла и непрерывна на ${{E}^{n}}$, а Х непусто и представляет собой теоретико-множественную разность множества точек поверхности $S = \{ x \in {{E}^{n}}\,:g(x) = 0\} $ и множества $\bigcup\nolimits_{i = 1}^l {\operatorname{int} {{G}_{i}}} $, где $g(x) \in {{C}^{1}}({{E}^{n}})$, и при любом $x \in S$ имеет место $\left\| {{{g}^{/}}(x)} \right\| \ne 0$, а ${{G}_{i}},\;i = \overline {1,l} $, выпуклы и замкнуты и $\operatorname{int} {{G}_{i}},\;i = \overline {1,l} $, непусты. Пусть каждое из ${{G}_{i}},\;i = \overline {1,l} $, в любой своей граничной точке х имеет единственную опорную гиперплоскость, нормаль которой считается внешней, т.е. для всех $y \in {{G}_{i}}$ орт ${{n}^{i}}(x)$ нормали удовлетворяет условию $\left\langle {{{n}^{i}}(x),y - x} \right\rangle \leqslant 0$. Тогда при каждом i орт ${{n}^{i}}(x)$ является непрерывной вектор-функцией на границе $\partial \,{{G}_{i}}$ множества ${{G}_{i}}$.

Введем обозначения: $n(x) = {{g}^{/}}(x){{\left\| {{{g}^{/}}(x)} \right\|}^{{ - 1}}}$ – орт нормали касательной гиперплоскости к поверхности S в точке $x \in S$; $\Lambda (x) = \{ y \in {{Е}^{n}}\,:\left\langle {n(x),y - x} \right\rangle = 0\} $ – касательная гиперплоскость к S в точке $x \in S$. В силу гладкости и невырожденности $g(x)$, гиперплоскость $\Lambda (x)$ существует для любого $x \in S$ и вектор-функция $n(x)$ непрерывна на S.

Считая $x \in Х$, введем следующие обозначения: ${{s}^{i}}(x)$ – проекция точки х на множество ${{G}_{i}}$ (в силу выпуклости и замкнутости ${{G}_{i}}$ последняя существует и единственна), ${{n}^{i}}(x)$ – орт нормали опорной гиперплоскости к ${{G}_{i}}$ в точке ${{s}^{i}}(x)$, ${{\Gamma }^{i}}(x) = \left\{ {e \in {{E}^{n}}\,:\left\langle {{{n}^{i}}({{s}^{i}}(x)),e - {{s}^{i}}(x)} \right\rangle \geqslant 0} \right\}$,

где ${{d}_{0}}$ – произвольное положительное число. Поскольку каждое из ${{G}_{i}},\;i = \overline {1,l} $, в любой своей граничной точке х имеет только одну опорную гиперплоскость, то векторы ${{n}^{i}}(x)\,,$ а значит, и полупространства ${{\Gamma }^{i}}(x)$, $i = 1,2,...,l$, определяются единственным образом для любого $x \in X.$ Поскольку по построению $x \in \Lambda (x)$ и $x \in T(x)$, а при каждом $i = 1,2,...,l$ имеет место $x \in {{\Gamma }^{i}}(x)$, то всегда $x \in \Lambda (х) \cap P(x) \cap Т(х)$.

Через $z(x)$ будем обозначать произвольную точку минимума $\varphi ({\kern 1pt} \cdot {\kern 1pt} )$ на $\Lambda (x) \cap Р(x) \cap Т(х)$. В силу замкнутости $\Lambda (x)$ и ${{\Gamma }^{i}}(x)$, $i = 1,2,...,l$, компактности $Т(х)$ и непрерывности $\varphi ({\kern 1pt} \cdot {\kern 1pt} )$, точка $z(x)$ при любом $x \in Х$ существует.

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

Шаг 0. Задается ${{d}_{0}} > 0$ и полагается $k = 0$.

Шаг 1. Пусть ${{x}_{k}} \in X$ есть k-е приближение.

Шаг 2. Строятся гиперплоскость $\Lambda ({{x}_{k}})$, проекции ${{s}^{i}}({{x}_{k}})$, $i = 1,2,...,l$, полупространства ${{\Gamma }^{i}}({{x}_{k}})$, $i = 1,2,...,l$, и куб $Т({{x}_{k}})$.

Шаг 3. Определяется точка $z({{x}_{k}})$ – решение задачи $\varphi (x) \to \min $, $x \in \Lambda ({{x}_{k}}) \cap P({{x}_{k}}) \cap T({{x}_{k}})$.

Шаг 4. Если $\varphi ({{x}_{k}}) = \varphi (z({{x}_{k}}))$, то вычисления заканчиваются, иначе осуществляется переход к шагу 5.

Шаг 5. Задается ${{\alpha }_{k}} \in (0;1]$.

Шаг 6. Пусть ${{x}_{{k + 1}}}$ – проекция точки ${{x}_{k}} + {{\alpha }_{k}}(z({{x}_{k}}) - {{x}_{k}})$ на $S \cap P({{x}_{k}})$.

Шаг 7. Полагается $k\,:\, = k + 1$ и осуществляется переход к шагу 1.

В [10] изучена задача минимизации гладкой функции на множестве Х рассматриваемого вида и показано, что вспомогательная задача проектирования точки на $S \cap P({{x}_{k}})$ всегда имеет решение. Ниже будет показано, что выполнение равенства $\varphi ({{x}_{k}}) = \varphi (z({{x}_{k}}))$ при некотором конечном k означает, что ${{x}_{k}}$ удовлетворяет необходимому условию локального минимума $\varphi (х)$ на Х. Это равенство может не выполняться ни при каком k, тогда алгоритм становится итерационным.

Будем считать, что при выбранном начальном приближении ${{x}_{0}} \in X$ выполняются условия:

1) множество $M({{x}_{0}}) = \left\{ {x \in X\,:\varphi (x) \leqslant \varphi ({{x}_{0}})} \right\}$ ограничено;

2) для любого $x \in M({{x}_{0}})$ гиперплоскость $\Lambda (x)$ и множество внутренних точек $Р(х)$ имеют непустое пересечение.

В [10] указаны некоторые частные случаи, когда для любого $x \in M({{x}_{0}})$ пересечение $\Lambda (x)$ и $\operatorname{int} Р(х)$ заведомо непусто. В силу непрерывности $\varphi (x)$ и замкнутости Х, вытекающей из замкнутости S и открытости $\operatorname{int} {{G}_{i}},\;i = \overline {1,l} $, множество $M({{x}_{0}})$ компактно, при этом для любого $x \in M({{x}_{0}})$ имеем $\left\| {x - z(x)} \right\| \leqslant {{d}_{0}}$.

Пусть $D(x) = \{ y \in {{R}^{n}}\,:\left\| {x - y} \right\| \leqslant 2{{d}_{0}}\} $ – шар радиуса $2{{d}_{0}}$ с центром в точке х, а Y – такое выпуклое компактное множество, что для любого $x \in М({{х}_{0}})$ справедливо включение $D(x) \subset Y$. В силу компактности Y и замкнутости S пересечение этих множеств является компактным, поэтому существует $K = \mathop {\min }\limits_{x \in S \cap Y} \left\| {{{g}^{/}}(x)} \right\| > 0$, так как $g(x) \in {{C}^{1}}({{E}^{n}})$ и $\left\| {{{g}^{/}}(x)} \right\| \ne 0$ при любом $x \in S$. Заметим, что если $x \in М({{х}_{0}})$, то при любом $\alpha \in (0;1]$ произвольная проекция точки $x + \alpha (z(x) - x)$ на множество $S \cap P(x)$ лежит в Y, поскольку

где первое слагаемое в правой части неравенства равно $\alpha \left\| {z(x) - x} \right\|$ и не превосходит ${{d}_{0}}$, а второе слагаемое не больше первого, так как $x \in S \cap P(x)$.

Будем полагать, что $g(x) \in {{C}^{{1,1}}}(Y)$, т.е. существует такая положительная константа Q, что для всех $x,y \in Y$ справедливо неравенство $\left\| {{{g}^{/}}(x) - {{g}^{/}}(y)} \right\| \leqslant Q\left\| {x - y} \right\|$. Тогда из показанного в [1] следует, что при $N = Q{\text{/}}K$ для всех $x,y \in S \cap Y$ имеет место $\left\| {n(x) - n(y)} \right\| \leqslant N\left\| {x - y} \right\|$.

В силу замкнутости $P(x)$ и компактности Y их пересечение компактно. Поскольку касательная гиперплоскость к S, построенная в произвольной точке $x \in М({{х}_{0}})$, имеет непустое пересечение с $\operatorname{int} P(x)$, то она имеет непустое пересечение и с $\operatorname{int} P(x) \cap \operatorname{int} Y$. Действительно, пусть $х \in М({{х}_{0}})$ и $h \in \operatorname{int} P(x) \cap \Lambda (x)$, тогда $(x;h] \subset \operatorname{int} P(x) \cap \Lambda (x)$, так как $\operatorname{int} P(x)$ и $\Lambda (x)$ выпуклы и по построению $х \in Р(х)$ и $х \in \Lambda (х)$. Из определения множества Y следует, что любая точка из $(x;h] \cap \operatorname{int} D(x)$ лежит одновременно в $\Lambda (x)$, в $\operatorname{int} P(x)$ и в $\operatorname{int} Y$. Отсюда вытекает справедливость требуемого утверждения.

2. ВСПОМОГАТЕЛЬНЫЕ УТВЕРЖДЕНИЯ

Справедливо следующее утверждение, доказательство которого приводится в [10].

Лемма 1. Функции ${{\psi }_{1}}(x) = \mathop {\max }\limits_{y \in P(x) \cap Y} \left\langle {n(x),y - x} \right\rangle $ и ${{\psi }_{2}}(x) = \mathop {\min }\limits_{y \in P(x) \cap Y} \left\langle {n(x),y - x} \right\rangle $ непрерывны на $S \cap Y$.

Замечание 1. Поскольку касательная гиперплоскость к S, построенная в произвольной точке х множества $M({{x}_{0}})$, имеет непустое пересечение с $\operatorname{int} Р(х) \cap \operatorname{int} Y$, то при любом фиксированном $х \in M({{x}_{0}})$ имеет место ${{\psi }_{1}}(x) > 0$ и ${{\psi }_{2}}(x) < 0$, поэтому в силу компактности $M({{x}_{0}})$ существуют положительные константы ${{\varepsilon }_{1}} = \mathop {\min }\limits_{х \in M({{x}_{0}})} {{\psi }_{1}}(х)$ и ${{\varepsilon }_{2}} = - \mathop {\max }\limits_{х \in M({{x}_{0}})} {{\psi }_{2}}(х)$.

В силу компактности Y существует $d = \mathop {\max }\limits_{x,y \in Y} \left\| {x - y} \right\| < \infty $. Обозначим $\varepsilon = 0.5\min \left\{ {{{\varepsilon }_{1}},{{\varepsilon }_{2}}} \right\}$.

Лемма 2. Существует такое $\gamma > 0$, что при любом $x \in S \cap \,Y$, для которого $\mathop {\min }\limits_{y \in M({{x}_{0}})} \left\| {x - y} \right\| \leqslant \gamma $, имеет место ${{\psi }_{1}}(x) \geqslant \varepsilon $, ${{\psi }_{2}}(x) \leqslant - \varepsilon $.

Доказательство. Из компактности множества $S \cap Y$ и леммы 1 следует, что функции ${{\psi }_{1}}(x)$ и ${{\psi }_{2}}(x)$ равномерно непрерывны на $S \cap Y$. Это означает, что найдутся ${{\gamma }_{1}} > 0$ и ${{\gamma }_{2}} > 0$, при которых для любых $х,у \in S \cap Y$ из неравенств $\left\| {х - у} \right\| \leqslant {{\gamma }_{1}}$ и $\left\| {х - у} \right\| \leqslant {{\gamma }_{2}}$ вытекают соответственно неравенства $\left| {{{\psi }_{1}}(х) - {{\psi }_{1}}(у)} \right| \leqslant \varepsilon $ и $\left| {{{\psi }_{2}}(х) - {{\psi }_{2}}(у)} \right| \leqslant \varepsilon $. Положим $\gamma = \min \left\{ {{{\gamma }_{1}},{{\gamma }_{2}}} \right\}$, тогда с учетом включения $М({{х}_{0}}) \subset (S \cap Y)$ из сказанного вытекает справедливость утверждения леммы 2.

Замечание 2. Из неравенства (1.1) следует, что если ${{х}_{*}} \in M({{х}_{0}})$, то $\left\| {{{x}_{*}} - {{{\Pr }}_{S}}({{x}_{*}} + {{2}^{{ - s}}}(z({{x}_{*}}) - {{x}_{*}}))} \right\| \leqslant 2{{d}_{0}}$/${{2}^{s}}$, $s = 0,\;1,\;...$. Решая относительно s неравенство $2{{d}_{0}}{\text{/}}{{2}^{s}} \leqslant \gamma $, получим $s \geqslant {{\log }_{2}}2{{d}_{0}}{\text{/}}\gamma $. Отсюда и из леммы 2 следует, что при целых $s \geqslant {{\bar {s}}_{1}}$, где ${{\bar {s}}_{1}}$ – наименьший из номеров s = 0, 1, …, при котором выполняется указанное неравенство, имеет место

Считая $х \in Х$, введем обозначения: ${{y}_{s}}(x) = x + {{2}^{{ - s}}}(z(x) - x)$, s = 0, 1, …; ${{u}_{s}}(x)$ – проекция точки ${{y}_{s}}(x)$ на поверхность S; ${{p}_{s}}(x)$ – проекция точки ${{y}_{s}}(x)$ на множество $S \cap P(x)$; ${{c}_{s}}(х)$ – решение задачи $\left\langle {n({{u}_{s}}(x)),y - {{u}_{s}}(x)} \right\rangle \to \min ,$ $y \in P(x) \cap Y$, при $\left\langle {n({{u}_{s}}(x)),{{y}_{s}}(x) - {{u}_{s}}(x)} \right\rangle \geqslant 0$ и задачи $\left\langle {n({{u}_{s}}(x)),y - {{u}_{s}}(x)} \right\rangle \to \max ,$ $y \in P(x) \cap Y$, при $\left\langle {n({{u}_{s}}(x)),{{y}_{s}}(x) - {{u}_{s}}(x)} \right\rangle < 0$. Отметим, что при фиксированных $х \in Х$ и $s \in \{ 0,1,...\} $ проекции ${{u}_{s}}(x)$ и ${{p}_{s}}(x)$ в общем случае определяются не однозначно, так как множества S и $S \cap P(x)$, вообще говоря, не являются выпуклыми. Точка ${{c}_{s}}(х)$ при выбранной проекции ${{u}_{s}}(x)$ тоже может определяться не однозначно, так как она есть точка минимума или максимума линейной функции, не являющейся строго выпуклой или строго вогнутой.

Пусть ${{x}_{*}}$ – произвольная точка множества $М({{х}_{0}})$, которая не совпадает с $z({{x}_{*}})$. Введем обозначения: ${{L}_{s}}({{x}_{*}})$ – прямая, проходящая через точку ${{y}_{s}}({{х}_{*}})$ перпендикулярно $\Lambda ({{u}_{s}}({{x}_{*}}))$ (в силу показанного в [1] она проходит и через точку ${{u}_{s}}({{х}_{*}})$); ${{\tilde {L}}_{s}}({{x}_{*}})$ – луч, начинающийся в точке ${{y}_{s}}({{х}_{*}})$ и проходящий через точку ${{c}_{s}}({{х}_{*}})$. Справедливо следующее утверждение, доказательство которого проводится аналогично доказательству соответствующего утверждения из [9].

Лемма 3. Пусть ${{x}_{*}} \in M({{x}_{0}})$, $s \in \{ 0,1,...\} $, ${v}$ – произвольная точка множества Y, a $\delta $ и $\bar {\delta }$ – расстояния от точки v соответственно до гиперплоскости $\Lambda ({{u}_{s}}({{x}_{*}}))$ и до прямой ${{L}_{s}}({{x}_{*}})$. Тогда, если v лежит на поверхности S, то при $0 < \delta < 2K{\text{/}}Q$ имеет место $\bar {\delta } \geqslant \sqrt {\delta \left( {2K{\text{/}}Q - \delta } \right)} $.

С учетом справедливости леммы 3 аналогично тому, как это было сделано в [9], доказываются приведенные ниже утверждения. В проводимых при доказательстве рассуждениях множество F при фиксированном ${{x}_{*}} \in M({{x}_{0}})$ заменяется на $Р({{х}_{*}}) \cap T({{x}_{*}})$.

Лемма 4. Если ${{x}_{*}} \in M({{x}_{0}})$, то при всех целых $s \geqslant \max \left\{ {{{{\bar {s}}}_{1}},{{{\bar {s}}}_{2}}} \right\}$, где ${{\bar {s}}_{1}}$ и ${{\bar {s}}_{2}}$ – некоторые номера из множества $\{ 0,1,...\} $, справедливо утверждение: если точка ${{y}_{s}}({{х}_{*}})$ не лежит на поверхности S, то на отрезке $[{{y}_{s}}({{x}_{*}});{{c}_{s}}({{x}_{*}})]$ существует точка, в которой $g\,(x)$ имеет знак, противоположный знаку $g({{y}_{s}}({{х}_{*}}))$.

Замечание 3. В данной формулировке ${{\bar {s}}_{1}}$ имеет тот же смысл, что и в замечании 2, а ${{\bar {s}}_{2}}$ – наименьший из номеров s = 0, 1, …, удовлетворяющий условию $s \geqslant {{\log }_{2}}2\sqrt 3 Nd{{d}_{0}}{\text{/}}\varepsilon $, если $\varepsilon \geqslant K{\text{/}}Q$, и условиям $s \geqslant {{\log }_{2}}2\sqrt 3 Nd{{d}_{0}}{\text{/}}\varepsilon $ и $s \geqslant {{\log }_{2}}2{{d}_{0}}\sqrt {N(K - Q\varepsilon )} {\text{/}}\sqrt {K\varepsilon } $ одновременно, если $\varepsilon < K{\text{/}}Q$.

Лемма 5. Если ${{x}_{*}} \in M({{x}_{0}})$ и $\varphi (z({{x}_{*}})) < \varphi ({{x}_{*}})$, то существует такая положительная константа ${{M}_{0}}$, что при всех целых $s \geqslant \bar {s}$, где $\bar {s}$ – некоторый номер из множества $\{ 0,1,...\} $, имеет место

Замечание 4. В данной формулировке $\bar {s} = \max \left\{ {{{{\bar {s}}}_{1}},{{{\bar {s}}}_{2}}} \right\}$, где ${{\bar {s}}_{1}}$ и ${{\bar {s}}_{2}}$ имеют тот же смысл, что и в замечаниях 2 и 3.

3. ДОКАЗАТЕЛЬСТВО СХОДИМОСТИ АЛГОРИТМА

В этом разделе будут получены необходимые условия локального минимума $\varphi (x)$ на Х и доказано предложение о сходимости алгоритма.

Лемма 6. Для того чтобы ${{x}_{*}} \in M({{x}_{0}})$ являлась точкой локального минимума функции $\varphi (x)$ на множестве Х, необходимо выполнение равенства $\varphi (z({{x}_{*}})) = \varphi ({{x}_{*}})$.

Доказательство. Пусть ${{x}_{*}} \in M({{x}_{0}})$ – произвольная точка локального минимума $\varphi (х)$ на Х. Предположим, что $\varphi (z({{x}_{*}}))$ не совпадает с $\varphi ({{x}_{*}})$. Тогда поскольку ${{x}_{*}} \in \Lambda ({{x}_{*}}) \cap Р({{х}_{*}}) \cap T({{x}_{*}})$ и $z({{x}_{*}})$ – точка минимума $\varphi (х)$ на $\Lambda ({{x}_{*}}) \cap Р({{х}_{*}}) \cap T({{x}_{*}})$, то $\varphi (z({{x}_{*}})) < \varphi ({{x}_{*}})$. В силу выпуклости $\varphi (x)$ это означает, что вектор ${{h}_{*}} = z({{x}_{*}}) - {{x}_{*}}$ является направлением убывания $\varphi (х)$ в точке ${{x}_{*}}$. Тогда, повторяя рассуждения, проведенные в доказательстве соответствующей леммы из [9], получим, что ${{х}_{*}}$ не является точкой локального минимума $\varphi (x)$ на Х. Из этого противоречия вытекает справедливость утверждения данной леммы.

Утверждение леммы 6 означает, что произвольная точка $x \in M\,({{x}_{0}})$, доставляющая наименьшее значение $\varphi ({\kern 1pt} \cdot {\kern 1pt} )$ на $\Lambda (x) \cap Р(x) \cap Т(х)$, является стационарной, т.е. удовлетворяет необходимому (но, вообще говоря, не достаточному) условию локального минимума $\varphi ({\kern 1pt} \cdot {\kern 1pt} )$ на Х. В частности, если при некотором k точка ${{x}_{k}} \in M({{x}_{0}})$ доставляет наименьшее значение $\varphi ({\kern 1pt} \cdot {\kern 1pt} )$ на $\Lambda ({{x}_{k}}) \cap Р({{x}_{k}}) \cap Т({{х}_{k}})$, т.е. имеет место $\varphi ({{x}_{k}}) = \varphi (z({{x}_{k}}))$, то ${{x}_{k}}$ стационарна в смысле утверждения леммы 6. Если же равенство $\varphi ({{x}_{k}}) = \varphi (z({{x}_{k}}))$ не выполняется ни при каком k, то алгоритм становится итерационным, однако ниже будет показано, что при некоторых условиях любая предельная точка $\left\{ {{{x}_{k}}} \right\}$ является стационарной в смысле того же утверждения.

Отметим, что если $\varphi (x)$ не является строго выпуклой, то из справедливости равенства $\varphi ({{x}_{*}}) = \varphi (z({{x}_{*}}))$ не следует, что точка $z({{x}_{*}})$ совпадает с ${{x}_{*}}$. Кроме того, выполнение данного равенства в общем случае не означает, что точка ${{x}_{*}}$ доставляет локальный (а тем более, глобальный) минимум $\varphi (х)$ на Х. Данное замечание относится и к необходимым условиям экстремума в задачах, рассмотренных в [1], [2], [9], [10].

Заметим, что множество Х может быть задано с помощью функциональных ограничений в форме $X = \{ x \in {{E}^{n}}\,:{{f}_{i}}(x) \leqslant 0,\;i = 1,2,...,l;\;g(x) = 0\} $, где $g(x)$ является гладкой, а ${{f}_{i}}(x)$, $i = 1,2,...,l$, – вогнутыми и гладкими на ${{E}^{n}}$, и для каждого $i = 1,2,...,l$ существует такая точка ${{\tilde {x}}_{i}}$, что $f({{\tilde {x}}_{i}}) > 0$. Тогда ${{G}_{i}} = \{ x \in {{E}^{n}}\,:{{f}_{i}}(x) \geqslant 0\} $, $i = 1,2,...,l$, и для любого ${{х}_{*}} \in Х$ имеет место представление ${{\Gamma }^{i}}({{x}_{*}}) = \left\{ {x \in {{E}^{n}}\,:\left\langle {f_{i}^{/}({{s}^{i}}({{x}_{*}})),\;x - {{s}^{i}}({{x}_{*}})} \right\rangle \leqslant 0} \right\}$, $i = 1,\;2,\;...,\;l$. Вводя обозначения ${{F}_{i}} = \{ x \in {{E}^{n}}\,:$ $:{{f}_{i}}(x) \leqslant 0\} $ и $F = \bigcap\nolimits_{i = 1}^l F $, получим, что $X = \{ x \in F\,:g(x) = 0\} $, при этом конусы внутренних направлений (в смысле определения из [15, c. 244]) множеств ${{F}_{i}}$ и ${{\Gamma }^{i}}({{x}_{*}})$ для каждого i в произвольной точке ${{х}_{*}} \in Х$ совпадают.

Введем обозначения: $K({{F}_{i}})$ и $K(F)$ – конусы внутренних направлений множеств ${{F}_{i}}$, $i = 1,2,...,l$, и F в точке ${{x}_{*}} \in Х$; $K({{\Gamma }^{i}}({{x}_{*}}))$, $K(Р({{х}_{*}}))$ и $K(Т({{х}_{*}}))$ – конусы внутренних направлений множеств ${{\Gamma }^{i}}({{x}_{*}})$, $i = 1,2,...,l$, $Р({{х}_{*}})$ и $Т({{х}_{*}})$ в точке ${{x}_{*}}$; $K(S)$ – конус касательных направлений множества S в точке ${{x}_{*}}$, $K(\varphi )$ – конус направлений убывания функции $\varphi (x)$ в точке ${{x}_{*}}$. Поскольку $F = \bigcap\nolimits_{i = 1}^l {{{F}_{i}}} $ и $Р({{х}_{*}}) = \bigcap\nolimits_{i = 1}^l {{{\Gamma }^{i}}({{х}_{*}})} $, то в силу показанного в [17, с. 14] имеет место $K(F) = \bigcap\nolimits_{i = 1}^l {K({{F}_{i}})} $, $K(Р({{х}_{*}})) = \bigcap\nolimits_{i = 1}^l {K({{\Gamma }^{i}}({{х}_{*}}))} $. Отсюда и из сказанного выше следует, что $K(F) = K(P({{x}_{*}}))$, а поскольку ${{х}_{*}} \in \operatorname{int} T({{x}_{*}})$, то $K(Т({{х}_{*}}))$ есть множество всех ненулевых векторов из ${{E}^{n}}$.

Лемма 7. Если точка ${{x}_{*}} \in M({{x}_{0}})$ такова, что $\varphi ({{х}_{*}}) = \varphi (z({{x}_{*}}))$, то существуют вектор ${\mathbf{c}} \in \partial \varphi ({{x}_{*}})$ и числа ${{\lambda }_{i}} \geqslant 0,$ $i = 1,2,...,l$, и ${{\lambda }_{{\text{0}}}},{{\lambda }_{{l + 1}}} \in R,$ не все равные нулю, при которых справедливы равенства

Доказательство. Если ${{x}_{*}} \in M({{x}_{0}})$ и ${\mathbf{0}} \in \partial \varphi ({{x}_{*}})$, то положив ${\mathbf{c}} = {\mathbf{0}}$, ${{\lambda }_{0}} = 1$, ${{\lambda }_{i}} = 0$, $i = 1,2,...,l + 1$, получим требуемое равенство.

Пусть теперь ${{x}_{*}} \in M({{x}_{0}})$ и ${\mathbf{0}} \notin \partial \varphi ({{x}_{*}})$. Предположим, что существует ненулевой вектор ${{h}_{*}} \in K(\varphi ) \cap K(P({{x}_{*}})) \cap K(T({{x}_{*}})) \cap K(S)$. Тогда найдется такое ${{\alpha }_{0}} > 0$, что при $\alpha \in (0;{{\alpha }_{0}})$ точка ${{x}_{*}} + \alpha {{h}_{*}}$ лежит в $\Lambda ({{x}_{*}}) \cap P({{x}_{*}}) \cap T({{x}_{*}})$ и при этом $\varphi {\text{(}}{{x}_{*}} + \alpha {{h}_{*}}{\text{)}} < \varphi {\text{(}}{{x}_{*}}{\text{)}}$. Но выполнение равенства $\varphi ({{x}_{*}}) = \varphi (z({{x}_{*}}))$ означает, что для любого $x \in \Lambda ({{x}_{*}}) \cap P({{x}_{*}}) \cap T({{x}_{*}})$ имеет место $\varphi {\text{(}}x{\text{)}} \geqslant \varphi {\text{(}}{{x}_{*}}{\text{)}}$; полученное противоречие показывает, что сделанное предположение неверно, т.е.

Отсюда и из показанного в [15, с. 205, 249, 251, 256] вытекает существование вектора ${\mathbf{с}} \in \partial \varphi ({{x}_{*}})$ и чисел ${{\lambda }_{i}} \geqslant 0,$ $i = 1,2,...,l$, и ${{\lambda }_{0}},{{\lambda }_{{l + 1}}} \in R$, не равных нулю одновременно, при которых справедливо (3.1). Утверждение леммы доказано.

Поскольку Y выпукло и компактно, то в силу показанного в [18, с. 62] существует такая константа $L > 0$, что для любых $x,y \in Y$ имеет место $\left| {\varphi (x) - \varphi (y)} \right| \leqslant L\left\| {x - y} \right\|$, т.е. $\varphi (x)$ является липшицевой на Y.

Введем обозначения: ${{z}_{k}} = z({{x}_{k}})$, ${{y}_{{k\,,\,\,s}}} = {{y}_{s}}({{x}_{k}})$, ${{u}_{{k,s}}} = {{u}_{s}}({{x}_{k}})$, ${{p}_{{k,s}}} = {{p}_{s}}({{x}_{k}})$. Рассмотрим способ выбора чисел ${{\alpha }_{k}}$, k = 0, 1, …, состоящий в том, что величина ${{\alpha }_{k}}$ при каждом k полагается равной ${{2}^{{ - {{s}_{k}}}}}$, где ${{s}_{k}}$ – первый из номеров s = 0, 1, …, при котором имеет место

Аналогично тому, как это было сделано в [2], можно показать, что выбор ${{\alpha }_{k}}$ из указанного условия всегда возможен.

Лемма 8. При выборе чисел ${{\alpha }_{k}},\;k = 0,1,...$, согласно указанному способу, имеет место $\varphi ({{x}_{k}}) - \varphi ({{z}_{k}})\;\xrightarrow[{k \to \infty }]{}\;0$.

Доказательство полностью совпадает с доказательством соответствующего утверждения из [2].

Предложение. Если последовательность $\left\{ {{{x}_{k}}} \right\}$ построена по изложенному алгоритму при выборе ${{\alpha }_{k}},\;k = 0,1,2,...$, согласно указанному способу, то любая ее предельная точка ${{x}_{*}}$ удовлетворяет условию $\varphi ({{x}_{*}}) = \varphi (z({{x}_{*}}))$.

Доказательство. Последовательность $\left\{ {{{x}_{k}}} \right\}$ лежит в ограниченном множестве $M({{x}_{0}})$, а значит, имеет хотя бы одну предельную точку. Пусть ${{x}_{*}}$ – произвольная предельная точка, а $\{ {{x}_{{{{k}_{m}}}}}\} $ – соответствующая ей подпоследовательность. В силу непрерывности $\varphi (х)$, множество $M({{x}_{0}})$ замкнуто, поэтому ${{х}_{*}} \in M({{x}_{0}})$. Покажем, что точка ${{x}_{*}}$ удовлетворяет условию $\varphi ({{x}_{*}}) = \varphi (z({{x}_{*}}))$.

Предположим, что при некотором $\eta > 0$ имеет место $\varphi (z({{x}_{*}})) = \varphi ({{x}_{*}}) - 2\eta $. Поскольку $\varphi (х)$ непрерывна и ${{х}_{*}} \in \operatorname{int} T({{x}_{*}})$, то существуют такие окрестности ${{U}_{\delta }}({{x}_{*}})$ и ${{U}_{\varepsilon }}(z({{x}_{*}}))$, что для любых $х \in {{U}_{\delta }}({{x}_{*}})$ и $y \in {{U}_{\varepsilon }}(z({{x}_{*}}))$ имеет место $\varphi (y) < \varphi (x) - \eta $ и при этом ${{U}_{\delta }}({{x}_{*}}) \subset \operatorname{int} T({{x}_{*}})$. Пусть $\bar {x}$ – произвольная точка из $\Lambda ({{x}_{*}}) \cap \operatorname{int} P({{x}_{*}})$ (в силу выполнения условия, приведенного после изложения алгоритма, такая точка существует), тогда, учитывая, что $\Lambda ({{х}_{*}})$ и $P({{x}_{*}})$ выпуклы и ${{x}_{*}} \in \Lambda ({{x}_{*}}) \cap P({{x}_{*}})$, получим $[\bar {x};{{x}_{*}}) \subset \Lambda ({{х}_{*}}) \cap \operatorname{int} P({{x}_{*}})$, а значит, любая точка из $[\bar {x};{{x}_{*}}) \cap {{U}_{\delta }}({{x}_{*}})$ лежит в $\Lambda ({{x}_{*}}) \cap \operatorname{int} P({{x}_{*}}) \cap \operatorname{int} Т({{х}_{*}})$.

Пусть теперь $\tilde {x}$ – произвольная точка, лежащая в $[\bar {x};{{x}_{*}}) \cap {{U}_{\delta }}({{x}_{*}})$, тогда, поскольку $Т({{х}_{*}})$ выпукло и $z({{x}_{*}}) \in \Lambda ({{x}_{*}}) \cap P({{x}_{*}}) \cap Т({{х}_{*}})$, имеем $[\tilde {x};z({{x}_{*}})) \subset \Lambda ({{x}_{*}}) \cap \operatorname{int} P({{x}_{*}}) \cap \operatorname{int} Т({{х}_{*}})$. Возьмем произвольную точку $h \in [\tilde {x};z({{x}_{*}})) \cap {{U}_{\varepsilon }}(z({{x}_{*}}))$, тогда $h \in \Lambda ({{x}_{*}}) \cap \operatorname{int} P({{x}_{*}}) \cap \operatorname{int} T({{x}_{*}})$ и $\varphi (h) < \varphi (x) - \eta $ для любого $х \in {{U}_{\delta }}({{x}_{*}})$. Обозначив через ${{h}_{k}}$ проекцию точки h на гиперплоскость $\Lambda \,({{x}_{k}})$, получим

где второе слагаемое справа равно нулю, так как ${{h}_{{{{k}_{m}}}}} \in \Lambda ({{x}_{{{{k}_{m}}}}})$, а модуль первого слагаемого есть расстояние от точки h до гиперплоскости $\Lambda ({{x}_{{{{k}_{m}}}}})$, так как векторы $n({{x}_{{{{k}_{m}}}}})$ и $h - {{x}_{{{{k}_{m}}}}}$ имеют одинаковое или противоположное направления и $\left\| {n({{x}_{{{{k}_{m}}}}})} \right\| = 1$.

Поскольку $\left\langle {n({{x}_{*}}),h - {{x}_{*}}} \right\rangle = 0$, так как $h \in \Lambda ({{x}_{*}})$, а $\{ {{x}_{{{{k}_{m}}}}}\} $ сходится к ${{x}_{*}}$, и $n(x)$ является непрерывной вектор-функцией на S, то из сказанного выше следует, что $\left\| {h - {{h}_{{{{k}_{m}}}}}} \right\|\;\xrightarrow[{m \to \infty }]{}\;0$. Кроме этого, существует окрестность ${{U}_{\gamma }}(h)$, целиком лежащая в ${{U}_{\varepsilon }}(z({{x}_{*}})) \cap \operatorname{int} P({{x}_{*}}) \cap \operatorname{int} T({{x}_{*}})$, так как $h \in \operatorname{int} {{U}_{\varepsilon }}(z({{x}_{*}}))$ и $h \in \operatorname{int} P({{x}_{*}}) \cap \operatorname{int} T({{x}_{*}})$, при этом найдется такое ${{m}_{0}} \in N$, что при всех $m \geqslant {{m}_{0}}$ имеет место $\left\| {\,h - {{h}_{{{{k}_{m}}}}}} \right\| < \gamma $. Для произвольного $х \in {{U}_{\gamma }}(h)$, очевидно, справедливы неравенства

В силу сходимости $\{ {{s}^{i}}({{x}_{{{{k}_{m}}}}})\} \;\xrightarrow[{m \to \infty }]{}\;{{s}^{i}}({{x}_{*}})$, вытекающей из сходимости $\{ {{x}_{{{{k}_{m}}}}}\} \;\xrightarrow[{m \to \infty }]{}\;{{x}_{*}}$, и сжимающего свойства оператора проектирования на выпуклые множества ${{G}_{i}}$, $i = 1,2,...,l$, найдется такое ${{m}_{1}} \in N$, что при всех $m \geqslant {{m}_{1}}$ справедливы неравенства Тогда при $m \geqslant \max \left\{ {{{m}_{0}},{{m}_{1}}} \right\}$ получим, что ${{h}_{{{{k}_{m}}}}} \in {{U}_{\gamma }}(h)$ и ${{U}_{\gamma }}(h) \subset P({{x}_{{{{k}_{m}}}}}) \cap T({{x}_{{{{k}_{m}}}}})$. Поскольку $\{ {{x}_{{{{k}_{m}}}}}\} \;\xrightarrow[{m \to \infty }]{}\;{{x}_{*}}$, то найдется такое ${{m}_{2}} \in N$, что при всех $m \geqslant {{m}_{2}}$ имеет место ${{x}_{{{{k}_{m}}}}} \in {{U}_{\delta }}({{x}_{*}})$. Следовательно, при $m \geqslant \max \left\{ {{{m}_{0}},{{m}_{1}},{{m}_{2}}} \right\}$ точки ${{h}_{{{{k}_{m}}}}} \in \Lambda ({{x}_{{{{k}_{m}}}}}) \cap P({{x}_{{{{k}_{m}}}}}) \cap T({{x}_{{{{k}_{m}}}}})$ удовлетворяют условию $\varphi ({{h}_{{{{k}_{m}}}}}) < \varphi ({{x}_{{{{k}_{m}}}}}) - \eta $, или $\varphi ({{x}_{{{{k}_{m}}}}}) - \varphi ({{h}_{{{{k}_{m}}}}}) > \eta $.

Однако в силу утверждения леммы 8, имеет место $\varphi ({{x}_{k}}) - \mathop {\min }\limits_{x \in \Lambda ({{x}_{k}}) \cap P({{x}_{k}}) \cap T({{x}_{k}})} \varphi (x)\;\xrightarrow[{k \to \infty }]{}\;0$. Из полученного противоречия следует, что сделанное предположение о выполнении равенства $\varphi (z({{x}_{*}})) = \varphi ({{x}_{*}}) - 2\eta $ при некотором $\eta > 0$ неверно, а значит, ${{x}_{*}}$ удовлетворяет условию $\varphi ({{x}_{*}}) = \varphi (z({{x}_{*}}))$. В силу произвольности рассмотренной предельной точки ${{x}_{*}}$ последовательности $\left\{ {{{x}_{k}}} \right\}$, утверждение предложения доказано.

Из данного предложения и леммы 7 следует, что если Х задано с помощью функциональных ограничений, то любая предельная точка ${{x}_{*}}$ последовательности $\left\{ {{{x}_{k}}} \right\}$, построенной по изложенному алгоритму при указанном способе выбора ${{\alpha }_{k}},\;k = 0,1,...$, удовлетворяет необходимому условию экстремума в форме Лагранжа, использующей субградиенты.