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

1. ВВЕДЕНИЕ

В данной статье рассматривается вариант метода асимптотических оценок для решения стандартной задачи линейного программирования вида максимизировать по $x \in {{E}^{n}}$ с координатным представлением $\left\| x \right\| = {{\left\| {{{\xi }_{1}},{{\xi }_{2}}, \ldots ,{{\xi }_{n}}} \right\|}^{{\text{T}}}}$

где каждая из функций $F(x),\;{{f}_{i}}(x)$ $\forall i = [1,m]$ линейна по всем своим аргументам.

2. СХЕМА МЕТОДА ОБРАТНЫХ СВЯЗЕЙ ДЛЯ ЛИНЕЙНЫХ ЗАДАЧ

Вначале рассмотрим использование предлагаемого подхода для решения пары взаимно двойственных задач линейного программирования, записанных в симметричной форме.

Пусть векторы $x \in {{E}^{n}}$ и $\Lambda \in {{E}^{m}},$ имеющие координатные столбцы вида $\left\| x \right\| = {{\left\| {{{\xi }_{1}}{{\xi }_{2}} \ldots {{\xi }_{n}}} \right\|}^{{\text{T}}}}$ и $\left\| \Lambda \right\| = {{\left\| {{{\lambda }_{1}}{{\lambda }_{2}} \ldots {{\lambda }_{m}}} \right\|}^{{\text{T}}}},$ являются искомыми, соответственно, для равносильной задачи (1.1), (1.2) паре задач следующего вида.

1. Прямой задачи линейного программирования, т.е.

максимизировать по $\{ {{\xi }_{1}},{{\xi }_{2}}, \ldots ,{{\xi }_{n}}\} $функцию $F(x) = \sum\nolimits_{j = 1}^n {{{\sigma }_{j}}{{\xi }_{j}}} $

Любое решение задачи (2.1) обозначим как $x{\kern 1pt} *,$ а $F(x{\kern 1pt} *)$ через $F{\kern 1pt} *$.

2. Двойственной задачи линейного программирования, т.е.

минимизировать по $\{ {{\lambda }_{1}},{{\lambda }_{2}}, \ldots ,{{\lambda }_{m}}\} $ функцию $G(\Lambda ) = \sum\nolimits_{i = 1}^m {{{\beta }_{i}}{{\lambda }_{i}}} $

Ее решение будем обозначать через $\Lambda {\kern 1pt} *$ и пусть $G{\kern 1pt} * = G(\Lambda {\kern 1pt} {\text{*}})$.

Последующее изложение может быть упрощено, если вначале привести краткое описание схемы решения пары задач (2.1) и (2.2) следующим вариантом метода гладких штрафных функций [1].

Предположим, что в этом методе используются вспомогательные функции вида

где функция $Р(\tau ,s)$ определяет “штраф” за нарушение ограничения $s \leqslant 0$ и удовлетворяет следующим условиям.

1. $\forall s$ и $\forall \tau > 0\,:$ $P(\tau ,s) \geqslant 0$ и $\mathop {lim}\limits_{\tau \to + 0} P(\tau ,s)\left\{ \begin{gathered} + \infty ,\quad s > 0, \hfill \\ 0,\quad s < 0. \hfill \\ \end{gathered} \right.$

2. Функция $P(\tau ,s)$ имеет непрерывные частные производные по всем своим аргументам

3. Для всех $\tau > 0$ и $\forall s$ выполнены неравенства $\tfrac{{\partial P}}{{\partial s}} > 0;$    $\tfrac{{{{\partial }^{2}}P}}{{\partial {{s}^{2}}}} > 0$.

Пусть

Тогда величины $F(\tilde {x}(\tau ))$ и $G(\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\smile}$}}{\Lambda } (\tau )),$ где точки $\tilde {x}(\tau )$ и $\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\smile}$}}{\Lambda } (\tau )$ являются стационарными для вспомогательных функций (2.3) $\forall \tau > 0,$ и, в силу основного свойства метода штрафных функций, их можно использовать в качестве аппроксимаций значений $F({{x}^{*}})$ и $G({{\Lambda }^{*}})$. Кроме того, к условиям стационарности функций (2.5): применима теорема о неявных функциях (например, теорема 2 § 41 из [2]), в силу чего вектор-функции $\bar {x}(\tau )$ и $\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\smile}$}}{\Lambda } (\tau )$ могут рассматриваться как неявно определяемые уравнениями (2.5).

Наконец, в регулярном случае (т.е. в случае однозначной разрешимости пары задач (2.1), (2.2)) $\tilde {x}(\tau )$ может служить аппроксимацией $x{\kern 1pt} *$ и соответственно $\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\smile}$}}{\Lambda } (\tau )$ – аппроксимацией для $\Lambda {\kern 1pt} *$. И, как показано, например в [3], при этом оказываются справедливыми равенства

