Главная  Методы условной оптимизации 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [ 44 ] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83]

методу поиска решения системы (5.78) предъявляются два требования: во-первых, он должен быть быстросходящимся и, во-вторых, должен давать ириедглемое направление спуска даже при знаконеопределенной ZHZ.

*5.в.2.2. Изменения в рабочем списке. Пока норма «велика», оптимизируются значения только базисных и супербазисных переменных. Когда какая-нибудь из них выходит на свою границу, ее «переводят» в разряд небазнснЬ1Х, рабочий список корректируется соответствующим образом и счет продолжается дальше.

Допустим теперь, что величина wZTgi стала «малой» (ср. с (5.2)). Это рассматривается как признак «близости» очередной точки к оптимальной для текущего рабочего списка. Здесь надо определить, можно ли еще и.зменить значение целевой функции, если освободить одну из небазисных переменных. Для этого требуется вычислить оценки множителей Лагранжа. Определяющая их система уравнений выглядит так:

в качестве искомых л и о берут

n = B-g: (5.80)

o = g-Nn. (5,81)

Они будут точными значениями соответствующих частей вектора множителей Лагранжа, если Zg = 0. Действительно, в этом случае

gs=SrB-g„=Sn.

т. е. п и о из (5.80), (5.81) прн Zg = 0 обеспечивают в (5.79) точное равенство. Вектор а составлен из оценок множителей, отвечающих простым ограничениям на небазисные переменные. В рептении его компоненты должны иметь определенные знаки. Если же правило знаков для какой-то компоненты в а нарушено, отвечающую ей небазисную компоненту переводят в разряд супербазисных и оптимизация продолжается.

Заканчивая разбор методов рептения больших задач, просуммируем их отличия от расслютренных прежде обычных методов активного набора. Этн отличия существенны, хотя идеи, лежащие в основе и тех и других методов, одинаковы. Во-первых, нуль-пространство матрицы Л определяется теперь путем разделения переменных, а не факторизацией, приводящей к Z с ортогональными столбцами. При этом из выражения (5.75) для Z видно, что плохая обусловленность базисной матрицы В может сильно снизить точность всех построений алгоритма и круто

изменить веса переменных. Еслн столбцы Z ортонор,мальны, выполняется неравенство Zgjg2; в противном случае вектор Zg оказывается «неотмасштабированным». Поскольку применение ортонормальных Z для больших задач, как правило, непрактично (и по памяти, и по трудоемкости), при построении р и приближений спроектированной матрицы Гессе в методах решения таких задач нередко возникают дополнительные численные трудности.

Далее оценки множителей Лагранжа, найденные по формулам (5.80) и (5.81), точны только при Zg = 0, и окрестность, в которой они будут иметь правильные знаки, зависит от обусловленности В. Значит, когда норма lZg просто «мала» (а не «очень мала»), освобождать небазисную переменную с неподходящей по знаку компонентой вектора а может оказаться бесполезным. Хотя какое-то направление спуска будет получено, не исключено, что на одной из ближайших итераций освобожденная переменная выйдет на прежнюю границу и ее снова придется зафиксировать. При решении малых задач, когда оценки множителей вычисляются с применением ортонормальной Z, аналогичная проблема стоит куда менее остро, поскольку области корректности знаков оценок будут зависеть тол1>ко от обусловленности Л. Уменьшение надежности оценок множителей Лагранжа при переходе от 0[)ТОГональпых Z к (5.75) неизбежно, и это всегда надо принимать во внимание.

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

Замечания и избранная библиография к разделу 5.6

В настоящее время есть немало коммерческих реализаций симплекс-метода, рассчитанных на задачи с тысячами переменных. Интересная история раннего этапа разработок коммерческих пакетов линейного программирования хорошо изложена в статье Орчард-Хейса (1978а). За деталями проектирования и реализации математического обеспечения линейных задач большой размерности мы отсылаем читателя к работам Орчард-Хейса (1968, 1978b, с). Била (1975), Бенишу и др. (1977), Гринберга (1978а, Ь) и Муртафа (1981).

