Журнал вычислительной математики и математической физики, 2021, T. 61, № 3, стр. 391-399

ВВЕДЕНИЕ

Один из возможных подходов к решению задачи вида $\varphi (x) \to {\text{min}}$, $x \in X \subset {{E}^{n}}$, в случае гладкой функции $\varphi (x)$ и выпуклого замкнутого множества Х состоит в построении итерационного процесса по правилу

где ${{\alpha }_{k}} \in (0;\;1]$ и ${{\beta }_{k}} \in (0; + \infty )$ – параметры алгоритма. В силу выпуклости и замкнутости Х задача проектирования всегда имеет единственное решение. Если нахождение проекций не требует привлечения трудоемких итерационных процедур, то соответствующий метод решения исходной задачи, называемый методом проекции градиента, может оказаться эффективным.

В [1] изучается одна из модификаций указанного метода для задач с неточно заданными исходными данными. В [2] предлагается подход к решению задач нелинейного программирования, объединяющий идеи метода проекции градиента и метода барьерных функций. В [3] рассмотрен непрерывный вариант метода в пространстве с переменной метрикой для решения задач равновесного программирования. Кроме того, к настоящему времени разработаны модификации метода, предназначенные для решения более сложных вычислительных задач. Например, в [4] на основе метода проекции градиента строится алгоритм нахождения квазирешения нелинейного некорректного операторного уравнения, в [5] исследуется непрерывный аналог метода в пространстве с переменной метрикой для численного решения квазивариационных неравенств, а в [6] рассматривается класс некорректных задач минимизации приближенно заданного гладкого функционала на выпуклом множестве в гильбертовом пространстве. Различные варианты метода проекции градиента и вопросы их сходимости изучаются также в [7]–[9].

Возвращаясь к задаче $\varphi (x) \to {\text{min}}$, $x \in X \subset {{E}^{n}}$, отметим, что в случае невыпуклого допустимого множества Х она существенно усложняется и для ее решения, как правило, приходится использовать иные, более трудоемкие методы. К числу наиболее распространенных из них относятся метод модифицированной функции Лагранжа и метод линеаризации. Однако для некоторых классов задач в последние годы было разработано обобщение метода проекции градиента. Одной из первых по соответствующей тематике является работа [10], где изучен класс допустимых множеств с пустой внутренностью, представляющих собой выпуклые гладкие поверхности. Идея алгоритма, предложенного в [10], лежит в основе алгоритмов, рассматриваемых в [11]–[13] и предназначенных для решения задач с ограничениями более сложного вида. В [11] изучаются допустимые множества, представляющие собой гладкие поверхности общего вида, в [12] – теоретико-множественные пересечения сферической поверхности и выпуклого множества произвольной структуры, в [13] – пересечения гладкой поверхности общего вида и выпуклого множества.

В данной статье рассматривается обобщение метода проекции градиента на случай ограничений, представимых в виде теоретико-множественной разности множества точек гладкой поверхности S и объединения конечного числа выпуклых открытых множеств $\operatorname{int} {{G}_{i}}$, $i = 1,\;2,\; \ldots ,\;l$, где каждое из замкнутых множеств G_i в любой своей граничной точке имеет единственную опорную гиперплоскость. В работе предлагается алгоритм построения итерационной последовательности $\{ {{x}_{k}}\} $ и доказывается, что при выполнении ряда предположений любая ее предельная точка удовлетворяет необходимым условиям локального минимума.

В процессе использования алгоритма на каждой итерации приходится решать вспомогательную задачу проектирования точки ${{x}_{k}} - \beta \varphi {\kern 1pt} '({{x}_{k}})$, $\beta > 0$, на пересечение l замкнутых полупространств, содержащих точку ${{x}_{k}}$, и касательной гиперплоскости к поверхности S, построенной в точке ${{x}_{k}}$. При l = 1 поиск точки z(x_k), являющейся решением этой задачи, осуществляется просто; с ростом l ее поиск усложняется. Однако, поскольку проектирование равносильно минимизации выпуклой квадратичной функции, то соответствующая задача сводится к задаче квадратичного программирования и может быть решена с помощью конечношаговых алгоритмов. Отметим также, что построению каждого из l полупространств предшествует решение вспомогательной задачи проектирования точки ${{x}_{k}}$ на одно из выпуклых замкнутых множеств G_i. Если эти множества имеют простую геометрическую структуру (например, являются шарами), то соответствующие задачи решаются просто; в противном случае поиск проекций усложняется и может потребовать привлечения итерационных процедур.

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

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

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

Рассмотрим задачу вида $\varphi (x) \to \min $, $x \in X \subset {{E}^{n}}$, в которой $\varphi (x) \in {{C}^{1}}(Х)$, а Х непусто и представляет собой теоретико-множественную разность множества точек поверхности $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{\kern 1pt} '(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ⁱ(x) нормали удовлетворяет условию $\left\langle {{{n}^{i}}(x),y - x} \right\rangle \leqslant 0$. Будем полагать, что при каждом i орт nⁱ(x) является непрерывной вектор-функцией на границе $\partial {{G}_{i}}$ множества G_i.

