Журнал вычислительной математики и математической физики, 2020, T. 60, № 2, стр. 221-233

1. ПОСТАНОВКА ЗАДАЧИ И ВВЕДЕНИЕ

1.1. На выпуклом замкнутом множестве $Q \times U \subset {{E}^{{n}}} \times {{E}^{{m}}}$ решаем задачу об отыскании седловой точки выпукло-вогнутой функции $\varphi ({\mathbf{x}},{\mathbf{u}})$, выпуклой по ${\mathbf{x}} \in Q \subset {{E}^{{n}}}$ и вогнутой по ${\mathbf{u}} \in U \subset {{E}^{{m}}}$, т.е. об отыскании точки $\left( {{\mathbf{x}}{\text{*}},{\mathbf{u}}{\text{*}}} \right) \in Q \times U$:

Предполагаем: а) множества $Q \subset {{E}^{{n}}}$ и $U \subset {{E}^{{m}}}$ непустые выпуклые замкнутые;

б) функция $\varphi ({\mathbf{x}},{\mathbf{u}})$ с овражными гиперповерхностями уровней определена в окрестности подмножества $W \subset Q \times U \subset {{E}^{{n + m}}}$, для всех фиксированных ${\mathbf{u}} \in U$ функция $g({\mathbf{x}}) = \varphi ({\mathbf{x}},{\mathbf{u}})$ выпукла на $Q \subset {{E}^{{n}}}$, а для каждого фиксированного ${\mathbf{x}} \in Q$ функция $h({\mathbf{u}}) = \varphi ({\mathbf{x}},{\mathbf{u}})$ вогнута на $U \subset {{E}^{{m}}}$; в) множество ${{W}_{*}} = {{Q}_{*}} \times U{\text{*}}$ седловых точек $\left( {{\mathbf{x}}{\text{*}},{\mathbf{u}}{\text{*}}} \right)$ функции $\varphi ({\mathbf{x}},{\mathbf{u}})$ на $W \subset {{E}^{{n + m}}}$ непустое; г) частные градиенты функции $\varphi ({\mathbf{x}},{\mathbf{u}})$ липшицевы на $Q \times U$,

где $L > 0$, ${{L}^{0}} > 0$ – константы Липшица. В терминах оператора проектирования седловая точка $\left( {{\mathbf{x}}{\text{*}},{\mathbf{u}}{\text{*}}} \right) \in {{W}_{*}}$ задачи (1.1) характеризуется равенствами [3] где ${{P}_{Q}}$ и ${{P}_{U}}$ – операторы проектирования соответствующих векторов ${\mathbf{x}} \in {{E}^{{n}}}$ и ${\mathbf{u}} \in {{E}^{{m}}}$ на множества $Q$ и $U$.

1.2. Различные классы экстремальных задач математической физики, оптимального управления, теории игр, математической экономики [1]–[7] приводят к решению задач вида (1.1)–(1.3). Например, вычисления оптимальных решений многих прямых и двойственных задач математического программирования могут быть сведены к отысканию седловых точек соответствующих функций Лагранжа или их модификаций [1]; задача выпуклого программирования (ЗВП)

приводит к эквивалентной (1.1) задаче отыскания седловой точки функции Лагранжа [1]–[5]

Методов  решения седловых задач (1.1) намного меньше, чем методов для задач оптимизации, это отмечено в [6] и других работах. Простейший из итеративных методов решения этой задачи – метод проекции градиента (МПГ) Эрроу–Гурвица ${{{\mathbf{x}}}^{{k + 1}}} = {{P}_{Q}}[{{{\mathbf{x}}}^{k}} - \tau \nabla {{f}_{x}}({{{\mathbf{x}}}^{k}},{{{\mathbf{u}}}^{k}})]$, ${{{\mathbf{u}}}^{{k + 1}}} = {{P}_{U}}[{{{\mathbf{u}}}^{k}} + \tau \nabla {{f}_{u}}({{{\mathbf{x}}}^{k}},{{{\mathbf{u}}}^{k}})]$, $\tau > 0$, $k \geqslant 0.$ Известно, для задачи минимизации $f({\mathbf{x}}) \to {\text{inf}}$, ${\mathbf{x}} \in Q \subset {{E}^{n}}$ на простом множестве $Q$ МПГ сходится, а для задач о точках равновесия сходимость МПГ доказана лишь при весьма ограничительных предположениях сильной выпукло-вогнутости, что не выполняется для многих нужных классов задач, например, функций Лагранжа задач минимизации при ограничениях, других седловых задач [1].

