Дискретная оптимизация и моделирование в условиях неопределенности данных
Перепелица В. А., Тебуева Ф. Б.,
В условиях неопределённости данных особого внимания заслуживают методы покоординатного спуска (градиентные алгоритмы) [83] по следующей причине. Если параметры задачи, например, в целевой функции (2.21) коэффициенты не являются действительными числами, а, допустим, являются интервалами [11] или нечеткими множествами [76], то эти алгоритмы можно использовать, заменяя операцию «поиск направления с максимальным (по абсолютной величине) числовым приращением целевой функции» на операцию «поиск наиболее предпочтительного направления». Иными словами, алгоритмы покоординатного спуска сохраняют свой принцип пошагового движения в «лучшем направлении» и в условиях неопределённости данных.
Описанный выше алгоритм решения задачи (2.22)-(2.23) относится к методам типа покоординатного спуска. Алгоритмы этого типа очень просты и малотрудоемки. Поэтому весьма интересно выявить класс задач, в которых искомый оптимум находится методом покоординатного спуска. В настоящем п.2.4 мы выделим один такой класс задач выпуклого (вогнутого) целочисленного программирования и установим признак разрешимости задачи из этого класса посредством алгоритма покоординатного спуска.
Обозначим через конечное множество целочисленных точек
, лежащее в положительном октанте
-мерного пространства
и содержащее начало координат
. В целях наглядности, на рис.2.5 дано геометрическое представление множества P в 3-мерном пространстве
.
.
Рисунок 2.5. Пример множества P в 3-мерном пространстве .
Рассмотрим следующий класс задач выпуклого целочисленного программирования с максимизирующей целевой функцией
,(2.24)
у которой аргумент – это
-мерный целочисленный вектор и
,(2.25)
где – выпуклые вверх (т.е. вогнутые) функции целочисленного аргумента
.
Нашей целью будет исследование разрешимости задачи (2.24)-(2.25) посредством алгоритма покоординатного спуска (алгоритма ПС). Приведем неформальное описание этого метода.
Алгоритм ПС. Процесс вычислений начинается с точки .
Пусть после некоторого числа шагов мы пришли к точке . Следующий шаг состоит в переходе к такой точке
, которая:
1) непосредственно следует за , т.е. отличается от
лишь одной координатой
и
;
2) выбирается так, чтобы приращение
было положительное и максимально возможное.
Если такой точки не существует, то процесс заканчивается в точке
, если же их несколько, то выбирается любая из них. За конечное число шагов процесс заканчивается в некоторой точке
. В этом случае будем говорить, что алгоритм приводит к точке
или
есть результат применения алгоритма ПС на множество
.
Вопрос (*): для каких множеств алгоритм ПС приводит к точке
, являющейся решением задачи (2.24)-(2.25) с целевой функцией
вида (2.25)?
Иными словами, мы хотим обосновать критерий, который очертил бы по возможности более широкий круг задач, решаемых посредством алгоритма ПС. Для этого нам понадобятся в дальнейшем следующие обозначения:
1) –
-мерные векторы с неотрицательными целочисленными компонентами;
означает, что компоненты векторов
и
удовлетворяют неравенствам
,
;
2) ;
3) – вектор,
-я компонента которого равна 1, а остальные
компонент равны нулю;
4) – множество допустимых направлений в точке
относительно множества
;
5) – множество максимальных точек множества
;
6) ;
7) , при
;
8) ,
– множества максимальных точек множеств
и
соответственно.
Рассмотрим значение целевой функции в точке
и сравним его со значением в соседней точке
. Полученное приращение обозначим
.
Заметим при этом, что для функции вида (2.25) при выполнении неравенства
имеем
,
. Согласно определению алгоритма ПС переход из точки
происходит в такую точку
, для которой
и
.
Исчерпывающий ответ на поставленный выше вопрос (*) дает
Теорема 2.5. Для того, чтобы алгоритм ПС приводил к решению задачи (2.24)-(2.25) при любых вида (2.25), необходимо и достаточно, чтобы множество
обладало двумя свойствами:
(А): если , то параллелепипед
;
(B): для всякого вектора существует число
такое, что из
следует
.
Доказательство необходимости. Для того, чтобы доказать необходимость условия (А), предположим противное. Пусть и
. Тогда найдутся точки
и координата
такие, что
,
,
.
Определим теперь целевую функциюследующим образом:
(2.26)
а для всех положим
(2.27)
Если к целевой функции , определяемой соотношениями (2.26) и (2.27), применим алгоритм ПС, то в результате покоординатного спуска придем в точку
. В то же время
. Полученное противоречие доказывает необходимость условия (А).
Доказательство необходимости условия (В) также проведем рассуждением от противного, т.е. предположим, что условие (В) нарушено следующим образом. Пусть для некоторого существуют точки
и
такие, что
и
(т.е.
и
– максимальные точки из одного и того же множества
), но
,
и
(т.е. указанного числа
, одинакового для всех
, не существует).
Положим теперь для определенности ,
,
Начиная с точки , будем искать оптимальное решение согласно определению алгоритма ПС. Согласно определению приращения
вначале, продвигаясь в
-мерном пространстве на каждом шаге на величину
, каждый раз получаем для
приращение
. Поскольку считается, что наше множество
обладает свойством (А), то через
шагов мы по необходимости придем в точку
, в которой значение
. По условию точка
, т.е.
– максимальная точка. Тогда попав в точку
, мы из нее уже не выйдем. Действительно, если по направлению
имеем неравенство
, то при попытке продвинуться на величину
, мы выйдем из множества
в силу максимальности точки
. Если же
, то при попытке продвинуться на величину
мы выйдем из множества
в силу
.
Итак, в качестве окончательного решения мы придем к точке . В то же время по условию имеем
, т.е.
. Следовательно, решение
– не является оптимальным, т.е. приходим к противоречию. Необходимость свойств (А) и (В) доказана.
Прежде, чем переходить к доказательству достаточности условий теоремы 1.5, отметим некоторые очевидные факты и докажем одну лемму.
Последовательность множеств является монотонно возрастающей и при достаточно больших
будет выполняться равенство
.
Замечание 2.3. Если всё множество обладает свойствами (A) и (B), то этими свойствами обладают так же и множества
,
. Кроме того, если
, то множество допустимых направлений
. Следовательно, если
есть результат применения алгоритма ПС на множестве
, а
– предпоследняя точка на пути из 0 в
, то имеем равенство
в случае
. В противном случае
.
Лемма 2.1. Если ,
и
обладает свойством (В), то найдется индекс
, для которого значение
.
Доказательство. В силу свойства (В) из условий леммы 2.1 следует неравенство . Предположим противное, т.е. что неравенство
выполняется при любом индексе
. Определим вектор
, положив
,
. Тогда на множестве
точки
и
являются максимальными, что невозможно из-за выполнения свойств (В). Полученное противоречие завершает доказательство леммы 2.1.
Продолжим доказательство теоремы 2.5.
Достаточность. Доказательство проведем для множеств методом индукции по
. При
утверждение тривиально. Предположим, что для множества
(
) алгоритм ПС приводит к решению задачи. Пусть
есть результат применения алгоритма ПС на множестве
.
Возможны два случая:
a) ;
b) .
Рассмотрим случай b). Пусть переход в точку произошел из точки
.Тогда эта точка
является результатом применения алгоритма ПС на множестве
. По предположению индукции функция
достигает в точке
максимума на
. Кроме того, по определению алгоритма ПС приращение на последнем шаге
. Последнее означает, в частности, что
.
Рассмотрим любую точку . По доказанной выше лемме 2.1 существует индекс
, для которого выполняется неравенство
и, следовательно, в силу вогнутости функции
выполняются соотношения
, т.е.
. Отсюда, т.к.
и в силу индукционного предположения в точке
достигается максимум.
Таким образом
.
Это соотношение в произвольности выбора y означает, что достигает в
максимума на
. Теорема 2.5 доказана полностью.
Итак, мы установили необходимые и достаточные условия (А) и (В), при выполнении которых класс задач выпуклого или вогнутого целочисленного программирования можно решать экономным методом ПС. Спрашивается, насколько широк указанный класс? Наглядный ответ на этот вопрос можно дать, если обратиться к конкретному виду ограничений определяющих множество .
Ниже мы исследуем один класс, соответствующий случаю, когда множества определяются линейными соотношениями. Именно, рассмотрим множества
, определяемые неравенствами:
,
,(2.28)
где ,
и
– целые неотрицательные числа. Удовлетворяющий этим условиям пример множества
для
представлен на рис.2.6.
Очевидно, что при любых
и
множество
, определяемое условиями (2.28), содержит начало координат и обладает свойством (А) (если
, то и параллелепипед
).
.
Рисунок 2.6. Пример множества P, удовлетворяющего условию (2.28) для .
Если каждая переменная входит хотя бы в одно ограничение (2.28), это множество
будет также и ограниченным, т.е. для любого
существует
такое, что
.
Что касается свойства (В), то при произвольных и
в (2.28) множество
этим свойством, вообще говоря, не обладает. Однако, можно указать такие дополнительные ограничения, налагаемые на матрицу
, при выполнении которых множество
будет обладать свойством (В) независимо от значений правых частей неравенств (2.28). С практической точки зрения именно этот случай представляет наибольший интерес.
Для формулировки указанных ограничений введем в рассмотрение множества ,
, где
есть множество номеров
всех переменных
, входящих в
-ое неравенство, т.е.
. Например, для матрицы
эти множества имеют вид:
,
,
,
.
Условимся, что в матрицах вида пустые клетки означают нули. Далее ради краткости будем говорить, что матрица
имеет структуру типа дерева, если любые два множества
,
,
, таковы что, либо они не имеют общих элементов, либо одно из них включает другое. Например, матрица
имеет структуру типа дерева, а матрица
– не имеет, т.е.
,
и
.
Теперь может быть сформулирована и доказана
Теорема 2.6. Для того, чтобы при фиксированных и произвольных
определяемые неравенствами (1.28) множества
обладали свойством (В), необходимо и достаточно, чтобы матрица
имела структуру типа дерева.
Доказательство необходимости проведем рассуждением от противного. Пусть структура матрицы отлична от указанной в условиях теоремы. Тогда найдутся два множества, скажем
и
, такие, что ни одно из них не включает другое и
. Пусть
,
,
. Правые части неравенств (2.28) положим следующими:
и
для всех
(2.29)
и рассмотрим множество при
.
Для этого множества максимальными являются следующие две точки: и
, для которых
, то есть свойства (В) нарушено. Т.о., при указанных в (2.29) величинах
множество
не обладает свойством (В).
Необходимость доказана.
Достаточность. Пусть матрица имеет структуру типа дерева и
. Тогда множество
, будучи ограниченным, имеет максимальные точки. Пусть
- максимальная точка.
Номер назовем критическим, если
- траекторией ограничение системы (2.28) выполнятся в точке
как равенство, и для любого
, такого, что
,
-е ограничение выполняется как строгое неравенство.
В силу максимальности точки , для любого
существует критический номер
такой, что
. Пусть
есть множество всех критических номеров
. Тогда семейство множеств
является разбиением множества
на непересекающиеся подмножества, и, следовательно,
. Кроме того, для произвольной точки
имеет место неравенство
.
В частности, для любой максимальной точки имеем
.
Поскольку ,
в наших рассуждениях можно поменять местами, то нами доказано равенство
. Таким образом, существует число
такое, что для любой максимальной точки
множества
имеет место равенство
.
Рассмотрим теперь некоторое и к множеству
, определяемому соотношением (2.28), добавим условия
,
, в результате чего получим множество
. Доказанное утверждение остается справедливым и в этом случае, т.е. получим выполнение свойства
.
Теорема 2.6 доказана полностью.
Алгоритм покоординатного спуска чаще всего используется в качестве приближённых методов дискретной оптимизации.