Научный журнал
Современные наукоемкие технологии
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,899

МОДИФИЦИРОВАННЫЙ МЕТОД ПРОЕКЦИИ ГРАДИЕНТА В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ

Безряков В.В. 1 Солодухин В.А. 2 Цибизова Т.Ю. 3
1 Управление государственного надзора за деятельностью в гражданской авиации Федеральной службы по надзору в сфере транспорта
2 ФГБОУ ВО «Санкт-Петербургский государственный университет гражданской авиации»
3 ФГБОУ ВО «Московский государственный технический университет имени Н.Э. Баумана (национальный исследовательский университет)»
Необходимость решения прикладных задач в реальном масштабе времени определяет интерес к разработке методов оптимизации с гарантийными оценками трудоемкости вычислений, а также дает возможности повышения эффективности известных методов путем их модификации. Методы симплексного типа остаются по-прежнему основными для решения задач линейного программирования, в связи с этим в теории и практике решения задач математического программирования относительно мало уделяется внимания исследованию вычислительной сложности решения задач линейного программирования другими методами. Целью данной работы является обоснование модификации метода проекции градиента, эквивалентной методу наискорейшего спуска, и дальнейшей модификации с целью ускорения сходимости модифицированного метода к решению задачи линейного программирования. Показано, что метод проекции градиента при изменении правила выбора проектирующей матрицы на очередной итерации позволяет определить наилучшее направление движения по границе множества допустимых решений, которое совпадает с направлением наискорейшего спуска. Представлены эффективные допустимые направления, являющиеся существенными при реализации модифицированного метода проекции градиента. Сделан вывод о том, что предложенный подход синтеза методов градиентного спуска и симплексного типа в линейном программировании при незначительном увеличении вычислительной сложности компенсируется существенным уменьшением общего количества итераций.
линейное программирование
метод проекции градиента
модификация
сходимость
алгоритм
1. Фам С.Ф., Цибизова Т.Ю. Методы построения математических моделей: генетические алгоритмы // Достижения вузовской науки. Труды международной научно-практической конференции. – М.: Изд-во МГОУ, 2014. – С. 158–162.
2. Хачиян Л.Г. Полиномиальные алгоритмы в линейном программировании // Журнал вычислительной математики и математической физики. – 1980. – Т. 20, № 1. – С. 51–68.
3. Батенков А.А., Батенков К.А., Яковлев А.В. Разработка алгоритма декодирования Евклидова кода на основе симплексного базиса // Информационные системы и технологии. – 2010. – № 3 (59). – С. 134–142.
4. Саушев А.В. Сеточный метод построения областей работоспособности технических объектов на основе алгоритма симплексного поиска // Журнал университета водных коммуникаций. – 2010. – № 1. – С. 58–69.
5. Моисеев О.В., Яковлев А.В. Алгоритм приема большого ансамбля сложных сигналов на основе симплексного базиса // Телекоммуникации. – 2012. – № 4. – С. 13–19.
6. Цибизова Т.Ю., Карпунин А.А. Применение метода анализа иерархий в оценке качества процессов управления // Современные проблемы науки и образования. – 2015. – № 2.
7. Черняев Ю.А. Сходимость метода проекции градиента для одного класса невыпуклых задач математического программирования // Известия высших учебных заведений. Математика. – 2005. – № 12. – С. 76–79.
8. Безряков В.В., Крыжановский Г.А., Солодухин В.А. Прямые и обратные задачи оптимизации управления потоками воздушного движения в районе аэродрома // Научный вестник Московского государственного технического университета гражданской авиации. – 2011. – № 171. – С. 109–113.
9. Тимофеев П.А., Ягудаев Г.Г., Горячкин Б.С., Строганов Д.В. Алгоритм управляемого имитационного процесса в системах массового обслуживания // Прикаспийский журнал: управление и высокие технологии. – 2011. – № 3. – С. 62–70.
10. Мясников Е.А. Нелинейное и динамическое программирование: уч. пособие. – Хабаровск: Изд-во Хабаровская гос. акад. экономики и права, 2011. – 139 с.
11. Перепелкин Е.А. Задача параметрического синтеза многосвязной динамической системы как задача нелинейного программирования // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. – 2008. – № 1. – С. 23–27.
12. Гусев М.И. Метод динамического программирования в задаче построения множеств достижимости нелинейных управляемых систем // Известия Института математики и информатики Удмуртского государственного университета. – 2012. – № 1. – С. 42–43.

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

