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

1. ЭЛЕМЕНТАРНОЕ ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ ЛАГРАНЖА ДЛЯ ЗАДАЧИ С РАВЕНСТВАМИ

Рассматривается задача

при условиях где $F = {{({{f}_{1}}, \ldots ,{{f}_{m}})}^{ \top }}$, $\varphi ,F \in {{C}^{2}}({{\mathbb{R}}^{n}})$, ${{f}_{i}}{\kern 1pt} :\;{{\mathbb{R}}^{n}} \to R$, $i = \overline {1,m} $, и ${{0}_{m}}$ есть вектор-столбец. Обозначим через $x{\kern 1pt} *$ решение задачи (1), (2). Тогда имеет место классическая теорема Лагранжа о необходимых условиях оптимальности [1], [2].

Теоpема 1. Пусть $\varphi ,F \in {{C}^{2}}({{\mathbb{R}}^{n}})$ и матрица Якоби

не вырождена. Тогда $\varphi {\text{'}}(x{\kern 1pt} {\text{*}}) \in {\text{Lin}}\{ f_{i}^{'}(x{\kern 1pt} {\text{*}}),i = 1, \ldots ,m\} $.

Известные доказательства этой теоремы весьма громоздки и используют такие факты, как теорема о неявной функции [1], предельные переходы [2], [3], теоремa Люстреника [1] и т.д. Мы покажем, как можно в доказательстве избежать этих сложностей и получить основной результат только на основе теоремы Вейерштрасса.

Доказательство. Предположим от противного, что . Тогда $\varphi {\text{'}}(x{\kern 1pt} {\text{*}}) = h + \bar {h}$, где $h \in \operatorname{Ker} F{\kern 1pt} {\text{'}}(x{\kern 1pt} {\text{*}})$, $\bar {h} \in {\text{Lin}}\{ f_{i}^{'}(x{\kern 1pt} {\text{*}}),i = 1, \ldots ,m\} $. Тогда для $\alpha \in (0,\varepsilon )$ и $\xi \in {{\mathbb{R}}^{m}}$, $\left\| \xi \right\| = 1$, ${{\left\| {F(x{\kern 1pt} {\text{*}} - \alpha h + {{\alpha }^{{3/2}}}F{\kern 1pt} {\text{'}}{{{(x{\kern 1pt} {\text{*}})}}^{ \top }}\xi )} \right\|}^{2}} \geqslant c{{\alpha }^{3}}$, и ${{\left\| {F(x{\kern 1pt} {\text{*}} - \alpha h)} \right\|}^{2}} \leqslant c{{\alpha }^{4}}$, где $\varepsilon > 0$ – достаточно малое и $c > 0$ – независимая константа. Это означает, по теореме Вейерштрасса, что существует $\eta (\alpha ){\kern 1pt} :\;{{R}^{1}} \to {{\mathbb{R}}^{m}}$ такое, что

и $\left\| {\eta (\alpha )} \right\| \leqslant 1$. Это означает, что или что подразумевает равенство и, значит, что противоречит локальной минимальности точки $x{\text{*}}$ и доказывает теорему 1.

2. НОВОЕ ЭЛЕМЕНТАРНОЕ ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ КУНА–ТАККЕРА

Рассматривается задача

при ограничениях Здесь $x \in {{\mathbb{R}}^{n}}$, $\varphi ,{{g}_{i}} \in {{C}^{1}}({{\mathbb{R}}^{n}})$, $i = 1, \ldots ,m$. Основной результат для характеризации решения $x{\text{*}}$ задачи (3), (4) – теорема Куна–Таккера (КТ), которая устанавливает необходимые условия для этой задачи (3), (4).

Теоpема 2. Пусть $x{\kern 1pt} {\text{*}}$ – решение задачи (3), (4) и $\varphi ,{{g}_{i}} \in {{C}^{1}}({{\mathbb{R}}^{n}})$, $i = 1, \ldots ,m$.

Тогда найдутся такие неотрицательные множители $\lambda _{0}^{*},\lambda _{1}^{*}, \ldots ,\lambda _{m}^{*}$, что выполнены условия

Обозначим множество активных ограничений через $I(x{\kern 1pt} {\text{*}}) = \{ i = 1, \ldots ,m\,|\,{{g}_{i}}(x{\kern 1pt} *) = 0\} $. Традиционные доказательства данной теоремы достаточно сложные и используют в своих конструкциях такие результаты, как теорему о неявной функции, теорему о замкнутости конуса, лемму Фаркаша, теоремы об отделимости, предельные теоремы и т.д. Приведем доказательство, которое не использует вышеупомянутые фундаментальные результаты, используя и опираясь только на тривиальную лемму о свойстве проекции.

Лемма 1. Пусть $\mathcal{K}$ – замкнутое выпуклое множество в ${{\mathbb{R}}^{n}}$.

Тогда для проекции $p = {{\Pr }_{\mathcal{K}}}{{0}_{n}}$ нулевого вектора ${{0}_{n}}$ на множество $\mathcal{K}$ имеет место неравенство

