Журнал вычислительной математики и математической физики, 2019, T. 59, № 1, стр. 37-49

ВВЕДЕНИЕ

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

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

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

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

В данной статье предлагается обобщение метода проекции градиента на случай множеств ограничений, представимых в виде пересечения гладкой поверхности S и выпуклого замкнутого множества F. Идея алгоритма состоит в том, что на каждой итерации строится касательная гиперплоскость $\Lambda ({{x}_{k}})$ к поверхности S в точке ${{x}_{k}} \in F \cap S$, после чего определяется точка $z\,({{x}_{k}})$ как решение задачи проектирования точки ${{x}_{k}} - \beta \varphi {\text{'}}({{x}_{k}})$, где $\beta $ – некоторая положительная константа, на $F \cap \,\Lambda \,({{x}_{k}})$. Далее задается число ${{\alpha }_{k}} \in (0\,;\,\,1]$ и определяется произвольная проекция точки ${{x}_{k}} + {{\alpha }_{k}}(z({{x}_{k}}) - {{x}_{k}})$ на $F \cap S$. Найденная проекция принимается за следующее приближение ${{x}_{{k + 1}}}$. В настоящей работе показано, что при выполнении некоторых дополнительных условий последовательность $\left\{ {{{x}_{k}}} \right\}$ сходится к точкам, удовлетворяющим необходимым условиям локального минимума.

Задача проектирования ${{x}_{k}} - \beta \varphi {\kern 1pt} '({{x}_{k}})$ на $F \cap \Lambda ({{x}_{k}})$ в силу выпуклости и замкнутости F и $\Lambda ({{x}_{k}})$ всегда имеет единственное решение, однако его нахождение не всегда является простым. Если, например, F представляет собой шар в ${{E}^{n}}$, то решение данной задачи может быть выписано в явном виде и его получение не вызывает затруднений. Если F представляет собой теоретико-множественное пересечение нескольких полупространств, задаваемых линейными неравенствами, то данная задача равносильна задаче квадратичного программирования и может быть решена с помощью конечношаговых алгоритмов. Если же F имеет более сложную структуру, то решение данной задачи проектирования, как правило, требует привлечения итерационных процедур.

Наиболее сложной является задача отыскания проекции точки ${{x}_{k}} + {{\alpha }_{k}}(z({{x}_{k}}) - {{x}_{k}})$ на невыпуклое множество $F \cap S$. В [15] предлагается итерационный алгоритм проектирования точки на множество вида $\left\{ {x \in A:g(x) = 0} \right\}$, где А – выпуклый компакт, а $g(x)$ является липшицевой или гёльдеровой на А. При использовании метода, излагаемого в данной работе, на каждой итерации требуется проектировать на $F \cap S$ различные точки отрезка $[{{x}_{k}},z({{x}_{k}})]$, при этом расстояние от проектируемой точки до ее проекции не может превосходить величину $\left\| {{{x}_{k}} - z({{x}_{k}})} \right\|$, так как ${{x}_{k}} \in F \cap S$, поэтому в качестве А можно брать замкнутый шар с центром в проектируемой точке и радиусом, не меньшим этой величины. Если $g(x) \in {{C}^{1}}({{Е }^{n}})$, то $g(x)$ на любом компакте является липшицевой, поэтому для приближенного решения задачи проектирования на $F \cap S$ при реализации предлагаемого метода может быть использован алгоритм, рассмотренный в [15]. Использование указанного алгоритма возможно и для приближенного нахождения проекции точки ${{x}_{k}} - \beta \varphi '({{x}_{k}})$ на выпуклое множество $F \cap \Lambda ({{x}_{k}})$, так как гиперплоскость $\Lambda ({{x}_{k}})$ задается линейным равенством.

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

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

Рассмотрим задачу вида $\varphi (x) \to \min ,\;x \in X \subset {{E}^{n}},$ в которой Х непусто и представляет собой теоретико-множественное пересечение выпуклого замкнутого множества F, имеющего непустую внутренность, и поверхности $S = \left\{ {x \in {{E}^{n}}:g(x) = 0} \right\}$, где $g(x) \in {{C}^{1}}({{E}^{n}})$ и $\left\| {g'(x)} \right\| \ne 0$ при любом $x \in S$. Предполагается, что $\varphi (x) \in {{C}^{1}}(Х )$.

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

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

Алгоритм

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

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

Шаг 2. Строятся гиперплоскость $\Lambda ({{x}_{k}})$ и точка $z({{x}_{k}})$.

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

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

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

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

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

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

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

б) касательная гиперплоскость к поверхности S, построенная в произвольной точке $M({{x}_{0}})$, имеет непустое пересечение с $\operatorname{int} F$ (последнее означает, что касательная гиперплоскость не является опорной к F).

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

Пусть $D(x) = \left\{ {y \in {{R}^{n}}:\left\| {x - y} \right\| \leqslant 2{{d}_{0}}} \right\}$ – шар радиуса $2{{d}_{0}}$ с центром в точке х, а Y – такое выпуклое компактное множество, что для любого $x \in М ({{х }_{0}})$ справедливо включение $D(x) \subset 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'(x)} \right\| \ne 0$ при любом $x \in S$. Заметим, что если $x \in М ({{х }_{0}})$, то при любом $\alpha \in (0;1]$ произвольная проекция точки $x + \alpha (z(x) - x)$ на множество Х лежит в Y, поскольку

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

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

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

Из непрерывности $n(x)$ на компакте $S \cap Y$ вытекает непрерывность $\psi (x,y) = \left\langle {n(х ),у - х } \right\rangle $ по $(х ,у )$ на декартовом произведении $S \cap Y$ и $F \cap Y$, a поэтому в силу компактности $F \cap Y$ и показанного в [16, с. 84] функции ${{\psi }_{1}}(x) = \mathop {\max }\limits_{y \in F \cap Y} \left\langle {n(x),y - x} \right\rangle $ и ${{\psi }_{2}}(x) = \mathop {\min }\limits_{y \in F \cap Y} \left\langle {n(x),y - x} \right\rangle $ непрерывны на $S \cap Y$. Поскольку касательная гиперплоскость к S, построенная в произвольной точке множества $M({{x}_{0}})$, имеет непустое пересечение с $\operatorname{int} F \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}}(х )$.