В работах [2] и [3] исследованы методы отыскания седловых точек модифицированной функции Лагранжа. В [4] предложены две модификации экстраградиентного метода (ЭГМ) с линейной скоростью сходимости решения седловой задачи для вогнуто-выпуклой функции $\varphi ({\mathbf{x}},{\mathbf{u}})$. Они требуют соответственно два и три вычисления градиента на каждую итерацию. Формулы лучшего из градиентов имеют вид

Метод имеет преимущества перед МПГ. Для квадратичных задач получена оценка ${{\rho }^{2}}({{{\mathbf{x}}}^{{k + 1}}},{{{\mathbf{u}}}^{{k + 1}}}) \leqslant (1 - mc){{\rho }^{2}}({{{\mathbf{x}}}^{k}},{{{\mathbf{u}}}^{k}})$ скорости сходимости, где константы $m > 0$, $c > 0$, $0 < 1 - mc < 1$, ${{\rho }^{2}}({{{\mathbf{x}}}^{k}},{{{\mathbf{u}}}^{k}}) = {{\left\| {{{{\mathbf{x}}}^{k}} - {\mathbf{x}}{\text{*}}} \right\|}^{2}} + {{\left\| {{{{\mathbf{u}}}^{k}} - {\mathbf{u}}{\text{*}}} \right\|}^{2}}$.

В [5] для решения задачи (1.1) предложен и обоснован, наряду с другими (в том числе и непрерывными), итерационный процесс

и неявный итерационный процесс где ${{P}_{ + }} - $ оператор проектирования на положительный ортант $E_{ + }^{m}$. Доказана сходимость методов к седловой точке задачи (1.1), без оценки скорости сходимости.

Рассматриваемые методы получили дальнейшее развитие в работе [6], где задачи вида (1.1) и многообразие других экстремальных задач и методы их решения обобщены к задачам и методам вычисления неподвижных точек экстремальных отображений.

В [7] предложены и исследованы два новых метода решения седловых и других задач, построенных на основе [8]. Один из них задан итерационными формулами

где $\forall ({{{\mathbf{x}}}^{0}},{{{\mathbf{u}}}^{0}}) \in {{E}^{n}} \times {{E}^{m}}$ – начальная точка; ${{{\mathbf{y}}}^{k}} = {{{\mathbf{x}}}^{k}} - {{{\mathbf{x}}}^{{k - 1}}}$; ${{{\mathbf{v}}}^{k}} = {{{\mathbf{u}}}^{k}} - {{{\mathbf{u}}}^{{k - 1}}}$; ${{{\mathbf{x}}}^{{ - 1}}} = {{{\mathbf{x}}}^{0}}$, ${{{\mathbf{u}}}^{{ - 1}}} = {{{\mathbf{u}}}^{0}}$; ${{\alpha }_{k}}$, ${{\beta }_{k}}$, ${{\lambda }_{k}}$, ${{\gamma }_{{1k}}}$, ${{\gamma }_{{2k}}}$ – положительные параметры метода. Доказана сходимость методов и получены оценки линейной скорости сходимости, без предположения о сильной выпукло-вогнутости. Метод имеет преимущества перед другими в скорости сходимости, но в окрестности седловой точки возможно замедление скорости.

Поскольку методы переменной метрики (МПМ) не характеризуются уменьшением локальной скорости, целью нашей работы является построение для решения задач вида (1.1) проекционного МПМ, по скорости сходимости и точности превосходящего построенные на основе МПГ, и для случая такой задачи, что гиперповерхности уровней функции $\varphi ({\mathbf{x}},{\mathbf{u}})$ имеют овражный характер. Для решения такой задачи исследуем метод, объединяющий достоинства многоточечных (многошаговых) проекционных методов и МПМ.

2. ПРЕДЛАГАЕМЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ

2.1. Для решения задачи (1.1), на основе проекционного обобщенного двухшагового двухэтапного квазиньютоновского метода из работы [9], построим обобщенный двухточечный экстраградиентный квазиньютоновский метод:

где ${{{\mathbf{y}}}^{k}} = {{{\mathbf{x}}}^{k}} - {{{\mathbf{x}}}^{{k - 1}}}$, ${{{\mathbf{v}}}^{k}} = {{{\mathbf{u}}}^{k}} - {{{\mathbf{u}}}^{{k - 1}}}$; $({{{\mathbf{x}}}^{0}},{{{\mathbf{u}}}^{0}}),({{{\mathbf{x}}}^{1}},{{{\mathbf{u}}}^{1}}) \in {{E}^{n}} \times {{E}^{m}} - $ начальные точки такие, что $\varphi ({{{\mathbf{x}}}^{0}},{{{\mathbf{u}}}^{0}}) > \varphi ({{{\mathbf{x}}}^{1}},{{{\mathbf{u}}}^{0}})$, $\varphi ({{{\mathbf{x}}}^{1}},{{{\mathbf{u}}}^{0}}) < \varphi ({{{\mathbf{x}}}^{1}},{{{\mathbf{u}}}^{1}})$; положительные параметры метода ${{\alpha }_{k}}$, ${{\beta }_{k}},$ ${{\lambda }_{k}}$; при каждом фиксированном соответственно ${\mathbf{x}} \in {{E}^{n}}$ ${\mathbf{A}}{\text{(}}{\mathbf{x}}{\text{)}}:{{E}^{n}} \to {{E}^{n}}$ и при каждом фиксированном ${\mathbf{u}} \in {{E}^{m}}$ ${\mathbf{B}}{\text{(}}{\mathbf{u}}{\text{)}}\,:{{E}^{m}} \to {{E}^{m}}$ – положительно-определенные самосопряженные линейные операторы, изменяющие метрику пространства; оператор ${\mathbf{A}}({\mathbf{x}})\,:\;\forall {\mathbf{x}} \in {{E}^{n}}$ (в (2.1) ${{{\mathbf{A}}}_{k}} = {\mathbf{A}}({{{\mathbf{z}}}^{k}})$) таков, что оператор ${\mathbf{B}}({\mathbf{u}})\;\;\forall {\mathbf{u}} \in {{E}^{m}}$ (в (2.1) ${{{\mathbf{B}}}_{k}} = {\mathbf{B}}({{{\mathbf{w}}}^{k}})$) таков, что Обратные операторы таковы, что

Для метода (2.1) характеристики (1.3) седловой точки запишутся в виде

Замечание 1. Отметим следующее: 1) везде в этой работе для простоты обозначено $\nabla {{\varphi }_{x}}$ – частный градиент по первому аргументу, а $\nabla {{\varphi }_{u}}$ – по второму; 2) поскольку в (2.1) операторы проекций в исходной метрике, критерии проекций по первой и второй переменным соответственно будут по первой метрике из (1.1) (см. [10, с. 189]):

(В новой метрике из п. 2.1 критериями проекций служат неравенства но здесь мы пользуемся (2.7), ибо в (2.1) проектирование в исходной метрике.)

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

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

3.1. Лемма 1. Если для (2.1) $\forall {{{\mathbf{u}}}^{k}} \in U \in {{E}^{m}}$ выпуклая функция $g({\mathbf{x}}) \in {{C}^{{1,1}}}(Q)$ такова, что

с учетом (2.4), то

Доказательство. Из (2.1) и критерия (2.7) проекции ${\mathbf{w}} = {{P}_{Q}}({\mathbf{v}})$, ${\mathbf{v}} \in {{E}^{n}}$, следует,

Из (3.2) при ${\mathbf{v}} = {\mathbf{x}}{\text{*}} \in {{Q}_{*}}$ получим (3.1).

3.2. Лемма 2. Если для (2.1) $\forall {{{\mathbf{x}}}^{k}} \in Q \subset {{E}^{n}}$ вогнутая функция $h\left( {\mathbf{u}} \right) \in {{C}^{{1,1}}}(U)$ такова, что

с учетом (2.4), то

Доказательство. Из (2.1) и критерия (2.7) проекции ${\mathbf{w}} = {{P}_{U}}({\mathbf{u}})$, ${\mathbf{u}} \in {{E}^{m}}$, имеем,

Из (3.4) при ${\mathbf{u}} = {\mathbf{u}}{\text{*}}$ следует (см. (3.3))