Приступим теперь к описанию предлагаемого подхода, используя соображения, изложенные в [4].

Как известно, по свойству взаимодвойственных задач (2.1), (2.2) компоненты вектора ${{x}^{*}}$ являются множителями Лагранжа для задачи (2.2), а компоненты вектора $\Lambda {\kern 1pt} *$ суть множители Лагранжа в задаче (2.1). Однако при каждом фиксированном $\tau > 0,$ вообще говоря, имеем

Эти соотношения оказываются верными равенствами лишь в пределе при $\tau \to + 0.$

Здесь можно предположить, что найдется ${{\tau }_{0}} > 0,$ для которого будут существовать вектор-функции $\bar {x}(\tau )$ и $\bar {\Lambda }(\tau ),$ являющиеся $\forall \tau \in (0,{{\tau }_{0}}]$ решениями системы уравнений вида

для которых (в случае совместности задач (2.1), (2.2)) верны соотношения: $\mathop {lim}\limits_{\tau \to + 0} F(\bar {x}(\tau )) = F{\kern 1pt} *$ и $\mathop {lim}\limits_{\tau \to + 0} G(\bar {\Lambda }(\tau )) = G{\kern 1pt} *,$ а в регулярном случае (т.е. при единственности $x{\kern 1pt} *$ и $\Lambda {\kern 1pt} *$), кроме того, и равенства: Тогда вектор-функции $\bar {x}(\tau )$ и $\bar {\Lambda }(\tau ),$ наряду с $\tilde {x}(\tau )$ и $\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\smile}$}}{\Lambda } (\tau ),$ можно было бы использовать в качестве оценочных аппроксимаций решений задач (2.1) и (2.2).

Заметим, что система (2.6) также может быть записана в виде

где функция $Q(\tau ,s) = {\text{inv}}\left( {\tfrac{{\partial P}}{{\partial s}}(\tau ,s)} \right)$ есть обратная к функции $\tfrac{{\partial P}}{{\partial s}}(\tau ,s)$.

Возможную истинность сделанного предположения подтверждает следующий

Пример 1. Для пары задач с параметром $v$:

прямая задача: максимизировать в ${{E}^{2}}$ функцию $F(x) = 2{{\xi }_{1}} + 3{{\xi }_{2}},$

при условиях ${{\xi }_{1}} \geqslant 0,$ ${{\xi }_{2}} \geqslant 0$ и ${{\xi }_{1}} + 2{{\xi }_{2}} \leqslant v,$ $2{{\xi }_{1}} + {{\xi }_{2}} \leqslant 6;$

двойственная задача: минимизировать в ${{E}^{2}}$ функцию $G(\Lambda ) = v{{\lambda }_{1}} + 6{{\lambda }_{2}},$

при условиях ${{\lambda }_{1}} \geqslant 0,$ ${{\lambda }_{2}} \geqslant 0$ и ${{\lambda }_{1}} + 2{{\lambda }_{2}} \geqslant 2,$ $2{{\lambda }_{1}} + {{\lambda }_{2}} \geqslant 3.$

Пусть значение $v = 6,$ тогда решения имеют вид $\xi _{1}^{*} = 2,$ $\xi _{2}^{*} = 2,$ $F{\kern 1pt} * = 10$ и $\lambda _{1}^{*} = \tfrac{4}{3},$ $\lambda _{2}^{*} = \tfrac{1}{3},$ $G{\kern 1pt} * = 10.$

Если использовать $P(\tau ,s) = \tau exp\left( {\tfrac{s}{\tau }} \right)$ и соответствующую ей $Q(\tau ,s) = {\text{inv}}\left( {exp\left( {\tfrac{s}{\tau }} \right)} \right) = \tau lns,$ то система (2.7) будет иметь вид

решения которой для различных значений параметра $\tau $ приведены в табл. 1.

В последующих разделах статьи рассматриваются условия применимости методов, основанных на решении систем подобных (2.7). Здесь же отметим, что из структуры этой системы следует, что $Q(\tau ,s)$ по сути является функцией, реализующей обратную связь в наборе ограничений для прямых и двойственных переменных в задачах (2.1) и (2.2). Поэтому далее (для краткости) будет употребляться термин обратная связь при ссылках как на сами функции типа $Q(\tau ,s),$ так и на методы решения задачи (1.1), (1.2), использующих эти функции.

