Главная Методы условной оптимизации [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] В такой ситуации можно создать искусственные вершины, поставив дополнительные простые ограничения. Правда, чтобы не было риска исключить этими ограничениями все допустимые точки, соответствующие границы придется брать очень свободными, а это значит, что симплекс-метод найдет «неразумное» допустимое приближение (так как для него какие-то из дополнительных ограничений обязательно обратятся в равенства). В силу сказанного при m < я для поиска допустимой точки предпочтительной может оказаться несимплексная стратегия, упомянутая в разд. 5.3.1. Когда т<п, ее разумно реализовать без построения Z (см. разд. 5.4). В этом случае спроектированное направление наискорейшего спуска p = - ZZrc (где с-градиент вспомогательной целевой функции) вычисляют по формуле р - =-- - (/ - YY)c, в которой строками Y служат векторы базиса пространства, натянутого на строки матрицы ограничений рабочего списка. Замечания и избранная библиография к разделу 5.7 В современных коммерческих пакетах линейного программирования фаза 1 симплекс-метода полностью вытеснила применявшийся ранее способ модификации исходной задачи, позволявший сразу указать допустимое базисное приближение. Эта модификация состоит в том, что в задачу вводится ряд искусственных неотрицательных переменных, которые и становятся базисными на первом шаге. Чтобы введение этих переменных не повлияло на решение, их включают в целевую функцию с большим множителем; поэтому но мере выполнения итерации они постепенно замещаются в базисе настоящими переменными и в решении оказываются равными нулю. Данный прием преобразования линейных задач известен под названием М-метод (см. Данциг (1968)). На практике он ненадежен. Детали реализации фазы 1 симплекс-метода в коммерческих пакетах математического программирования можно найти в работах Орчард-Хейса (1968) и Гринберга (1978b). *5.8. РЕАЛИЗАЦИЯ МЕТОДОВ АКТИВНОГО НАБОРА •5.8.1. ОПРЕДЕЛЕНИЕ НАЧАЛЬНОГО РАБОЧЕГО СПИСКА Хотя поиск решения задачи с линейными ограничениями осуществляется в две фазы, на первой из которых определяется допустимая точка, а на второй - собственно решение, его организуЕот так, что всю работу фактически выполняет один алгоритм активного набора, но только сначала ему предлагается вспомогательная целевая функция, а после того, как он найдет допустимое приближение,- настоящая. Исходная точка x„ может быть произвольной. Важно отметить, что в момент смены целевых функций рабочий список сохраняегпся. Эффективность любого из упомянутых в этой главе методов активного набора сильно зависит от количества ограничений в рабочем списке. Методы нуль-пространства будут работать тем лучше, чем больше строковая размерность А; для методов ранг-прострат[Ства предпочтительно, чтобы она была малой. При этом ограничения ВВОДЯТСЯ и выводятся из рабочего списка по одгюму, т. е. его состав меняется довольно медленно. Соответственно большое значение имеет размер начального рабочего списка. Состав начального рабочего списка определяется перед запуском первой фазы оптимизации с помощью специальных процедур, именуемых стартовыми. Единственное обязательное требование к этому списку состоит в том, что он должен включать все линейно независимые ограничения-равенства. Прочее в основном зависит от того, к какому классу относится метод расчета направления поиска, применяемый на второй фазе оптимизации. Если это - метод пулы пространства, в начальный рабочий список стараются ввести как можно больше ограничений. Если же на второй фазе используется метод ранг-пространства, никакие другие ограничения, кроме упомянутых выше равенств, в начальный список не включаются. Обозначим через матрицу, чьи линейно независимых строк отвечают ограничениям из стартового рабочего списка. Если tc < п, то найдется бесконечно много точек, для которых А,х = К. (5.82) Первая фаза оптимизации обычно запускается с точки х, удовлетворяющей (5.82) и в каком-то смысле являющейся ближайшей к заданному пользователем начальному приближению х„. Например, в качестве х„ может выступать х„ +р, где р-вектор минимальной квадратичной нормы, удовлетворяющий равенству Л, (х-„-Ьр) = Ь,. Имея LQ-разложение такой вектор р вычисляют по формулам p = Kjn, гле /.,t) = 6,, - Лх„. Здесь Y и -соответствующие блоки LQ-разложения. Подбор стартового рабочего списка для метода нуль-пространства можно организовывать многими способами, например включать в него все линейно независимые равенства и те из линейно независимых неравенств, для которых \а]х„-6,К6. где Б-некоторое малое число. Самые сложные стартовые процедуры применяются для больших задач линейного программирования, которые обычно ставятся в стандартной форме (см. разд. 5.6.1). Здесь требуется найти начальную базисную матрицу В. При этом, как правило, стартовая процедура ищет ие ту матрицу, которая определяет точку, близкую к заданной пользователем, а ту, которая удобна для треугольного разложения. Например, стартовый базис может быть набран только из вспомогательных переменных или в него войдут основные переменные, столбцы которых образуют треугольную или почти треугольную матрицу Be- Во многих промышленных пакетах стартовые процедуры работают в несколько этапов, используя приведенные цены, отвечающие уже построенной легко обратимой базисной матрице, для выбора следующего, более подходящего начального базиса. *5.8.2. ЛИНЕЙНО ЗАВИСИМЫЕ ОГРАНИЧЕНИЯ Линейная зависимость ограничений - явление для прикладных .задач рядовое, и надо сразу сказать, что она не порождает каких-либо серьезных вычислительных трудностей. Когда в некоторой точке ограничения, выполненные как равенства, линейно зависимы, говорят, что имеет место вырождение, и называют вырожденной точкой. Важная черта модельной схемы решения задач LIP, данной в разд. 5.2.1, состоит в том, что при выборе направления движения из текущей допустиьюй точки х. не обязательно должны учитываться все ограничения, обращающиеся в л:,, в равенства. Если каких-то из этих ограничений в рабочем списке нет, одно из них может попасть туда на следующей итерации, но лишь прн усповии, что выбранное направление выводит вне его допустилгого множества. Затем, возможно, потребуется ввести в рабочий список еще одно из указанных ограничений и т. д. Таким образом, ограничения вводятся в рабочий список по одному, даже если не учтенных в нем равенств несколько. Эта стратегия расширения рабочего списка гарантирует, что содержащиеся в нем ограничения всегда будут линейно независимыми. В саном деле, предположим, что вектор представляет собой нормаль некоторого ограничения, которое обращается в аг в равенство, но которого нет в рабочем списке, причем щ есть линейная комбинация строк Л Тогда, так как выбранное направление р будет удовлетворять равенству ЛрО, получим о;+,р=0. Зиачпт, движение вдоль р не нарушает этого ограничения, и оно не попадет в рабочий список. Рассмотрим теперь ситуацию, возникающую в вырожденной точке при выводе ограничения из рабочего списка. Здесь р не будет удовлетворять равенству Лйр=0, и соответственно любой положительный шаг вдоль р может нарушать одно из неучтенных в рабочем списке линейно зависимых активных ограничений; его придется включить туда, «сделав нулевой шаг» вдоль р. Еслн х,, не вершина, двигаться можно, не сокращая рабочего списка. В вершине же какое-то ограничение обязательно должно быть отброшено. При наличии вырождения шаг вдоль полученного в результате направле- ипя может оказаться нулевым, рабочий список снова придется расширить и т. д. Не исключено, что, выводя и вводя Ограничения в одной и той же вырожденной точке, мы через несколько итераций вернемся к исходному варианту рабочего списка, после чего все начнется сначала. Это явление называется зацикливанием. Отметим, что само по себе вырождение неприяттюстаЧ не доставляет, и если бы не вероятность зацикливания (как его следствия), то о нем можно было бы просто не говорить. Перебрав в вырожденной верштше достаточное количество возможных рабочих списков, всегда можно иайти такой, при котором будет получено направление, позволяющее уйти из нее с уменьшением целевой функции. Однако это - комбинаторная задача, которая в принципе может оказаться очень трудоемкой. Здесь были бы основания для беспокойства, но, к счастью, зацикливание редко встречается на практике, а при использовании неких апе-ментарных эвристических приедгов не наблюдается вообще. 5.8.3. НУЛЕВЫЕ МНОЖИТЕЛИ ЛАГРАНЖА Когда точные значения некоторых из множителей Лагранжа задачи с линейными ограничениями-равенствами, соответствующей текущему рабочему списку, оказываются нулевыми или очень близ-ки.мн к нулю, решение вопроса о целесообразности сокращения рабочего списка может существашо осложниться. Понятно, что близость к нулю оценок каких-то множителей приводит к затруднениям далеко ие всегда. Например, еслн очередная точка х еще далека от стационарной, то всегда можно подождать с выводом ограничений в надежде, что по мере приближения к промежуточному оптимуму модули близких к нулю оценок множителей возрастут. Проблел) не будет и в том случае, когда наряду с почти нулевыми есть существенно отрицательные оценки (например, если - = (1, о, -1)). Здесь ясно, какое ограничение отбросить. Трудности возникают тогда, когда близка к нулю минимальная нз оценок множителей и при этом «почти равен нулю» спроектированный градиент. Чтобы гарантировать оптимальность условно стационарной точки с неотрицательными множителями Лагранжа, среди которых есть нулевые, нужно исследовать вторые производные, а они доступны далеко не всегда. Если отрицательность множителя говорит о том, что, исключив соответствующее ограничение из рабочего списка, мы наверняка получим точки с меньшим значением целевой функции, то равенство множителя пулю означает лишь отстутствие возлюжности предсказать существование лучших точек по информации первого порядка. Непосредстветшая же проверка направлений, получающихся при сокращении рабочего списка, даст определенный ответ только при условии, что будут просмотрены все комбинации ограничений с нулевыми множителями. направление убЬШаиия F(x) Когда таких ограничений много, этот просмотр потребует огромной работы. Представленный ниже пример показывает, что проверка ограничений с нулевым множителем по одному проблемы не решает. Пример 5.5. На рис. 5а изображены линии уровня целевой фуик-цин двумерной задачи вида найти min -х.,х, при ограничениих 0<x,.<10, i=l, 2. Для нее точка начала координат является допустимой вершиной (и соответственно условно стационарной точкой), причем множители Лагранжа обоих об-ращаюгцихся в ней в равенства условий неотрицательности равны нулю. При этом, хотя ни одно из этих условий не будет активным в решении, вывод любого из них из рабочего списка, если сохранить другое, не дает возможности уменьшить значение критерия. Трудности с нулевыми множителями усугубляются ошибками машинных вычислений. Из-за этих ошибок существует конечный порог точности численных оценок множителей. Поэтому мы в принципе не можем отличить нулевые множители от «малых» и не можем выяснить истинных знаков последних. Таким образом, отрицательность малой по модулю оценки множителя не является гарантией целесообразности вывода соответствуютцсго ограничения из рабочего списка, даже если есть уверенность, что точка, где подсчитана эта оценка, близка к условно стационарной. Замечания и избраннаи библиография к разделу 5.8 Процедура выбора начального рабочего списка с использованием ортогональной факторизации реализована в библиотеке ФОРТРАН-программ для решения задач с линейными ограничениями, которую можно приобрести в Лаборатории оптимизации систем Стэнфордского университета (см. Гилл и др. (1980)). Эти профаммы обра- (0,0) Рис 5а. Случаи одновременного обращения в нуль двух множителей Лагранжа. батывают простые ограничения и ограничения общего вида раздельно II оперируют ортогональным разложением матрицы Арр (см. разд. 5.5.2). (Отмстим, что подобные средства очень легко приспосабливаются для задач минимизации, в которых есть только простые ограничения.) Подробные сведения о стартовых процедурах, применяемых в коммерческих пакетах линейного программирования, читатель найдет в книге Орчард-Хейса (1968). Стартовая процедура для алгоритма решения задач с нелинейными целевыми функциями, относящегося к классу методов ранг-пространства, должна генерировать вершину с максимальным числом искусственных ограничений (онределетше искусственных ограничений дано в разд. 5.3.2.2). Среди приемов борьбы с зацикливанием при наличии вырождения надо упомянуть метод возмущеншт Чарнеса (см. Чариес (1952)), лексикографический метод Данцига, Ордена и Вулфа (1955) и метод Вулфа (1963а) (см. также Харрис (1973) и Бенишу и др. (1977)). Блэнд (1977) предложил защищенную от зацикливания версию симплекс-метода, основанную на применении при выборе ведущего элемента правила «минимального индекса». Перо.пд (1981а, Ь) показал, что прн смене базисов в вырожденной точке в процедуре пересчета разложения базисной матрицы возможна некоторая экономия вычислений. Методы ра:*бора ситуаций с близкими к нулю множителями Ла-фанжа, предназначенные для задач с произвольиьЕмп гладкими целевыми функциями, даны в работе Гилла и Мюррея (1977b). В терминологии линейного программирования нулевые множители иногда называют вырожденными двойственными переменными. Заметим, что для линейных задач проблема нулей стоит не так остро, поскольку неотрицательности множителей достаточно, чтобы утверждать, что найдегю решение. Худшее, что здесь возможно,- это ненужные итерации с выводом из рабочего списка ограничений, имеющих «малые» множители. [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.0016 |