Введем следующие обозначения: $n(x) = g{\kern 1pt} '(x){{\left\| {g{\kern 1pt} '(x)} \right\|}^{{ - 1}}}$ – орт нормали касательной гиперплоскости к поверхности S в точке $x \in S$; $\Lambda (x) = \{ y \in {{E}^{n}}:\left\langle {n(x),y - x} \right\rangle = 0\} $ – касательная гиперплоскость к S в точке $x \in S$; sⁱ(x) – проекция точки х на множество G_i, nⁱ(x) – орт нормали опорной гиперплоскости к G_i в точке sⁱ(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\}$, $P(x) = {{\Gamma }^{1}}(х) \cap {{\Gamma }^{2}}(x) \cap \ldots \cap {{\Gamma }^{l}}(x)$.

В силу гладкости g(x), гиперплоскость $\Lambda (x)$ существует для любого $x \in S$ и вектор-функция n(x) непрерывна на S. Проекции sⁱ(x) при любом $x \in Х$ определяются однозначно, так как ${{G}_{i}},\;i = \overline {1,l} $, являются выпуклыми замкнутыми множествами евклидова пространства Eⁿ. Поскольку каждое из ${{G}_{i}},\;i = \overline {1,l} $, в любой своей граничной точке х имеет только одну опорную гиперплоскость, то векторы nⁱ(x), а значит, и полупространства ${{\Gamma }^{i}}\left( x \right)$, $i = 1,\;2,\; \ldots ,\;l,$ определяются единственным образом для любого $x \in X.$ Поскольку по построению при каждом $i = 1,\;2,\;. \ldots ,\;l$ имеет место $x \in {{\Gamma }^{i}}(x)$, то всегда $x \in P(x)$.

Через z(x) будем обозначать проекцию точки $x - \beta \varphi {\kern 1pt} '(x)$, $x \in Х$, на множество $\Lambda (x) \cap Р(x)$, где β – фиксированное положительное число. В силу выпуклости и замкнутости $\Lambda (x)$ и ${{\Gamma }^{i}}(x)$, $i = 1,\;2,\;. \ldots ,\;l$, проекция z(x) при любом $x \in Х$ определяется однозначно.

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

Шаг 0. Задается β > 0 и полагается k = 0.

Шаг 1. Пусть x_k есть k-е приближение.

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

Шаг 3. Если x_k = z(x_k), то вычисления заканчиваются, иначе осуществляется переход к шагу 4.

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

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

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

Множество S в силу непрерывности $g(x)$ является замкнутым, поэтому, в силу замкнутости ${{\Gamma }^{i}}(x)$, $i = 1,\;2,\;. \ldots ,\;l$, множество $S \cap P({{x}_{k}})$ тоже замкнуто, а значит, задача проектирования на него всегда имеет хотя бы одно решение. Действительно, пусть $\tilde {x} \in {{E}^{n}}$, $y \in S \cap P({{x}_{k}})$ и $Т = \{ x \in {{E}^{n}}:\left\| {x - \tilde {x}} \right\| \leqslant r\} $, где r – произвольное число, не меньшее $\left\| {\tilde {x} - y} \right\|$, тогда каждая проекция точки $\tilde {x}$ на $S \cap P({{x}_{k}})$ является также проекцией на $S \cap P({{x}_{k}}) \cap T$ и наоборот. Но $\psi (x) = \left\| {x - \tilde {x}} \right\|$ непрерывна при любом фиксированном $\tilde {x}$, а значит, в силу компактности $S \cap P({{x}_{k}}) \cap T$, вытекающей из компактности Т и замкнутости $S \cap P({{x}_{k}})$, существует $\mathop {\min }\limits_{x \in S \cap P({{x}_{k}}) \cap T} \left\| {x - \tilde {x}} \right\|$, поэтому задача проектирования $\tilde {x}$ на $S \cap P({{x}_{k}})$ имеет решение.

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

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

2) для любого x ∈ M(x₀) гиперплоскость Λ(x) и множество внутренних точек P(x) имеют непустое пересечение.

Заметим, что если точка x ∈ M(x₀) не принадлежит границе никакого из множеств ${{G}_{i}},\;i = \overline {1,l} $, то $\operatorname{int} P(x) \cap \Lambda (x)$ заведомо непусто, а если точка x ∈ M(x₀) принадлежит границе только одного из множеств ${{G}_{i}},\;i = \overline {1,l} $, то непустота $\operatorname{int} P(x) \cap \Lambda (x)$ означает несовпадение касательной гиперплоскости к поверхности S с опорной гиперплоскостью к соответствующему множеству G_i в этой точке. Если l = 1 или ${{G}_{i}},\;i = \overline {1,l} $, являются попарно непересекающимися, то для любой точки x ∈ M(x₀), очевидно, имеет место один из двух указанных случаев.