3. ОБОСНОВАНИЕ МЕТОДА ОБРАТНЫХ СВЯЗЕЙ ДЛЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Определим функцию $P(\tau ,s)$ так, чтобы для нее выполнялись все условия пп. 1–3 из (2.4). Тогда непрерывно дифференцируемая функция $\tfrac{{\partial P}}{{\partial s}}$ монотонно возрастает по $s$ $\forall s$ и имеет непрерывно дифференцируемую обратную функцию $Q(\tau ,s),$ которая, в свою очередь, монотонно возрастает по $s$ $\forall s > 0.$ Кроме того, для нее имеем $\mathop {lim}\limits_{s \to + 0} Q(\tau ,s) = - \infty $ $\forall \tau > 0$, $\mathop {lim}\limits_{s \to + \infty } Q(\tau ,s) = + \infty $ $\forall \tau > 0$ и $\mathop {lim}\limits_{\tau \to + 0} Q(\tau ,s) = 0$ $\forall s > 0$.

Через $R(\tau ,s)$ обозначим неотрицательную, имеющую единственный ноль функцию, для которой справедливо равенство

Заметим, что в сделанных предположениях функция $R(\tau ,s)$ существует и единственна.

Введем в рассмотрение вспомогательную (называемую далее для краткости $U$-функцией) функцию вида

Заметим, что в этом случае решения системы (2.7) (если они существуют) – векторы $\bar {x}(\tau )$ и $\bar {\Lambda }(\tau )$ – суть стационарные точки $U$-функции по совокупности переменных $\{ x;\Lambda \} .$

Теорема 3.1. Функция $U(\tau ,x,\Lambda )$ строго выпукла вверх по $x$ и строго выпукла вниз по $\Lambda $ в любой конечной точке с положительными координатами в пространстве ${{E}^{n}} \otimes {{E}^{m}}$ $\forall \tau > 0$.

Доказательство. Из соотношений (3.2) и (2.7) находим, что компоненты матрицы Гессе для $U(\tau ,x,\Lambda )$ (как функции от $x$ при фиксированных $\tau $ и $\Lambda $) имеют вид

(где ${{\delta }_{{jk}}}$ – символ Кронекера). Тогда ее главные миноры вида

Числа $\tfrac{{\partial Q}}{{\partial {{\xi }_{j}}}}$ положительные, так как в силу соотношения между производными взаимно обратных функций и условия п. 3 из (2.4)

Таким образом, в рассматриваемой подматрице Гессе все главные миноры нечетного порядка отрицательны, четного – положительны, и, согласно критерию Сильвестра, матрица Гессе функции $U(\tau ,x,\Lambda )$ по компонентам $x$ отрицательно определена. Поэтому функция $U(\tau ,x,\Lambda )$ по компонентам $x$ строго выпукла вверх.

Рассуждая аналогично, для подматрицы Гессе функции $U(\tau ,x,\Lambda )$ по компонентам $\Lambda $ получаем, что значения ее главных миноров равны $\prod\nolimits_{i = 1}^k {\tfrac{{\partial Q}}{{\partial {{\lambda }_{i}}}}} $ $\forall k = [1,m]$. В силу (3.3) эти значения положительны. Тогда, согласно критерию Сильвестра, подматрица Гессе функции $U(\tau ,x,\Lambda )$ по компонентам $\Lambda $ положительно определена, а сама функция $U(\tau ,x,\Lambda )$ по компонентам $\Lambda $ является строго выпуклой вниз при любых фиксированных $\tau $ и $x$.

Докажем теперь совместность системы (2.7).

Теорема 3.2. Система уравнений (2.7) имеет единственное решение с положительными компонентами при любом фиксированном $\tau > 0$ для любой пары задач (2.1), (2.2).

Доказательство. 1. Для каждого вектора $\Lambda $ с конечными положительными компонентами существует единственный конечный вектор $\hat {x}(\Lambda )$ с положительными компонентами такой, что верно равенство $\mathop {{\text{grad}}}\limits_x \,U(\tau ,\hat {x}(\Lambda ),\Lambda ) = 0,$ имеющее в силу (3.2) вид

поскольку функция $U(\tau ,x,\Lambda )$ строго выпукла вверх по $x,$ а условия (3.4) равносильны равенствам в которых правые части существуют, положительны и определены однозначно. Это, в свою очередь, означает, что $\hat {x}(\Lambda ) = \mathop {{\text{argmax}}}\limits_x \,U(\tau ,x,\Lambda ).$

Рассуждая аналогично, заключаем, что для каждого конечного вектора $x$ с положительными компонентами будет существовать конечный вектор $\hat {\Lambda }(x)$ с положительными компонентами такой, что

и что $\hat {\Lambda }(x) = \mathop {{\text{argmin}}}\limits_\Lambda \,U(\tau ,x,\Lambda )$ в силу строгой выпуклости $U(\tau ,x,\Lambda )$ вниз по $\Lambda .$

