Двойственный метод приведенного градиента в выпуклом программировании и порожденное им семейство алгоритмов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение . ^

Глава I. Задача выпуклого программирования с линейными ограничениями. ^

§1. Описание метода.4 Я

§2. Обоснование метода . ^

§3. Устойчивость метода . .Я-Я

§4. Вычислительные особенности

§5. Связь с другими методами.3Z

Глава П. Декомпозиция. ^ <

§1. Декомпозиция задачи выпуклого программирования с блочной структурой ограничений

§2. Обобщённые верхние границы.

§3. Метод подвижного базиса.с/Я

Глава Ш. Задача квадратичного программирования . 5"

§1. Применение прямых итеративных методов для решения Р-задачи. S

§2. Применение прямых конечных методов для решения Р-задачи.

§3. Применение двойственных итеративных методов для решения Р-задачи. 6 о

§4. Применение двойственного метода для решения

Р-задачи без обращения С.4

§5. Обсуждение.

Глава 1У. Численный эксперимент.4

§1. Описание эксперимента.

§2. Обсуждение результатов эксперимента . 8Z

В последнее время методы решения прикладных задач развиваются особенно быстрыми темпами. И это неудивительно, так как применение математических методов в экономике часто приводит к большой экономии средств при незначительных дополнительных затратах. Так за последние 20 лет были разработаны эффективные методы решения оптимизационных задач /см. работы [V, 3 5-3 /. Полученные результаты используются при анализе, проектировании и планировании работы

В настоящей диссертации предложен двойственный метод решения задач выпуклого программирования с линейными ограничениями, рассмотрены различные декомпозиционные подходы с использованием указанного метода. Метод детализируется для решения важной с точки зрения црактического применения задачи квадратичного программирования. Потребность в эффективных методах подобного рода диктуется тем, что при использовании ряда методов выпуклого программщювания на каждом шаге приходится решать задачу минимизации выпуклой функции при линейных ограничениях. Это прежде всего различные варианты методов возможных направлений, отсечения^ЗЗ], проекций градиента ]. Процедура решения задач квадратичного программирования используется как подзадача во многих приложениях и поэтому должна решаться большое число раз В связи с этим эффективность метода имеет особую ценность [S4}-1<I3~] .

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

