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

1. ВВЕДЕНИЕ

1.1. Известны множество методов оптимизации и меньшее число методов для решения седловых задач (см. [1]–[11]); последние предназначены для отыскания седловых точек или точек равновесия. Напомним, точку (x*, u*) ∈ Q × U ⊂ Eⁿ × E^m, называют седловой точкой всякой функции φ(x, u), ${\mathbf{x}} \in Q \subset {{E}^{n}}$, ${\mathbf{u}} \in U \subset {{E}^{m}}$, с непустыми множествами $Q \subset {{E}^{n}}$, $U \subset {{E}^{m}}$, в евклидовых пространствах ${{E}^{n}}$ и ${{E}^{m}}$, если эта точка есть решение системы неравенств:

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

В работах [3], [10] детально рассмотрены применения седловых методов, в [10] седловые задачи охарактеризованы “как мостик, через который можно попытаться перенести развитую технику решения задач оптимизации для решения игровых задач”, исследованы управляемые (обратными связями по производной, по невязке и смешанными) НПМОСТ второго порядка. Разработана методика преобразования седловых задач и методов к равновесным. В [11] построены и изучены не исследованные в [10] равновесные методы второго порядка на основе управляемого (дифференциального) НПМОСТ второго порядка. В [3] исследовано, наряду с другими, несколько перспективных игровых равновесных методов. Здесь предлагается и исследуется базовый НПМОСТ второго порядка с переменной метрикой, на основе которого можно построить частные методы решения конкретных случаев седловых и равновесных задач в перечисленных науках.

Рассматриваемые НПМОСТ соответствуют задаче Коши для обыкновенных дифференциальных уравнений (ОДУ), описывающих динамические процессы. Существенно одно из благоприятных свойств дифференциальных моделей — возможность использования численных методов вычислительной математики, для решения ОДУ в алгоритмах численной реализации НПМОСТ и НПММ [3]–[6].

Седловые задачи для конкретных математических моделей решаются при своих требованиях (к пространствам, множествам и функциям), выражающихся в постановке задачи и влияющих на метод ее решения. В этой работе предлагается и исследуется НПМОСТ для решения задачи в следующей постановке.

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

2.1. Предлагается для решения задачи (1.1)–(1.3) НПОЭКМС второго порядка, обычно записываемый в виде задачи Коши для системы ОДУ:

где функции $\alpha (t) \in {{C}^{2}}[0,\infty ),\beta (t),\gamma (t),\sigma (t)$, $\theta (t) \in {{C}^{1}}[0,\infty ),$ — положительные параметры метода, таковы, что $\mathop {\lim }\limits_{t \to \infty } \alpha (t) = {{\alpha }_{0}}$, $\mathop {\lim }\limits_{t \to \infty } \beta (t) = {{\beta }_{0}}$, $\mathop {\lim }\limits_{t \to \infty } \gamma (t) = {{\gamma }_{0}} > 0$; $\mathop {\lim }\limits_{t \to \infty } \sigma (t) = {{\sigma }_{0}} > 0$, $\mathop {\lim }\limits_{t \to \infty } \theta (t) = {{\theta }_{0}} > 0$, $\alpha (t) \geqslant {{\alpha }_{0}}$ > 0, $1 > \beta (t) > 0$, $1 > \sigma (t) > 0$, $1 > \theta (t) > {{\theta }_{0}} > 0$; $\alpha {\kern 1pt} '(t) < 0$, $\beta {\kern 1pt} '(t) < 0$, $\sigma {\kern 1pt} '(t) < 0$, $\gamma {\kern 1pt} '(t) < 0$, $\theta {\kern 1pt} '(t) < 0$, $\alpha {\kern 1pt} ''(t) > 0$.