Главные различия в реализациях симплекс-метода относятся к способам решения уравнений (5.69) и (5.70). Первые программы оперировали явным представлением матрицы, обратной к базисной (см., например, Орчард-Хейс (1968)). Более поздние работают с /.(/-разложением (Бартелс и Голуб (1969), Форрест и Томлин (1972)), с LQ-разложением без запоминания Q (Гилл и Мюррей (1973с)), с



/-С-разложатем, где Q хранится в виде произведения диагональной и ортогональной матриц (Гилл, Мюррей, Сондерс (1975)).

Прогресс в линейном программировании в основном стимулировался достижениями в области методов решения больших разреженных систем линейных уравнений. Одна из первых схем выбора упорядочения столбцов и строк базисной матрицы В была разработана Марковицем (1957). В ней выбор очередного ведущего эле.мента во время /.{/-факторизации осуществляется путем локальной минимизации возможного заполнения в строках и столбцах, которые еще предстоит факторизовать. Схема Марковица была реализована Райдом (1975, 1976). Хеллерман и Рарик (1971, 1972) предложили метод перестановок, предназначенный для преобразования базисной матрицы до того, как начнется ее факторизация. Перестановки строк и столбцов в этом методе сначала подбираются так, чтобы переделанная матрица отличалась от нижней треугольной только несколькими диагональными блоками, именуемыми горбами (см также Тарьян (1972), Дафф и Райд (1978)). После этого каждый горб обрабатьшается до тех пор, пока не станет отличаться от нижней треугольной матрицы лишь некоторыми столбцами. Их «над-диагональные ненулевые выросты» принято назьшать спайками. Можно показать, что при последующей L -факторизации заполнение возможно только в тех столбцах, где есть спайки.

Наиболее эффективные из современных реализаций симплекс-метода, предназначенных для решения больших задач, оперируют /. -разложением базисной матрицы В. Два основных способа пересчета факторов этого разложения при замене столбца В сконструированы Форрестом и Томлином (1972) (см. также Томлин (1975а)) и Бартелсом и Голубом (см. Бартелс (1971)). Конечным итогом пересчета фактора и по методу Форреста - Томлина является замена в нем одного из столбцов. Поэтому метод лучше всего согласуется с процедурами, предполагающими запись U по столбцам. Основное его достоинство в том, что он может быть эффективно реализован в случаях, когда для хранения L к U используется внешняя или вир-т-альная память.

Метод Бартелса - Голуба в отличие от метода Форреста - Томлина включает определенные действия, направленные на обеспечение численной устойчивости пересчета. В нем используются перестановки строк , и в некоторых из строк могут появляться новые ненулевые элементы. Последнее означает, что способ записи ненулей U должен быть таков, чтобы ее можно было дополнять новыми элементами, не переупорядочивая старых. Эта особенность метода предполагает хранение U целиком в оперативной памяти. Эффективная ФОРТРАН-реализашгя метода Бартелса - Голуба с компактной записью U по строкам разработана Райдом (1975, 1976). В ней ненули каждой строки размещаются в памяти рядом, но соседние строки могут быть записаны в несмежных областях. Программа Райда хорошо работает и в реальной, и в виртуальной

памяти. Сондерс (1976) предложил иной способ реализации метода Бартелса - Голуба. Он показал, что если перед первой факторизацией применить процедуру Хеллермана - Рарика, то удается предсказать блоки и, в которых при последующих пересчетах будут возникать новые ненули. Их можно хранить в оперативной памяти в явном виде, и тот-да доступ к элементам U во время пересчетов упрощается до предела.

Некоторые важные в прикладном отношении задачи линейного программирования большой размерности характеризуются специ-альнььми структурами заполнения матриц ограничений; например, матрицы моделей динамических систем имеют местничную» структуру. Обсуждение таких задач выходит за рамки настоящей книги. Библиографию по этому поводу читатель найдет в сборнике под редакцией Данцига и др. (1981).

Значительный интерес в среде специалистов во всем мире вызвала недавняя публикация советского математика Хачияна (1979), где доказано, что некий алгоритм эллипсоидов находит допустимую точку системы линейных неравенств с рациональными коэффициентами за число шагов, полиномиально зависищее от (исчисляемой специальным способом) размерности системы. В этом алгоритме, принципиально разработанном Шором (см. Шор (1970, 1977), Шор и Гершович (1979)) и Немировским и Юдиным (1979), сначала строится эллипсоид, содержащий кусок допустимой области ненулевого обьема, а затем - последовательность сокращающихся в объеме эллипсоидов, каждый из которых содержит в себе этот кусок. Доказательством от противного можно установить, что в конце концов центр одного из эллипсоидов окажется допустимой точкой (иначе пришлось бы признать возможным существование эллипсоида, объем которого меньше, чем объем содержащейся в нем части допустимого множества). Поскольку задачи линейного программирования всегда могут быть сведены к задачам на поиск допустимой точки, результат Хачияна о полиномиальной сходимости распространяется и на них. В то же время оценка числа итераций симплекс-метода экспоненциальна, причем есть примеры, на которых эта оценка достигается. Естественно возник вопрос: выльется ли теоретическое преимущество метода эллипсоидов, следующее из упомянутых оценок, в практическое? Оказалось, что, несмотря на большое значение этого метода для теории, виды на разработку на его основе эффективных пакетов решения больших задач линейного программирования плохие (результаты численных экспериментов с ним на некоторых задачах большой размерности можно найти у Гилла и др. (1981а)). После появления на свет статьи Хачияна о методе эллипсоидов писали многие, и в том числе Эспвол и Стоун (1980), Гач и Ловас (1981), Гоффен (1980), Лоулер (1980) и Вулф (1980а, Ь).

Одним из недшогих практичных алгоритмов решения больших задач с линейными ограничениями и нелинейной целевой функцией



является метод аппроксимации (см. Гриффит и Стюарт (1961)). Его часто называют также методом последовательного линейного программирования. Известно много разных реализаций этого метода. Выбор версии обычно определялся доступной библиотекой оптимизационных программ; о методе писали Бейкер н Венткер (1980), Бил (1974, 1978), Бэтчелор и Бил (1976). -

Термин «супербазисные переменные» введен Муртафом н Сондер-сом (1978). Они - авторы схемы решения больших задач с линейными ограничениями, изложенной в разд. 5.6.2. Метод Муртафа - Сондерса (разработанное ими конкретное воплощение этой схемы) оперирует разложением по Холесскому квазиньютоновской аппроксимации (в соответствии с BFGS-формулой) спроектированной матрицы Гессе, а когда памяти для записи факторов не хватает, он переключается на традиционный метод сопряженш>1Х градиентов. Переносимую ФОРТРАН-программу MINOS, реализующую этот метод, можно приобрести в Лаборатории оптимизации систем Стэнфордского университета (см. Муртаф и Сондерс (1977)).

Марстен и Шанно (1979) (см. также Марстен (1978)) предложили метод, аналогичный методу Муртафа - Сондерса и отличающийся от последнего только тем, что вместо BFGS-формулы для аппроксимации спроектированной матрицы Гессе в нем используется квазиньютоновский метод с ограниченной памятью. При этом рестарт в момент ввода в рабочий список нового ограничения не обязателен. Бакли (1975) построил квазиньютоновский метод решения больших задач, использующий пХп-матрицу Г вида (5.31). Лучше всего этот метод работает в случаях, когда число ограничений общего В1ща превышает число переменных.

*5.7. ПОИСК НАЧАЛЬНОЙ ДОПУСТИМОЙ ТОЧКИ

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

В пакетах линейного программирования задача отыскания начального допустимого приближения решается алгоритлюм, именуемым азой / симплекс-метода. Введем для системы из m линейных неравенств Лл:>6 искусственную целевую функцию вида

f (х) = - 2 (а]к-Ь,). /есг

где 5 есть набор индексов ограничений, нарушенных в х. Функция f представляет собой сумму «недопустимостей» и при

фиксированном 3 линейна. Заметьте, что F равна нулю в любой допустимой точке и положительна в любой недопустимой. Следовательно, найти допустимую точку можно, минимизируя F (х) прн ограничениях й[х-6у>0,/3.

Для решения поставленной оптимизационной задачи обычно используют слегка модифицированный симплекс-метод. Мы укажем две распространенные модификации, касающиеся правила выбора шага вдоль направления поиска- Во-первых, можно делать максимальный шаг, не нарушающий ни одного из выполненных в начале итерации ограничений. Обозначим через х и р текущую допустимую точку и выбранное в ней направление поиска; пусть далее Ж - набор индексов ограничений, выполненных в х как неравенства. Тогда формула расчета шага а, о котором идет речь, будет выглядеть так;

Ограничение с некоторым индексом г из Ж, определяющее минимум справа, как обычно, войдет в рабочий список следующей итерации. Второй способ выбора шага-находить его из условия минимума F вдоль р. Тогда, например, если при а, вычисленном предыдущим способом, производная от f в х--ар по направлению р, равная

- 2 aJp-аГр,

окажется отрицательной, то шаг будет увеличен.

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

Когда исходная задача линейна, т будет больше п. В данном случае можно набрать п линейно независимых ограничений и определить тем самым некую (недопустимую) вершину. Соответственно для поиска допустимой точки можно будет воспользоваться симплекс-методом. В момент обнуления вспомогательной целевой функции мы получим допустимую вершину, в которой и запустим симплекс-метод решения исходной задачи.

Если т<я (что нередко случается в задачах с нелинейными F), непосредственно применить симплекс-метол нельзя, так как у допустимого множества вспомогательной задачи не будет вершин.



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [ 44 ] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83]

0.0012