Обозначив через ${{h}_{{\,х }}}$ проекцию точки $h \in {{E}^{n}}$ на гиперплоскость $\Lambda (х )$, $x \in S$, получим $\left\langle {n(x),h - x} \right\rangle = \left\langle {n(x),h - {{h}_{х }}} \right\rangle + \left\langle {n(x),{{h}_{х }} - x} \right\rangle $, где второе слагаемое равно нулю, так как $x,{{h}_{х }} \in \Lambda (x)$ и $n(x)$ ортогонален $\Lambda (х )$, а первое слагаемое c точностью до знака равно расстоянию от ${{h}_{{\,х }}}$ до $\Lambda (х )$, так как векторы $n(x)$ и $h - {{h}_{х }}$ коллинеарны и $\left\| {n(x)} \right\| = 1$. Это означает, что расстояние от точки $h \in {{E}^{n}}$ до гиперплоскости $\Lambda (х )$, $x \in S$, равно $\left| {\left\langle {n(x),h - x} \right\rangle } \right|$.

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\}$, докажем следующее утверждение.

Лемма 1. При любом $x \in S$, для которого

имеет место ${{\psi }_{1}}(x) \geqslant \varepsilon $, ${{\psi }_{2}}(x) \leqslant - \varepsilon $.

Доказательство. Для любых $x,y \in S \cap Y$ и $h \in F \cap Y$ имеет место соотношение

так как $\left\| {h - x} \right\| \leqslant d$, поскольку $h,x \in Y$, и $\left\| {n(y)} \right\| = 1$. Отсюда следует, что если $x,y \in S \cap Y$ и $\left\| {x - y} \right\| \leqslant \frac{\varepsilon }{{Nd + 1}}$, то для любого $h \in F \cap Y$ имеет место $\left| {\left\langle {n(x),h - x} \right\rangle - \left\langle {n(y),h - y} \right\rangle } \right| \leqslant \varepsilon $, откуда вытекает справедливость леммы.

Замечание 1. В силу показанного выше, если ${{х }_{*}} \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,\;...$ Решая относительно s неравенство $\frac{{2{{d}_{0}}}}{{{{2}^{s}}}} \leqslant \frac{\varepsilon }{{Nd + 1}}$, получаем $s \geqslant {{\log }_{2}}\frac{{2{{d}_{0}}(Nd + 1)}}{\varepsilon }$. Отсюда и из леммы 1 следует, что при целых $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,\;...$; ${{u}_{s}}(x)$ – проекция точки ${{y}_{s}}(x)$ на поверхность S; ${{p}_{s}}(x)$ – проекция точки ${{y}_{s}}(x)$ на множество Х; ${{c}_{s}}(х )$ – решение задачи

при $\left\langle {n({{u}_{s}}(x)),{{y}_{s}}(x) - {{u}_{s}}(x)} \right\rangle \geqslant 0$ и задачи при $\left\langle {n({{u}_{s}}(x)),{{y}_{s}}(x) - {{u}_{s}}(x)} \right\rangle < 0$. Отметим, что при фиксированных $х \in Х $ и $s \in \left\{ {0,1,2,\;...} \right\}$ проекции ${{u}_{s}}(x)$ и ${{p}_{s}}(x)$ в общем случае определяются не однозначно, так как множества S и X, вообще говоря, не являются выпуклыми. Точка ${{c}_{s}}(х )$ при выбранной проекции ${{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}}({{х }_{*}})$. С целью сокращения записи в доказательствах приведенных ниже вспомогательных утверждений вместо ${{y}_{s}}({{х }_{*}})$, ${{c}_{s}}({{х }_{*}})$, ${{u}_{s}}({{х }_{*}})$, ${{p}_{s}}({{х }_{*}})$, ${{L}_{s}}({{x}_{*}})$, ${{\tilde {L}}_{s}}({{x}_{*}})$ при фиксированном s будем записывать соответственно у, с, u, р, L, $\tilde {L}$.

