Научная электронная библиотека

Монографии, изданные в издательстве Российской Академии Естествознания

Дискретная оптимизация и моделирование в условиях неопределенности данных

Перепелица В. А., Тебуева Ф. Б.,

2.4. Методы типа покоординатного спуска для дискретных экстремальных задач.

В условиях неопределённости данных особого внимания заслуживают методы покоординатного спуска (градиентные алгоритмы) [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 доказана полностью.

Алгоритм покоординатного спуска чаще всего используется в качестве приближённых методов дискретной оптимизации.