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

ВВЕДЕНИЕ

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

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

В настоящей работе изучается задача минимизации выпуклой негладкой функции φ(x) на множестве X, представляющем собой теоретико-множественное пересечение гладкой поверхности S произвольного вида и выпуклого компактного множества F. Предлагаемый алгоритм основан на сведении исходной задачи к последовательности задач выпуклого программирования, и его использование требует решать вспомогательные задачи поиска проекций на допустимое множество.

При реализации рассматриваемого в данной работе алгоритма сначала задается начальное приближение ${{x}_{0}} \in X$, после чего на каждой итерации сначала строится касательная гиперплоскость $\Lambda ({{x}_{k}})$ к поверхности S в точке ${{x}_{k}} \in X$ и определяется точка z_k – решение задачи $\varphi (x) \to \min $, $x \in F \cap \Lambda ({{x}_{k}})$. Далее задается число ${{\alpha }_{k}} \in (0;1]$ и определяется проекция на X точки ${{x}_{k}} + {{\alpha }_{k}}({{z}_{k}} - {{x}_{k}})$, которая принимается за следующее приближение ${{x}_{{k + 1}}}$. Задача $\varphi (x) \to \min $, $x \in F \cap \Lambda ({{x}_{k}})$ и задача проектирования точки ${{x}_{k}} + {{\alpha }_{k}}({{z}_{k}} - {{x}_{k}})$ на X в общем случае решаются не однозначно, поэтому данные шаги предполагают нахождение произвольных решений. В настоящей работе показано, что при выполнении некоторых дополнительных условий последовательность $\{ {{x}_{k}}\} \subset X$ сходится к точкам, удовлетворяющим необходимым условиям локального минимума.

В силу выпуклости множеств F и $\Lambda ({{x}_{k}})$ и функции φ(x), задача $\varphi (x) \to \min $, $x \in F \cap \Lambda ({{x}_{k}})$ на практике может быть приближенно решена с помощью одного из итерационных методов выпуклого программирования. При использовании метода проекции субградиента, рассмотренного в [12, с. 281–287], на каждой итерации необходимо вычислять произвольный субградиент функции φ(x) в точке x_k и находить проекцию некоторой точки на выпуклое множество $F \cap \Lambda ({{x}_{k}})$. Если, например, множество F представляет собой замкнутый шар, то названный метод может оказаться наиболее подходящим, так как проекция точки на пересечение шара с гиперплоскостью определяется просто. Если F представляет собой пересечение конечного числа замкнутых полупространств, заданных линейными неравенствами, то задача проектирования точки на $F \cap \Lambda ({{x}_{k}})$ сводится к задаче квадратичного программирования и может быть решена с помощью конечношаговых алгоритмов, поэтому применение метода проекции субградиента также может оказаться целесообразным.

Достаточно сложной является задача нахождения проекции точки на допустимое множество X, которое в общем случае является невыпуклым. В последние годы появились работы, посвященные разработке итерационных алгоритмов нахождения проекции точки на множество вида $\{ x \in F:g(x) = 0\} $, где F – выпуклый компакт, а g(x) удовлетворяет тому или иному условию подчинения. В [13] рассмотрен случай, когда g(x) является липшицевой или гёльдеровой на F. При использовании алгоритма, излагаемого в настоящей работе, на каждой итерации требуется искать проекцию некоторой точки на пересечение выпуклого компакта F с гладкой поверхностью S, которая аналитически задается в виде $\{ x \in {{E}^{n}}:g(x) = 0\} $, где g(x) является гладкой. В силу компактности множества F функция g(x) является липшицевой на нем, поэтому для решения задач проектирования на X может быть использован, например, алгоритм, рассмотренный в [13].

Полезно отметить, что если функция φ(x) является гладкой, то задача ее минимизации на пересечении гладкой поверхности и выпуклого компакта существенно упрощается и для ее решения может быть использован, например, обобщенный метод проекции градиента, предложенный в [9]. Необходимость в решении трудоемких вспомогательных задач проектирования на невыпуклое допустимое множество при реализации указанного метода, однако, остается. Во избежание указанной трудности в случае гладкой функции φ(x) используются также методы непроекционного типа. К числу наиболее распространенных из них относится метод линеаризации, различные варианты которого изучаются, например, в [14]–[18].

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

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