2. Теперь найдем минимум $U(\tau ,\hat {x}(\Lambda ),\Lambda )$ по $\Lambda .$ Из формулы (3.2) мы получаем

В силу строгой выпуклости вниз этой функции, достаточное условие ее минимума будет

или, после перегруппировки слагаемых, поскольку $\forall j = [1,n]$ и $\forall q = [1,m]$

Тогда, за счет использования (3.4), равенство (3.6) – достаточное условие минимума функции $U(\tau ,\hat {x}(\Lambda ),\Lambda )$ по $\Lambda $ – может быть упрощено до

где вектор с неотрицательными компонентами $\hat {\hat {\Lambda }} = \mathop {{\text{argmin}}}\limits_\Lambda \,U(\tau ,\hat {x}(\Lambda ),\Lambda ),$ для которого верно равенство $\mathop {min}\limits_\Lambda \mathop {max}\limits_x U(\tau ,x,\Lambda ) = U(\tau ,\widehat x(\Lambda ),\hat {\hat {\Lambda }})$ и такого, что $\left\| {\hat {\hat {\Lambda }}} \right\| = \mathop {\left\| {{{{\hat {\hat {\lambda }}}}_{1}}{{{\hat {\hat {\lambda }}}}_{2}} \ldots {{{\hat {\hat {\lambda }}}}_{m}}} \right\|}\nolimits^{\text{T}} ,$ существует и единственен в силу строгой выпуклости вниз по $\Lambda $ функции $U(\tau ,x,\Lambda )$.

Найдем теперь значение минимума по $\Lambda $ для функции $U(\tau ,\hat {x}(\Lambda ),\Lambda ).$ Имеем

Перегруппировав слагаемые, имеем, что Наконец, в силу (3.4), получим

3. Теперь рассуждениями, аналогичными п. 2, найдем $\mathop {max}\limits_x \mathop {min}\limits_\Lambda U(\tau ,x,\Lambda ).$

Поскольку функция $U(\tau ,x,\Lambda )$ строго выпукла вниз по совокупности компонент вектора $\Lambda ,$ то достаточное условие ее минимума по $\Lambda $ будет

Значение минимума функции $U(\tau ,x,\Lambda )$ по $\Lambda $ при фиксированных $\tau $ и $x$ равно

В силу строгой выпуклости вверх этой функции по $x$, достаточное условие ее максимума по $x$ (после перегруппировки слагаемых) есть

Выражения, стоящие в квадратных скобках в (3.10), равны нулю в силу (3.9) и, следовательно, достаточное условие максимума $U(\tau ,x,\hat {\Lambda }(x))$ по $x$ принимает вид

где вектор с неотрицательными компонентами $\hat {\hat {x}} = \mathop {{\text{argmax}}}\limits_x \,U(\tau ,x,\hat {\Lambda }(x)),$ для которого верно равенство $\mathop {max}\limits_x \mathop {min}\limits_\Lambda U(\tau ,x,\Lambda ) = U(\tau ,\hat {\hat {x}},\hat {\Lambda }(x)),$ существует и единственен в силу строгой выпуклости вверх по $x$ функции $U(\tau ,x,\Lambda )$.

