22.18 П93 УДК519.6 Метод линеаризации. Пшеничный Б. Н. - М.: Наука. Главная редак- ция физико-матиматической литературы, 1983. - 136с. Книга посвящена систематическому изложению метода линеаризации - одного из универсальных методов решения общих задач математического программирования, а также его применениям к задачам безусловной оптими- зации, линейного и квадратичного программирования, нахождению решений систем неравенств, задачам минимакса. Изложение доведено до стадии описа- ния конкретных алгоритмов для конкретных задач. Табл. 6 Библ. 47 назв. Борис Николаевич Пшеничный МЕТОД ЛИНЕАРИЗАЦИИ Редакторы Л Д. Вайнштейн, И.В. Викторенкова Тех. редактор С.В. Геворкян Корректоры Т.В. Обод, Т.Д. Печко ИБ № 12230 Сдано в набор 11.11.82. Подписано к печати 22.03.83 Т-06977. Бумага 60Х90/16 офсетная. Печать офсетная Усл.печ.л. 8,50.Уч.изд.л. 8,82 . Тираж 7500 экч. Тип.зак. 562. Цена 1 р. 10 к. Издательство "Наука" Главная редакция физико-математической литературы 117071 Москва, В-71, Ленинский проспект, 15 4-я типография издательства "Наука" 630077, Новосибирск, 77, ул. Станиславского, 25 1702070000-072 П ——————————— 25-83 053(02)-83 Издательство "Наука". Главная редакция физико-математической литературы, 1983 СОДЕРЖАНИЕ Предисловие .......................................... 5 Глава 1. Задачи выпуклого и квадратичного программирования ........ 7 § 1. Введение ......................................... 7 § 2. Необходимые условия минимума и двойственность .............. 12 1. Выпуклые множества ................................. 12 2. Выпуклые функции .................................. 13 3. Основы выпуклого программирования ...................... 15 4. Двойственность в выпуклом программировании ................ 20 5. Необходимые условия экстремума. Общая задача ............... 22 6. Необходимые условия экстремума второго порядка ............. 23 7. Задача о минимаксе .................................. 23 8. Метод штрафных функций ............................. 24 § 3. Задача квадратичного программирования ..................... 27 1. Метод сопряженных направлений ......................... 27 2. Алгоритм метода сопряженных направлений .................. 29 3. Существование решения ............................... 30 4. Необходимые условия экстремума и двойственная задача .......... 31 5. Приложение. Проектирование на подпространство ............... 33 6. Алгоритм для задачи квадратичного программирования ........... 35 7. Вычислительные аспекты .............................. 40 8. Алгоритм для простых ограничений. Обобщение ................ 44 Глава 2. Метод линеаризации ................................. 45 § 4. Общий алгоритм .................................... 45 1. Основные предположения .............................. 46 2. Формулировка алгоритма .............................. 46 3. Сходимость алгоритма .................................. 46 4. Вычислительные аспекты .........'..................... 50 5. Некоторые обобщения ................................ 51 6. Задача линейного программирования ....................... 54 7. Метод линеаризации при ограничениях типа равенств ............. 57 8. Простые ограничения ................................. 58 9. Выбор параметров в методе линеаризации. Модифицированный алгоритм 60 § 5. Решение систем равенств и неравенств ....................... 65 1. Вспомогательная задача ............................... 66 2. Алгоритм ........................................ 66 3. Сходимость алгоритм.). ................................ 66 § 6. Ускорение сходимости метода линеаризации ................... 74 1. Основные предположения .............................. 74 3 2. Локальный анализ вспомогательной задачи ................... 75 3. Предварительные леммы ............................... 80 4. Алгоритм метода линеаризации с ускоренной сходимостью ......... 81 5. Линейные преобразования задачи ......................... 84 6. Модификации метода линеаризации ........................ 87 Глава 3. Задача дискретного минимакса и алгоритмы ................ 94 § 7. Задача дискретного минимакса ........................... 94 1. Вспомогательная задача ............................... 95 2. Некоторые оценки .................................. 97 3. Алгоритмы ....................................... 98 4. Алгоритм при А^ = f^ ............................... 100 5. Ускорение сходимости в выпуклом случае ................... 104 § 8. Двойственный алгоритм для задачи выпуклого программирования . .... 107 1. Двойственный алгоритм ............................... 108 2. Оценка скорости сходимости ............................ 111 3. Алгоритм для задачи выпуклого программирования ............. 115 § 9. Алгоритмы и примеры расчетов ........................... 121 1. Метод линеаризации .................................. 121 2. Ускоренный метод линеаризации .......................... 123 3. Примеры расчетов ................................... 125 Библиографический комментарий ............................ 133 Литература ........................................... 135 ПРЕДИСЛОВИЕ Обычно в предисловии принято писать о практической важности пробле- мы и характеризовать содержание книги. Но практическая важность реше- ния задач оптимизации давно уже не вызывает каких-либо сомнений. Этой тематике посвящена такая обширная научная и научно-популярная литература, что вряд ли есть необходимость еще раз повторять, что теория и методы оптимизации находят приложение в многочисленных пробле- мах экономики, автоматическом управлении, инженерном деле и т.д. С другой стороны, краткое содержание подробно описано в первом ввод- ном параграфе этой книги. В связи с этим на нем также нет смысла останав- ливаться. Вместо этого я позволю себе высказать несколько общих заме- чаний относительно теории и численных методов оптимизации и их взаимо- действия в процессе решения реальной сложной задачи. Электронные вычислительные машины начали применяться для реше- ния задач оптимизации с первых лет своего появления. Первоначально это применение было связано с относительно простыми по своей структу- ре задачами линейного программирования, которые можно было решать разработанными регулярными методами, и со сравнительно несложными нелинейными задачами, решение которых достигалось за счет простых интуитивных соображений в соединении со способностью вычислительной техники производить огромное количество вычислительных операций. Но появление все новых и новых задач возрастающего объема, содержащих сложные нелинейности, не позволяло ограничиться простыми приемами и грубой силой. Решение достаточно общих нелинейных задач требовало как более глубокого теоретического исследования свойств их решений, так и более тонких и сложных приемов для получения численного резуль- тата в разумное для данной конкретной задачи время. Процесс создания та- кого арсенала средств для решения проблемы оптимизации интенсивно раз- вивался в течение последних двадцати лет. Представляется, что метод линеаризации - предмет исследований в настоящей книге - является одним из довольно многих плодов, получен- ных в результате этого процесса. Действительно, метод линеаризации, как это видно из дальнейшего изложения, тесно связан с методом Ньютона решения систем уравнений, методом штрафных функций, в частности, негладких штрафных функций, а в связи с последним обстоятельством и с методами недифференцируемой оптимизации. Успешное применение метода линеаризации невозможно без эффективного решения задач квадратичного программирования, что связывает его с методами сопряженных градиентов и переменной 5 метрики. Желание решать задачи большого объема требует привлечения ап- парата, разработанного в линейном программировании, т.е. приемов работы с разреженными матрицами, мультипликативного представления обратных матриц и т.п. Наконец, исследование области и скорости сходимости невозможно без привлечения теории необходимых условий экстремума, множителей и функций Лагранжа, понятия двойственной задачи. Как следует из сказан- ного, достаточно законченное изложение свойств метода линеаризации невозможно без привлечения широкого круга понятий, разработанного как в самой абстрактной теории, так и при самой конкретной машин- ной реализации. Естественно, что все это в большей или меньшей степени нашло отражение в книге. Не всем вопросам можно было уделить одинако- вое внимание при разумном ограничении объема книги. Однако, даже если какие-то проблемы упоминаются лишь бегло (например — методы сопряженных направлений и переменной метрики, методы работы с раз- реженными матрицами), то это не значит, что они не имеют существен- ного значения. Чаще наоборот, как это показывает пример с разреженными матрицами. Без умения успешно работать с ними время работы с задачами большого объема катастрофически возрастает. Укажем еще на одну и очень существенную причину, в силу которой специалист, заинтересованный в первую очередь в конкретном применении метода, должен тем не менее быть хотя бы знакомым с понятиями и идея- ми, связанными с методами. Дело в том, что метод рассчитан на решение общей задачи нелинейного программирования и может в силу этого затра- чивать на решение каких-то подзадач данной задачи значительное время. Но конкретная задача (или класс задач) всегда имеет свою специфику (например, большинство ограничений имеет очень простой вид), и поэ- тому учет этой специфики за счет изменения каких-то блоков алгоритма может привести к существенному сокращению времени решения и требуе- мого объема памяти. Ясно, что такое изменение нельзя провести успешно без понимания движущих пружин, которые делают алгоритм сходящимся. Хотя данная книга продиктована стремлением подвести некоторый итог исследованиям в области метода линеаризации, автор надеется, что она вовсе не будет служить конечной точкой в этой области. Свидетельст- вом тому является все увеличивающееся число статей, посвященных этой и связанной с ней тематике. Кроме того, имеется целый ряд проблем, требующих более глубокого и детального изучения. В частности, требуют дальнейшего исследования вопросы выбора правил перехода с простого на ускоренный метод линеаризации, уточнение правил выбора шага при та- ком переходе, алгоритм изменения константы в функции штрафа, способы аппроксимации матрицы вторых производных функций Лагранжа в реше- нии. Необходимо более детально рассмотреть специфику метода линеари- зации применительно к задачам большего объема, методы декомпозиции исходной и вспомогательной задач и т.д. Все эти проблемы нетривиальны, и автор будет рад, если данная книга послужит не только для расширения сферы практического применения метода, но и отправным пунктом для его совершенствования и развития. Б.Н. Пшеничный Глава!. ЗАДАЧИ ВЫПУКЛОГО И КВАДРАТИЧНОГО ПРОГРАММИРОВАНИЯ § 1.ВВЕДЕНИЕ Предлагаемая читателю книга целиком, за исключением § 8, посвяще- на одному методу решения задач нелинейного программирования — мето- ду линеаризации. Этим она отличается от большинства книг, посвященных тому же предмету, в которых обычно рассматриваются различные методы. Описание в монографиях различных алгоритмов и подходов не случайно. Оно связано с тем, что многолетняя практика решения нелинейных задач оптимизации привела специалистов к достаточно единодушному мнению о невозможности 'создания универсального алгоритма, который бы одина- ково успешно решил все задачи. И автор этой книги с таким мнением полностью согласен. Действительно, задачи нелинейной оптимизации чрез- вычайно разнообразны. Они отличаются структурой вхождения нелиней- ности, количеством переменных и ограничений, требуемым объемом памя- ти. И практический опыт показывает, что существуют классы задач, в кото- рых, казалось бы, самый неэффективный с теоретической 'точки зрения метод благодаря простоте реализации и специфике задачи дает хорошие результаты. В связи с этим вычислительная практика в целом требует набо- ра различных алгоритмов. Сосредоточение же в этой книге на одном методе связано с желанием достаточно глубоко выяснить его свойства и возмож- ности, выделить те особенности и преимущества, которые он может дать на практике. Тем более что использование метода линеаризации на прак- тике в течение многих лет показало его высокую эффективность при реше- нии достаточно широких классов задач. Поэтому здесь мы постараемся выделить наиболее характерные черты, обеспечивающие его высокую эф- фективность. 1. Более точная постановка задачи и требования к ней будут даны по ходу изложения. Здесь же мы не будем себя ограничивать особой математи- ческой строгостью. Итак, пусть/ ={l... ., т} - конечное множество индексов. Рассмат- ривается задача нахождения минимума функции /о (х) при ограничениях fi(x) ^ 0, / = 1..... т. Более коротко, niin{/o (х) : ff(x} < 0, / = 1,. . ., т ]. (1.1) Хотя можно без особого труда в методе линеаризации рассматривать и огра- ничения вида )',{х} = 0, для упрощения здесь мы этого делать не будем. По аналогии с известным методом Ньютона решения систем нелинейных уравнений попробуем нелинейную задачу (1.1) в данной точке х линеари- зовать и приращение аргумента вычислить из решения соответствующей 7 Заметим, что попутно мы получили формулы (3.21) — (3.23) для вы- числения множителей Куна — Таккера. Обратим также внимание на то, что равенство J'у = ф. k > 1, указывает лишь на завершение процесса минимизации по методу сопряженных гради- ентов. Равенство J^ =ф указывает лишь на то, что при фиксированных пас- сивных неременных нельзя добиться дальнейшего уменьшения значения функции. Далее, по построению базисные переменные всегда строго положительны. Это, а также возможность перестройки базиса при обращении одной из них в нуль, обеспечивается условием невырожденности. 7. Вычислительные аспекты. В предыдущем изложении был оставлен без внимания ряд существенных практических вопросов, без решения которых приведенный алгоритм не может рассматриваться как эффективный. К счастью, эти вопросы уже давно успешно решены в линейном программиро- вании и здесь будут кратко изложены. Более детальное их рассмотрение читатель найдет в литературе к этому параграфу. Для начала работы алгоритма необходима какая-либо точка, удовлетво- ряющая ограничениям Лх = h, x > 0. Если такая точка неизвестна из каких- либо априорных соображений, то следует использовать какую-либо стан- дартную программу линейного программирования. Такие программы достаточно широко распространены, и поэтому на этом вопросе мы не будем останавливаться. Сосредоточим внимание на вопросах вычисле- ния матриц BJ, BjAj, которые необходимы в ходе работы алго- ритма. Пусть решается система /» Х « уравнений Ах=Ь. (3.24) причем среди столбцов матрицы А имеется т линейно независимых. Обозначим строки матрицы А через а,, столбцы через А,, а элементы через а,,. Стандартный прием решения системы (3.24) состоит в том, что из /-го уравнения, если д,у -Ф- 0, выражается x1 через остальные переменные и под- ставляется в остальные уравнения. Такой метод исключения неизвестных называется методом исключения Гаусса - Жордана. Из преобразованной системы исключается следующее не- известное и т.д. Опишем этот прием в удобной для дальнейшего форме. Известно, что он эквивалентен следующему преобразованию: следует умножить /-ю строку матрицы на множитель /* и прибавить ее к А--и строке, выбрав /^ так, что-. бы преобразованный элемент а^/ равнялся нулю, если k ^ i, и единице, ес- ли k = /. Если преобразованную матрицу обозначить через А, то Ok = Uk + tk a,- fk=- 4kila„, k ^ i. (3.25) а,=1,а,. /,= \la„. Из этих формул следует, что если а ц = 0, то Oki = akl ЯЛ" всего столбца /. 40 Введем матрицу 111 - ' 10 ... о /I о о 0 1 t,-l u о ^= о о t, о о о о 1,^1 ' о о о t,„ о ... 0 1 (3.26) Ее определитель, очевидно, равен /, Ф 0, так что матрица невырождена. Тогда указанное преобразование, как нетрудно убедиться, приводит к но- вой системе Ах = Ь, А = ТцА, b = Tjjb. При этом переменная x1 входит только в /-е уравнение с коэффициентом 1: д^у =0, k ^ i, a/, = 1. По-другому это можно записать в виде А,- = с„ где с,- - вектор, у которого все компоненты равны нулю, кроме У-й, кото- рая равна 1. Поступим теперь следующим образом. Возьмем / = 1 и найдем д^ -Ф- 0. Обозначим /(1) = /i. Положим ГС^Г,/,, А^^Т^А. й°) = Т^Ь. Выбрав / = 2, аналогичным образом среди элементов д^ находим ненуле- вой: а[у ^0. Такой элемент обязательно должен найтись, так как в про- тивном случае вся вторая строка матрицы А(') была бы нулевой и ранг А'1' был бы меньше т. Но так как ранг матрицы А равен т, а матрица Т^0 невырождена, то ранг/1е0 также равен т. Кроме того./д ^/i, так как д^ =0, k -Ф- 1, по построению А ('), так что а^, = 0. Полагаем /(2)=/,, T-t^T^, А^^Т^А^^Т^Т^А, Ь^^Т^Т^Ь. причем элементы матрицы Т-ц строятся по элементам матрицы Л01. За- метим при этом, что так как а01 = 0, то А^ ± А^') = с,. Продолжая аналогично, после m шагов получаем матрицы ^(та) = •р(т) у(1) А = т4"')/! <'"-'), ^т) ^ •р(т) т^0, &= Г('") 6(m-l) (3.27) и взаимно однозначное отображение /(/) = /,. В силу взаимной однозначнос- ти определено и обратное отображение /(/) для / e{/i, /,, ... ,/„,}: i(j^) = k. По построению столбец с номером/^ совпадает с k-м единичным ортом е^: (3.28) tk 41 Глава 2. МЕТОД ЛИНЕАРИЗАЦИИ S 4. ОБЩИЙ АЛГОРИТМ В этом параграфе мы рассмотрим метод решения общей задачи матема- тического программирования, не делая каких-либо допущений о выпуклос- ти встречающихся функций. Существенной особенностью метода является возможность учета нелинейных ограничений типа равенств, что является камнем преткновения для большинства других методов. Пусть требуется минимизировать функцию fo(x). x ? /:'", при ограни- чениях ./;(х)<0, /С/-, y,(.v)=0, <е/°, (4.1) где /-, /° - конечные множества индексов. Предположим, что все функ- ции/,^) непрерывно дифференцируемы. Более полно ограничения, при которых исследуется задача, будут оговорены ниже. Заменим в точке х» все ограничения (4.1) н/'о(х) на линейные, линеаризовав /',(х) в точке Ху В результате получится некоторая задача линейного программирования. Естественно было бы решение линеаризованной задачи взять в качестве следующего приближения, как это делается в методе Ньютона для решения систем нелинейных уравнений. К сожалению, прямо этот путь не приводит к цели, так как обычно вспомогательная задача линейного программирования не имеет решения. Поэтому необходимо наложить некоторые ограничения на приращение вектора х в точке Хц, чтобы решение линеаризованной задачи в точке XQ не уходило слишком далеко от Ху, оставаясь в такой окрестнос- ти XQ , в которой линеаризация еще справедлива. Это и будет проделано ниже путем добавления квадратичного члена к линеаризованной целевой функции. Заметим, что каждое равенство ,f,(x) = О эквивалентно двум неравенст- вам/,^) < О, -/,(JC) < 0. Поэтому можно ограничиться рассмотрением лишь случая наличия только ограничений типа неравенств. Такое ограниче- ние удобно по крайней мере при теоретическом обосновании алгоритма, хо- тя удвоение числа неравенств может быть неудобным при вычислениях. Ниже будет изложено теоретическое обоснование алгоритма для задачи ми- нимизации fo(x) при ограничениях /,(JC)