В частности, этим условиям удовлетворяют такие параметры−функции НПОЭКМС (2.1): $\alpha (t) = {{\alpha }_{0}} + \tfrac{1}{{1 + t}}$, $\beta (t) = {{\beta }_{0}} + \frac{1}{{2 + t}}$, $\gamma (t) = {{\gamma }_{0}} + \frac{1}{{3 + t}}$, $\lambda (t) = {{\lambda }_{0}} + \frac{1}{{3 + t}}$, $\sigma (t) = {{\sigma }_{0}} + \frac{1}{{t + 1}}$, $\theta (t) = {{\theta }_{0}} + \frac{1}{{t + 1}}$.

Операторы ${\mathbf{B}}({\mathbf{x}}):{{E}^{n}} \to {{E}^{n}}$ $\forall {\mathbf{x}} \in {{E}^{n}}$ фиксированного и ${\mathbf{G}}({\mathbf{u}}):{{E}^{m}} \to {{E}^{m}}$ $\forall {\mathbf{u}} \in {{E}^{m}}$ фиксированного — положительно-определенные самосопряженные линейные, изменяющие метрику пространства; они в (2.1) таковы, что

Обратные операторы таковы, что

2.2. Для метода (2.1)−(2.4) характеристики вида (1.3) седловой точки $\left( {{\mathbf{x}}*,{\mathbf{u}}{\kern 1pt} *} \right)$ имеют следующий вид:

2.3. Замечание. Отметим следующее.

1. В этой работе для простоты обозначены через $\nabla {{\varphi }_{x}}$ − частный градиент по первому аргументу, а $\nabla {{\varphi }_{u}}$ – по второму.

2. Поскольку в (2.1) операторы проектирования в исходной метрике, критерии проекций ${\mathbf{w}} = {{P}_{Q}}({\mathbf{v}})$ по первой и ${\mathbf{s}} = {{P}_{U}}({\mathbf{v}})$ по второй переменным будут по исходной метрике (см. [8, с. 189]):

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

3. Имеются и непрерывные, и итеративные, проекционные методы с операторами проектирования: ${{P}_{Q}}(.)$, ${{P}_{U}}(.)$ – в исходной метрике; $P_{Q}^{{{\mathbf{G}}({\mathbf{v}}(t))}}$, $P_{U}^{{{\mathbf{G}}({\mathbf{u}}(t))}}$ – в новой метрике.

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

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

3.1. Лемма 1. Если для (2.1) при любом фиксированном ${\mathbf{u}} \in U \in {{E}^{m}}$ выпуклая функция ${{g}_{1}}\left( {\mathbf{x}} \right) \in {{C}^{{1,1}}}(Q)$ такова, что $\nabla {{g}_{1}}({\mathbf{x}}) = {{{\mathbf{B}}}^{{ - 1}}}({\mathbf{x}})\nabla {{\varphi }_{x}}\left( {{\mathbf{x}},{\mathbf{u}}} \right)$,

то

Доказательство. Из характеристического свойства (2.5) седловой точки, критерия проекции ${\mathbf{w}} = {{P}_{Q}}({\mathbf{v}})$, ${\mathbf{v}} \in {{H}_{Q}}$ из (2.7), и равенства из условия леммы 1, имеем

$\gamma > 0$, ${\mathbf{x}} \in Q$. Из правого неравенства (3.1а) получим (3.1).

3.2. Лемма 2. Если для (2.1) при любом фиксированном ${\mathbf{x}} \in Q \subset {{E}^{n}}$ вогнутая функция ${{h}_{1}}\left( {\mathbf{u}} \right) \in {{C}^{{1,1}}}(U)$ такова, что $\nabla {{h}_{1}}\left( {\mathbf{u}} \right)$ = ${{{\mathbf{G}}}^{{ - 1}}}({\mathbf{u}})\nabla {{\varphi }_{u}}\left( {{\mathbf{x}},{\mathbf{u}}} \right)$,

то

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

4. ОБОСНОВАНИЕ СХОДИМОСТИ НПОЭКМС (2.1)