В силу непрерывности $\varphi (x)$ и замкнутости Х, вытекающей из замкнутости S и открытости $\operatorname{int} \,{{G}_{i}}$, $i = \overline {1,l} $, множество M(x₀) компактно, при этом в силу непрерывности $\varphi {\kern 1pt} '(x)$ существует ${{d}_{0}} = \beta \mathop {\max }\limits_{x \in M({{x}_{0}})} \left\| {\varphi {\kern 1pt} '(x)} \right\| < \infty $, а в силу сжимающего свойства проектирования на выпуклое множество Λ(x) при любом $x \in M({{x}_{0}})$ имеем $\left\| {x - z(x)} \right\| \leqslant \beta \left\| {\varphi {\kern 1pt} '(x)} \right\| \leqslant {{d}_{0}}$.

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

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

Будем полагать, что g(x) ∈ C^1.1(Y), т.е. существует такая положительная константа М, что для всех x, y ∈ Y справедливо неравенство $\left\| {g{\kern 1pt} '(x) - g{\kern 1pt} '(y)} \right\| \leqslant M\left\| {x - y} \right\|$. Тогда из показанного в [11] следует, что при N = M/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)$ и Λ(x) выпуклы и по построению $х \in Р(х)$ и $х \in \Lambda (х)$. Из определения множества Y следует, что любая точка $(x;h] \cap \operatorname{int} D(x)$ лежит одновременно в Λ(x), в $\operatorname{int} P(x)$ и в $\operatorname{int} Y$. В силу произвольности рассмотренных точек $х \in М({{х}_{0}})$ и $h \in \operatorname{int} P(x) \cap \Lambda (x)$, отсюда вытекает справедливость требуемого утверждения.

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

Справедлива следующая

Лемма 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 ∩ Y.

Доказательство. Докажем непрерывность ${{\psi }_{1}}(x)$; непрерывность ${{\psi }_{2}}(x)$ доказывается аналогично. Пусть ${{x}_{*}}$ – произвольная точка из $S \cap Y$, {x_k} – произвольная последовательность, лежащая в $S \cap Y$ и сходящаяся к ${{x}_{*}}$. Обозначим через y_k (k = 1, 2, …) произвольную точку максимума ${{\xi }_{k}}(y) = \left\langle {n({{x}_{k}}),y - {{x}_{k}}} \right\rangle $ на $Р({{х}_{k}}) \cap Y$. В силу неравенства Коши–Буняковского имеет место $\left| {\left\langle {n(x),y - x} \right\rangle } \right| \leqslant \left\| {n(x)} \right\|\left\| {y - x} \right\| = \left\| {y - x} \right\|$, а поскольку $\{ {{x}_{k}}\} \subset Y$, $\{ {{y}_{k}}\} \subset Y$ и Y ограничено, то $\left\{ {{{\psi }_{1}}({{x}_{k}})} \right\}$ ограничена.

Покажем, что $\mathop {\lim }\limits_{k \to \infty } \,{{\psi }_{1}}({{x}_{k}}) = {{\psi }_{1}}({{x}_{*}})$. Предположим противное, тогда в силу ограниченности $\{ {{\psi }_{1}}({{x}_{k}})\} $ найдется такая подпоследовательность $\{ {{х}_{{{{k}_{m}}}}}\} $, что $\{ {{\psi }_{1}}({{x}_{{{{k}_{m}}}}})\} $ сходится к числу, отличному от ${{\psi }_{1}}({{х}_{*}})$. Множество Y компактно и {y_k} ⊂ Y, поэтому, не ограничивая общности рассуждений, будем считать, что $\{ {{y}_{{{{k}_{m}}}}}\} $ сходится к некоторой точке ${{y}_{*}} \in Y$. Поскольку ${{y}_{k}} \in P({{x}_{k}})$, $k = 1,\;2,\; \ldots ,$ то $\left\langle {{{n}^{i}}({{x}_{k}}),{{y}_{k}} - {{s}^{i}}({{x}_{k}})} \right\rangle \geqslant 0$, $i = 1,\;2,\; \ldots ,\;l$, $k = 1,\;2,\; \ldots $, а тогда, в силу сходимости $\{ {{y}_{{{{k}_{m}}}}}\} $ к ${{y}_{*}}$ и $\{ {{х}_{k}}\} $ к ${{х}_{*}}$, сжимающего свойства оператора проектирования на выпуклые множества G_i, $i = 1,\;2,\; \ldots ,\;l$, и непрерывности nⁱ(x) на $\partial {{G}_{i}}$, имеет место $\left\langle {{{n}^{i}}({{x}_{*}}),{{y}_{*}} - {{s}^{i}}({{x}_{*}})} \right\rangle \geqslant 0$, $i = 1,\;2,\; \ldots ,\;l$, т.е. ${{y}_{*}} \in P({{х}_{*}})$.