Применительно к задачам линейного программирования (ЛП) в качестве первой успешной попытки решения проблемы можно рассматривать результаты работы [2], распространенные в дальнейшем на некоторые классы задач нелинейного программирования. Несмотря на это, методы симплексного типа (МСТ) остаются по-прежнему основными для решения задач ЛП [3, 4], благодаря их более высокой статистической эффективности практически на всем многообразии прикладных задач, хотя и известны «искусственные» примеры, когда применение МСТ равносильно полному перебору опорных планов задачи [5, 6].

По-видимому, в связи с этим в теории и практике решения задач математического программирования относительно мало уделяется внимания исследованию вычислительной сложности решения задач ЛП другими методами.

В частности, еще в [7] отмечалось, что метод проекции градиента (МПГ) часто требует для решения задачи ЛП меньшего числа итераций по сравнению с МСТ. Интуитивно высокая эффективность МПГ объясняется тем, что при его реализации переход между точками на очередной итерации может осуществляться по внутренней части многогранника допустимых решений или по его граням, в то время как при МСТ переходы всегда происходят по ребру многогранника.

Однако в известных алгоритмах МПГ эти потенциальные возможности реализованы не полностью. Основной их недостаток состоит в том, что размерность пространства (граней), в котором осуществляется движение, на каждой итерации уменьшается на единицу до получения опорного плана задачи ЛП. Далее вычислительный процесс становится эквивалентным использованию двойственного симплекс-метода [8]. Это приводит в результате к таким же сложностям получения оценок эффективности МПГ, как и при рассмотрении МСТ.

Целью настоящей работы является обоснование модификации МПГ, эквивалентной методу наискорейшего спуска, и дальнейшей модификации с целью ускорения сходимости модифицированного метода к решению задачи ЛП.

Модифицированный метод проекции градиента

Задачу ЛП в Rn без нарушения общности рассмотрения можно представить в следующем виде:

bez01.wmf (1)

при ограничениях

bez02.wmf

bez03.wmf (2)

где Rn – n-мерное арифметическое пространство, f(x) – целевая функция; с – матрица коэффициентов ai и bi; x – матрица переменных.

Будем считать, что условия (2) линейно независимы.

Для приведения к такому виду общей задачи ЛП с линейно-независимыми условиями вида bez04.wmf достаточно разрешить эту систему уравнений относительно любых m1 переменных и исключить их из системы условий (2).

Для решения задачи ЛП методом ПГ на каждой итерации определяется [9, 10]: Nk (mk*n) – матрица, образованная транспонированными векторами-градиентами ограничений, которые по предположению на протяжении k-й итерации являются существенными, то есть выполняются как строгие равенства; Rk (n*n) – матрица проектирования; rk – n-вектор направления движения; δk – mk-вектор двойственных переменных, соответствующих существенным ограничениям.

При этом имеют место следующие соотношения

bez05.wmf, (3)

где bez06.wmf

Вычисления начинаются с допустимого решения системы (2) x0.

Значение вектора переменных после выполнения k итераций определяется выражением

bez07.wmf (4)

где λk ≥ 0 – величина максимально допустимого шага в направлении rk.

Условия оптимальности решения xk имеют вид

bez08.wmf (5)

где bez09.wmf – соответственно множества индексов существенных ограничений на k-й итерации.