Введем следующие обозначения: $n(x) = g{\kern 1pt} '(x){{\left\| {g{\kern 1pt} '(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) гиперплоскость Λ(x) существует для любого $x \in S$ и вектор-функция n(x) непрерывна на S.

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

Алгоритм

Шаг 0. Полагается k = 0.

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

Шаг 2. Строятся гиперплоскость Λ(x_k) и определяется точка z(x_k) – решение задачи $\varphi (x) \to \min $, $x \in F \cap \Lambda ({{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}})$ на X.

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

Из компактности F, замкнутости Λ(x_k) и непрерывности φ(x), вытекающей из ее выпуклости, следует, что задача $\varphi (x) \to \min $, $x \in F \cap \Lambda ({{x}_{k}})$ имеет хотя бы одно решение. В статье [9] изучена задача минимизации гладкой функции на множестве X рассматриваемого вида и показано, что вспомогательная задача проектирования точки на X также имеет решение. Ниже будет показано, что выполнение равенства φ(x_k) = φ(z(x_k)) при некотором конечном k означает, что x_k удовлетворяет необходимому условию локального минимума φ(x) на X. Это равенство может не выполняться ни при каком k, тогда алгоритм становится итерационным.

В силу компактности F существует ${{d}_{0}} = \mathop {\max }\limits_{x,y \in F} \left\| {x - y} \right\| < \infty $. Введем обозначение $M({{x}_{0}}) = \{ x \in $ $ \in \;X:\varphi (x) \leqslant ({{x}_{0}})\} $, где ${{x}_{0}} \in X$ – выбранное начальное приближение. Пусть $D(x) = \{ y \in $ $ \in \;{{R}^{n}}:\left\| {x - y} \right\| \leqslant 2{{d}_{0}}\} $ – шар радиуса 2d₀ с центром в точке x, а Y – такой выпуклый компакт, что для любого $x \in M({{x}_{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{\kern 1pt} '(x)} \right\| \ne 0$, $x \in S$.

Будем считать, что числа ${{\alpha }_{k}} \in (0;1]$, k = 0, 1, 2, …, выбираются так, что {φ(x_k)} не возрастает (ниже будет рассмотрен вопрос о возможности такого выбора), тогда $\{ {{x}_{k}}\} \subset M({{x}_{0}})$. Поскольку $z({{x}_{k}}) \in Z$, k = 0, 1, 2, …, то при любых ${{\alpha }_{k}} \in (0;1]$ и $k \in \{ 0,1,2, \ldots \} $ произвольная проекция точки ${{x}_{k}} + \alpha (z({{x}_{k}}) - {{x}_{k}})$ на множество X лежит в Y, так как

где первое слагаемое в правой части неравенства равно $\alpha \left\| {z({{x}_{k}}) - {{x}_{k}}} \right\|$ и не превосходит d₀, а второе слагаемое не больше первого, так как ${{x}_{k}} \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\|$. Тогда из показанного в [1] следует, что при N = M/K для всех $x,y \in S \cap Y$ имеет место $\left\| {n(x) - n(y)} \right\| \leqslant N\left\| {x - y} \right\|$.

В статье [9] показано, что функции ${{\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$ и существуют положительные константы ${{\varepsilon }_{1}} = \mathop {\min }\limits_{х \in M({{x}_{0}})} {{\psi }_{1}}(х )$ и ${{\varepsilon }_{2}} = - \mathop {\max }\limits_{х \in M({{x}_{0}})} {{\psi }_{2}}(х )$, а расстояние от произвольной точки $h \in {{E}^{n}}$ до гиперплоскости Λ(x), $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$, для которого $\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 $.

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

Считая $x \in X$, введем обозначения: z(x) – произвольное из решений задачи $\varphi (y) \to \min $, $y \in F \cap \Lambda (x)$; ${{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) на множество X; c_s(x) – решение задачи

при $\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$. Задача $\varphi (y) \to \min $, $y \in F \cap \Lambda (x)$ имеет хотя бы одно решение в силу непрерывности φ(x) и компактности $F \cap \Lambda (x)$, а существование проекций y_s(x) на S и X вытекает из замкнутости этих множеств и показанного в [9]. Существование точки минимума или максимума линейной функции на $F \cap Y$ вытекает из непрерывности этой функции и компактности $F \cap Y$.

Отметим, что если φ(x) не является строго выпуклой, то задача $\varphi (y) \to \min $, $y \in F \cap \Lambda (x)$ может иметь более одного решения. При фиксированных $x \in X$ и $s \in \{ 0,1,2, \ldots \} $ проекции u_s(x) и p_s(x) в общем случае определяются не однозначно, т.к. множества S и X, вообще говоря, не являются выпуклыми. Точка c_s(x) при выбранной проекции u_s(x) тоже может определяться не однозначно, так как она есть точка минимума или максимума линейной функции, не являющейся строго выпуклой или строго вогнутой.

Пусть ${{x}_{*}}$ – произвольная точка множества X, для которой $\varphi (z({{x}_{*}})) < \varphi ({{x}_{*}})$, тогда в силу выпуклости φ(x) вектор ${{h}_{*}} = z({{x}_{*}}) - {{x}_{*}}$ является направлением убывания φ(x) в точке ${{x}_{*}}$. Введем обозначение: ${{L}_{s}}({{x}_{*}})$ – прямая, проходящая через точку ${{y}_{s}}({{x}_{*}})$ перпендикулярно $\Lambda ({{u}_{s}}({{x}_{*}}))$. Справедливы следующие утверждения, доказательство которых проводится аналогично доказательству соответствующих утверждений из [9].

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

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

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

С учетом справедливости вышеприведенных лемм аналогично доказательству соответствующей леммы из [9] доказывается

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

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

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

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

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

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

Заметим, что допустимое множество X рассматриваемого в задаче вида может быть задано с помощью функциональных ограничений в форме

где g(x) является гладкой, а  f_i(x), i = 1, 2, …, l – выпуклыми и гладкими на E ⁿ. В [2] был рассмотрен частный случай, когда равенство g(x) = 0 задает сферическую поверхность.

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

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

Замечание. Положим $f(x) = \max \{ {{f}_{1}}(x),{{f}_{2}}(x), \ldots ,{{f}_{l}}(x)\} $, получим $F = \{ x \in {{E}^{n}}:f(x) \leqslant 0\} $. Тогда неравенства ${{f}_{i}}(x) \leqslant 0$, i = 1, 2, …, l, можно заменить одним неравенством f(x) ≤ 0, где f(x) выпукла на E ⁿ, и нетрудно показать, что если $\operatorname{int} F \cap \Lambda ({{x}_{*}})$ пусто или $\varphi ({{x}_{*}}) = \varphi (z({{x}_{*}}))$, то существуют векторы ${\mathbf{c}} \in \partial \varphi ({{x}_{*}})$ и ${\mathbf{d}} \in \partial f(x)$ и числа ${{\lambda }_{1}} \geqslant 0$ и λ₀, ${{\lambda }_{2}} \in R$, не все равные нулю, при которых ${{\lambda }_{0}}{\mathbf{c}} + {{\lambda }_{1}}{\mathbf{d}} + {{\lambda }_{2}}g{\kern 1pt} '({{x}_{*}}) = {\mathbf{0}}$, ${{\lambda }_{1}}f({{x}_{*}}) = 0$, ${{\lambda }_{2}}g({{x}_{*}}) = 0$.

Поскольку Y выпукло и компактно, то в силу показанного в [19, с. 62] существует такая положительная константа L, что для любых $x,y \in Y$ имеет место $\left| {\varphi (x) - \varphi (y)} \right| \leqslant L\left\| {x - y} \right\|$, т.е. φ(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}})$. Рассмотрим способ выбора чисел α_k, k = 0, 1, 2, …, состоящий в том, что величина α_k при каждом k полагается равной ${{2}^{{ - {{s}_{k}}}}}$, где s_k – первый из номеров s = 0, 1, 2, …, при котором

Покажем, что выбор α_k из указанного условия всегда возможен. Для этого положим, что при некотором $k \in \{ 0,1,2, \ldots \} $ построена точка x_k и φ(z_k) < φ(x_k). Поскольку ${{x}_{k}},{{z}_{k}} \in Y$, то в силу выпуклости Y точки ${{y}_{{k,s}}}$, s = 0, 1, 2, …, лежат в Y и $\varphi ({{x}_{k}}) - \varphi ({{y}_{{k,s}}}) \geqslant {{2}^{{ - s}}}(\varphi ({{x}_{k}}) - \varphi ({{z}_{k}}))$, s = 0, 1, 2, … . Поскольку

то при справедливо включение ${{U}_{\delta }}({{y}_{{k,s}}}) \subset Y$, а значит, для любого $x \in {{U}_{\delta }}({{y}_{{k,s}}})$ имеем В силу леммы 5 и показанного в [1], при всех целых $s \geqslant \bar {s}$, где $\bar {s}$ – некоторый номер из множества {0, 1, 2, …}, имеет место Решая неравенство относительно s, получаем $s > {{\log }_{2}}\frac{{8{{M}_{0}}LNd_{0}^{2}}}{{\varphi ({{x}_{k}}) - \varphi ({{z}_{k}})}}.$ Это означает, что при целых $s \geqslant \bar {s}$, удовлетворяющих полученному условию, имеет место $\varphi ({{p}_{{k,s}}}) \leqslant \varphi ({{x}_{k}}) - \frac{{0.5(\varphi ({{x}_{k}}) - \varphi ({{z}_{k}}))}}{{{{2}^{s}}}}$. Отсюда следует, что при каждом k выполнения последнего неравенства, а значит, и неравенства (3.1) удается добиться при конечном s, т.е. выбор α_k из указанного условия всегда возможен.

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

Доказательство. Пусть α_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 0.5 \cdot {{2}^{{ - s}}}(\varphi ({{x}_{k}}) - \varphi ({{z}_{k}}))$, поэтому

Поскольку то последовательность $\{ \varphi ({{x}_{k}})\} $ не возрастает. Отсюда и из компактности множества X, в котором лежит $\{ {{x}_{k}}\} $, следует, что $\{ \varphi ({{x}_{k}})\} $ ограничена снизу. Следовательно, $\mathop {\lim }\limits_{k \to \infty } [\varphi ({{x}_{k}}) - \varphi ({{x}_{{k + 1}}})] = 0$, а значит, $\frac{{\varphi ({{x}_{k}}) - \varphi ({{z}_{k}})}}{{{{2}^{{{{s}_{k}}}}}}}\;\xrightarrow[{k \to \infty }]{}\;0$. Но из (3.2) имеем откуда $\varphi ({{x}_{k}}) - \varphi ({{z}_{k}})\;\xrightarrow[{k \to \infty }]{}\;0$. Утверждение леммы доказано.

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

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

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

Замечание. Требование ограниченности выпуклого замкнутого множества F в рассматриваемой задаче можно заменить более слабым требованием ограниченности множества M(x₀). Действительно, для произвольного $x \in X$ положим

где d₀ – некоторая положительная константа. Тогда множество T(x) выпукло, компактно и представляет собой n-мерный шар или куб с центром в точке x и при любом $y \in T(x)$ имеет место $\left\| {x - y} \right\| \leqslant {{d}_{0}}$. Принимая в качестве z(x) произвольное из решений задачи $\varphi (y) \to \min $, $y \in F \cap \Lambda (x) \cap T(x)$ и учитывая неравенство $\left\| {x - z(x)} \right\| \leqslant {{d}_{0}}$, справедливое при любом $x \in X$, нетрудно проверить, что все рассуждения, проводимые при изложении вспомогательных утверждений и доказательстве сходимости алгоритма, остаются верными. В силу замкнутости F и Λ(x_k) и компактности T(x_k), задача минимизации φ(x) на $F \cap \Lambda ({{x}_{k}}) \cap T({{x}_{k}})$ на шаге 2 алгоритма при каждом k имеет решение, а из показанного в [9] следует, что решение задачи проектирования на множество $X = F \cap S$ на шаге 5 существует независимо от ограниченности F.