3.3. Лемма 3. Для всякой тройки точек ${\mathbf{v}},{\mathbf{u}},{\mathbf{x}} \in {{E}^{n}}$ (или ${\mathbf{v}},{\mathbf{u}},{\mathbf{x}} \in {{E}^{m}}$)

где $0 < {{\varepsilon }_{1}} \leqslant \varepsilon \leqslant {{\varepsilon }_{2}}$; есть решение неравенстваэквивалентного (3.5а), тогда ${{l}_{1}} = {{\left\| {{\mathbf{u}} - {\mathbf{v}}} \right\|}^{2}}$, ${{l}_{2}} = {{\left\| {{\mathbf{u}} - {\mathbf{x}}} \right\|}^{2}}$, ${{l}_{3}} = {{\left\| {{\mathbf{v}} - {\mathbf{x}}} \right\|}^{2}}$, $s = {{l}_{1}} + {{l}_{2}} + {{l}_{3}}$.

Доказательство леммы 3 приведено в работе [7].

3.4.

Замечание 2. Верхняя и нижняя границы числа $\varepsilon > 0$ в (3.5а) зависят от соотношений длин сторон треугольника с вершинами ${\mathbf{v}},\;{\mathbf{u}},\;{\mathbf{x}}$; случай их расположения на одной прямой возможен. Пример не обременительных ограничений, при которых допустимы конкретные значения $\varepsilon > 0$ в доказательствах теорем:

Для вычисления границ $\varepsilon > 0$ в (3.5), при ограничении (3.6) решаем эквивалентное (3.5) неравенство вида (3.5б), ${{l}_{3}} \geqslant (\varepsilon - 1){{l}_{3}} - 4(1 - {{\varepsilon }^{{ - 1}}}){{l}_{3}}$, то есть ${{\varepsilon }^{2}} - 6\varepsilon + 4 \leqslant 0$, получаемое при $0.25{{l}_{3}} = {{l}_{1}} = {{l}_{2}}$ в (3.5а). Вычислим ${{\varepsilon }_{{1,2}}} = 3 \mp \sqrt 5 $, ${{\varepsilon }_{1}} = 0.764$, ${{\varepsilon }_{2}} = 5.236$; тогда можно взять приближенное множество допустимых значений $\varepsilon \in [0.8;5.0]$.

3.5. Лемма 4. Для всякой тройки точек ${\mathbf{u}},{\mathbf{v}},{\mathbf{w}} \in {{E}^{n}}$ (или ${\mathbf{u}},{\mathbf{v}},{\mathbf{w}} \in {{E}^{m}}$)

Доказательство приведено в работе [7].

4. ОБОСНОВАНИЕ СХОДИМОСТИ МЕТОДА

Теорема 1. Пусть выполнены: предположения а)–г) из п. 1 о задаче (1.1) и функции $\varphi ({\mathbf{x}},{\mathbf{u}})$, неравенства (2.2)–(2.4), а параметры константы метода (2.1) таковы, что

Тогда найдется седловая точка $\left( {{\mathbf{x}}{\text{*}},{\mathbf{u}}{\text{*}}} \right) \in {{Q}_{*}} \times U{\text{*}}$ функции $\varphi ({\mathbf{x}},{\mathbf{u}})$ такая, что процесс (2.1), (4.1) по норме пространства ${{E}^{n}} \times {{E}^{m}}$ к ней сходится, т.е. ${{{\mathbf{x}}}^{k}} \to {\mathbf{x}}{\text{*}} \in {{Q}_{*}}$, ${{{\mathbf{u}}}^{k}} \to {\mathbf{u}}{\text{*}} \in U{\text{*}}$ при $k \to \infty $ для всех $({{{\mathbf{x}}}^{0}},{{{\mathbf{u}}}^{0}}) \in {{E}^{{n + m}}}$.

Доказательство. Представим каждое уравнение из (2.1), пользуясь (2.7), в виде вариационного неравенства, тогда этот итерационный процесс запишется в виде

(далее обозначаем ${{\alpha }_{k}} = \alpha $, ${{\beta }_{k}} = \beta $, ${{\lambda }_{k}} = \lambda $).

Здесь сначала преобразуем первое и второе неравенства, пользуясь свойствами скалярного произведения, (2.1), неравенством Коши–Буняковского и нерасширяющим свойством оператора проектирования ([10, с. 190]). Положив ${\mathbf{v}} = {{{\mathbf{x}}}^{k}}$, из (4.2) имеем