Впервые термин "двойственный метод" был введён Лемке [1QZ 3 для обозначения метода решения задач линейного программирования. Этот метод получил дальнейшее развитие в работах Вагнера для ограниченных сверху переменных и Розена Для случая блочно-диагональной матрицы ограничении. Оригинальный подход для декомпозиции задачи линейного программирования предложил Озе . Имеется много различных модификаций перечисленных методов, их полное перечисление заняло бы слишком много места. Мы ограничились перечислением лишь тех работ, в которых двойственный метод был использован для решения задач линейного программирования со своей спецификой ограничений. К их числу относится также работа [s* в которой двойственный метод применялся для решения задачи линейного программирования с обобщёнными верхними границами.

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

Данном и Винстоном Q/o^-fO? 3 в 1964 rW« В работе [г*05] приведено сравнение этого метода с прямым методом Била Характерной особенностью метода \jQ6~\ является то, что он представляет собой точную копию прямого метода Данцига

26 с зэменой вектора прямых переменных на вектор двойственных переменных и наоборот. Оба метода являются методами симплексного типа. Детализация метода на случай ограниченных сверху переменных была выполнена Винстоном

-U6~] .

От жёсткой симплексной схемы свободен метод Григориа-диса и Риттера который является попыткой применения двойственного подхода для декомпозиции задач линейного и выпуклого программирования с блочной структурой матрицы ограничений. Суть метода заключается в том, что в каждом блоке выделяется группа базисных переменных, выраженных через остальные переменные блока. Их выражения подставляются в целевую функцию и блочные ограничения, общие для ■ всех блоков. Полученная таким образом задача называется модифицированной и отличается от исходной тем, что с базисных переменных снято ограничение неотрицательности. Модифицированная задаш проще исходной, так как в ней отсутствуют блочные ограничения. После решения модифицированной задачи вычисляются значения базисных переменных. В случае их неотрицательности получено оптимадьное решение исходной задачш, в противном случае делается обмен между отрицательной базисной переменной блока и одной из внебазисныя переменных. Такой обмен обеспечивает монотонность изменения значений целевой функции. Однако, авторы требуют, чтобы выбранная для обмена внебазисная переменная имела положительное значение. В тех случаях, когда такая переменная отсутствует, авторы предлагают включить нарушенное ограничение в число общих ограничений модифицированной задачи. Нет гарантии, что таким образом не прийдётся включить в их число все блочные ограничения. Невозможность избавиться от блочных ограничений в модифицированной задаче не позволила применить этот подход к решению задач с произвольной структурой ограничений.

Предложенный в настоящей диссертации метод кроме двойственной идеи использует также способ подстановки, который часто встречается в прямых методах. В частности его используют Бэст и Карон £ $& однако они не накладывают условия неотрицательности на переменные задачи, что позволяет им применить прямой метод. К этой работе примыкает более ранняя статья гДе описана реализация прямого метода решения задачи нелинейного программирования с линейными ограничениями. Как указывают сами авторы, их работа является дальнейшей разработкой прямого метода Вульфа £ -1G J с использованием последних достижений в области численных методов. Описанная Вульфом в \-iG схема решения задач с линейными ограничениями является универсальной для прямых методов. В этом смысле предложенная в диссертации двойственная схема противопоставляется схеме Вульфа как двойственная прямой. В своей работе [ji'C^i ^ Муртаг и Саундерс указывают, что при числе ограничений, во много раз превосходящем число переменных, требуется метод, аналогичный двойственному методу линейного программирования.

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

1. Архипова Т.А. Сергиенко И.В.2. Бакман Е.Г.3. Бакман Е.Г.4. Бакман Е .Г.

2. Бейко И.В. Бублик Б.II. Зинько П.Н.

3. Демьянов В.Ф. Малозёмов В.Н.29. Ддорж А. Лю Д.30. Евтушенко Ю.Г,31. Евтушенко Ю.Г. Жадан В.Г.32. Ерёмин И.И. Астафьев Н.Н.33. Ерёмин И.М.

4. Журбенко Г.Н. Исследование одного класса алгоритмов минимизации негладких функций и их применение к решению задач большой размерности.-Автореф. дис. . канд.физ.-мат. наук. Киев, 1977.- 24с.

5. Зангвилл У. Нелинейное программирование. Единый подход.ГЛ.: Сов .рацио, 1973.

6. Зуховицкий С.й.Линейное и выпуклое программирование.- М.: Авдеева Л.И. Наука, 1967.

7. Иванов В.В. Об оптимальных алгоритмах минимизации функцийнекоторых классов.- Кибернетика, 1972, М.

8. Ицкович И.А. Метод дробных шагов для решения оптимизационных задач.- Оптимизация, 1974, №14,с.55-65.

9. Карманов В.Г. Математическое программирование.- М.: Наука,1975.- 272с.

10. Кириевский Л. Об ускорении сходимости методов выпуклого про-Поляк Р.А. грамм1фования.- Докл.АН СССР, 1973, 209, 15.

11. Малков У.Х. Обзор программ решения общей задачи линейногопрограммирования.- Экономика и мат. методы, 1969 , 5, М, с.594-597.

12. Михалевич B.C. Последовательные алгоритмы оптимизации и ихприменение. 4.1-2.- Кибернетика, 1965,

13. Михалевич B.C. Исследование методов решения оптимизационных Сергиенко И.В. задач и их приложения.- Кибернетика, 198I, Шор Н.З. М, с.89-113.

14. Немировский А. Информационная сложность математического про-Юдин Д.Б. граммирования.- Изв.АН СССР. Техн. кибернет.,1983, Ж, с.88-117.

15. Нестеров Ю.Е. К вопросу тестирования алгоритмов превого поСкоков В.А. рядка безусловной минимизации. 4исл. методыматемат. программирования, М., 1980, с.77-91.

16. Пропой А.И. Параметрическое квадратичное и илинейное про-Ядыкин А.Б. граммирование.- Автоматика и телемех., 1978,S2, С.Ю2-П2, 114, с. 135-143.

17. Пшеничный Б.Н. Численные методы в экстремальных задачах.- М.: Данилин Ю.М. Наука, 1975.- 319с.57. Полак Э.58. Поляк Б.Т.59. Поляк Б.Т.60. Поляк Б.Т.61. Поляк Р.А.gs

18. Пшеничный Б.Н. Ускорение сходимости метода линеаризации для Соболенко Л .А. задачи условной минимизации.- Ж.вычисл. матем.и мат. физики, 1980, 20, №3, с.605-614.

19. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи.- М.:Наука, 1980.- 320с.

20. Пшеничный Б.Н. Метод линеаризации.- М.: Наука, 1983,- 136с.

21. Ракецкий В.М. Прямой опорный метод квадратичного программирования.- Пробл. оптимального управления. Минск, 1981, с.318-335.

22. Соболенко Л.А. Методы ускорения сходимости некоторых алгоритмов оптимизации и их эффективная реализация.-Автореф. дис. канд.физ.-мат. наук.- Киев, 1983.- 21с.

23. Численные методы условной оптимизации, /ред. Ф.Гилл, У.Мгоррэй/- М.: Мир, 1977.- 290с.

24. Шор Н.З. Методы минимизации недифференцируемых функций и