Теорема 1. Пусть выполнены предположения а)−г) о задаче и функции $\varphi ({\mathbf{x}},{\mathbf{u}})$ из разд.1 и функциях-параметрах из п. 2.1; неравенства (2.2)−(2.7); леммы 1 и 2; параметры метода (2.1), функции $\alpha (t),\beta (t),\gamma (t),\sigma (t),\theta (t)$ таковы, что

Тогда НПОЭКМС (2.1), (4.1) $\forall \left( {{{{\mathbf{x}}}^{0}},{{{\mathbf{u}}}^{0}}} \right) \in {{E}^{n}} \times {{E}^{m}}$ по норме сходится к седловой точке $\left( {{\mathbf{x}}*,{\mathbf{u}}{\kern 1pt} *} \right)$ ∈ ∈ ${{Q}_{*}} \times U{\kern 1pt} *$ функции $\varphi ({\mathbf{x}},{\mathbf{u}})$,

т.е. ${{{\mathbf{x}}}^{k}} \to {\mathbf{x}}* \in {{Q}_{*}}$, ${{{\mathbf{u}}}^{k}} \to {\mathbf{u}}* \in U{\kern 1pt} *$ при $k \to \infty $.

Доказательство. Представим первые два уравнения НПОЭКМС (2.1), пользуясь (2.7), в виде вариационных неравенств

где ${\mathbf{w}}(t)$ = $\alpha (t){\mathbf{x}}{\kern 1pt} ''(t) + \beta (t){\mathbf{x}}{\kern 1pt} '(t) + {\mathbf{x}}(t) \in Q$, ${\mathbf{s}}(t) = \alpha (t){\mathbf{u}}{\kern 1pt} ''\; + \beta (t){\mathbf{u}}{\kern 1pt} '\; + {\mathbf{u}} \in U$.

Неравенства (4.4) преобразуем, пользуясь свойствами скалярного произведения, неравенством Коши–Буняковского, нерасширяющим свойством оператора проектирования (см. [8, с. 190]), а также (2.1), (4.1), леммами 1 и 2.

В первом неравенстве (4.4) положим $a = {\mathbf{x}}{\kern 1pt} *$, пользуясь леммой 1, неравенство (3.1) умножим на $\gamma > 0$, примем ${\mathbf{x}} = {\mathbf{w}}(t)$, полученные неравенства сложим и получим

Преобразуем (4.5). Для левой части, пользуясь (2.1), последовательно получаем

Правую часть (4.5) оценим с помощью следующего неравенства (см. [8, с. 175])

где $K = \frac{L}{m}$ из леммы 1,

Подставив эту оценку и (4.6) в (4.5), получим

где ${{a}_{1}}(t) = {{\alpha }^{2}}\left( {1 - \frac{{K\gamma }}{4}} \right)$; ${{a}_{2}}(t) = {{\beta }^{2}} + \beta \sigma - \frac{{K\gamma }}{4}{{(\beta + \sigma )}^{2}}$; ${{a}_{3}} = \alpha \left[ {2\beta + \sigma - \frac{{K\gamma }}{2}(\beta + \sigma )} \right]$; ${{a}_{4}}(t) = \beta (t) + \sigma (t)$; ${{a}_{j}}(t) > 0$ $\forall j \in [1:4]$, $0 < \gamma (t) < \frac{{4\beta }}{{K(\beta + \sigma )}}$.

Неравенство (4.7) преобразуем с помощью тождеств

тогда (обозначив ${{a}_{{21}}}(t) = {{a}_{2}} - \alpha > 0$, ${{a}_{{31}}}(t) = {{a}_{3}}(t){\text{/}}2$, ${{a}_{{41}}}(t) = {{a}_{4}}(t){\text{/}}2$) получим где $0 < \alpha < \beta (\beta + \sigma )$, $0 < \beta < 1$, $0 < \gamma < 4({{\beta }^{2}} + \beta \sigma - \alpha ){\text{/}}[K{{(\beta + \sigma )}^{2}}] = {{\gamma }^{{11}}}$.

Проинтегрировав (4.9) на отрезке $[\xi ,t]$, $t > \xi \geqslant 0$, придем к неравенству

