Главная Методы условной оптимизации [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] а = а, его нужно дополнить, отразив тем самым тот факт, что еще одно ограничение обратилось в равенство. Когда появилось сразу несколько новых равенств, в рабочий список включают только одно из них (другие иногда приходится включать на последующих итерациях). Последствия расширения рабочего списка зависят от способа представ,пення матрицы Z и от метода, используемого для расчета pj, (см. разд. 5,2.4). Логика шага LI5 подразумевает, что ограничение вводится в рабочий список сразу же, как только «проявится» ([Юмешает увеличить шаг). В дальнейшем, оставаясь в рабочем списке, оно будет сохранено как равенство, т. е. не нарушится Таким образом, шаг LI5 гарантирует допустимость генернруемы.х точек. Однако ее можно обеспечить и по-другом}. Например, ограничение с индексом 1, обратившееся в равенство на k-ii итерации, можно вводить в рабочий список (к-\-1)-й итерации только при условии, если окажется, что пренебрежение им приведет к неравенству aTpi+i <0. 5,2.3. ИНТЕРПРЕТАЦИЯ ОЦЕНОК МНОЖИТЕЛЕЙ ЛАГРАНЖА В этом разделе мы вкратце обсудим проблемы, связанные с организацией вывода ограничений из рабочего списка, причем основной акцент будет сделан на необходимость аккуратной интерпретации оценок множителей Лагранжа. В методах активного набора поиск оптимума для L1P осуществляется поспедовательными циклами итераций решения промежуточных задач вида найти min f (х) прн ограничениях ЛдлгЬд. (5.35) Чередование этих циклов (этих задач) определяется рассмотренными выше правилами расширения рабочего списка и правилами его сокращения, о которых сейчас пойдет речь. Пусть -решение текущей задачи (5.35). Тогда найдется вектор множителей Лагранжа }. - решение совместной системы уравнений gk = li- (5.36) Если какая-нибудь компонента А, окажется отрицательной, значение F(x) можно будет уменьшить, сделав из Xf, шаг вдоль допустимого для LIP направления, сохраняющего равенства во всех ограничениях (5.35), кроме того, которому отвечает отрицательный множитель. Это значит, что указанное ограничение целесообразно вывести из рабочего списка. Таким образом, правила сокращения рабочего списка можно ориентировать на знаки множителей Лагранжа, отвечающих решению (5.35). Любая практичная стратегия вывода ограничений, основанная на знаках множителей Лагранжа, есть результат компромисса. С одной стороны, представляется неразумным решать промежуточные задачи (5.35) с высокой степенью точности, так как сам по себе оптимум в (5.35) интереса не представляет. И уж если рабочий список придется сокращать (т. е. он не верен), то желательно сделать это, не тратя лишних усилий на поиск точного решения этой задачи, в соответствии с оценками ее множителей Лагранжа (см. разд. 5.1.5). С другой стороны, существующие методы оценивания множителей не обеспечивают точности или хотя бы правильности знаков оценок, если точка не будет «достаточно близкой» к решению задачи (5.35) (см. пример 5.3). Прн этом излишняя поспешность в сокраще-1Н5и рабочего списка чревата серьезной потерей эффективности поиска в целом Во-первых, оиа может привести к хорошо известному явлению зигзага, когда какое-то ограничение то выводится из рабочего списка, то включается в него вновь, п это влечет за собой падение скорости сходимости к решению или, еще хуже, сходимость в точку, далекую от оптимальной. Во-вторых, так как вывод ограничения связан со значительными затратами на пересчет данных представления матрицы Z, при неоправданно частых сокращениях рабочего списка средняя трудоемкость одгюй итерации сильно возрастает. Из сказанного следует, что решение об отбрасывании ограничения должно приниматься лишь при определенной уверенности в знаке соогветсгвующего множитег1я. Поскольку приемов, гарантирующих правильность знаков оценок множителей, не существует, бьши разработаны сложные стратегии одновременного измерения надежности оценки и выигрыша, который сулит вывод ограничения из рабочего списка. К счастью, хотя в точке jcs, далекой от решения (5.35), оценки множителей Лагранжа могут сильно отличаться от оригиналов, нх знаки все же обычно оказываются верными, и это позволяет правильно выбирать кандидатов на оывод из рабочего списка. Метод оценивания множителей Лагранжа и метод расчета направления поиска должны быть согласованы. Иначе после вывода из рабочего списка ограничения с отрицательной оценкой можно получить направление, не допустимое относительно отброшенного ограничения. Например, допустимость ньютоновского направления в рассматриваемой ситуации гарантирована только в том случае, если множители оцениваются методом второго порядка. Пример 5.4. Рассмотрим задачу найтн minx;--2x; при ограничении -х,-xl. Ее единственное ограничение «отрезает» точку безусловного мини, мума F, и решением оказывается х*=(-2/3, -1/3), Соответствующий ему множитель Лагранжа равен 4/3. В точке х=(-3, 2), где ограничение выполнено как равенство, оценка первого порядка для множителя Лагранжа, вычисленная по схеме наименыинх квадратов, равна Xi,=-1. Однако если в этой точке исключить ограничение из рабочего списка и после этого вычислить направление поиска методом Ньютона, то получится вектор, указывающий в точку безусловного минимума F и соответственно в недопустимую область ограничения. Если же оценку множителя вычислить методом второго порядка, то окажется, что ограничение выводить из рабочего списка нельзя, так как эта оценка будег положительной - в силу квадратнчности F она просто-напросто совпадет с точным значением множителя. Располагая вторыми производными, надежность принимаемых оценок множителей Лагранжа можно поиысить, требуя определенного согласования между оценками первого и второго порядков. Когда они существенно различны, ни те, ни другие надежными считать нельзя. При этом любая наперед заданная степень соответствия достижима, так как разброс между оценками разных типов по мере приближения к х* стремится к нулю. Допустим, что Z строится методом £.(3-факторнзацин, а множители Лагранжа оцениваются вектором определяемым в результате ренжния подзадачи (5.11) и совместной системы (5.30). Тогда объем дополнительных вычислений, необходимых для построения оценки первого порядка Х, будет незначительным. Обозначим через 6j разность между (-ми компонентами Хг. и 1], т. е. 6i=(iii,-?.). В качестве одного нз тестов на соответствие между оценками (Xt.)j и (tl)i можно использовать неравенство 2в,<п1т{ (iijil, l(Xi,)il}. Заметим, что оно выполнимо только при совпадении знаков Q.ji и (ili,)i- Выявление еозжожносты вывода ограничения из рабочего списка вовсе не означает, что этой возможностью надо тут же воспользоваться. Здравый смысл подсказывает, что принимать решение о сокращении рабочего списка надо лишь в том случае, если это сулит больший выигрыш по критерию иа очередной итерации. Последнее означает, что при выводе ограничения помимо отрицательности оценки его множителя Лагранжа надо проверять и другие условия. Например, если модуль множителя мал относительно нормы спроектированного на текущее подпространство градиента, то скорее всего больший прогресс будет достигнут, если сохранить рабочий список неизменным. 5.2.4. вычисления при изменении рабочего списка Когда какое-то ограничение вводится в рабочий список, к текущей матртще Лд приписывается новая строка. (Для простоты обычно предполагают, что она становится последней.) При выводе ограничения одна из строк Лд изымается. В обоих случаях неэффективно строить новую матрицу Z., начиная «с пуля»; значительно экономнее определять ее пересчетом старой. Как пересчитывают Zj и другие матрицы при единичных изменениях рабочего списка, будет показано в оставшейся части данного раздела Для упрощения записей индекс текущей итерации * в представленных нине формулах опущен. Через Л будет обозначаться матрица, отвечающая исходному рабочему списку, а через Л-модифицированному. Буквой t будем обозначать число ограничений в рабочем списке до модификации. *5.2.4.1. Пересчет матрицы Z. Если матрица Z определяется по /.-разложению Л, ее пересчет вьшолняют с помощью обычных ортогональных преобразований. При дополнении рабочего списка новым ограничением модифицированные факторы LQ-раз-ложения можно вычислять по схе.че. описанной в разд. 2.2.5.7 применительно к QR-факторизации. Обозначим через а строку, которая дописывается к Л и становится (<-(-1)-й в матрице Л. Тогда Отсюда видно, что новый ортогональный фактор Q будет произведением Q на преобразование Хаусхо.пдера, обнуляющее компоненты вектора aQ с ((--2)-й по п-ю. Первые t компонент оно сохранит неизменными. Таким образом. Q = QH, (5.38) где Я-матрица Хаусхолдера, причем первые t сто.тбнов Q ч Q идентичны, а столбцы Q с номерами от < -- 1 до « суть линейные комбинации соответствующих столбцов Q. Вместо однократного преобразования Н можно использовать эквивалентную ему последовательность плоских поворотов (см. разд. 2.2.5.3), Когда s-e ограничение выводится из рабочего списка, мы получаем AQ=i.M 0), где строки М с 1-й по (s- 1)-ю образуют нижнюю треугапьиую матрицу, а остальные строки имеют по одному лишнему иад-днагональному элементу. Чтобы привести М к нижнему треугольному виду, т. е. преобразовать ее в искомую матрицу L, надо применить к Q справа последовательность плоских поворотов, которые не повлияют на последние п-t столбгюв Q. Соответственно матрица 2 получится присоединением к Z одного нового столбца: Z = (Z 1). (5.39) Этот столбец будет линейной комбинацией первых t столбцов Q. Генерируя Z методом исключения переменных, матрицу А разбивают на две составляющие: A = (V U). При этом для невырожденной составляющей V обычно строится С-разложе-нне. Обозначим через V результат модификации V (связанной с переходом от Л к Л). Еслн к А дописывается новая строка, то V будет (t + 1)-мерной невырожденной матрицей, отличающейся от V только последними строкой и сто.пбцом, прпчем (t-\-l)-n столбец 1 должеп выбираться из (п-t) последних столбцов Л. Если же Л получается из Л отбрасыванием строки, то преобразование V в V состоит в изъятии соответствующих строки и столбца. В обоих случаях модифицированные факторы L и U получаются нз исходных э-печентарными преобразованиями того же типа, которые применяются для построения £7-разложения «с нуля». *5.2.4.2. Модификации других матриц. Помимо Z при изменениях рабочего списка приходится пересчитывать другие матрицы. Какие именно-зависит от используемого метода построения вектора р. Мы рассмотрим пос.педствия изменений рабочего списка в случае, когда Z определяется по С-разложению Л; приемы пересчета, аналогичные представленным ниже, применяются и в схеме исключения переменных. В методах ньютоновского типа введение нового ограничения в рабочий спнсок требует пересчета только матрицы Z. Что же касается спроектироватюй матрицы Гессе, то ее корректировать не приходится, поскольку ограничение вводится на заключительной стадии итерации, где она уже не нужна, а в начале следующей итерации ее все равно надо строить заново. Когда в процессе ньютоновского поиска ограничение выводится из рабочего списка, в точке, где это происходит, спроектированная матрица Гессе С, отвечающая исходному списку, уже построена, и здесь нужен пересчет. При этом новая матрица Z связана со старой Z формулой (5.39). Следовательно, новой спроектированной матрицей Гессе будет Вектор Gz можно сформировать обычным образом, но можно и заменить оценкой, вычисляемой по конечным разностям компонент градиента вдоль z. Для пересчета факторов модифицированного раз.т10жепия Холесского матрицы Gz прн замене ее на (5.40) пона- добится лишь один дополнительный шаг процедуры построковой факторизации, описанной в разд. 2.2.5.2. В квазиньютоновских методах изменение рабочего списка при. водит к необходимости пересчета матрицы Bz, ( ажающей кривизну f в подпространстве с базисом Z. Когда в рабочь ..нок вводится новое ограничение, факторы Холесского для новой (меньшей по размерности) аппроксимации спроектированной матрицы Гессе могут быть получены нз факторов представления текущей матрицы Bz о использованием формулы (5.38). Соответствующие правила достаточно сложны и здесь обсуждаться не будут (читатель найдет нх по приведенным ниже ссылкам). Вывод ограничения из рабочего списка означает увеличение подпространства, в котором совершается штнимизация; прн этом никакой информации о кривизне F вдоль нового вектора z в текущей матрице Bz не содержится. Поэтому в качестве новой аппроксимации спроектированной матрицы Гессе естественно взять Величину у обычно полагают равной единице. Однако, если есть какая-то дополнительная информация относительно масштабов вторых производных, у можно определять и по-другому. Еще один способ заполнить последние строку н столбец новой квазнньютоновской матрицы - строить ее по образцу (5.40), используя конечно-разностгюе приближение для Gz. В данном случае пересчет факторов разложения Bz по Холесскому осуществляется так же, как в методах ньютоновского типа. Замечания и избранная библиография к разделу 5.2 Некоторые нз известных алгоритлюв решения задач специального вида не вполне вписываются в представленную выше схему «активного набора». Например, Конн (1976) предложил однофазный метод линейного программирования (см. разд. 5.3.1), в котором каждое приближение удовлетворяет части ограничений как равенствам, но при этом может быть ттедопустиыым. В этом методе спуск осуществляется по отношению к недифференцируемой штрафной функции (см. ра.зд. 6.2.2), в то время как значения исходного линейного критерия могут изменяться немонотонно. Аналогичный метол, использующий /.{/-факторизацию, разработан Бартелсом (1980). Уклонения от общей схемы разд. 5.2.1 бывают и в способах расчета направлений поиска. В некоторых методах активного набора эти направления определяются в результате решеитш довольно сложных подзадач. В частности, существует класс методов, в которых в качестве таковых используются задачи квадратичного про- [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.0015 |