Из непрерывности $п(х)$ и сделанного предположения следует, что ${{y}_{*}}$ не является точкой максимума $\xi (y) = \left\langle {n({{x}_{*}}),y - {{x}_{*}}} \right\rangle $ на $Р({{х}_{*}}) \cap Y$, т.е. имеется точка ${{\bar {у}}_{*}} \in Р({{х}_{*}}) \cap Y$, для которой $\xi ({{\bar {у}}_{*}}) > \xi ({{y}_{*}})$. Но тогда найдутся такие окрестности ${{U}_{\delta }}({{x}_{*}})$ и ${{U}_{\varepsilon }}({{\bar {y}}_{*}})$, что для всех $х \in {{U}_{\delta }}({{x}_{*}})$ и $у \in {{U}_{\varepsilon }}({{\bar {y}}_{*}})$ справедливо неравенство $\left\langle {n(x),y - x} \right\rangle > 0.5(\xi ({{\bar {у}}_{*}}) + \xi ({{у}_{*}}))$. Возьмем произвольную точку $h \in \operatorname{int} P({{x}_{*}}) \cap \operatorname{int} Y$ (выше было показано, что такая точка на $\Lambda ({{х}_{*}})$ обязательно существует), тогда в силу выпуклости множества Y и полупространств ${{\Gamma }^{i}}({{x}_{*}})$, $i = 1,\;2,\; \ldots ,\;l$, справедливо включение $({{\bar {y}}_{*}};h] \subset \operatorname{int} Р({{x}_{*}}) \cap \operatorname{int} Y$, а значит, для всех х из $({{\bar {y}}_{*}};h]$ имеем $\left\langle {{{n}^{i}}({{x}_{*}}),х - {{s}^{i}}({{x}_{*}})} \right\rangle > 0$, $i = 1,\;2,\; \ldots ,\;l$. В силу сходимости $\{ {{х}_{k}}\} $ к ${{х}_{*}}$, существует такое k₁ ∈ N, что при всех k ≥ k₁ точка x_k лежит в ${{U}_{\delta }}({{x}_{*}})$, тогда, взяв произвольную точку $\tilde {h} \in ({{\bar {y}}_{*}};h] \cap {{U}_{\varepsilon }}({{\bar {y}}_{*}})$, получим, что при k ≥ k₁ имеет место

Кроме этого, $\left\langle {{{n}^{i}}({{x}_{*}}),\tilde {h} - {{s}^{i}}({{x}_{*}})} \right\rangle > 0$, $i = 1,\;2,\; \ldots ,\;l$, а тогда, в силу сходимости $\{ {{х}_{k}}\} $ к ${{х}_{*}}$ и сжимающего свойства оператора проектирования, найдется такое ${{k}_{2}} \in N$, что при $k \geqslant {{k}_{2}}$ имеет место $\left\langle {{{n}^{i}}({{x}_{k}}),\tilde {h} - {{s}^{i}}({{x}_{k}})} \right\rangle > 0$, $i = 1,\;2,\; \ldots ,\;l$, т.е. $\tilde {h} \in P({{x}_{k}}) \cap Y$.

Поскольку $\xi ({{y}_{*}}) = \left\langle {n({{x}_{*}}),{{y}_{*}} - {{x}_{*}}} \right\rangle $, то в силу непрерывности $п(х)$ и сходимости $\{ {{y}_{{{{k}_{m}}}}}\} $ к ${{y}_{*}}$ и $\{ {{х}_{k}}\} $ к ${{х}_{*}}$ существует такое ${{m}_{0}} \in N$, что при $m \geqslant {{m}_{0}}$ имеем

Отсюда и из вышеприведенных рассуждений следует, что при больших m точка ${{y}_{{{{k}_{m}}}}}$ не доставляет максимум ${{\xi }_{{{{k}_{m}}}}}(y)$ и $Р({{x}_{{{{k}_{m}}}}}) \cap Y$, так как ${{\xi }_{{{{k}_{m}}}}}(\tilde {h}) > {{\xi }_{{{{k}_{m}}}}}({{y}_{{{{k}_{m}}}}})$. Из полученного противоречия следует, что сделанное выше предположение неверно, а значит, $\mathop {\lim }\limits_{k \to \infty } {{\psi }_{1}}({{x}_{k}}) = {{\psi }_{1}}({{x}_{*}})$. В силу произвольности рассмотренной последовательности {x_k}, лежащей в $S \cap Y$ и сходящейся к ${{x}_{*}}$, утверждение леммы доказано.