где ${{a}_{{22}}}(s) = {{a}_{{21}}}(s) - a_{{31}}^{'}(s) > 0$ при $a_{{31}}^{'}(s) < 0$, что выполняется для коэффициенты положительны при условиях (4.1) и интеграл положителен. Из (4.10) без положительных слагаемых следует

Умножим это неравенство на

Отсюда с учетом производной $e{\kern 1pt} '(t) = {{a}_{{43}}}(t)e(t){\text{/}}\alpha (t)$, имеем

Проинтегрировав его на $[\xi ,t]$ и умножив полученное неравенство на ${{e}^{{ - 1}}}(t)$, получим

Из (4.11) следует

Оценим второе и третье слагаемые для второго соотношения из (4.2) с помощью неравенств (4.10) и (4.7). Учитывая (4.1) и (4.8), существование чисел $r > 0$ (пусть $r = {{\beta }_{0}}{{\gamma }_{0}}{{\sigma }_{0}}{{\theta }_{0}}$) и $\eta \geqslant 0$ таких, что для $s > \eta \geqslant \xi \geqslant 0$ коэффициенты подынтегральных слагаемых в (4.10) ${{a}_{1}}(s) \geqslant r > 0$, ${{a}_{{22}}}(s) \geqslant r > 0$, ${{a}_{{42}}}(s) \geqslant r > 0$, из (4.10) получим

В (4.13) третье слагаемое оценим с помощью известного неравенства

при $\varepsilon = \beta (t)$, $a = {\mathbf{x}}{\kern 1pt} '(t)$, $b = {\mathbf{x}}(t) - {\mathbf{x}}{\kern 1pt} *$, т.е.

Тогда из (4.13) следует

где коэффициенты при втором и третьем слагаемых положительны при условиях (4.1), и ${{a}_{{23}}} - \frac{{\alpha \beta }}{2}$ = $\frac{{\alpha \beta }}{2} + \frac{{\alpha \sigma }}{2}$ – $\frac{{K\alpha \gamma }}{4}(\beta + \sigma ) - \beta ]$ > $\frac{{\alpha \beta }}{4}$, $0 < \alpha < (\beta + \sigma )(3\beta - 2\sigma ){\text{/}}4$ < $\beta (\beta + \sigma )$ в неравенстве $0 < \gamma < \frac{{\beta + 2\sigma }}{{K(\beta + \sigma )}} < {{\gamma }^{{11}}}$, $0 < \sigma < \frac{3}{2}\beta $; ${{a}_{{41}}} - \frac{\alpha }{{2\beta }} - \alpha {\kern 1pt} '{\kern 1pt} {\text{/}}2 > 0$ в силу (4.1). Из (4.15) получим

Из (4.15а) и (4.15б) с учетом условий (4.1) при $t \to \infty $ следует

Далее оценим $\left\| {{\mathbf{x}}{\kern 1pt} ''(t)} \right\|$, исходя из (4.7) и пользуясь (4.14). Неравенства

следуют из (4.14) соответственно при $\varepsilon = \frac{4}{\alpha }$, $\varepsilon = \frac{\alpha }{4}$, $\varepsilon = 1$. С их учетом из (4.7) имеем

В (4.18а) оценим коэффициенты при квадратах норм при условиях (4.1):

Учитывая эти оценки, из (4.18а) получаем

Из (4.18б) с учетом оценок (4.11), (4.15б) имеем

С учетом условий (4.1), а также соотношений (4.12), (4.17), из (4.18) следует

где

Асимптотическую устойчивость траектории системы (2.1) и единственность предельной точки траектории можно показать по аналогии с работами [3]–[6].

Из (4.11), (4.12) следует, что траектория x(t) ограничена, а в силу (4.16) имеем

и существует подпоследовательность $\{ {{t}_{i}}\} $, такая, что

Если в ${{C}_{1}}(\xi ,{\mathbf{x}}*)$ из (4.10) положим $t = {{t}_{i}}$, учтем (4.9) и для ${{t}_{i}} \geqslant {{t}_{1}}$ обозначим