для всех $z \in \mathcal{K}$.

Доказательство данной леммы тривиально и мы его не приводим. Пусть

Доказательство теоремы КТ. Покажем, что

так как соотношение (7) эквивалентно (5). Действительно, если это не так, т.е. , то поскольку $\varphi {\text{'}}(x{\kern 1pt} {\text{*}}) \in \mathcal{K}$, из леммы 1 следует и, поскольку $g_{i}^{'}(x{\kern 1pt} {\text{*}}) \in \mathcal{K}$, $i = 1, \ldots ,m$, имеем Отсюда следует, что и при $\alpha > 0$ достаточно малых. А это противоречит минимальности точки $x{\text{*}}$. Теорема доказана.

3. ТЕОРЕМА ФАРКАША И ТЕОРЕМА О ЗАМКНУТОСТИ КОНУСА

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

Теоpема 3 (Фаркаша). Пусть векторы $\eta ,{{\xi }_{i}} \in {{\mathbb{R}}^{n}}$, $i = 1, \ldots ,m$, и для каждого $x \in {{\mathbb{R}}^{n}}$ такого, что $\left\langle {{{\xi }_{i}},x} \right\rangle \geqslant 0$, $i = 1, \ldots ,m$, выполнено неравенство

Назовем это условием Фаркаша.

Тогда

Доказательство. Введем в рассмотрение функцию

здесь При выполнении условий Фаркаша существует $y{\kern 1pt} {\text{*}} = \mathop {{\text{Argmin}}}\limits_{x \in {{\mathbb{R}}^{n}}} \,\Phi (x)$. По теореме Ферма $\Phi {\text{'}}(y{\kern 1pt} {\text{*}}) = {{0}_{n}}$ или $\eta + {{\sum\nolimits_{i = 1}^m {2\left\langle {{{\xi }_{i}},y{\kern 1pt} {\text{*}}} \right\rangle } }_{ - }}{{\xi }_{i}} = {{0}_{n}}$. Обозначив через $ - \lambda _{i}^{*} = 2{{\left\langle {{{\xi }_{i}},y{\kern 1pt} {\text{*}}} \right\rangle }_{ - }}$, $i = 1, \ldots ,m$, получаем $\eta = \sum\nolimits_{i = 1}^m {\lambda _{i}^{*}x_{i}^{*}} $, $\lambda _{i}^{*} \geqslant 0$, $i = 1, \ldots ,m$, т.е. $\eta \in {\text{Cone}}\{ {{\xi }_{i}}\,{\text{|}}\,i = 1, \ldots ,m\} $.

Замечание 1. Из доказательства явно следует вид множителей Фаркаша $\lambda _{i}^{*}$.

Известные доказательства этой теоремы в большинстве своем полагаются на теоремы отделимости, предельные переходы и, обязательно, на теорему о замкнутости конуса. Однако существующие доказательства теоремы о замкнутости конуса весьма громоздки. Приведем здесь доказательство, которое отличается своей простотой и изяществом. Это доказательство опирается на лемму Фаркаша.

Теоpема 4 (о замкнутости конуса). Множество

замкнуто.

Доказательство. Пусть последовательность $\{ {{y}_{i}}\} $, $i = 1,2, \ldots $, такова, что ${{y}_{i}} \in \mathcal{K}$, $i = 1,2, \ldots $, $\left\| {{{y}_{i}}} \right\| \leqslant c$, $i = 1,2, \ldots $, и ${{y}_{i}} \to y$ при $i \to \infty $. Нужно показать, что $y \in \mathcal{K}$. Действительно, $\forall x \in {{\mathbb{R}}^{n}}$ и такого, что $\left\langle {{{a}_{j}},x} \right\rangle \geqslant 0$, $j = 1, \ldots ,m$, следует, что $\left\langle {{{y}_{i}},x} \right\rangle \geqslant 0$, $i = 1,2, \ldots $. Но тогда, переходя к пределу при $i \to \infty $, получаем $\forall x \in {{\mathbb{R}}^{n}}$ и такого, что $\left\langle {{{a}_{j}},x} \right\rangle \geqslant 0$, $j = 1, \ldots ,m$, следует

и по теореме Фаркаша $y \in {\text{Cone}}\{ {{a}_{j}}\,{\text{|}}\,j = 1, \ldots ,m\} $, т.е. $\mathcal{K}$ замкнуто.

Таким образом, теорема Фаркаша и о замкнутом конусе эквивалентны, т.е. одна следует из другой. Это новый взгляд на данные основополагающие результаты в оптимизации.

4. ОБ ИЗБЫТОЧНОСТИ УСЛОВИЙ В ТЕОРЕМЕ ФАРКАША

Основные теоремы об условиях оптимальности в задаче с неравенствами получены с использованием теоремы Фаркаша. Однако оказывается, что требование (10): $\forall x \in {{\mathbb{R}}^{n}}$ такого, что $\left\langle {\xi ,x} \right\rangle \geqslant 0$, $i = 1, \ldots ,m$, следует $\left\langle {\eta ,x} \right\rangle \geqslant 0$ избыточно. Достаточно взять некоторый конечный набор элементов ${{z}_{j}}$ и если на нем выполнено (10), а именно $\forall {{z}_{j}}$, $j = 1, \ldots ,k$, из того, что $\left\langle {{{\xi }_{i}},{{z}_{j}}} \right\rangle \geqslant 0$, $i = 1, \ldots ,m$ $ \Rightarrow $ $\left\langle {\eta ,{{z}_{j}}} \right\rangle \geqslant 0$, $j = 1, \ldots ,k$, то $\eta = \sum\nolimits_{i = 1}^m {{{\alpha }_{i}}{{\xi }_{i}}} $, ${{\alpha }_{i}} \geqslant 0$, $i = 1, \ldots ,m$. Например, ${{\xi }_{1}} = {{(0,1)}^{ \top }}$, ${{\xi }_{2}} = {{(1,0)}^{ \top }}$, $\eta = {{(1,1)}^{ \top }}$, ${{z}_{1}} = {{(1,0)}^{ \top }}$, ${{z}_{2}} = {{(0,1)}^{ \top }}$. Очевидно, что $\left\langle {{{\xi }_{i}},{{z}_{j}}} \right\rangle \geqslant 0$, $i = 1,2$ и $\left\langle {\eta ,{{z}_{j}}} \right\rangle \geqslant 0$, $j = 1,2$ $ \Rightarrow $ $ \Rightarrow \eta = {{\alpha }_{1}}{{\xi }_{1}} + {{\alpha }_{2}}{{\xi }_{2}}$, ${{\alpha }_{1}} = 1$, ${{\alpha }_{2}} = 1$.

Набор векторов $\{ {{z}_{j}}\} $ определяется следующим образом. Пусть ${\text{span}}\{ {{\xi }_{i}}\,{\text{|}}\,i = 1, \ldots ,m\} \triangleq {{\mathbb{R}}^{p}}$, $p \leqslant n$, ${{\xi }_{i}} \in {{\mathbb{R}}^{n}}$, $\eta \in {{\mathbb{R}}^{n}}$. Тогда ${{\mathbb{R}}^{n}} = {{\mathbb{R}}^{p}} \oplus {{\mathbb{R}}^{{n - p}}}$ и пусть ${{y}_{1}}, \ldots ,{{y}_{{n - p}}}$ – базис в ${{\mathbb{R}}^{{n - p}}}$. Тогда

1) чтобы $\eta $ принадлежал ${\text{Cone}}\,\{ {{\xi }_{i}}\,{\text{|}}\,i = 1, \ldots ,m\} $ нужно, чтобы $\eta \in {\text{span}}\{ {{\xi }_{i}}\,{\text{|}}\,i = 1, \ldots ,m\} $, а значит, $\left\langle {\eta ,{{y}_{j}}} \right\rangle = 0$, $j = 1, \ldots ,n - p$. Это можно записать как неравенство: из того, что $\left\langle {{{\xi }_{i}}, \pm {{y}_{j}}} \right\rangle \geqslant 0$ $ \Rightarrow $ $ \Rightarrow \left\langle {\eta , \pm {{y}_{j}}} \right\rangle \geqslant 0$ $j = 1, \ldots ,n - p$;

2) имеем $\eta \in {\text{span}}\{ {{\xi }_{i}}\,{\text{|}}\,i = 1, \ldots ,m\} $. Далее в ${{\mathbb{R}}^{p}}$ строим выпуклый конус ${{\mathcal{K}}_{p}} \triangleq \{ z \in {{\mathbb{R}}^{n}} \cap {{\mathbb{R}}^{p}}\,{\text{|}}\,\left\langle {{{\xi }_{i}},z} \right\rangle \geqslant 0,\;i = 1, \ldots ,m\} $ ${{\mathcal{K}}_{p}} \triangleq \{ z \in {{\mathbb{R}}^{n}} \cap {{\mathbb{R}}^{p}}\,{\text{|}}\,\left\langle {{{\xi }_{i}},z} \right\rangle \geqslant 0,\;i = 1, \ldots ,m\} $. Пусть ${{x}_{1}}, \ldots ,{{x}_{r}}$ – его крайние (одномерные) ребра. Очевидно, что их число $r$ конечно, как число вершин $y$ многогранника. Полагаем

т.е. определяем систему $\{ {{z}_{j}}\} $, $j = 1, \ldots ,k$, $k = r + 2(n - p)$.

Теоpема 5 (обобщенная лемма Фаркаша). Пусть выполнено $\left\langle {{{\xi }_{i}},{{z}_{j}}} \right\rangle \geqslant 0$, $i = 1, \ldots ,m$, $ \Rightarrow $ $\left\langle {\eta ,{{z}_{j}}} \right\rangle \geqslant 0$, $j = 1, \ldots ,k$, где $k$ определено выше. Тогда

Доказательство. Очевидно, что $\eta \in {\text{span}}\{ {{\xi }_{i}}\,{\text{|}}\,i = 1, \ldots ,m\} $. Покажем, что $\eta = \sum\nolimits_{i = 1}^m {{{\alpha }_{i}}{{\xi }_{i}}} $, ${{\alpha }_{i}} \geqslant 0$, $i = 1, \ldots ,m$. Действительно, $\forall x\left\langle {{{\xi }_{i}},x} \right\rangle \geqslant 0$, $i = 1, \ldots ,m$ $ \Rightarrow $ $x \in {{\mathbb{R}}^{n}} \cap {{\mathbb{R}}^{p}}$ $ \Rightarrow $ $x \in {{\mathcal{K}}_{p}}$ и, значит, $x = {{\beta }_{1}}{{x}_{1}} + \ldots + {{\beta }_{r}}{{x}_{r}}$, ${{z}_{1}} = {{x}_{1}}, \ldots ,{{z}_{r}} = {{x}_{r}}$, ${{\beta }_{j}} \geqslant 0$, $j = 1, \ldots ,r$. Но $\left\langle {\eta ,{{x}_{1}}} \right\rangle \geqslant 0, \ldots ,\left\langle {\eta ,{{x}_{r}}} \right\rangle \geqslant 0$ $ \Rightarrow $ $ \Rightarrow \left\langle {\eta ,{{\beta }_{1}}{{x}_{1}} + \ldots + {{\beta }_{r}}{{x}_{r}}} \right\rangle = \left\langle {\eta ,x} \right\rangle \geqslant 0$ $ \Rightarrow $ выполнены условия теоремы Фаркаша и соотношение (11).

5. О СВОДИМОСТИ ЗАДАЧИ ОПТИМИЗАЦИИ С ОГРАНИЧЕНИЯМИ НЕРАВЕНСТВАМИ К ЗАДАЧЕ ОПТИМИЗАЦИИ С РАВЕНСТВАМИ

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

Тогда необходимые условия минимума Куна–Таккера выглядят следующим образом: плюс условие дополняющей нежесткости Достаточные условия для задачи (3), (4) будут следующими:

– если в допустимой точке $x{\kern 1pt} {\text{*}}$ $({{g}_{i}}(x{\kern 1pt} {\text{*}}) \leqslant 0,i = 1, \ldots ,m)$ выполнены необходимые условия (12)–(14) при некотором $\lambda {\text{*}}$ и

$\forall h \ne 0$ такого, что $\left\langle {g_{i}^{'}(x{\kern 1pt} {\text{*}}),h} \right\rangle \leqslant 0$, $i \in I(x{\kern 1pt} {\text{*}}) = \left\{ {i \in \{ 1, \ldots ,m\} \,{\text{|}}\,{{g}_{i}}(x{\kern 1pt} {\text{*}}) = 0} \right\}$, то $x{\kern 1pt} {\text{*}}$ – точка локального минимума задачи (3), (4) (см., например, [5]).

Существенным недостатком этих условий от достаточных условий оптимальности для задачи с равенствами является то, что точка $x{\kern 1pt} {\text{*}}$ должна быть допустима. Уравнения (12)–(14) не гарантируют этого, в отличие от необходимых условий для задачи с равенствами. Поэтому модифицируем задачу (3), (4) в виде задачи с равенствами путем введения новой искусственной переменной $s = {{({{s}_{1}}, \ldots ,{{s}_{m}})}^{ \top }}$.

Задачи (3), (4) и (16) эквивалентны [6]. Необходимые условия оптимальности для задачи (16) выглядят следующим образом: где $\lambda s = {{({{\lambda }_{1}}{{s}_{1}}, \ldots ,{{\lambda }_{m}}{{s}_{m}})}^{ \top }}$. Заметим, что из систем (17)–(19) нельзя определить знак величины $\lambda _{i}^{*} \geqslant 0$, $i = 1, \ldots ,m$. Но уже не требуется допустимости решения $x{\text{*}}$ – она следует из системы (19). Обозначим $\mathop {\bar {g}}\nolimits_i (x,s) = {{g}_{i}}(x) + s_{i}^{2}$, $i = 1, \ldots ,m$, и введем функцию Лагранжа для задачи (16) Пусть $g(x) = \mathop {({{g}_{1}}(x), \ldots ,{{g}_{m}}(x))}\nolimits^ \top $, ${{s}^{2}} = \mathop {(s_{1}^{2}, \ldots ,s_{m}^{2})}\nolimits^ \top $. Считаем, что в решении $x{\kern 1pt} *$ выполнено условие регулярности ограничений (УРО), если векторы $\{ g_{i}^{'}(x{\kern 1pt} {\text{*}})\} $, $i \in I(x{\kern 1pt} {\text{*}})$, линейно независимы. Тогда достаточные условия оптимальности означают положительную определенность матрицы $\bar {L}_{{(x,s)}}^{{''}}(x{\kern 1pt} {\text{*}},s{\kern 1pt} {\text{*}},\lambda {\text{*}})$ на ядре $\operatorname{Ker} \bar {g}{\kern 1pt} {\text{'}}(x{\kern 1pt} {\text{*}},s{\kern 1pt} {\text{*}})$, т.е. для любых $h \in \operatorname{Ker} \bar {g}(x{\text{*}},s{\text{*}})$. Отсюда, кстати, следует неотрицательность $\lambda _{i}^{*} \geqslant 0$, $i = 1, \ldots ,m$. Запишем, для наглядности, что Однако матрица $\bar {L}{\text{''}}(x{\kern 1pt} {\text{*}},s{\kern 1pt} {\text{*}},\lambda {\text{*}})$ не будет положительно определена на ядре $\bar {g}{\kern 1pt} {\text{'}}(x{\kern 1pt} {\text{*}},s{\kern 1pt} {\text{*}})$, если не выполнено условие строгой дополняющей нежесткости (УСДН), т.е. $\lambda _{i}^{*}$ и $s_{i}^{*}$ не равны нулю одновременно при $i = 1, \ldots ,m$. То есть достаточные условия (15) и (21) не равноценны. Это связано с тем, что можно ослабить необходимые условия оптимальности $2$-го порядка для задачи с равенствами, а значит, и построить более слабые достаточные условия. Поясним следующее. Пусть существует такое ${{h}_{2}} \in \operatorname{Ker} F{\kern 1pt} {\text{'}}(x{\kern 1pt} {\text{*}})$ для задачи (1), (2), что и, значит, достаточные условия $2$-го порядка не выполнены. Пусть $\operatorname{Ker} F{\kern 1pt} {\text{'}}(x{\kern 1pt} {\text{*}}) = \mathbb{R}_{1}^{n}$ и $\mathbb{R}_{2}^{n} = {{(\mathbb{R}_{1}^{n})}^{ \bot }}$. Тогда ${{\mathbb{R}}^{n}} = \mathbb{R}_{1}^{n} + \mathbb{R}_{2}^{n}$. Будет верна следующая

Теоpема 6 (необходимые и достаточные условия оптимальности специального вида). Пусть $\varphi ,F \in {{C}^{3}}({{\mathbb{R}}^{n}})$ и для любого ${{h}_{2}} \in \operatorname{Ker} F{\kern 1pt} {\text{'}}(x{\kern 1pt} {\text{*}})$ $(\left\| h \right\| = 1)$ такого, что $L{\text{''}}(x{\kern 1pt} {\text{*}}\lambda {\text{*}}){{[{{h}_{2}}]}^{2}} = 0$ или $\left( {L{\text{''}}(x{\text{*}}\lambda {\text{*}}){{h}_{2}} = 0} \right)$ выполняются условия

1)

2) и существуют ${{h}_{1}} \in \mathbb{R}_{2}^{r}$ и $C({{h}_{2}}) \geqslant c > 0$, $\left\| {{{h}_{1}}} \right\| = 1$, удовлетворяющие соотношению

Тогда (необходимость), если $x{\text{*}}$ – решение (1), (2), то $\exists \lambda {\text{*}}$ такое, что $L{\text{'}}(x{\kern 1pt} {\text{*}},\lambda {\text{*}}) = 0$ иБолее того (достаточность), если $\forall {{h}_{1}},{{h}_{2}}$, удовлетворяющих (23), (24), существует $\beta > 0$ такое, что $L{\text{'}}(x{\kern 1pt} {\text{*}},\lambda {\text{*}}) = 0$ ито $x{\text{*}}$ – локальный минимум задачи (1), (2).

Замечание 2. Элемент ${{h}_{1}}$ может не принадлежать $\operatorname{Ker} F{\kern 1pt} {\text{'}}(x{\text{*}})$.

Доказательство. Необходимость. Покажем, что $\forall t \in (0,\varepsilon )$, $\varepsilon > 0$ достаточно малое, существует $\omega (t)\mathbb{R} \to {{\mathbb{R}}^{n}}$ такое, что дуга

и $\left\| {\omega (t)} \right\| = o({{t}^{2}})$. Действительно, В силу невырожденности $F{\kern 1pt} {\text{'}}(x{\text{*}})$ можем применить принцип сжимающих отображений [1] к отображению из которого следует существование $\omega (t)$ такого, что и Далее применим стандартную технику к соотношению $L(x{\kern 1pt} {\text{*}} + {{c}_{2}}t{{h}_{2}} + {{t}^{2}}{{h}_{1}} + \omega (t),\lambda {\text{*}}) \geqslant L(x{\kern 1pt} {\text{*}},\lambda {\text{*}})$ получим $L_{{xx}}^{{''}}(x{\kern 1pt} {\text{*}},\lambda {\text{*}}){{[{{h}_{1}}]}^{2}} \geqslant 0$. Необходимость доказана.

Достаточность. Предполагая противное, т.е. что существует последовательность точек $\{ {{x}_{k}}\} \in M(x{\kern 1pt} {\text{*}})$ и ${{x}_{k}} \to x{\kern 1pt} {\text{*}}$ при $k \to \infty $ такая, что $\varphi ({{x}_{k}}) < \varphi (x{\text{*}})$, используя доказательство необходимости и стандартную технику доказательства достаточности условий, приходим к противоречию с соотношением (26).

Пример 1. Рассмотрим задачу (16) в виде

при $F(x) = g(y) + {{s}^{2}} = {{0}_{m}}$. Здесь роль $x$ играет $(y,s)$ (чтобы не было путаницы с последними записями, мы заменили в задаче (3), (4) $x$ на $y$). Если точка $(y{\kern 1pt} {\text{*}},s{\kern 1pt} {\text{*}})$, $s{\kern 1pt} {\text{*}} = 0$ – решение задачи (3), (4), то для ${{h}_{2}} = {{(0,\bar {s})}^{ \top }}$ очевидно существует ${{h}_{1}} = {{(\bar {y},0)}^{ \top }}$ такое, что Поскольку условия оптимальности носят локальный характер, мы рассмотрим только активные ограничения, т.е. $i \in I(x{\kern 1pt} {\text{*}})$ и, не нарушая общности, считаем $r = m$. Очевидно, что условие (23) выполнено, если $\bar {s} \ne 0$. А условие (24) выполнено в силу регулярности ограничений $\{ {{g}_{i}}(x)\} $, $i = 1, \ldots ,m$, в точке $x{\kern 1pt} {\text{*}}$, при этом ${{c}_{2}} = 1$. Таким образом, к задаче (16) применима теорема 6, так как $L_{{xx}}^{{''}}(x{\kern 1pt} {\text{*}},\lambda {\kern 1pt} {\text{*}}){{[{{h}_{2}}]}^{2}} = 0$, хотя ${{h}_{2}} = {{(0,\bar {s})}^{ \top }} \in \operatorname{Ker} F{\kern 1pt} {\text{'}}(x{\kern 1pt} {\text{*}}) = \{ (\bar {y},\bar {s})\,{\text{|}}\,g{\text{'}}(y{\kern 1pt} {\text{*}})\bar {y} + 0 \cdot \bar {s} = 0\} $. Более того будет справедлива следующая теорема об эквивалентности.

Теоpема 7 (об эквивалентности условий оптимальности). Пусть $\varphi ,g \in {{C}^{3}}({{\mathbb{R}}^{n}})$. Тогда условия оптимальности (12), (13), (15) и (26) эквивалентны.

Доказательство. Очевидно нужно проверить только достаточную часть условий оптимальности. Пусть выполнены условия (12)–(15). Тогда, беря $\bar {s} \ne 0$, получаем $\bar {y} = {{\{ g{\text{'}}(y{\kern 1pt} {\text{*}})\} }^{{ - 1}}}( - {{\bar {s}}^{2}})$ из условия (24). При этом $L_{{xx}}^{{''}}(y{\kern 1pt} {\text{*}},s{\kern 1pt} {\text{*}}\lambda {\kern 1pt} {\text{*}}){{[y]}^{2}} \geqslant \beta {{\left\| {\bar {y}} \right\|}^{2}}$, так как выполнено достаточное условие (15). Здесь $\bar {y}$ играет роль ${{h}_{1}}$ в теореме 6 и поэтому имеет место (26), а значит, выполнены достаточные условия теоремы 6. В одну сторону теорема доказана.

Пусть теперь выполнены достаточные условия (26) для задачи (31). Тогда $\forall h$ такого, что $g{\text{'}}(y{\kern 1pt} {\text{*}})h < {{0}_{m}}$ будет $\bar {s} \ne 0$ и, значит, выполнено (26) при ${{h}_{1}} = h$, т.е. $L_{{xx}}^{{''}}(y{\kern 1pt} {\text{*}},0,\lambda {\kern 1pt} {\text{*}}){{[h]}^{2}} \geqslant \beta {{\left\| h \right\|}^{2}}$, а это значит, что $L_{{xx}}^{{''}}(y{\kern 1pt} {\text{*}},\lambda {\kern 1pt} {\text{*}}){{[h]}^{2}} \geqslant \beta {{\left\| h \right\|}^{2}}$ (где $L(y,\lambda )$ играет роль функции $L(x,\lambda ) = \varphi (x) + \sum\nolimits_{i = 1}^m {{{\lambda }_{i}}{{g}_{i}}(x)} $ в задаче (3), (4)), и окончательно выполнены достаточные условия (15) для задачи (3), (4). Теорема доказана.

6. $2$-ФАКТОР-МЕТОД РЕШЕНИЯ ВЫРОЖДЕННЫХ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ

Для численного решения систем уравнений, в частности возникающих из необходимых условий оптимальности, основной конструкцией для построения различного рода итерационных процессов является метод Ньютона [4]. Однако если для системы нелинейных уравнений

в решении $x{\kern 1pt} {\text{*}}$ матрица $\Phi {\text{'}}(x{\kern 1pt} {\text{*}})$ вырождена, то применение метода Ньютона, итерационная схема которого имеет вид становится неэффективным или вообще невозможным. В этом случае применяется так называемый 2-фактор-метод, обеспечивающий сходимость, и, более того, квадратичную скорость сходимости. В общем случае, схема 2 -фактор-метода решения вырожденной системы нелинейных уравнений (33) при $x \in {{\mathbb{R}}^{n}}$ имеет следующий вид: где $P$ – матрица ортогонального проектирования на $\mathop {\left( {\operatorname{Im} \Phi {\text{'}}(x{\kern 1pt} {\text{*}})} \right)}\nolimits^ \bot $, а вектор $h$, $\left\| h \right\| = 1$ – некоторый фиксированный вектор такой, что матрица $\left\{ {\Phi {\text{'}}(x{\kern 1pt} {\text{*}}) + P\Phi {\text{''}}(x{\kern 1pt} {\text{*}})h} \right\}$ невырожденна, т.е. отображение $\Phi ( \cdot )$ является $2$-регулярным на векторе $h$ в точке решения ${{x}^{ * }}$ системы (33). В этом случае справедлива следующая

Теоpема 8. Пусть $\Phi \in {{C}^{3}}({{\mathbb{R}}^{n}})$ и $\Phi (\, \cdot \,)$ $2$-регулярно в решении $x{\kern 1pt} {\text{*}}$ на векторе $h$. Тогда для ${{x}_{0}} \in {{U}_{\varepsilon }}(x{\kern 1pt} {\text{*}})$ последовательность $\{ {{x}_{k}}\} $, определяемая схемой (35), сходится к решению $x{\kern 1pt} {\text{*}}$, причем справедлива оценка скорости сходимости

где $\varepsilon > 0$ – достаточно малое.

Доказательство см., например, в [7]. Покажем, как $2$-фактор-метод можно применять для численного решения задач оптимизации с ограничениями неравенствами при использовании искусственных переменных.

7. ПОНЯТИЕ $2$-РЕГУЛЯРНОСТИ И $2$-ФАКТОР-МЕТОДА НЬЮТОНА ДЛЯ РЕШЕНИЯ ВЫРОЖДЕННОЙ СИСТЕМЫ КУНА–ТАККЕРА

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

Итак, имеем задачу (3), (4)

при которую заменяем на задачу (16) Введем функцию Лагранжа и обозначим $u = (x,s,\lambda )$. Тогда имеем Введем систему из $\ell $ нелинейных уравнений, где $\ell = n + 2m$Пусть $u{\kern 1pt} {\text{*}} = {{(x{\kern 1pt} {\text{*}},s{\kern 1pt} {\text{*}},\lambda {\kern 1pt} {\text{*}})}^{ \top }} \in {{\mathbb{R}}^{\ell }}$ ее решение. Если $\lambda {\text{*}} \geqslant {{0}_{m}}$, $L{\text{'}}(u{\kern 1pt} {\text{*}}) = {{0}_{\ell }}$, то в точке $(x{\kern 1pt} {\text{*}},\lambda {\kern 1pt} {\text{*}})$ выполнены необходимые условия минимума для задачи (3), (4). Если при этом добавить достаточные условия (15), то точка $x{\kern 1pt} {\text{*}}$ будет локальным решением задачи (3), (4). Однако наличие неравенства $\lambda {\text{*}} \geqslant {{0}_{m}}$ не позволяет получить полную систему равенств. Поэтому заменим $\lambda {\text{*}} \geqslant {{0}_{m}}$ на систему равенств где $y \in {{\mathbb{R}}^{m}}$, ${{y}^{2}} = {{(y_{1}^{2}, \ldots ,y_{m}^{2})}^{ \top }}$ и рассмотрим расширенную систему где $z = {{(x,s,\lambda ,y)}^{ \top }}$, $r = n + 3m$. Таким образом, мы задачу оптимизации с неравенствами свели к системе равенств. Причем в решении $(x{\kern 1pt} {\text{*}},\lambda {\text{*}})$ выполнены необходимые условия КТ, и теперь $\lambda {\text{*}} \geqslant 0$. Пусть Здесь ${{I}_{m}}$ – единичная матрица размерности $m \times m$. Метод Ньютона для решения системы (42) имеет вид Если в решении $z{\kern 1pt} {\text{*}}$ не выполнено УСДН, то матрица $\Psi {\text{'}}(z{\kern 1pt} {\text{*}})$ вырождена и метод (43) не гарантирует сходимость. Построим так называемый $2$-фактор-метод Ньютона для решения системы (41), обеспечивающий квадратичную скорость сходимости. Следуя [7], [8], введем отображение и $2$-фактор-оператор где $r \times r$ матрица $P$ проектирует вектор $\Psi {\text{''}}(z{\kern 1pt} {\text{*}})h$ на $\mathop {\operatorname{Im} \Psi {\text{'}}(z{\kern 1pt} {\text{*}})}\nolimits^ \bot $, $r$-мерный вектор $h$, имеющий единичную норму, выбирается из условия невырожденности $\Phi {\text{'}}(z{\kern 1pt} {\text{*}})$. Отметим, что матрицу $P$ можно выбирать, вообще говоря, просто из условия невырожденности $2$-фактор-оператора $\Phi {\text{'}}(z{\kern 1pt} {\text{*}})$.

Теоpема 9. Пусть $\varphi ,g \in {{C}^{3}}({{\mathbb{R}}^{n}})$, существует удовлетворяющий системе (41) вектор $z{\kern 1pt} {\text{*}}$, в точке $(x{\kern 1pt} {\text{*}},\lambda {\kern 1pt} {\text{*}})$ выполнены достаточные условия оптимальности (15) и УРО. Тогда $2$-фактор-матрица $\Phi {\text{'}}(z{\kern 1pt} {\text{*}})$ невырожденна.

Доказательство. Покажем, что отображение $\Psi (z)$ будет $2$-регулярно в точке $z{\kern 1pt} {\text{*}}$ на векторе ${{h}^{ \top }} = (0_{n}^{ \top },0_{m}^{ \top },e_{0}^{ \top },e_{1}^{ \top })$, где ${{e}_{0}} \in {{\mathbb{R}}^{m}}$ и каждая $i$-я компонента вектора ${{e}_{0}}$ равна единице, если $i \in {{I}_{0}}(x{\kern 1pt} {\text{*}}) = \{ i \in I(x{\kern 1pt} {\text{*}})\,|\,\lambda _{i}^{*} = 0,s_{i}^{*} = 0\} $, и равно нулю в противном случае, а ${{e}_{1}} \in {{\mathbb{R}}^{m}}$ и каждая $i$-я компонента вектора ${{e}_{1}}$ равна единице, если $\lambda _{i}^{*} = 0$, и равна нулю в противном случае. Определим матрицу

где $r \times r$-диагональная матрица $P$ имеет $i$-й диагональный элемент, равный нулю, если $1 \leqslant i \leqslant k$ или $k + m + 1 \leqslant i \leqslant \ell $, а при $k + 1 \leqslant i \leqslant n + m$, $i$-й диагональный элемент равен единице, если $i - n \in {{I}_{0}}(x{\kern 1pt} {\text{*}})$, и равен нулю в противном случае. При $\ell + 1 \leqslant i \leqslant r$, $i$-й диагональный элемент равен единице, если $i - \ell \in {{I}_{0}}(x{\kern 1pt} {\text{*}})$, и равен нулю в противном случае. При этом $m \times m$-диагональная матрица ${{J}_{0}}(x{\kern 1pt} {\text{*}})$ имеет $j$-й диагональный элемент, равный либо нулю, либо единице, если $j \in {{I}_{0}}(x{\kern 1pt} {\text{*}})$. В свою очередь $m \times m$-диагональная матрица ${{J}_{1}}(x{\kern 1pt} {\text{*}})$ имеет $j$-й диагональный элемент, равный единице, если $j \in {{I}_{0}}(x{\kern 1pt} {\text{*}})$, и нулю в противном случае. Отсюда следует, что при $h = {{({{0}^{ \top }},{{0}^{ \top }},e_{0}^{ \top },e_{1}^{ \top })}^{ \top }}$ получаем и справедливость формулы (46), а также и невырожденность матрицы $\Phi {\text{'}}(z{\kern 1pt} {\text{*}})$.

Очевидно, что $2$-фактор-метод, примененный к системе (41), имеет вид

Теоpема 10.  Пусть  $\Psi \in {{C}^{3}}({{\mathbb{R}}^{r}})$ и  для $h \in {{\mathbb{R}}^{r}}$, $\left\| h \right\| \ne 0$, существует ${{\left( {\Psi {\text{'}}(z{\kern 1pt} {\text{*}}) + P\Psi {\text{''}}(z{\kern 1pt} {\text{*}}h)} \right)}^{{ - 1}}}$. Тогда $2$-фактор-метод (47) сходится к решению $z{\kern 1pt} {\text{*}}$ системы (41) с квадратичной скоростью, т.е.

где ${{z}_{0}} \in {{U}_{\varepsilon }}(z{\kern 1pt} {\text{*}})$, $\varepsilon > 0$ – достаточно малое, а $c > 0$ независимая константа.

Доказательство. Следует из того факта, что $2$-фактор-метод (47) есть обычный метод Ньютона, примененный к системе

так как точка $z{\kern 1pt} {\text{*}}$ – решение системы (41), будет одновременно решением системы (48) и для нее выполнены все условия сходимости метода Ньютона с квадратичной скоростью.