Положив ${\mathbf{v}} = {\mathbf{x}}{\text{*}}$, из (4.3) получим неравенство

и первое слагаемое в нем выразим с помощью известного тождества тогда Подставим эту оценку в (4.7) и запишем полученное после этого неравенство

В (4.9) сначала преобразуем третье слагаемое в левой части с помощью нерасширяющего свойства оператора проектирования ([10, с. 190]):

где скалярное произведение преобразуем с помощью (4.8): В результате получим и, с его учетом, неравенство (4.9) запишем в виде

В (4.10) оценим скалярное произведение в правой части. Воспользуемся леммой 1 при $g({\mathbf{x}}) = f({\mathbf{x}})$ $\forall {\mathbf{x}} \in {{E}^{n}}$ , ${\mathbf{x}} = {{{\mathbf{z}}}^{k}}$. Представив скалярное произведение в виде суммы, прибавим к слагаемым правое неравенство (3.2), умноженное на два, соответственно при ${\mathbf{v}} = {\mathbf{x}}{\text{*}}$, ${\mathbf{z}} = {{{\mathbf{x}}}^{k}}$ и ${\mathbf{v}} = {{{\mathbf{x}}}^{k}}$, ${\mathbf{z}} = {{{\mathbf{x}}}^{{k + 1}}}$, затем преобразуем с учетом (1.2), (2.1), (2.2), (2.4), (2.5), (3.1), неравенства Коши–Буняковского, правого (3.7) при $\varepsilon = 2$

а также оценки (см. [11, гл. 1, с. 25]):

Второе слагаемое в левой части (4.10) оценим с помощью левого неравенства (3.7) при $\varepsilon = 1{\text{/}}4$, ${\mathbf{v}} = {{{\mathbf{z}}}^{k}}$, ${\mathbf{u}} = {{{\mathbf{x}}}^{{k + 1}}}$, ${\mathbf{w}} = {{{\mathbf{x}}}^{k}}$, затем учтем (4.6):

С учетом (4.11) и (4.12) из (4.10) следует где

Теперь преобразуем (4.4) с помощью нерасширяющего свойства оператора проектирования ([10, с. 190]). При ${\mathbf{u}} = {{{\mathbf{u}}}^{k}}$ из (4.4) следует

Из (4.5) при ${\mathbf{u}} = {\mathbf{u}}{\text{*}}$ имеем

Здесь правую часть представим с учетом леммы 2 при $h({\mathbf{u}}) = g({\mathbf{u}})$ $\forall {\mathbf{u}} \in {{E}^{m}}$ , ${\mathbf{u}} = {{{\mathbf{w}}}^{k}}$ в виде суммы и в первом скалярном произведении воспользуемся неравенством (см. [12, гл. 2, c. 44]) а во втором (см. [10, гл. 2, с. 93; число $R$ из леммы 2]) неравенством: Тогда, приведя подобные, учитывая, что в силу вогнутости $g({\mathbf{u}}{\text{*}}) - g({{{\mathbf{u}}}^{{k + 1}}}) \geqslant 0$, имеем

В (4.15) первое скалярное произведение преобразуем с помощью тождества (4.8):

тогда с учетом (4.16), (4.15) запишется в виде

В (4.17) воспользуемся нерасширяющим свойством оператора проектирования:

где скалярное произведение в правой части преобразуем с помощью тождества (4.8), тогда Второй квадрат нормы в (4.17) преобразуем с учетом левого неравенства (3.7) при $\varepsilon = 1{\text{/}}4$, и (4.14): С учетом этой оценки и (4.18), из (4.17) следует, где

Сложив неравенства (4.13) и (4.19), получим

Просуммируем (4.20) от $k = 1$ до $k = m$, $m \geqslant 1$, тогда