В классической процедуре МПГ анализ существенности ограничений производится только в том случае, когда выполняется первое из необходимых условий оптимальности (5). При этом если xk не оптимально, одно из ограничений, для которого bez10.wmf переводится в несущественные (из матрицы Nk исключается строка) [11]. Затем осуществляется k + 1-я итерация.

Суть предлагаемой модификации МПГ состоит в том, что для перехода от xk к xk+1 определяется наилучшее из возможных направление движения по границе множества допустимых решений сокращенной задачи, которое далее используется для определения допустимого направления движения.

Один из возможных алгоритмов реализации модификации МПГ состоит из последовательности итераций, на каждой из которых (k ≥ 0) необходимо:

1) определить λk и xk+1;

2) сформировать Nk+1 путем присоединения к матрице Nk строки lT, соответствующей вектору градиента ограничения, определяющего λk, определить rk+1, δk+1;

3) проверить выполнение условий оптимальности.

Из матрицы Nk+1 последовательно исключить все строки, соответствующие несущественным ограничениям, для которых bez11.wmf, и скорректировать значения rk+1, δk+1, перейти к п.1.

Обоснование алгоритма модификации МПГ

Исследуем две вспомогательные задачи оптимизации, решение которых определяют направление движения: наилучшее в градиентных методах (задача А) и в методе ПГ (задача Б).

Задача А имеет вид [10]

bez12.wmf (6)

при ограничениях

bez13.wmf (7)

Задача Б отличается от задачи А только характером ограничений, которые имеют вид:

bez14.wmf (8)

Если задача Б разрешима, то ее решение bez15.wmf может быть найдено по алгоритму МПГ. При этом выполнение последнего из условий (8) обеспечивается нормировкой (путем деления bez16.wmf на bez17.wmf). Оптимальность bez18.wmf для задачи Б следует непосредственно из определения проекции вектора на множество.

Понятно, что решения задач А и Б отличаются в том случае, когда среди ограничений bez19.wmf и bez20.wmf есть несущественные для выбора наилучшего направления. Обозначим bez21.wmf.

По теореме Куна – Таккера необходимые и достаточные условия оптимальности решения r задач А и Б состоят в существовании векторов (α, αr) и rs ≥ 0 таких, что [10]:

bez22.wmf (9)

При этом для задачи Б первое условие имеет вид Nkrk = 0, а последнее удовлетворяется при любых α, так как rs = 0.

Учитывая выражения для Pk и δk, легко видеть, что переменные α = δk удовлетворяют второму условию из (9) при αr = 0,5. Следовательно, δk являются множителями Лагранжа для задачи Б.

Представим линейные ограничения (8) в виде Nkr = β.

Известно, что bez23.wmf.

Отсюда следует, что уменьшение любого bez24.wmf приводит к увеличению значения целевой функции. Поэтому соответствующее ограничение является несущественным и его закрепление может быть снято. Исключив его из системы (8), приходим к задаче Б меньшей размерности.

Если имеются другие bez25.wmf, процесс исключения может быть повторен. В результате получим задачу Б для которой все bez26.wmf неотрицательны. Решение последней задачи совпадает с решением задачи А.

В противоположном случае среди ограничений (8) должно найтись ограничение bez27.wmf или bez28.wmf, которое в задаче А несущественно. То есть, по крайней мере, для одного из этих ограничений должно быть bez29.wmf.

Геометрически увеличение значения целевой функции в задаче Б или А означает увеличение значения косинуса угла между вектором-градиентом целевой функции и направлением движения, определяемым текущим решением bez30.wmf и, следовательно, увеличение длины проекции вектора-градиента целевой функции на множество допустимых решений в задаче Б.

В силу единственности проекции вектора на множество – наилучшее направление также единственно. Следовательно, процесс исключения несущественных ограничений приводит к одной и той же задаче независимо от порядка их рассмотрения. При этом процесс может быть начат с любого ограничения, для которого bez31.wmf. Отсюда следует, что все такие ограничения могут быть исключены одновременно.