то в пределе с учетом (4.12), (4.17), (4.20а), (4.20б) получим

Тогда с учетом (4.21) из (4.15а), (4.16) следует первое доказываемое соотношение из (4.2), а из (4.12), (4.17), (4.19), (4.20б), (4.21) следует второе соотношение из (4.2).

Из второго неравенства (4.4) при $b = {\mathbf{u}}{\kern 1pt} *$, с учетом (3.2) из леммы 2, имеем

где скалярное произведение в правой части представим в виде суммы двух слагаемых:

Слагаемые в правой части (4.23) преобразуем с помощью неравенства для вогнутой функции (см. [9, § 2.4, с. 44]),

и другого неравенства (см. [8, гл. 2, § 3, с. 93; R из леммы 2]). Подставим их в (4.23) и преобразованное (4.23) будет иметь вид где учтено, что ${{h}_{1}}\left( {\mathbf{s}} \right) - {{h}_{1}}\left( {{\mathbf{u}}{\kern 1pt} *} \right) \leqslant 0$ ввиду вогнутости функции ${{h}_{1}}\left( {\mathbf{u}} \right)$. Пользуясь (4.23а) в (4.22), получаем

В (4.24) подставим разложения для левой части и квадрата нормы в правой части

После их подстановки из (4.24) следует

где

Справедливы аналогичные (4.8) тождества

Преобразуем (4.25) с помощью тождеств (4.8a), тогда получим

где

Проинтегрировав (4.26), на отрезке $[\xi ,t]$, $t > \xi \geqslant 0$, получим

где с учетом (4.8а) имеем коэффициенты и интеграл положительны. Из (4.27) без положительных слагаемых следует

Умножим (4.28) на

Отсюда с учетом производной $g{\kern 1pt} '(t) = {{b}_{{43}}}(t)g(t){\text{/}}\alpha (t)$ имеем

Проинтегрировав (4.29) на $[\xi ,t]$ и умножив полученное неравенство на ${{g}^{{ - 1}}}(t)$, получим

Отсюда имеем

Оценим второе и третье слагаемые во втором соотношении из (4.3) с помощью неравенств (4.8а) и (4.14). Учитывая (4.1) и то, что существуют числа $r > 0$ и $\eta \geqslant 0$ такие, что для $s > \eta \geqslant \xi \geqslant 0$ коэффициенты подынтегральных слагаемых в (4.27) ${{b}_{1}}(s) \geqslant r > 0$, ${{b}_{{21}}}(s) \geqslant r > 0$, ${{b}_{{42}}}(s) \geqslant r > 0$, и применяя (4.8а), из (4.27) получаем

В (4.31) третье слагаемое оценим с помощью неравенства (4.14) при $\varepsilon = \beta $, $a = {\mathbf{u}}{\kern 1pt} '(t)$, $b = {\mathbf{u}}(t) - {\mathbf{u}}{\kern 1pt} *$, т.е.

Тогда верно

где коэффициенты при втором и третьем слагаемых неотрицательны при условиях (4.1),

Неравенство (4.32) эквивалентно системе

Из (4.33а), (4.34а), с учетом $\lim {{b}_{{32}}}(t) = {{\alpha }_{0}}{{\beta }_{0}} + \frac{3}{2}{{\alpha }_{0}}{{\theta }_{0}} = b_{{32}}^{0}$ при $t \to \infty $, и условий (4.1) для параметров метода, следует

Оценку для $\left\| {{\mathbf{u}}{\kern 1pt} ''(t)} \right\|$ получим из (4.25) с помощью (4.8a) и (4.14). С учетом оценок

получаемых из (4.14) соответственно при $\varepsilon = 4{\text{/}}\alpha $, $\varepsilon = 1$, $\varepsilon = \alpha {\text{/}}4$, из (4.25) следует где следующие оценки коэффициентов верны при условиях (4.1):