где последние две слагаемые в правой части преобразуем с помощью правого неравенства (3.7) при $\varepsilon = 1$, первое и второе слагаемые из левой части перенесем в правую часть и приведем подобные, первое и второе слагаемые правой части преобразуем с помощью правого неравенства (3.7) при $\varepsilon = 1$: Тогда при $1 - 2\alpha > {{a}_{1}} - {{a}_{2}} > 0$, $0 < {{a}_{1}} - 2\alpha < {{a}_{1}} - {{a}_{2}}$, $0 < {{a}_{5}} - 2\alpha < {{a}_{5}} - {{a}_{6}}$, $0 < \alpha < 1{\text{/}}4$, $0 < \lambda < 2m(3 - 8\alpha ){\text{/}}(3{{L}^{0}}) < 2m{\text{/}}{{L}^{0}}$, условиях (4.1), из (4.21) получаем где ${{a}_{3}} = 2{{a}_{2}} - \alpha $, ${{a}_{4}} = 2{{a}_{2}} + 1$, ${{a}_{7}} = 2{{a}_{6}} - \alpha $, ${{a}_{8}} = 2{{a}_{6}} + 1$.

Из (4.22) при $m \to \infty $ следует сходимость ряда

Следовательно, для (4.22) имеем $\left\| {{{{\mathbf{x}}}^{{k + 1}}} - {{{\mathbf{x}}}^{k}}} \right\| \to 0$, $\left\| {{{{\mathbf{u}}}^{{k + 1}}} - {{{\mathbf{u}}}^{k}}} \right\| \to 0$, $k \to \infty $, последовательность $\left\{ {{{{\left\| {{{{\mathbf{x}}}^{k}} - {\mathbf{x}}{\text{*}}} \right\|}}^{2}} + {{{\left\| {{{{\mathbf{u}}}^{k}} - {\mathbf{u}}{\text{*}}} \right\|}}^{2}}} \right\}$ невозрастающая и ограничена; (4.22) эквивалентно неравенству и по теореме Больцано–Вейерштрасса существует сходящаяся подпоследовательность

Тогда при $k \to \infty $ из второго и четвертого уравнений (2.1) следуют (2.5), (2.6), эквивалентные характеристике (1.3) седловой точки в терминах оператора проектирования; следовательно, $\left( {{\mathbf{x}}{\text{*}};{\mathbf{u}}{\text{*}}} \right)$ – седловая точка функции $\varphi ({\mathbf{x}},{\mathbf{u}})$, т.е. решение задачи (1.1).

Положим , , выберем $\forall \varepsilon > 0$ и числа ${{k}_{{{{i}_{0}}}}} = r$ и $m > r$ так, чтобы выполнялись неравенства

Просуммируем (4.20) от $k = m$ до $k = N$ при , , $N > m > r$:

Здесь третье и четвертое слагаемые в правой части (4.25) с учетом неравенств получаем пятое и шестое слагаемые в левой части (4.25) преобразуем с помощью левого неравенства (3.7) при $\varepsilon = 1{\text{/}}2$:

С учетом этих оценок и неравенств $1 - 2\alpha > 0$, $0 < {{a}_{1}} - 2\alpha < {{a}_{1}} - {{a}_{2}}$, $0 < {{a}_{5}} - 2\alpha < {{a}_{5}} - {{a}_{6}}$, верных при условиях (4.1), из (4.25) получим

Отсюда с учетом (4.23), (4.24), рассуждений и выкладок после (4.21), следует Из этого неравенства и предыдущих рассуждений следует, что вся последовательность $\{ {{{\mathbf{x}}}^{k}};{{{\mathbf{u}}}^{k}}\} $ из любой начальной точки сходится к седловой точке задачи (1.1), , $k \to \infty $, ибо пространство ${{E}^{{n + m}}}$ полное, неравенства (4.24) выполняются для седловой точки $\left( {{\mathbf{x}}{\text{*}};{\mathbf{u}}{\text{*}}} \right) \in {{Q}_{*}} \times U{\text{*}}$ и последовательность $\left\{ {{{{\left\| {{{{\mathbf{x}}}^{k}} - {\mathbf{x}}{\text{*}}} \right\|}}^{2}} + {{{\left\| {{{{\mathbf{u}}}^{k}} - {\mathbf{u}}{\text{*}}} \right\|}}^{2}}} \right\}$ монотонна и ограничена.

Теорема 1 доказана.

Следствие. Поскольку по теореме 1 (расстояние до точки минимума монотонно убывает) последовательность $\{ {{{\mathbf{x}}}^{k}};{{{\mathbf{u}}}^{k}}\} $ сходится монотонно, то имеют место неравенства

5. ОЦЕНКА СКОРОСТИ СХОДИМОСТИ МЕТОДА