Таким образом, МПГ при изменении правила выбора проектирующей матрицы на очередной итерации позволяет определить наилучшее направление движения по границе множества допустимых решений, которое совпадает с направлением наискорейшего спуска.

Определение эффективных допустимых направлений по данным модифицированного МПГ

Эффективность модифицированного МПГ в значительной степени определяется структурой множества допустимых решений и прежде всего количеством ограничений (2), которые могут оказаться существенными при реализации МПГ. Сокращение количества исследуемых гиперплоскостей может быть достигнуто при использовании полученных результатов для построения допустимых направлений движения во внутренней области МДР (максимально достижимым кодовым расстоянием) [12], которые приводят на каждом шаге к возможно наибольшему приращению целевой функции.

Пусть выполнено k итераций с использованием таких допустимых направлений и определено множество X = {xs|s = 0,…, k}.

На (k + 1)-й итерации очередная точка определяется в виде

bez32.wmf,

bez33.wmf. (10)

Очевидно, найдутся такие значения m, l, что xk + 1, определяемое таким образом, является допустимой точкой. В частности, при m = 1, l = lk получаем точку, соответствующую МПГ.

Для определения направления, приводящего к наибольшему приращению целевой функции, рассмотрим задачу

bez34.wmf (11)

при ограничениях

bez35.wmf

bez36.wmf

Возможны два случая решения этой задачи.

В первом случае m* = 1, l* = lk. Это означает, что нельзя найти допустимое направление выбранного вида, приводящее к большему значению целевой функции по сравнению с модифицированным МПГ. При этом выделяется одно новое существенное ограничение.

Во втором случае m* < 1, l* > lk. При этом выделяются два новых существенных ограничения.

Пусть при m = 1, l = lk существенным становится ограничение с номером q. Тогда для всех bez37.wmf имеем bez38.wmf

Обозначим l = 1 – e, m = lk + d. Очевидно существуют такие e, d > 0, что имеет место

bez39.wmf

bez40.wmf

Для таких e, d получаем

bez41.wmf

bez42.wmf

Исключая из равенства одну из переменных e, d и подставляя ее значение в неравенство, получаем, что при фиксированных значениях e, d наибольшее приращение целевой функции при движении в q-й гиперплоскости достигается тогда, когда

bez43.wmf

Выбор такого направления обеспечивает наилучшее приближение к направлению движения в q-й гиперплоскости при использовании модифицированного МПГ и поэтому может считаться наиболее целесообразным.

Задача (11) при фиксированном xs сводится к задаче линейного программирования с двумя переменными. Ее решение вычислительных трудностей не представляет.

Решение исходной задачи сводится, таким образом, к решению последовательности задач вида (11).

При этом, если m* = 1 определение rk и проверка условий оптимальности осуществляются по алгоритму модифицированного МПГ. При m* < 1 матрица Nk+1 формируется по двум ограничениям, определяющим решение задачи (11) и выражения (3) для определения rk, δk можно записать в явном виде.

Заключение

Сопоставление детального анализа оценок вычислительной сложности отдельных итераций и результатов многократной практической апробации алгоритма, реализующего предложенный подход, показывает, что незначительное увеличение вычислительной сложности, связанное с решением на каждой итерации задачи вида (11), компенсируется существенным уменьшением общего количества итераций по сравнению с алгоритмом МПГ. Предложенная схема формирования допустимых направлений не претендует на получение безупречно точного наиболее эффективного метода, а является только примером возможного синтеза методов градиентного спуска и симплексного типа в линейном программировании.


Библиографическая ссылка

Безряков В.В., Солодухин В.А., Цибизова Т.Ю. МОДИФИЦИРОВАННЫЙ МЕТОД ПРОЕКЦИИ ГРАДИЕНТА В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ // Современные наукоемкие технологии. – 2018. – № 6. – С. 20-24;
URL: https://top-technologies.ru/ru/article/view?id=37027 (дата обращения: 29.11.2021).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074