С учетом этих оценок и (4.30а), (4.34а), из (4.35) получим

С учетом (4.30), (4.34) из (4.36а) следует

где

Далее, в силу (4.30а), (4.30) траектория ${\mathbf{u}}(t)$ ограничена, а в силу (4.33) имеем

и существует подпоследовательность $\{ {{t}_{i}}\} $, что

Если в (4.10) положим $t = {{t}_{i}}$, учтем (4.9) и для ${{t}_{i}} \geqslant {{t}_{1}}$ обозначим

то в пределе, с учетом (4.30), (4.34), (4.36), (4.37) получим,

Тогда с учетом (4.37) из (4.33) следует третье доказываемое соотношение из (4.3), а из (4.30), (4.34), (4.36), (4.37) следует четвертое соотношение из (4.3).

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

5. ОЦЕНКА СКОРОСТИ СХОДИМОСТИ НПОЭКМС (2.1)

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

Теорема 2. Пусть выполнены все условия теоремы 1, включая (4.1)−(4.3), леммы 1 и 2. Тогда траектория $\left\{ {{\mathbf{x}}(t);{\mathbf{u}}(t)} \right\}$ НПОЭКМС (2.1), (4.1)−(4.3) сходится к седловой точке $\left( {{\mathbf{x}}*;{\mathbf{u}}{\kern 1pt} *} \right) \in {{Q}_{*}} \times U{\kern 1pt} *$ задачи (1.1) $\forall t \geqslant 0$ с экспоненциальной скоростью с оценками:

где

Доказательство. Заметим, что при выполнении всех условий теоремы 2, выкладки и результаты теоремы 1 о сходимости метода (2.1) справедливы (обозначения коэффициентов, совпадающих с полученными в теореме 1, сохраняем; новые коэффициенты ${{C}_{{21}}}$, ${{C}_{{31}}}$ приведены в формулировке теоремы 2). Проведя аналоги выкладок из теоремы 1 от (4.4), но теперь при $\xi = 0$, получим аналог (4.11)

Из (5.7) следует оценка (5.1).

Проведем выкладки, аналогичные проведенным в теореме 1 от (4.13) до (4.15б), только при $\xi = 0$, тогда аналог (4.15б) имеет вид

Из (5.8) следует оценка (5.2).

Для получения (5.3) вычислим аналоги (4.16)−(4.18) для $\xi = 0$, тогда (сохраняя из теоремы 1 и обозначения, за исключением ${{p}_{2}}(t)$ и ${{q}_{2}}(t)$), с учетом (5.7), (5.8) получим

где ${{p}_{2}}(t)$ из (5.7) (см. условия теоремы 2). Из (5.9) следует оценка (5.3).

Теперь проведем аналоги выкладок из теоремы 1 по ${\mathbf{u}}(t)$, но при $\xi = 0$. Вычислив аналоги для (4.26)−(4.29), затем получим аналог неравенства (4.30а)

Из неравенства (5.10) следует оценка (5.4).

Далее получим оценку (5.5). Проведем аналоги выкладок из теоремы 1 после (4.30) до получения неравенства (4.34а), только при $\xi = 0$, с учетом неравенства (5.10), оценок коэффициентов, получим

Из (5.11) следует оценка (5.5).

Для вычисления оценки (5.6) продолжим аналоги выкладок из теоремы 1 после (4.34) до получения (4.36а), только при $\xi = 0$; с учетом неравенств (5.10), (5.11) получим

где ${{q}_{2}}(t)$ из (5.10). Из неравенства (5.12) следует оценка (5.6).

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

6. ВЫВОДЫ

Исследованный в данной работе НПОЭКМС (2.1) продолжает на непрерывные проекционные ЭГМ второго порядка для решения седловых задач идею использования операторов переменной метрики, впервые воплощенную в НПММ первого порядка в работе [4]. НПОЭКМС (2.1) обладает достоинствами, присущими и НПММ, и методам переменной метрики; он имеет лучшую точность и скорость сходимости в окрестности седловой точки.