Для значения максимума функции $U(\tau ,x,\hat {\Lambda }(x))$ по $x$ (после перегруппировки слагаемых и учета (3.11) в итоге имеем

4. Теперь заметим, что из условий (3.7) и (3.9) следует равенство $\hat {\hat {\Lambda }} = \hat {\Lambda }(\hat {\hat {x}}),$ а из условий (3.4) и (3.11) следует соответственно $\hat {\hat {x}} = \hat {x}(\hat {\hat {\Lambda }}),$ поскольку условие (3.7) является достаточным условием максимума функции $U(\tau ,x,\widehat \Lambda (x))$ по $x,$ а условие (3.11) – соответственно достаточным условием минимума функции $U(\tau ,\hat {x}(\Lambda ),\Lambda )$ по $\Lambda .$

Поясним эти утверждения, получив, к примеру, формулу $\hat {\hat {x}} = \hat {x}(\hat {\hat {\Lambda }}).$ Для этого перепишем равенства (3.4) и (3.11), переобозначив в последнем индекс $k$ на $j$.

Первая группа равенств (3.13) выполняется при любых положительных ${{\lambda }_{i}}\forall i = [1,m],$ в том числе и при ${{\hat {\lambda }}_{i}}({{\hat {\hat {\xi }}}_{j}})\forall i = [1,m].$ Очевидно, что в этом случае правые части равенств оказываются одинаковыми. Но тогда будут равны и левые, т.е. Последнее же равенство означает, что, в силу монотонности по $s$ функции $Q(\tau ,s),$ будут верны равенства ${{\hat {\xi }}_{j}}(\hat {\hat {\Lambda }}) = {{\hat {\hat {\xi }}}_{j}}$ $\forall j = [1,n],$ т.е., $\hat {\hat {x}} = \hat {x}(\hat {\hat {\Lambda }}).$

Из сопоставления формул (3.8) и (3.12) получаем, что

Это означает, что функция $U(\tau ,x,\Lambda )$ имеет седловую точку, которая, в силу непрерывной дифференцируемости $U(\tau ,x,\Lambda ),$ является для нее стационарной. Условия же стационарности можно записать в виде равносильном в своей совокупности системе (2.7), что доказывает утверждение теоремы.

В дальнейшем (если не оговорено противное) мы будем предполагать, что функция $P(\tau ,s)$ не только удовлетворяет условиям (2.4), но и что $\tfrac{{\partial P}}{{\partial s}}(\tau ,s)$ является функцией одного аргумента $u = \tfrac{s}{\tau },$ т.е.

где $\Phi (u)$ – определенная $\forall u$ функция, обеспечивающая выполнение условий (2.4).

Условие (3.14) формально является дополнительным ограничением общности при выборе вида функции $P(\tau ,s),$ не играющим существенного практического значения в силу инструментальной роли самой функции $P(\tau ,s),$ однако, позволяющим не только упростить обоснование метода обратных связей, но и, как показано в [5], улучшить характеристики его сходимости при $\tau \to + 0.$

Рассмотрим теперь свойства функции $R(\tau ,s).$ Эта функция очевидно определена при любых положительных $\tau $ и $s,$ в своей области определения неотрицательна и имеет единственный ноль, а также дважды непрерывно дифференцируема и строго выпукла вниз по $s$ на $s > 0.$ Кроме того, важное для дальнейшего свойство функции $R(\tau ,s)$ описывает

Теорема 3.3. Для любого фиксированного $s \in (0, + \infty )$ имеем $\mathop {lim}\limits_{\tau \to + 0} R(\tau ,s) = 0$.

Доказательство. В силу (3.14) функция обратной связи $Q(\tau ,s)$ определяется соотношением $\Phi \left( {\tfrac{Q}{\tau }} \right) = s$ и имеет вид $Q(\tau ,s) = \tau \Psi (s),$ где $\Psi (u)$ есть функция, определенная на интервале $(0, + \infty ),$ обратная к $\Phi (u).$

Тогда при любом конечном положительном $s$ из

следует справедливость утверждения теоремы.

Другое полезное свойство $U$-функции описывает

Теорема 3.4. Если $L(x,\Lambda )$ – функция Лагранжа пары задач (2.1) и (2.2), то $\forall x$ и $\forall \Lambda $ из области определения $L(x,\Lambda )$

Доказательство. Функция Лагранжа задач (2.1) и (2.2) имеет вид

Поэтому $U$-функцию можно записать как Применяя к формуле (3.16) утверждение теоремы 3.3, получаем утверждение доказываемой теоремы.

Дадим следующее

Определение. Совокупность точек пространства ${{E}^{n}} \otimes {{E}^{m}}$ вида $\{ \bar {x}(\tau );\bar {\Lambda }(\tau )\} $ $\forall \tau > 0$ – назовем седловой траекторией $U$-функции пары задач (2.1) и (2.2).

Из теоремы 3.2 следует, что на каждой седловой траектории определены вектор-функции $\bar {x}(\tau ),$ $\bar {\Lambda }(\tau )$, а также скалярная функция $\bar {U}(\tau ) = U(\tau ,\bar {x}(\tau ),\bar {\Lambda }(\tau ))$. Рассмотрим их свойства.

Теорема 3.5. Для собственных задач (2.1) и (2.2), т.е. задач, имеющих ограниченные оптимальные значения целевых функций, вектор-функции $\bar {x}(\tau )$ и $\bar {\Lambda }(\tau )$ имеют ограниченные компоненты на множестве $\forall \tau > 0.$

Доказательство. 1. Исходя из (2.6) и использовав (2.1)–(2.2), условия стационарности вспомогательной $U$-функции (3.2) можно записать в виде

т.е. система (2.7) распадается на две независимые подсистемы, неизвестными в первой из которых являются компоненты вектор-функции $\bar {\Lambda }(\tau ),$ а во второй – компоненты $\bar {x}(\tau ).$

Исследуем подробно вторую из них, введя для удобства следующие скалярные функции:

В этом случае вторая группа уравнений в (3.17) принимает вид системы равенств а частная производная от функции $\tfrac{{\partial P}}{{\partial s}}(\tau ,{{W}_{j}}(\tau ,x))$ по ${{\xi }_{k}}$ будет иметь вид Откуда, принимая во внимание, что в силу (2.4) вторая производная $\tfrac{{{{\partial }^{2}}P}}{{\partial {{s}^{2}}}}\left( {\tau ,s} \right)$ определена и строго положительна $\forall s,$ получаем причем в случае $\sum\nolimits_{i = 1}^m {\left| {{{\alpha }_{{ik}}}} \right|} > 0$ это неравенство будет строгим.

Таким образом, правая часть $j$-го уравнения в системе (3.18) есть монотонно убывающая функция k-й компоненты вектора $\bar {x}(\tau )$.

2. Рассмотрим теперь $j$-е уравнение в системе (3.18), в котором зафиксированы все неизвестные, кроме ${{\bar {\xi }}_{j}}$. Пусть оно имеет вид ${{\bar {\xi }}_{j}} = Z({{\bar {\xi }}_{j}})$. Заметим, что как область определения функции $Z({{\bar {\xi }}_{j}})$, так и область ее значений есть множество положительных чисел. При этом из п. 1 следует, что на всей области определения непрерывная функция $Z({{\bar {\xi }}_{j}})$ монотонно убывающая. Тогда для нее существует монотонно убывающая обратная функция $T({{\bar {\xi }}_{j}})$.

Пусть $\bar {\xi }_{j}^{*}$ – решение рассматриваемого уравнения, т.е. $\bar {\xi }_{j}^{*} = Z(\bar {\xi }_{j}^{*})$. Очевидно, что и $T(\bar {\xi }_{j}^{*}) = \bar {\xi }_{j}^{*}$. Если $\bar {\xi }_{j}^{*}$ ограничено сверху, то $\exists + \infty > {{D}_{j}} > 0:\;\;\bar {\xi }_{j}^{*} \leqslant {{D}_{j}},$ а значит, и $\bar {\xi }_{j}^{*} = T(\bar {\xi }_{j}^{*}) = Z(\bar {\xi }_{j}^{*}) \leqslant {{D}_{j}}.$ Тогда в силу монотонного убывания функции $T({{\bar {\xi }}_{j}})$ получаем $T(Z(\bar {\xi }_{j}^{*})) \geqslant T({{D}_{j}}).$ Иначе говоря, $\exists {{d}_{j}} > 0:\;\;{{d}_{j}} \leqslant \bar {\xi }_{j}^{*},$ где ${{d}_{j}} = T({{D}_{j}}) \leqslant {{D}_{j}}.$ Следовательно, $\bar {\xi }_{j}^{*}$ ограничена и снизу, причем строго положительной величиной.

Аналогичными рассуждениями можно показать, что из ограниченности снизу компоненты $\bar {\xi }_{j}^{*}$ следует ее ограниченность и сверху.

3. Покажем теперь, что в собственном случае решения системы (3.17) ограничены $\forall \tau > 0$ и имеют неограниченные компоненты в случае несобственном.

Действительно, если решения задач (2.1), (2.2) существуют и конечны, то системы

совместны.

Рассмотрим вторую из них. В этом случае для каждого $j = [1,n]$ найдется вектор ${{x}_{{(j)}}}$ такой, что ${{W}_{j}}(\tau ,{{x}_{{(j)}}}) = 0.$ Заметим, что каждая левая часть в уравнениях (3.18), которая по теореме 3.2 имеет конечное значение при любом фиксированном $\tau > 0,$ может оказаться равной, большей или меньшей, чем $\Phi (0) = \tfrac{{\partial P}}{{\partial s}}(\tau ,0).$ Тогда в силу оценок п. 2, она оказывается ограниченной как снизу, так и сверху одним из трех строго положительных чисел $T(\Phi (0)),\Phi (0)$ или $D(\Phi (0)),$ каждое из которых по предположению (3.14) не зависит от $\tau .$ Следовательно, все левые части в (3.18) равномерно ограничены на множестве значений $\tau \in (0, + \infty ).$

Для первой из систем (3.19) рассуждения аналогичны.

В несобственном же случае по крайней мере одна из систем (3.19) несовместна. Допустим, что это – вторая из них. Тогда хотя бы при одном значении индекса $i$ будет ${{f}_{i}}(x) > 0$ при всех $x$ с неотрицательными компонентами. В том числе и для $\bar {x}(\tau )$ – решение системы (3.18), которое существует по теореме 3.2.

Но тогда в силу

будет выполняться предельное равенство что и приводит к заключению о наличии неограниченных компонент решений системы (3.17) для несобственной пары задач (2.1)–(2.2).

В случае несовместности первой из систем (3.19) рассуждения аналогичны.

Теорема 3.6. Для собственных задач (2.1) и (2.2) вектор-функции $\bar {x}(\tau )$ и $\bar {\Lambda }(\tau )$ непрерывно дифференцируемы $\forall \tau > 0$.

Доказательство. 1. Введем следующие обозначения:

Матрица Якоби системы (2.7), совпадающая с матрицей Гессе вспомогательной функции (3.2), в этом случае имеет вид или, в блочной записи, $\left\| H \right\| = \left\| {\begin{array}{*{20}{c}} { - \left\| X \right\|}&{ - {{{\left\| A \right\|}}^{{\text{T}}}}} \\ { - \left\| A \right\|}&{\left\| Y \right\|} \end{array}} \right\|$.

Здесь элементами матрицы $\left\| A \right\|$ являются числа ${{\alpha }_{{ij}}}$ $\forall i = [1,m],$ $j = [1,n],$ а диагональные матрицы $\left\| X \right\|$ и $\left\| Y \right\|$ имеют элементы, определяемые формулами ${{\delta }_{{ij}}}{{\kappa }_{j}}$ $\forall i,j = [1,n]$ и ${{\delta }_{{ij}}}{{\mu }_{i}}$ $\forall i,j = [1,m]$ соответственно.

Оценим знак величины $det\left\| H \right\|$. По свойству шуровского дополнения (см., например, гл. 4, § 6, п. 5 в [6]) и в силу правил действия с матрицами, в рассматриваемом случае справедливо равенство

Числа ${{\kappa }_{j}}$ $\forall j = [1,n]$ и ${{\mu }_{i}}$ $\forall i = [1,m]$ положительные, поскольку функция $Q(\tau ,s)$ строго монотонно возрастающая. Поэтому очевидно, что $det{{\left\| X \right\|}^{{ - 1}}} > 0.$

Оценим теперь второй сомножитель: $det(\left\| Y \right\| + \left\| A \right\|{{\left\| X \right\|}^{{ - 1}}}{{\left\| A \right\|}^{{\text{T}}}}).$ Заметим, что матрицу $\left\| Y \right\|$ можно рассматривать как матрицу некоторой положительно определенной квадратичной формы в пространстве ${{E}^{m}},$ в то время как матрица $\left\| A \right\|{{\left\| X \right\|}^{{ - 1}}}{{\left\| A \right\|}^{{\text{T}}}}$ (при любом значении ранга матрицы $\left\| A \right\|$) по следствию теоремы Бине–Коши (см. гл. 4, § 5, п. 6 в [6]) задает либо положительно определенную, либо положительно полуопределенную квадратичную форму в том же пространстве.

Ясно, что в этом случае матрица $(\left\| Y \right\| + \left\| A \right\|{{\left\| X \right\|}^{{ - 1}}}{{\left\| A \right\|}^{{\text{T}}}})$ также задает в ${{E}^{m}}$ положительно-определенную квадратичную форму и имеет (в силу критерия Сильвестра) положительный детерминант. Поэтому окончательно мы получаем, что $det\left\| H \right\| > 0.$

2. Невырожденность матрицы Якоби для системы уравнений (2.7) в сочетании со сделанными предположениями о гладкости функции $Q(\tau ,s)$ допускает применение утверждений теоремы о неявных функциях [2] к этой системе. Отсюда следует непрерывность вектор-функций $\bar {x}(\tau )$ и $\bar {\Lambda }(\tau )$.

При этом компоненты вектор-функций $\tfrac{{d\bar {x}}}{{d\tau }}$ и $\tfrac{{d\bar {\Lambda }}}{{d\tau }}$ определяются $\forall \tau > 0$ системой линейных уравнений

где Причем последние функции ограничены и непрерывны в силу теоремы 3.5. Поэтому из (3.20) вытекает непрерывная дифференцируемость вектор-функций $\bar {x}(\tau )$ и $\bar {\Lambda }(\tau )$ на множестве $\tau > 0$.

Следствие 3.1. На седловой траектории для собственной пары задач (2.1) и (2.2) существуют конечные пределы $\mathop {lim}\limits_{\tau \to + 0} \bar {x}(\tau )$, $\mathop {lim}\limits_{\tau \to + 0} \bar {\Lambda }(\tau )$ и $\mathop {lim}\limits_{\tau \to + 0} U(\tau ,\bar {x}(\tau ),\bar {\Lambda }(\tau ))$.

Доказательство. Из непрерывной дифференцируемости и ограниченности вектор-функций $\bar {x}(\tau )$ и $\bar {\Lambda }(\tau )\forall \tau > 0$ в собственном случае следует их равномерная непрерывность на этом множестве. Поэтому пределы, указанные в формулировке следствия, существуют и конечны.

Свойства этих пределов описывают следующие теоремы.

Теорема 3.7. На седловой траектории для собственной пары задач (2.1) и (2.2), имеют место равенства

Доказательство. 1. Заметим вначале, что для конечных $s > 0$ в силу (3.14) имеет место равенство

Умножая обе части равенств (2.7) на ${{\bar {\lambda }}_{i}}$ $\forall i = [1,m]$ и ${{\bar {\xi }}_{j}}$ $\forall j = [1,n]$ соответственно, приходим к соотношениям

Тогда в силу сделанного выше замечания приходим к первым двум утверждениям леммы.

2. Из условий стационарности $U$-функции следуют равенства

в силу которых Аналогично находим, что

Почленное вычитание двух последних равенств дает

Тогда на седловой траектории в силу п. 1 будет верным и равенство

Теорема 3.8. На седловых траекториях для собственных задач (2.1) и (2.2) имеем

а в случае единственности решений (регулярности) пары задач (2.1) и (2.2) справедливы также равенства

Доказательство. На седловой траектории в силу (3.16)

поэтому $\forall \tau > 0$ справедливы оценки и

Для собственных задач в силу теоремы 3.5 значения всех компонент вектор-функций $\bar {x}(\tau )$ и $\bar {\Lambda }(\tau )$ ограничены на седловой траектории. Тогда из следствия 3.1 и теоремы 3.3 вытекает, что

и существуют пределы

В сделанных выше предположениях вектор-функции $\bar {x}(\tau )$ и $\bar {\Lambda }(\tau )$ непрерывны $\forall \tau > 0.$ Тогда из непрерывности $L(x,\Lambda ),$ неравенств (3.23), (3.24) и свойств суперпозиции непрерывных функций получаем

А это означает, что пределы (3.21) существуют, и что для них

Наконец, в регулярном случае функция Лагранжа задач (2.1) и (2.2) имеет единственную седловую точку $\{ x{\kern 1pt} {\text{*}},\Lambda {\kern 1pt} {\text{*}}\} ,$ поэтому тогда справедливы и равенства (3.22).

В завершение описания свойств $U$-функции для линейных задач заметим, что единственность седловой точки $U$-функции позволяет рассматривать ее представление в виде суммы функции Лагранжа и слагаемого

как метод регуляризации собственных (но нерегулярных) задач, а саму U-функцию как вариант модифицированной функции Лагранжа. Существенно, что неотрицательность оценок множителей Лагранжа гарантирована условиями (2.4).

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

Проиллюстрируем утверждения теорем 3.5–3.8 следующими вариантами примера 1.

Примером 1 со значением параметра $v = 3$, решение которого: $\xi _{1}^{*} = 3$, $\xi _{2}^{*} = 0$, $F{\kern 1pt} {\text{*}} = 6$ и $\lambda _{1}^{*} = 2 - 2t$, $\lambda _{2}^{*} = t$ $\forall t \in \left[ {0,\;\tfrac{1}{3}} \right]$, $G{\kern 1pt} {\text{*}} = 6$. Решение прямой задачи единственное и переопределенное (т.е. в точке решения число активных ограничений больше числа переменных), а решение двойственной задачи неединственное.

И примером 1 со значением параметра $v = - 3$, в котором прямая задача несовместна, а двойственная имеет неограниченное решение.

При решении задач (как альтернативу системе (2.8)) в качестве $P(\tau ,s)$ выберем функцию, для которой $\tfrac{{\partial P}}{{\partial s}} = \tfrac{s}{\tau } + \sqrt {\mathop {\left( {\tfrac{s}{\tau }} \right)}\nolimits^2 + 1} $ и соответственно $Q(\tau ,s) = \tfrac{\tau }{2}\left( {s - \tfrac{1}{s}} \right)$.

Заметим, что при таком выборе $P(\tau ,s)$ является бесконечно дифференцируемой аппроксимацией стандартной квадратичной штрафной функции, поскольку $\tfrac{s}{\tau } + \sqrt {\mathop {\left( {\tfrac{s}{\tau }} \right)}\nolimits^2 + 1} \sim \tfrac{{s + \left| s \right|}}{\tau }$ для малых положительных $\tau $. В этом случае система (2.8) принимает вид

Решения системы (3.26) для различных значений параметра $\tau $ приведены в табл. 2 и 3, а их графические представления с логарифмической шкалой аргумента показаны на фиг. 1. При этом в таблицах использованы обозначения: $\bar {F}(\tau ) = F({{\bar {\xi }}_{1}}(\tau ),{{\bar {\xi }}_{2}}(\tau ))$, $\bar {G}(\tau ) = G({{\bar {\lambda }}_{1}}(\tau ),{{\bar {\lambda }}_{2}}(\tau ))$ и ${{\bar {g}}_{1}}(\tau ) = {{g}_{1}}({{\bar {\lambda }}_{1}}(\tau ),{{\bar {\lambda }}_{2}}(\tau ))$.