Замечание 1. Поскольку касательная гиперплоскость к S, построенная в произвольной точке х множества M(x₀), имеет непустое пересечение с $\operatorname{int} Р(х) \cap \operatorname{int} Y$, то при любом фиксированном $х \in M({{x}_{0}})$ имеет место ${{\psi }_{1}}(x) > 0$ и ${{\psi }_{2}}(x) < 0$, поэтому в силу компактности M(x₀) существуют положительные константы ${{\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 \{ {{\varepsilon }_{1}},{{\varepsilon }_{2}}\} $. Ниже приведено утверждение, доказательство которого проводится аналогично доказательству соответствующего утверждения из [13], где в качестве допустимого множества Х рассматривается пересечение гладкой поверхности S и выпуклого замкнутого множества F. Отличие состоит в том, что в проводимых рассуждениях множество F при каждом х заменяется на P(x).

Лемма 2. При любом x ∈ S, для которого $\mathop {\min }\limits_{y \in M({{x}_{0}})} \left\| {x - y} \right\| \leqslant \frac{\varepsilon }{{Nd + 1}}$, имеет место ${{\psi }_{1}}(x) \geqslant \varepsilon $, ${{\psi }_{2}}(x) \leqslant - \varepsilon $.

Замечание 2. В силу показанного выше, если ${{х}_{*}} \in M({{х}_{0}})$, то

$\left\| {{{x}_{*}} - {{{\Pr }}_{S}}({{x}_{*}} + {{2}^{{ - s}}}(z({{x}_{*}}) - {{x}_{*}}))} \right\| \leqslant \frac{{2{{d}_{0}}}}{{{{2}^{s}}}}$,    $s = 0,\;1,\;2,\; \ldots $ .

Решая относительно s неравенство $\frac{{2{{d}_{0}}}}{{{{2}^{s}}}} \leqslant \frac{\varepsilon }{{Nd + 1}}$, получаем $s \geqslant {{\log }_{2}}\frac{{2{{d}_{0}}(Nd + 1)}}{\varepsilon }$. Отсюда и из леммы 2 следует, что при целых $s \geqslant {{\bar {s}}_{1}}$, где ${{\bar {s}}_{1}}$ – наименьший из номеров s = 0, 1, 2, …, при котором выполняется указанное неравенство, имеет место

Считая $х \in Х$, введем обозначения: ${{y}_{s}}(x) = x + {{2}^{{ - s}}}(z(x) - x)$, $s = 0,\;1,\;2,\; \ldots $; u_s(x) – проекция точки y_s(x) на поверхность S; p_s(x) – проекция точки y_s(x) на множество S ∩ P(x); c_s(x) – решение задачи $\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 ∈ {0, 1, 2, …} проекции ${{u}_{s}}(x)$ и ${{p}_{s}}(x)$ в общем случае определяются не однозначно, так как множества S и S ∩ P(x), вообще говоря, не являются выпуклыми. Точка ${{c}_{s}}(x)$ при выбранной проекции ${{u}_{s}}(x)$ тоже может определяться не однозначно, так как она есть точка минимума или максимума линейной функции, не являющейся строго выпуклой или строго вогнутой.

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

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

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

Лемма 4. Если ${{x}_{*}} \in M({{x}_{0}})$, то при всех целых $s \geqslant \max \{ {{\bar {s}}_{1}},{{\bar {s}}_{2}}\} $, где ${{\bar {s}}_{1}}$ и ${{\bar {s}}_{2}}$ – некоторые номера из множества $\left\{ {0,\;1,\;2,\; \ldots } \right\}$, справедливо утверждение: если точка ${{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,\;2,\; \ldots $, удовлетворяющий условию $s \geqslant {{\log }_{2}}\frac{{2\sqrt 3 Nd{{d}_{0}}}}{\varepsilon }$, если $\varepsilon \geqslant \frac{K}{М}$, и условиям $s \geqslant {{\log }_{2}}\frac{{2\sqrt 3 Nd{{d}_{0}}}}{\varepsilon }$ и $s \geqslant {{\log }_{2}}\frac{{2{{d}_{0}}\sqrt {N(K - M\varepsilon )} }}{{\sqrt {K\varepsilon } }}$ одновременно, если $\varepsilon < \frac{K}{М}$.

Лемма 5. Если точки ${{x}_{*}} \in M({{x}_{0}})$ и $z({{x}_{*}})$ не совпадают, то существует такая положительная константа ${{M}_{0}}$, что при всех целых $s \geqslant \bar {s}$, где $\bar {s}$ – некоторый номер из множества $\{ 0,\;1,\;2,\; \ldots \} $, имеет место $\left\| {{{y}_{s}}({{x}_{*}}) - {{p}_{s}}({{x}_{*}})} \right\| \leqslant {{M}_{0}}\left\| {{{y}_{s}}({{x}_{*}}) - {{u}_{s}}({{x}_{*}})} \right\|$.

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

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

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

Лемма 6. Если ${{x}_{*}} \in M({{x}_{0}})$ – точка локального минимума функции $\varphi (x)$ на множестве Х, то $z({{x}_{*}})$ совпадает с ${{x}_{*}}$.

Доказательство проводится аналогично доказательству соответствующей леммы из [13] с заменой множества F при фиксированном ${{x}_{*}} \in M({{x}_{0}})$ на $Р({{х}_{*}})$.

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

Заметим, что множество Х может быть задано с помощью функциональных ограничений в  форме $X = \{ x \in {{E}^{n}}:{{f}_{i}}(x) \leqslant 0,\;i = 1,2, \ldots ,l;\;g(x) = 0\} $, где $g(x)$ является гладкой, а ${{f}_{i}}(x)$, $i = 1,\;2,\; \ldots ,\;l$, – вогнутыми и гладкими на ${{E}^{n}}$ и для каждого $i = 1,\;2,\; \ldots ,\;l$ существует такая точка ${{\tilde {x}}_{i}}$, что $f({{\tilde {x}}_{i}}) > 0$. Тогда ${{G}_{i}} = \{ x \in {{E}^{n}}:{{f}_{i}}(x) \geqslant 0\} $, $i = 1,\;2,\; \ldots ,\;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,\; \ldots ,\;l$. Вводя обозначения ${{F}_{i}} = \{ x \in {{E}^{n}}:{{f}_{i}}(x) \leqslant 0\} $ и $F = \bigcap\nolimits_{i = 1}^l {{{F}_{i}}} $, получим, что $X = \{ x \in F:g(x) = 0\} $, при этом конусы возможных направлений множеств ${{F}_{i}}$ и ${{\Gamma }^{i}}({{x}_{*}})$ для каждого i в произвольной точке ${{х}_{*}} \in Х$ совпадают.

Лемма 7. Если точка ${{x}_{*}} \in M({{x}_{0}})$ совпадает с $z({{x}_{*}})$, то она стационарна в смысле Лагранжа.

Доказательство проводится аналогично доказательству соответствующей леммы из [12] с учетом введенного выше определения точки z(x) и непустоты $\operatorname{int} P(x) \cap \Lambda (x)$ для всех $x \in М({{х}_{0}})$.

Будем  считать,  что   $\varphi (x) \in {{C}^{{1,1}}}(Y)$,  тогда  существует  константа  $L = \mathop {\max }\limits_{x \in Y} \left\| {\varphi {\kern 1pt} '(x)} \right\| < \infty $. Отсюда следует, что для любых $x,y \in Y$ при некотором $\theta \in [0;\;1]$ имеет место $\left| {\varphi (x) - \varphi (y)} \right| = \left\| {\varphi {\kern 1pt} '(x + \theta (y - x))} \right\|\left\| {x - y} \right\| \leqslant L\left\| {x - y} \right\|$, т.е. $\varphi (x)$ является липшицевой на Y.

Введем обозначения: ${{z}_{k}} = z({{x}_{k}})$, ${{\varphi }_{k}}(x) = \left\langle {\varphi {\kern 1pt} '({{x}_{k}}),x - {{x}_{k}}} \right\rangle $, ${{p}_{{k,s}}} = {{p}_{s}}({{x}_{k}})$. Рассмотрим способ выбора чисел ${{\alpha }_{k}}$, $k = 0,\;1,\;2,\; \ldots $, состоящий в том, что величина ${{\alpha }_{k}}$ при каждом k полагается равной ${{2}^{{ - {{s}_{k}}}}}$, где ${{s}_{k}}$ – первый из номеров $s = 0,\;1,\;2,\; \ldots $, при котором $\varphi ({{x}_{k}}) - \varphi ({{р}_{{k,s}}}) \geqslant 0.25 \times {{2}^{{ - s}}}\left| {{{\varphi }_{k}}({{z}_{k}})} \right|$. Аналогично тому, как это было сделано в [13], можно показать, что выбор ${{\alpha }_{k}}$ из указанного условия всегда возможен.

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

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

Лемма 9. Точка $z(x)$ непрерывно зависит от х на множестве $М({{х}_{0}})$.

Доказательство. Пусть ${{x}_{*}}$ – произвольная точка из $М({{х}_{0}})$, а $\{ {{x}_{k}}\} $ – произвольная последовательность, лежащая в $М({{х}_{0}})$ и сходящаяся к ${{x}_{*}}$. Покажем, что последовательность $\{ {{z}_{k}}\} $ сходится к $z({{x}_{*}})$, откуда будет вытекать непрерывность $z(x)$ в точке ${{x}_{*}}$.

Предположим, что $\{ {{z}_{k}}\} $ не сходится к $z({{x}_{*}})$. Тогда поскольку $М({{х}_{0}})$ ограничено и $\left\| {{{x}_{k}} - {{z}_{k}}} \right\| \leqslant {{d}_{0}}$, $k = 0,\;1,\;2,\; \ldots $, то $\{ {{z}_{k}}\} $ тоже ограничена, а значит, существует подпоследовательность $\{ {{z}_{{{{k}_{m}}}}}\} $, сходящаяся к некоторой точке ${{z}_{*}}$, отличной от $z({{x}_{*}})$. Поскольку ${{x}_{k}},{{z}_{k}} \in \Lambda ({{x}_{k}}) \cap P({{x}_{k}})$, $k = 0,\;1,\;2,\; \ldots $, то $\left\langle {n({{x}_{k}}),{{z}_{k}} - {{x}_{k}}} \right\rangle = 0$ и $\left\langle {{{n}^{i}}({{x}_{k}}),{{z}_{k}} - {{s}^{i}}({{x}_{k}})} \right\rangle \geqslant 0$, $i = 1,\;2,\; \ldots ,\;l$, а значит, в силу сходимости $\{ {{x}_{k}}\} $ к ${{x}_{*}}$ и $\{ {{z}_{{{{k}_{m}}}}}\} $ к ${{z}_{*}}$, имеем $\left\langle {n({{x}_{*}}),{{z}_{*}} - {{x}_{*}}} \right\rangle = 0$ и $\left\langle {{{n}^{i}}({{x}_{*}}),{{z}_{*}} - {{s}^{i}}({{x}_{*}})} \right\rangle \geqslant 0$, $i = 1,\;2,\; \ldots ,\;l$, т.е. ${{z}_{*}} \in \Lambda ({{x}_{*}}) \cap P({{x}_{*}})$. Точка $z({{x}_{*}})$ является проекцией ${{x}_{*}} - \beta \varphi {\kern 1pt} '({{x}_{*}})$ на выпуклое множество $Р({{x}_{*}}) \cap \Lambda ({{x}_{*}})$, поэтому $\left\| {{{x}_{*}} - \beta \varphi {\kern 1pt} '({{x}_{*}}) - z({{x}_{*}})} \right\| < \left\| {{{x}_{*}} - \beta \varphi {\kern 1pt} '({{x}_{*}}) - {{z}_{*}}} \right\|$. Тогда, поскольку ${{x}_{{{{k}_{m}}}}}\;\xrightarrow[{m \to \infty }]{}\;{{x}_{*}}$, ${{z}_{{{{k}_{m}}}}}\;\xrightarrow[{m \to \infty }]{}\;{{z}_{*}}$, то существуют такое ${{m}_{1}} \in N$ и такая окрестность ${{U}_{\delta }}(z({{x}_{*}}))$, что при $m \geqslant {{m}_{1}}$ для всех $х \in {{U}_{\delta }}(z({{x}_{*}}))$ справедливо неравенство $\left\| {{{x}_{{{{k}_{m}}}}} - \beta \varphi {\kern 1pt} '({{x}_{{{{k}_{m}}}}}) - x} \right\| < \left\| {{{x}_{{{{k}_{m}}}}} - \beta \varphi {\kern 1pt} '({{x}_{{{{k}_{m}}}}}) - {{z}_{{{{k}_{m}}}}}} \right\|$.

Пусть $\bar {х}$ – произвольная точка из $\operatorname{int} Р({{x}_{*}}) \cap \Lambda ({{x}_{*}})$, тогда $(z({{x}_{*}}),\bar {x}] \subset \operatorname{int} Р({{x}_{*}}) \cap \Lambda ({{x}_{*}})$ в силу выпуклости $Р({{x}_{*}})$ и $\Lambda ({{x}_{*}})$. Возьмем произвольную точку $h \in (z({{x}_{*}}),\bar {x}] \cap {{U}_{\delta }}(z({{x}_{*}}))$, тогда найдется окрестность ${{U}_{\varepsilon }}(h)$, целиком лежащая в ${{U}_{\delta }}(z({{x}_{*}})) \cap \operatorname{int} Р({{x}_{*}})$, поскольку ${{U}_{\delta }}(z({{x}_{*}}))$ является открытым шаром и $h \in {{U}_{\delta }}(z({{x}_{*}})) \cap \operatorname{int} Р({{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}}}}}\} \;\xrightarrow[{m \to \infty }]{}\;{{x}_{*}}$, a $n(x)$ является непрерывной вектор-функцией на S, то это означает, что $\left\langle {n({{x}_{{{{k}_{m}}}}}),h - {{x}_{{{{k}_{m}}}}}} \right\rangle \;\xrightarrow[{m \to \infty }]{}\;0$, откуда $\left\| {h - {{h}_{{{{k}_{m}}}}}} \right\|\;\xrightarrow[{m \to \infty }]{}\;0$. Окрестность ${{U}_{\varepsilon }}(h)$ целиком лежит в $\operatorname{int} \,P({{x}_{*}})$, а значит, для всех $х \in {{U}_{\varepsilon }}(h)$ имеет место $\left\langle {{{n}^{i}}({{x}_{*}}),х - {{s}^{i}}({{x}_{*}})} \right\rangle > 0$, $i = 1,\;2,\; \ldots ,\;l$. Но тогда из сходимости $\{ {{x}_{{{{k}_{m}}}}}\} \;\xrightarrow[{m \to \infty }]{}\;{{x}_{*}}$ и сжимающего свойства оператора проектирования на выпуклые множества следует, что найдется такое ${{m}_{2}} \in N$, что при всех $m \geqslant {{m}_{2}}$ справедливы неравенства $\left\| {h - {{h}_{{{{k}_{m}}}}}} \right\| < \varepsilon $ и $\left\langle {{{n}^{i}}({{x}_{{{{k}_{m}}}}}),{{h}_{{{{k}_{m}}}}} - {{s}^{i}}({{x}_{{{{k}_{m}}}}})} \right\rangle > 0$, $i = 1,\;2,\; \ldots ,\;l$, т.е. ${{h}_{{{{k}_{m}}}}} \in {{U}_{\varepsilon }}(h) \cap P({{x}_{{{{k}_{m}}}}})$. Окрестность ${{U}_{\varepsilon }}(h)$ целиком лежит в ${{U}_{\delta }}(z({{x}_{*}}))$, поэтому при $m \geqslant \max \left\{ {{{m}_{1}},{{m}_{2}}} \right\}$ имеем $\left\| {{{x}_{{{{k}_{m}}}}} - \beta \varphi {\kern 1pt} '({{x}_{{{{k}_{m}}}}}) - {{h}_{{{{k}_{m}}}}}} \right\| < \left\| {{{x}_{{{{k}_{m}}}}} - \beta \varphi {\kern 1pt} '({{x}_{{{{k}_{m}}}}}) - {{z}_{{{{k}_{m}}}}}} \right\|$, где ${{h}_{{{{k}_{m}}}}} \in P({{x}_{{{{k}_{m}}}}}) \cap \Lambda ({{x}_{{{{k}_{m}}}}})$.

Поскольку ${{z}_{k}}$ – проекция ${{x}_{k}} - \beta \varphi {\kern 1pt} '({{x}_{k}})$ на $P({{x}_{k}}) \cap \Lambda ({{x}_{k}})$ при $k = 0,\;1,\;2,\; \ldots $, то выполнение последнего неравенства невозможно. Из полученного противоречия следует, что ${{z}_{*}}$ совпадает с $z({{x}_{*}})$, а значит, $\left\{ {{{z}_{k}}} \right\}$ сходится к $z({{x}_{*}})$. В силу произвольности рассмотренной точки ${{x}_{*}} \in M({{x}_{0}})$ и последовательности $\{ {{x}_{k}}\} $, лежащей в $M({{x}_{0}})$ и сходящейся к ${{x}_{*}}$, утверждение леммы доказано.

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

Доказательство. Поскольку $\{ {{x}_{k}}\} \subset М({{х}_{0}})$ и $М({{х}_{0}})$ ограничено, то $\{ {{x}_{k}}\} $ имеет хотя бы одну предельную точку. Пусть ${{x}_{*}}$ – произвольная предельная точка, а $\{ {{x}_{{{{k}_{m}}}}}\} $ – соответствующая ей подпоследовательность.

Покажем, что ${{x}_{*}}$ совпадает с $z({{x}_{*}})$. Из леммы 8 имеем $\mathop {\lim }\limits_{m \to \infty } \left\langle {\varphi {\kern 1pt} '({{x}_{{{{k}_{m}}}}}),z({{x}_{{{{k}_{m}}}}}) - {{x}_{{{{k}_{m}}}}}} \right\rangle = 0$, а значит, $\left\langle {{{\varphi }^{/}}({{x}_{*}}),z({{x}_{*}}) - {{x}_{*}}} \right\rangle = 0$, так как ${{x}_{{{{k}_{m}}}}}\;\xrightarrow[{m \to \infty }]{}\;{{x}_{*}}$ и из леммы 9 следует, что $z({{x}_{{{{k}_{m}}}}})\;\xrightarrow[{m \to \infty }]{}\;z({{x}_{*}})$. Поскольку $z({{x}_{*}})$ – проекция точки ${{x}_{*}} - \beta \varphi {\kern 1pt} '({{x}_{*}})$ на выпуклое множество $Р({{x}_{*}}) \cap \Lambda ({{x}_{*}})$ и при этом ${{x}_{*}} \in Р({{x}_{*}}) \cap \Lambda ({{x}_{*}})$, то

где $\left\langle {\varphi {\kern 1pt} '({{x}_{*}}),z({{x}_{*}}) - {{x}_{*}}} \right\rangle = 0$, а значит, ${{x}_{{\,*}}}$ совпадает с $z({{x}_{*}})$. В силу произвольности рассмотренной предельной точки ${{x}_{*}}$ последовательности $\{ {{x}_{k}}\} $, утверждение предложения доказано.

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