Получим оценку скорости сходимости метода (2.1), (4.1) для выпукло-вогнутой функции.

Теорема 2. Пусть выполнены все условия теоремы 1, включая (4.1) и, кроме того:

1) выполнены неравенства (3.6); 2) параметры метода и функции таковы:

Тогда последовательность $\{ {{{\mathbf{x}}}^{k}};{{{\mathbf{u}}}^{k}}\} $ метода (2.1), (4.1) сходится к некоторой седловой точке $\left( {{\mathbf{x}}{\text{*}};{\mathbf{u}}{\text{*}}} \right) \in {{Q}_{*}} \times U{\text{*}}$ задачи (1.1) со скоростью геометрической прогрессии с оценкой

гдепри условиях теоремы.

Доказательство. Заметим, что в условиях теоремы 4 неравенство (4.20) справедливо. Преобразуем его для получения оценки (5.2). Пятое и шестое слагаемые в (4.20) оценим с помощью левого неравенства (3.7); при ${\mathbf{u}} = {{{\mathbf{x}}}^{{k - 1}}}$, ${\mathbf{v}} = {\mathbf{x}}{\text{*}}$, ${\mathbf{w}} = {\mathbf{x}}{\text{*}}$, $\varepsilon = 2$ и ${\mathbf{u}} = {{{\mathbf{u}}}^{{k - 1}}}$, ${\mathbf{v}} = {{{\mathbf{u}}}^{k}}$, ${\mathbf{w}} = {\mathbf{u}}{\text{*}}$, $\varepsilon = 2$ соответственно получим два неравенства:

Аналогично для оценки частей третьего и четвертого слагаемых в левой части (4.20) из (3.5) при ${\mathbf{u}} = {{{\mathbf{x}}}^{{k + 1}}}$, ${\mathbf{x}} = {\mathbf{x}}{\text{*}}$, ${\mathbf{v}} = {{{\mathbf{x}}}^{k}}$, $\varepsilon = 4$ и ${\mathbf{u}} = {{{\mathbf{u}}}^{{k + 1}}}$, ${\mathbf{x}} = {\mathbf{u}}{\text{*}}$, ${\mathbf{v}} = {{{\mathbf{u}}}^{k}}$, $\varepsilon = 4$ соответственно получим два неравенства

После подстановки оценок (5.3), (5.4) в (4.20), придем к неравенству

где

Далее покажем, что

Для доказательства заметим, что в силу следствия теоремы 1 имеем Пользуясь первым неравенством (5.7), неравенствами ${{a}_{{24}}} - 2{{a}_{1}}{\text{/}}3 \leqslant 0$, $({{a}_{{24}}} - 2{{a}_{1}}{\text{/}}3)$ $\left( {{{{\left\| {{{{\mathbf{x}}}^{{k + 1}}} - {{{\mathbf{x}}}^{k}}} \right\|}}^{2}} - {{{\left\| {{{{\mathbf{y}}}^{k}}} \right\|}}^{2}}} \right) \geqslant 0$ (при $0 < \beta < (1 - 4\alpha - 8{{\alpha }^{2}})m{\text{/}}[2L(1 + 4{{\alpha }^{2}})]$, $0 < \alpha < \tfrac{{\sqrt 3 - 1}}{4}$), верными при условиях (5.1), получим первое утверждение из (5.6):

В силу второго неравенства (5.7) и ${{b}_{{24}}} - 2{{a}_{5}}{\text{/}}3 \leqslant 0$ (при $0 < \alpha < \tfrac{{\sqrt 3 - 1}}{4} \cong 0.18$, $0 < \lambda < 2m(1 - 4\alpha - 8{{\alpha }^{2}}){\text{/}}[{{L}^{0}}(1 - 6{{\alpha }^{2}})]$), $\left( {{{b}_{{24}}} - 2{{a}_{5}}{\text{/}}3} \right)\left( {{{{\left\| {{{{\mathbf{u}}}^{{k + 1}}} - {{{\mathbf{u}}}^{k}}} \right\|}}^{2}} - {{{\left\| {{{{\mathbf{v}}}^{k}}} \right\|}}^{2}}} \right) \geqslant 0$, $2{{a}_{5}}{\text{/}}3 \geqslant {{b}_{{24}}} - 2{{a}_{5}}{\text{/}}3$, получим вторую оценку из (5.6):