Лемма 2. Пусть ${{x}_{*}} \in M({{x}_{0}})$, $s \in \left\{ {0,1,2,\;...} \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)} $.

Доказательство. Поскольку $u,v \in Y$, то в силу показанного в [17, с. 100] имеет место соотношение

Если $v \in S$, то $g(u) = g(v) = 0$, так как $u \in S$, поэтому $\left| {\left\langle {g{\kern 1pt} '(u),v - u} \right\rangle } \right| \leqslant 0.5M{{\left\| {v - u} \right\|}^{2}}$. Обозначив через w проекцию $v$ на $\Lambda (u)$, получим $\left\langle {n(u),v - u} \right\rangle = \left\langle {n(u),v - w} \right\rangle + \left\langle {n(u),w - u} \right\rangle $, где второе слагаемое равно нулю, а первое c точностью до знака совпадает с расстоянием от $v$ до $\Lambda (u)$. Из теоремы Пифагора имеем ${{\left\| {v - u} \right\|}^{2}} = {{\left\| {v - w} \right\|}^{2}} + {{\left\| {w - u} \right\|}^{2}}$. Поскольку то, обозначая через $\bar {v}$ проекцию $v$ на $L$ и учитывая равенства $\delta = \left\| {v - w} \right\| = \left\| {\bar {v} - u} \right\|$ и $\bar {\delta } = \left\| {v - \bar {v}} \right\| = \left\| {w - u} \right\|$, получаем откуда ${{\bar {\delta }}^{2}} \geqslant \frac{{2K}}{M}\,\delta - {{\delta }^{2}} = \delta \,\left( {\frac{{2K}}{M} - \delta } \right)$, т.е. при $\delta \in \left( {0;\frac{{2К }}{М }} \right)$ имеет место $\bar {\delta } \geqslant \sqrt {\delta \left( {\frac{{2K}}{M} - \delta } \right)} $. Лемма доказана.

Замечание 2. Из показанного в [17, с. 275] следует, что при $\alpha \in \left( {0;\frac{2}{M}} \right)$ имеет место $g\left( {u + \alpha g'(u)} \right) > g(u)$ и $g\left( {u - \alpha g'(u)} \right) < g(u)$, поэтому при $\alpha \in \left( {0;\frac{{2К }}{M}} \right)$ получим $g\left( {u + \alpha п (u)} \right) > g(u)$ и $g\,\left( {u - \alpha п (u)} \right) < g(u)$. Отсюда следует, что если точка $v \in Y$ такова, что $\delta \in \left( {0;\frac{{2К }}{М }} \right)$ и $\bar {\delta } < \sqrt {\delta \left( {\frac{{2K}}{M} - \delta } \right)} $, то она не лежит в S и значение $g(v)$ имеет тот же знак, что и $g(\bar {v})$: если $g(v)$ и $g(\bar {v})$ имели бы разные знаки, то в силу непрерывности $g(x)$ на отрезке $[v;\bar {v}]$ существовала бы точка, лежащая в S, что противоречит выполнению неравенства $\bar {\delta } = \left\| {v - \bar {v}} \right\| < \sqrt {\delta \left( {\frac{{2K}}{M} - \delta } \right)} $. Поскольку из показанного в [11] следует, что при $y \notin S$ векторы $y - u$ и $n\,(u)$ имеют одинаковое или противоположное направление, то при $0 < \left\| {y - u} \right\| < \frac{{2K}}{M}$ значение $g(у )$ отлично от нуля. Если y и $v$ лежат по разные стороны от $\Lambda (u)$, то значения $g(у )$ и $g(v)$ имеют разные знаки, если по одну сторону – один знак.

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

Доказательство. Пусть ${{x}_{*}} \in M({{x}_{0}})$ и $s \in \left\{ {0,1,2,\;...} \right\}$. Будем считать, что векторы ${{у }_{s}}({{x}_{*}}) - {{u}_{s}}({{x}_{*}})$ и $п ({{u}_{s}}({{x}_{*}}))$ одинаково направлены. Случай, когда они противоположно направлены, рассматривается аналогично.

Введем обозначения: $\bar {с }$– проекция точки с на прямую L; ${{h}_{\tau }} = y + \tau (c - y)$, $\tau > 0$; $\theta $ – угол между векторами $y - c$ и $\bar {c} - c$ (если с лежит на L, то положим $\theta = \pi {\text{/}}2$). Угол $\theta $ удовлетворяет условиям $0 < \theta \leqslant \pi {\text{/}}2$ и $\operatorname{ctg} \theta \geqslant 0$, а в силу показанного в [12] для любого $\tau > 0$ точка ${{\bar {h}}_{\tau }} = y + \tau (\bar {с } - y)$ является проекцией ${{h}_{\tau }}$ на L, при этом угол $\theta $ равен углу между векторами $y - {{h}_{\tau }}$ и ${{\bar {h}}_{\tau }} - {{h}_{\tau }}$.

Пусть $v$ – произвольная точка множества Y, лежащая на луче $\tilde {L}$. Обозначая $q = \left\| {y - u} \right\|$ и сохраняя в силе введенные ранее обозначения $\delta $ и $\bar {\delta }$, заметим, что если y и $v$ лежат по разные стороны от $\Lambda (u)$, то $\bar {\delta } = (q + \delta )ctg\theta $. В силу показанного выше, при $q < \frac{{2К }}{М }$ имеет место $g(y) > 0$, а при $0 < \delta < \frac{{2K}}{M}$ и $\bar {\delta } < \sqrt {\delta \,\left( {\frac{{2K}}{M} - \delta } \right)} $ имеет место $g(v) < 0$.

Решим относительно $\delta $ неравенство

Проводя преобразования, получаем Дискриминант квадратного относительно $\delta $ уравнения имеет вид При ${{\operatorname{ctg} }^{2}}\theta > \frac{{{{K}^{2}}}}{{{{М }^{2}}{{q}^{2}}}}{{\left( {\frac{{2K}}{{М q}} + 1} \right)}^{{ - 1}}}$ значение D отрицательно и левая часть неравенства (1.1) строго положительна при любом $\delta $, так как $1 + {{\operatorname{ctg} }^{2}}\theta > 0$.

При ${{\operatorname{ctg} }^{2}}\theta \leqslant \frac{{{{K}^{2}}}}{{{{М }^{2}}{{q}^{2}}}}{{\left( {\frac{{2K}}{{М q}} + 1} \right)}^{{ - 1}}}$ значение D неотрицательно, и тогда, решая уравнение (1.2), получаем

Поскольку и ${{q}^{2}}{{\operatorname{ctg} }^{2}}\theta \geqslant 0$, то в силу формул Виета сумма и произведение корней, а значит, и сами корни квадратного уравнения (1.2) неотрицательны, при этом значения большего и меньшего корня не превосходят, соответственно, $\frac{{2К }}{М }$ и $\frac{К }{М }$.

Заметим, что $\left\| {c - \bar {c}} \right\| \leqslant \left\| {c - y} \right\| \leqslant d$, так как $c,y \in F \cap Y$ и $\bar {c}$ – проекция точки с на прямую L, содержащую y. Прямая L перпендикулярна гиперплоскости $\Lambda (u)$, а поскольку $\bar {c}$ – проекция с на L, то расстояния от точек с и $\bar {c}$ до $\Lambda \,(u)$ совпадают и при целых $s \geqslant {{\bar {s}}_{1}}$ (значение ${{\bar {s}}_{1}}$ указано в замечании 1) по величине не меньше $\varepsilon $. Таким образом, $\left\| {y - \bar {c}} \right\| = \left\| {y - u} \right\| + \left\| {u - \bar {c}} \right\| \geqslant \left\| {u - \bar {c}} \right\| \geqslant \varepsilon $, откуда

Рассмотрим неравенство

При $q < \frac{K}{M}$ имеем $\frac{{{{K}^{2}}}}{{М q(2K + М q)}} > \frac{K}{{3М q}}$. Решив относительно q неравенство $\frac{{{{d}^{2}}}}{{{{\varepsilon }^{2}}}} \leqslant \frac{K}{{3Mq}}$, получим $q \leqslant \frac{{K{{\varepsilon }^{2}}}}{{3M{{d}^{2}}}}$. Поскольку $\left\| {c - y} \right\| \leqslant \left\| {c - \bar {c}} \right\| + \left\| {\bar {c} - y} \right\|$, откуда $\varepsilon \leqslant \left\| {\,y - \bar {c}\,} \right\| \leqslant \left\| {\,c - y\,} \right\| \leqslant d$, то $\frac{{K{{\varepsilon }^{2}}}}{{3M{{d}^{2}}}} < \frac{K}{M}$. Отсюда видно, что при $q \leqslant \frac{{K{{\varepsilon }^{2}}}}{{3M{{d}^{2}}}} = \frac{{{{\varepsilon }^{2}}}}{{3N{{d}^{2}}}}$ значение D неотрицательно, а значит, уравнение (1.2) имеет действительные корни. Из показанного в [11] следует, что $q \leqslant \frac{{4Nd_{0}^{2}}}{{{{{({{2}^{s}})}}^{2}}}}$, $s = 0,1,2,\;...$ Решая относительно s неравенство $\frac{{4Nd_{0}^{2}}}{{{{{({{2}^{s}})}}^{2}}}} \leqslant \frac{{{{\varepsilon }^{2}}}}{{3N{{d}^{2}}}}$, получаем $s \geqslant {{\log }_{4}}\frac{{12{{N}^{2}}{{d}^{2}}d_{0}^{2}}}{{{{\varepsilon }^{2}}}} = {{\log }_{2}}\frac{{2\sqrt 3 Nd{{d}_{0}}}}{\varepsilon }$.

Из проведенных рассуждений следует, что если точки y и $v$ лежат по разные стороны от $\Lambda (u)$, причем значение $\delta $, равное расстоянию от $v$ до $\Lambda (u)$, находится в интервале $\left( {{{\delta }_{1}},{{\delta }_{2}}} \right)$, где ${{\delta }_{1}}$ и ${{\delta }_{2}}$ определяются согласно выражениям, приведенным выше, то при целых $s \geqslant \max \left\{ {{{{\bar {s}}}_{1}},{{{\bar {s}}}_{2}}} \right\}$, где ${{\bar {s}}_{2}}$ – наименьший из номеров $s = 0,1,2,\;...$, для которого справедливо последнее неравенство, имеет место $g(v) < 0$. При $q \leqslant \frac{{K{{\varepsilon }^{2}}}}{{3M{{d}^{2}}}}$ в силу неравенства $\frac{{K{{\varepsilon }^{2}}}}{{3M{{d}^{2}}}} < \frac{K}{M}$ и замечания к лемме 2 имеет место $g\,(y) > 0$, а значит, при целых $s \geqslant \max \left\{ {{{{\bar {s}}}_{1}},{{{\bar {s}}}_{2}}} \right\}$ на луче $\tilde {L}$ существует точка, в которой $g(x)$ имеет знак, противоположный знаку $g(у )$. Поскольку в силу показанного выше имеем ${{\delta }_{1}} \leqslant \frac{К }{М }$, то при $\varepsilon \geqslant \frac{К }{М }$ такая точка существует и на отрезке $[y;c]$. Лемма доказана.

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

Доказательство. Пусть ${{x}_{*}} \in M({{x}_{0}})$ и $s \in \left\{ {0,1,2,\,...} \right\}$. Будем считать, что векторы ${{у }_{s}}({{x}_{*}}) - {{u}_{s}}({{x}_{*}})$ и $п ({{u}_{s}}({{x}_{*}}))$ одинаково направлены. Случай, когда они противоположно направлены, рассматривается аналогично.

Все обозначения, использованные в доказательстве предыдущей леммы, остаются в силе. Поскольку

$s \geqslant {{\log }_{2}}2{{d}_{0}}\sqrt {\frac{{N(K - M\varepsilon )}}{{K\varepsilon }}} .$

Отсюда следует, что при целых $s \geqslant \max \left\{ {{{{\bar {s}}}_{1}},{{{\bar {s}}}_{2}},{{{\bar {s}}}_{3}}} \right\}$, где значение ${{\bar {s}}_{1}}$ указано в замечании 1, значение ${{\bar {s}}_{2}}$ – в доказательстве предыдущей леммы, а ${{\bar {s}}_{3}}$ – наименьший из номеров $s = 0,1,2,\;...$, для которого справедливо последнее неравенство, имеет место $g(v) < 0$. В силу показанного ранее, при указанных s имеет место $g\,(y) > 0$. Таким образом, при $s \geqslant \max \left\{ {{{{\bar {s}}}_{1}},{{{\bar {s}}}_{2}},{{{\bar {s}}}_{3}}} \right\}$ на отрезке $[y;c]$ существует точка, в которой $g(x)$ имеет знак, противоположный знаку $g(у )$. Лемма доказана.

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

Доказательство. Пусть ${{x}_{*}} \in M({{x}_{0}})$ и $z({{x}_{*}})$ не совпадают. Если при некотором s точка у лежит на поверхности S, то точки u и p, очевидно, совпадают с у и тогда обе части требуемого нестрогого неравенства равны нулю, т.е. оно справедливо при любом ${{M}_{0}}$. Пусть теперь у не лежит на S. Положим $\bar {s} = \max \left\{ {{{{\bar {s}}}_{1}},{{{\bar {s}}}_{2}}} \right\}$, если $\varepsilon \geqslant \frac{K}{M}$, и $\bar {s} = \max \left\{ {{{{\bar {s}}}_{1}},{{{\bar {s}}}_{2}},{{{\bar {s}}}_{3}}} \right\}$, если $\varepsilon < \frac{K}{M}$. В силу полученных выше результатов при $s \geqslant \bar {s}$ на отрезке $y;c]$ существует точка ${{v}_{0}}$, в которой $g({{v}_{0}}) < 0$. Поскольку при $s \geqslant {{\bar {s}}_{2}}$ имеет место $g(y) > 0$, то в силу непрерывности $g(x)$ на отрезке $[y,{{v}_{0}}]$ существует точка, лежащая на поверхности S. Из полученных ранее результатов следует, что эта точка лежит или по ту же сторону от гиперплоскости $\Lambda (u)$, что и y (в частном случае она может лежать в гиперплоскости), или по другую сторону, на расстоянии, не превосходящем ${{\delta }_{1}}$.

Пусть теперь $v$ – точка пересечения отрезка $[y,{{v}_{0}}]$ с поверхностью S (эта точка, очевидно, удовлетворяет одному из двух указанных условий). Если имеет место первое условие, то $\left\| {y - v} \right\| \leqslant \frac{q}{{\sin \theta }}$, где $\frac{1}{{{{{\sin }}^{2}}\theta }} = 1 + {{\operatorname{ctg} }^{2}}\theta \leqslant \frac{{{{\varepsilon }^{2}} + {{d}^{2}}}}{{{{\varepsilon }^{2}}}}$, а значит, при ${{M}_{0}} = \frac{{\sqrt {{{\varepsilon }^{2}} + {{d}^{2}}} }}{\varepsilon }$ справедливо неравенство $\left\| {y - v} \right\| \leqslant {{M}_{0}}\left\| {y - u} \right\|$. Во втором случае в силу полученных выше результатов имеет место $\bar {\delta } = (q + \delta )ctg\theta \leqslant (q + {{\delta }_{1}})\frac{d}{\varepsilon }$, где ${{\delta }_{1}}$ – некоторое неотрицательное число, удовлетворяющее условию

При выполнении данного неравенства имеем Кроме этого, поэтому т.е. $\left\| {y - v} \right\| \leqslant {{M}_{0}}\left\| {y - u} \right\|$, где ${{M}_{0}} = \frac{3}{\varepsilon }\sqrt {\frac{{К \,({{\varepsilon }^{2}} + {{d}^{2}})}}{M}} $.

Объединяя два возможных случая расположения точек y и $v$ относительно гиперплоскости $\Lambda (u)$, получаем, что при всех целых $s \geqslant \bar {s}$ справедливо неравенство $\left\| {y - v} \right\| \leqslant {{M}_{0}}\left\| {y - u} \right\|$, где

Точки y и с по построению лежат в $F \cap Y$, которое выпукло в силу выпуклости F и Y. Отсюда следует, что $v$ лежит в Х, так как она является точкой пересечения отрезка $[y,c]$, лежащего в F, с поверхностью S. Поскольку p – проекция y на Х и $v \in X$, то $\left\| {y - p} \right\| \leqslant \left\| {y - v} \right\| \leqslant {{M}_{0}}\left\| {y - u} \right\|$, где значение ${{М }_{0}}$ указано выше. В силу произвольности рассмотренной точки ${{x}_{*}} \in M({{x}_{0}})$, не совпадающей с $z({{x}_{*}})$, утверждение леммы доказано.

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

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

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

Доказательство. Пусть ${{x}_{*}} \in M({{x}_{0}})$ – произвольная точка локального минимума $\varphi (х )$ на Х. Предположим, что ${{x}_{*}}$ и $z({{x}_{*}})$ не совпадают. Тогда поскольку ${{x}_{*}} \in F \cap \Lambda ({{x}_{*}})$ и $z({{x}_{*}})$ – проекция точки ${{х }_{*}} - \beta \varphi ({{х }_{*}})$ на выпуклое множество $F \cap \Lambda ({{x}_{*}})$, то

откуда $\left\langle {\varphi {\kern 1pt} '({{х }_{*}}),z({{х }_{*}}) - {{х }_{*}}} \right\rangle < 0$. Это означает, что вектор ${{h}_{*}} = z({{х }_{*}}) - {{х }_{*}}$ является направлением убывания $\varphi (х )$ в точке ${{х }_{*}}$. Это означает, что существует такая окрестность ${{U}_{\delta }}({{h}_{*}})$ и такое число ${{\alpha }_{0}} > 0$, что $\varphi ({{х }_{*}} + \alpha h) < \varphi ({{х }_{*}})$ для всех $h \in {{U}_{\delta }}({{h}_{*}})$ и $\alpha \in (0;{{\alpha }_{0}})$. Отсюда следует, что существует такое $\tilde {s} \in \left\{ {0,1,2,\;...} \right\}$, что для всех $h \in {{U}_{\delta }}({{h}_{*}})$ и всех целых $s \geqslant \tilde {s}$ имеет место $\varphi ({{х }_{*}} + {{2}^{{ - s}}}h) < \varphi ({{х }_{*}})$.

Вектор ${{h}_{*}}$ также является касательным направлением множества S, так как лежит в касательной гиперплоскости к S. Отсюда следует, что

а значит, $\left\| {{{y}_{s}}({{х }_{*}}) - {{u}_{s}}({{х }_{*}})} \right\| \times {{2}^{s}}\;\xrightarrow[{s \to \infty }]{}\;0$. Из леммы 5 следует, что при всех целых $s \geqslant \bar {s}$, где $\bar {s}$ – некоторый номер из множества $\left\{ {0,1,2,\;...} \right\}$, имеет место где ${{M}_{0}}$ – положительная константа, а значит, $\left\| {{{y}_{s}}({{х }_{*}}) - {{р }_{s}}({{х }_{*}})} \right\| \times {{2}^{s}}\;\xrightarrow[{s \to \infty }]{}\;0$. Отсюда и из сказанного выше следует, что при больших s имеет место $\varphi ({{p}_{s}}({{х }_{*}})) < \varphi ({{х }_{*}})$.

Точка ${{p}_{s}}({{х }_{*}})$ при всех $s \in \left\{ {0,1,2,\;...} \right\}$ лежит в Х и $\left\| {{{х }_{*}} - {{p}_{s}}({{х }_{*}})} \right\| = \left\| {{{х }_{*}} - {{y}_{s}}({{х }_{*}})} \right\| + \left\| {{{y}_{s}}({{х }_{*}}) - {{p}_{s}}({{х }_{*}})} \right\|$, при этом

в силу ограниченности $\left\| {{{h}_{*}}} \right\|$ и $\left\| {{{y}_{s}}({{х }_{*}}) - {{p}_{s}}({{х }_{*}})} \right\| \leqslant \left\| {{{х }_{*}} - {{y}_{s}}({{х }_{*}})} \right\|$, так как ${{х }_{*}} \in Х .$ Следовательно, $\left\| {{{x}_{*}} - {{p}_{s}}({{x}_{*}})} \right\|\;\xrightarrow[{s \to \infty }]{}\;0$, т.е. в любой окрестности ${{х }_{*}}$ существует точка $x \in X$, для которой $\varphi (x) < \varphi ({{х }_{*}})$, а значит, ${{х }_{*}}$ не является точкой локального минимума $\varphi (х )$ на Х. Из полученного противоречия следует, что произвольная точка ${{х }_{*}} \in M({{x}_{0}})$ локального минимума $\varphi (х )$ на Х совпадает с точкой $z({{х }_{*}})$. Утверждение леммы доказано.

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

Заметим, что допустимое множество Х рассматриваемого в задаче вида может быть задано с помощью функциональных ограничений в форме $X = \left\{ {x \in {{R}^{n}}:{{f}_{i}}(x) \leqslant 0,i = 1,2,\;...,\;l;g(x) = 0} \right\}$, где $g(x)$ является гладкой, а ${{f}_{i}}(x)$, $i = 1,2,\;...,\;l$ – выпуклыми и гладкими на ${{E}^{n}}$.

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

Доказательство проводится аналогично доказательству соответствующей леммы из [12] с учетом непустоты $\operatorname{int} F \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 $, ${{y}_{{k,s}}} = {{y}_{s}}({{x}_{k}})$, ${{p}_{{k,s}}} = {{p}_{s}}({{x}_{k}})$. Рассмотрим способ выбора чисел ${{\alpha }_{k}}$, $k = 0,1,2,\;...$, состоящий в том, что величина ${{\alpha }_{k}}$ при каждом k полагается равной ${{2}^{{ - {{s}_{k}}}}}$, где ${{s}_{k}}$ – первый из номеров $s = 0,1,2,\;...$, при котором

Покажем, что выбор ${{\alpha }_{k}}$ из указанного условия всегда возможен. Для этого предположим, что при некотором $k \in \{ 0,1,2,\;...\} $ построена точка ${{x}_{k}} \in M({{x}_{0}})$ и ${{z}_{k}}$ не совпадает с ${{x}_{k}}$, т.е. ${{\varphi }_{k}}({{z}_{k}}) < 0$. Поскольку ${{x}_{k}},{{z}_{k}} \in Y$ и $\varphi (x) \in {{C}^{{1,1}}}(Y)$, то из показанного в [18, с. 202] следует, что при $0 < \alpha \leqslant \frac{{\left| {{{\varphi }_{k}}({{z}_{k}})} \right|}}{{2{{L}_{0}}{{{\left\| {{{x}_{k}} - {{z}_{k}}} \right\|}}^{2}}}}$, где ${{L}_{0}}$ – константа Липшица для $\varphi {\kern 1pt} '(x)$ на Y, имеем Поскольку ${{y}_{{k,s}}} \in Y$, то при $\delta = \frac{{0.25\left| {{{\varphi }_{k}}({{z}_{k}})} \right|}}{{{{2}^{s}}L}}$ для любого $x \in {{U}_{\delta }}({{y}_{{k,s}}})$ имеет место $\varphi (x) \leqslant \varphi ({{x}_{k}}) - \frac{{0.25\left| {{{\varphi }_{k}}({{z}_{k}})} \right|}}{{{{2}^{s}}}}$. В силу леммы 5 и показанного в [11] при целых $s \geqslant \bar {s}$ имеет место $\left\| {{{y}_{s}}({{x}_{*}}) - {{p}_{s}}({{x}_{*}})} \right\| \leqslant {{M}_{0}}\left\| {{{y}_{s}}({{x}_{*}}) - {{u}_{s}}({{x}_{*}})} \right\| \leqslant \frac{{4{{M}_{0}}Nd_{0}^{2}}}{{{{{({{2}^{s}})}}^{2}}}}$. Решая неравенство $\frac{{0.\,25\left| {{{\varphi }_{k}}({{z}_{k}})} \right|}}{{{{2}^{s}}L}} > \frac{{4{{M}_{0}}Nd_{0}^{2}}}{{{{{({{2}^{s}})}}^{2}}}}$ относительно s, получаем $s > {{\log }_{2}}\frac{{16{{M}_{0}}LNd_{0}^{2}}}{{\left| {{{\varphi }_{k}}({{z}_{k}})} \right|}}$. Это означает, что при целых $s \geqslant \bar {s}$, удовлетворяющих полученному условию, имеет место $\varphi ({{р }_{{k,s}}}) \leqslant \varphi ({{x}_{k}}) - \frac{{0.25\left| {{{\varphi }_{k}}({{z}_{k}})} \right|}}{{{{2}^{s}}}}$. Отсюда следует, что при каждом k выполнения последнего неравенства, а значит, и неравенства (2.1) удается добиться при конечном s, т.е. выбор ${{\alpha }_{k}}$ из указанного условия всегда возможен.

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

Доказательство. Пусть ${{\alpha }_{k}},k = 0,1,2,\;...$, выбираются согласно указанному способу. Тогда при каждом k в качестве ${{x}_{{k + 1}}}$ берется точка ${{р }_{{k,{{s}_{k}}}}}$, где ${{s}_{k}}$ – наименьшее из чисел $s = 0,1,2,\;...$, удовлетворяющее условию $\varphi ({{x}_{k}}) - \varphi ({{р }_{{k,s}}}) \geqslant \frac{{0.25\left| {{{\varphi }_{k}}({{z}_{k}})} \right|}}{{{{2}^{s}}}}$, поэтому

Поскольку $\varphi ({{x}_{k}}) - \varphi ({{x}_{{k + 1}}}) \geqslant \frac{{0.25\left| {{{\varphi }_{k}}({{z}_{k}})} \right|}}{{{{2}^{{{{s}_{k}}}}}}}$, $k = 0,1,2,\;...$, то последовательность $\left\{ {\varphi ({{x}_{k}})} \right\}$ не возрастает. Отсюда, из непрерывности $\varphi (x)$ и компактности множества $M({{x}_{0}})$, в котором лежит $\left\{ {{{x}_{k}}} \right\}$, следует, что $\left\{ {\varphi ({{x}_{k}})} \right\}$ ограничена снизу. Следовательно, $\mathop {\lim }\limits_{k \to \infty } [\varphi ({{x}_{k}}) - \varphi ({{x}_{{k + 1}}})] = 0$, а значит, $\frac{{\left| {{{\varphi }_{k}}({{z}_{k}})} \right|}}{{{{2}^{{{{s}_{k}}}}}}}\;\xrightarrow[{k \to \infty }]{}\;0$. Но ${{s}_{k}} \leqslant \max \left\{ {\bar {s},{{{\log }}_{2}}\frac{{32{{M}_{0}}LNd_{0}^{2}}}{{\left| {{{\varphi }_{k}}({{z}_{k}})} \right|}}} \right\}$, поэтому откуда ${{\varphi }_{k}}({{z}_{k}})\;\xrightarrow[{k \to \infty }]{}\;0$. Утверждение леммы доказано.

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

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

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

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

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

В тех задачах, где множество Х ограничено и касательная гиперплоскость к S, построенная в произвольной точке Х, имеет непустое пересечение с $\operatorname{int} F$, можно положить ${{d}_{0}} = \beta \mathop {\max }\limits_{x \in Х } \left\| {\varphi '(x)} \right\| < \infty $ и в качестве Y принять такое выпуклое компактное множество, что для любого $x \in Х $ справедливо включение $D(x) \subset Y$, где $D(x)$ – шар радиуса $2{{d}_{0}}$ с центром в точке х. Тогда положив, что $\varphi (х ),g(x) \in {{C}^{{1,1}}}(Y)$, во всех проводимых в данной работе рассуждениях можно заменить $М ({{х }_{0}})$ на Х.