Диссертация (1150576), страница 8
Текст из файла (страница 8)
Далее с помощьюразрежения матрицы задачи находится расширенное множество решений, а затем полное решение в виде некоторого семейства подмножеств. Предлагаютсяпроцедуры, позволяющие сократить число подмножеств, которые необходимоисследовать при построении полного решения. Показано, как полное решениезадачи может быть записано в параметрическом виде в компактной векторнойформе. Для иллюстрации полученных результатов приводится пример численного решения задачи на множестве трехмерных векторов.3.1Задачи тропической оптимизацииЗадачи тропической оптимизации обычно состоят в минимизации или максимизации некоторой целевой функции, заданной на векторах над идемпотентным полуполем.
Такие задачи возникают, например, при исследовании уравнения = , для которого требуется найти точное или приближенное решение [40, 44, 60–62].54Сначала предположим, что заданы матрица ∈ X× и вектор ∈ X .Пусть требуется найти регулярные векторы ∈ X , которые решают задачуmin ()− ⊕ − (3.1)Решение этой задачи обеспечивает наилучшее приближенное решение уравнения = в смысле псевдочебышевской метрики. Исследование задачибыло проведено, например, в работe [102], где приводится частичное решение вследующем виде.Лемма 4. Для любых регулярных матрицы и вектора минимум в задаче(3.1) равенΔ = (((− )− )− )1/2и достигается при = Δ(− )− .Обобщением задачи (3.1) с дополнительным вектором ∈ X является задача нахождения регулярных векторов , которые обеспечиваютmin ()− ⊕ − .(3.2)Заметим, что при = получается задача минимизации функции− ⊕ − ,полное решение которой было получено в [101, 102].В настоящей работе задача (3.2) рассматривается в следующей форме.
Пустьзаданы матрица ∈ X× и векторы , ∈ X . Требуется найти все регулярныевекторы ∈ X , на которых достигаетсяmin ()− ⊕ − .(3.3)В работах [101, 102] было получено частичное решение этой задачи.Ниже для решения задачи (3.3) сначала также, как в работах [101, 102], будет определен минимум целевой функции и получено одно из решений. Затем55для полного решения задачи строится система неравенств, которая определяетмножество всех решений. На основе использования разреженных матриц, находится более широкое множество решений, а затем полное решение задачи вформе семейства подмножеств решений.3.2Предварительный анализ задачиЦель этого раздела состоит в том, чтобы найти минимум целевой функции,охарактеризовать множество решений и описать некоторые свойства этого множества.
Для этого будем использовать подход [59,63,101,102], при котором вводится параметр для обозначения минимума целевой функции, а затем задачаоптимизации сводится к решению параметризованного неравенства. Докажемследующее утверждение.Лемма 5. Пусть – регулярная по строкам матрица, а и – регулярныевекторы. Тогда минимум в задаче (3.3) равенΔ = (()− )1/2 ,(3.4)а все регулярные решения определяются системой неравенств ≥ Δ−1 , ≤ Δ.(3.5)В частности, минимум достигается при = Δ .Доказательство.
Обозначим минимум целевой функции через . Рассмотримравенство = ()− ⊕ − .Заметим, что для всех регулярных векторов справедливо > 0. Так как –минимум, то можно заменить равенство на неравенство ≥ ()− ⊕ − ,56которое эквивалентно двум неравенствам ≥ ()− , ≥ − .Решая с помощью леммы 1.4 первое неравенство относительно , а второеотносительно , приходим к системе из двух неравенств ≤ , ≤ .После подстановки второго неравенства системы в первое, получаем ≤ 2 ,а затем ≥ (()− )1/2 = Δ,и таким образом находим нижнюю границу для . Проверим, что эта границадостигается при = Δ . Действительно, после подстановки в целевую функцию имеем()− ⊕ − = Δ−1 ()− ⊕ Δ − = Δ.Следовательно, нижняя граница Δ для оказывается точной и поэтомуопределяет минимум целевой функции.Заменив в системе на Δ, а затем, умножив обе части первого неравенствана Δ−1 , получаем, что все регулярные решения задачи (3.3) должны удовлетворять системе (3.5).
Учитывая эквивалентность преобразований, верно и обратное утверждение: любой регулярный вектор , удовлетворяющий системе (3.5),является решением задачи (3.3).Следствие 1. Множество решений задачи (3.3) вместе с любыми решениямисодержит их всевозможные выпуклые линейные комбинации.Доказательство. Рассмотрим случай выпуклой линейной комбинации двух решений. Пусть 1 и 2 – решения задачи (3.3), а 1 и 2 – такие числа, что1 ⊕ 2 = 1.57Так как векторы 1 и 2 являются решениями задачи (3.3), то они определяются системой (3.5). Тогда их выпуклая комбинации удовлетворяет соотношениям(1 1 ⊕ 2 2 ) ≥ 1 Δ−1 ⊕ 2 Δ−1 = (1 ⊕ 2 )Δ−1 = Δ−1 ,1 1 ⊕ 2 2 ≤ 1 Δ ⊕ 2 Δ = (1 ⊕ 2 )Δ = Δ.Следовательно, вектор 1 1 ⊕ 2 2 также является решением задачи (3.3).Полученный результат легко обобщается на случай с произвольным количеством решений.3.3Разрежение матрицы задачиДля расширения множества решений задачи (3.3) применим метод с использованием разрежения матриц, предложенный в [103].
Сначала преобразуем мат-̂︀ = (̂︀рицу задачи = ( ) в разреженную матрицу ), приравнивая к нулювсе элементы, которые строго меньше порогового значения по следующему правилу:⎧⎨ , если ≥ Δ−2 −1 ;̂︀ =⎩0,в противном случае.̂︀, полученную при помощи такого преобразования, будемДалее матрицу называть разреженной матрицей задачи.
Свойства этой матрицы отражает следующий результат.̂︀ не меняет множество решений задачиЛемма 6. Замена матрицы на (3.3).Доказательство. Сначала проверим, что переход к разреженной матрице сохраняет минимальное значение Δ целевой функции, полученное в лемме 5. Дляупрощения выкладок рассмотрим величину Δ2 . Определим индексы и следующим образом: = arg max (1 1 ⊕ · · · ⊕ )−1 ,1≤≤ = arg max ,1≤≤58и запишем выражение для Δ2 в виде⨁︁Δ = () =(1 1 ⊕ · · · ⊕ )−1 =2−=1= (1 1 ⊕ · · · ⊕ )−1 = ( )−1 .Регулярность по строкам матрицы и регулярность вектора гарантируют, что1 1 ⊕ · · · ⊕ > 0, = 1, .
. . ,.Кроме того, так как вектор – регулярный, то Δ > 0, а значит и > 0.Рассмотрим произвольную строку матрицы . Из формулы для Δ2 видно,чтоΔ2 ≥ (1 ⊕ · · · ⊕ )−1 .Это эквивалентно неравенству1 1 ⊕ · · · ⊕ ≥ Δ−2 ,которое верно только при условии, что выполняется неравенство ≥ Δ−2 для некоторого индекса . Отсюда заключаем, что в каждой строке матрицы существует по меньшей мере один элемент , который удовлетворяет условию ≥ Δ−2 −1 .(3.6)Рассмотрим строку матрицы , чтобы убедиться в справедливости неравенства ≤ Δ−2 −1для всех в этой строке. Если = 0, то это неравенство, очевидно, выполняется. При условии > 0 имеем( )−1 ≥ (1 1 ⊕ · · · ⊕ )−1 = Δ2 ,59из чего следует, что неравенство также выполняется.
Так какΔ2 = ( )−1 ,то в строке есть элементы, которые превращают неравенство (3.6) в равенство,но нет ни одного, для которого (3.6) становится строгим неравенством.Предположим теперь, что неравенство (3.6) не выполняется для некоторых и . Учитывая, что > 0, можно записать < Δ−2 −1 ≤ (1 1 ⊕ · · · ⊕ )−1 ,откуда получаем неравенство < 1 1 ⊕ · · · ⊕ .В этом случае уменьшение путем понижения значения вплоть до 0, невлияет на величину 1 1 ⊕ · · · ⊕ и, следовательно, на значениеΔ2 ≥ (1 1 ⊕ · · · ⊕ )−1 .Проверим, что все элементы , которые не удовлетворяют неравенству(3.6), можно обнулить, оставляя без изменений множество регулярных решений задачи (3.3).Рассмотрим систему (3.5). Записав первое неравенство системы в скалярнойформе, получим, что для каждого выполняется неравенство1 1 ⊕ · · · ⊕ ≥ Δ−1 .Учитывая регулярность векторов и , умножая обе части второго неравенства системы на регулярный вектор − слева, можно привести это неравенствок эквивалентному неравенству − ≤ Δ.60В скалярной форме получаем, что1−1 1 ⊕ · · · ⊕ −1 ≤ Δ.Предположим, что в матрице имеется элемент, скажем , удовлетворяющий условию < Δ−2 −1и тем самым нарушающий неравенство (3.6).
Тогда будем иметь < Δ−2 −1 ≤ Δ−2 (1−1 1 ⊕ · · · ⊕ −1 ) ≤≤ Δ−1 ≤ 1 1 ⊕ · · · ⊕ .В этом случае слагаемое не вносит никакого вклада в значение суммы 1 1 ⊕ · · · ⊕ . Следовательно, можно положить = 0, не изменяямножество решений уравнения.Осталось понять, что обнуление элементов , которые не удовлетворяют̂︀.неравенству (3.6), равносильно замене матрицы на ̂︀ отвечают условиюЗаметим, что ненулевые элементы матрицы ̂︀ ≥ Δ−2 −1 .̂︀− = (̂︀Тогда для элементов матрицы − ) справедливо соотношение2−1̂︀− ≤ Δ .В матричной форме имеем неравенство̂︀− ≤ Δ2 − ,которое будет использовано ниже.613.4Полное решение задачиВ этом разделе будет представлено полное решение задачи (3.3) в виде семейства решений, которое задается множеством матриц, полученных из разреженной матрицы задачи путем дальнейшего обнуления ее элементов.Начнем с того, что расширим решение = Δ , полученное в лемме 5, донекоторого множества с помощью следующего утверждения.Лемма 7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