Подставим оценки (5.6) в (5.5), тогда получим

Учитывая, что ${{a}_{1}} < {{a}_{5}}$, ${{a}_{{23}}} < {{b}_{{23}}}$ при ${{L}^{0}}\lambda < 4L\beta $, в обозначении п. 1 из (5.8) получаем

то есть где Тогда имеем где при ${{a}_{1}} > 0$, ${{b}_{{23}}} > 0$, $48L\beta + 16m\alpha < 6m + 9{{L}^{0}}\lambda $. Здесь с учетом условия ${{L}^{0}}\lambda < 4L\beta $ имеем $48L\beta > 12{{L}^{0}}\lambda $, поэтому $16m\alpha + 12{{L}^{0}}\lambda < 6m + 9{{L}^{0}}\lambda $ или $3{{L}^{0}}\lambda < 6m - 16m\alpha = 2m(3 - 8\alpha )$. Тогда $0 < \lambda < 2m(3 - 8\alpha ){\text{/}}(3{{L}^{0}})$, т.е. выполнено условие для $\lambda $ из теоремы 1. Из (5.9) следует оценка (5.2).

Теорема 2 доказана.

Замечание 3. Исследованный в данной статье проекционный экстраградиентный двухточечный метод (2.1) с переменной метрикой, для решения седловых задач, продолжает на итеративные проекционные методы идею использования операторов переменной метрики, впервые воплощенную в непрерывных проекционных методах минимизации [13].

Метод (2.1) обладает преимуществами, присущими двум классам методов решения оптимизационных задач: многоточечным методам и методам переменной метрики. Он является длинношаговым скоростным методом как многошаговые методы и не теряет скорость сходимости в окрестности седловой точки как квазиньютоновский метод. Нельзя переоценить и неравенство (3.5) в обосновании метода.

Замечание 4. Кратко рассмотрим другие методы по работам [14]–[28]. Прежде всего заметим, что задача (1.1) с помощью нормализованной функции вида $\Phi ({\mathbf{v}},{\mathbf{w}}) = \varphi ({\mathbf{z}},{\mathbf{u}}) - \varphi ({\mathbf{x}},{\mathbf{y}})$, где ${\mathbf{w}} = ({\mathbf{z}},{\mathbf{y}}),$ ${\mathbf{v}} = ({\mathbf{x}},{\mathbf{u}})$, преобразуется в задачу вычисления неподвижной точки экстремального включения

эквивалентную задаче (1.1), и множества решений обоих задач совпадают, так как функция $\Phi ({\mathbf{v}},{\mathbf{w}})$ сепарабельна по переменным ${\mathbf{z}},{\mathbf{y}}$ и выпуклое замкнутое множество $\Omega = Q \times U$ имеет блочную структуру (см., например, работы [6], [21]).

Кроме выше отмеченных, имеются работы, так или иначе связанные с использованием или построением методов решения седловых задач, для недифференцируемых и дифференцируемых функций. Из них неградиентные методы решения седловых задач рассматривались в работе [14]. В работе [15] описан субградиентный алгоритм для решения обобщенной равновесной задачи, частные случаи которой возникают в теории игр, при решении вариационных неравенств, в оптимизационных задачах. Метод решения негладких равновесных задач предложен в [23].

В работах [16], [17] предложены непрерывные проекционные экстраградиентные методы переменной метрики для решения задач равновесного программирования. Доказана сходимость методов. Идея построения непрерывных седловых и равновесных методов переменной метрики восходит к работе [13].

В работах [18]–[23] в целом предложены и исследованы итеративные методы решения задач, приводящих для своего решения к использованию имеющегося или к построению нового метода, для седловой задачи или вычисления неподвижной точки экстремального отображения. Из них в работах [18]–[20] предложены и исследованы двухточечные методы решения седловых задач. Оценки скорости сходимости методов получены в [19] и [20].

В работах [21]–[23] предложены методы типа проекции градиента для решения равновесных задач, из которых в [21] и [22] доказана сходимость методов.

В работах [24]–[28] предложены и исследованы методы решения задач оптимального управления (ЗОУ) сведением к задаче равновесного программирования, последняя решается с помощью экстраградиентных методов. Заслуживают внимания алгоритмы решения задач в них, идею одной из которых опишем для [24].

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