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

[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]

граммирования с ограничениями-неравенствами вида найти minft + gjp-l-J-pBjP

при ограничениях Лр>0.

(5.41)

Здесь В к- некоторая аппроксимация матрицы Гессе функции F на очередном шаге (ср. с (5.11)). Выбор рд иа основании задачи (5.41) связан с определенными трудностями. Во-первых, он предполагает хранение либо самой матрицы В,„ либо какого-нибудь из ее разложений (разбор методов решения (5.41) приводится в разд. 5.3.2). На 1-й итерации решения (5.41) нужна только матрица Z[BZ„ но из-за того, что Z, от шага к шагу MOaiCT меняться, без хранения В, целиком не обойтись. Во-вторых, матрица Вд не обязательно будет положительно определенной. (В частности, матрица Гессе функции F часто знаконеопределена даже в х*.) Если же Вд знаконеопределена, у задачи (5.41) может не существовать конечного решения, а если оно и существует, то ие обязательно будег направлением спуска для F, т. е. не исключено, что окажется gJp/,>0. Правильная ориентация решения задачи (5.4.1) с знаконеопределенной Вд ие обеспечена даже в том случае, когда оно реализует сильный локальный минимум и иа каждой итерации его поиска матрица ZJBtZi положительно опредетена. (Более полное обсуждение квадратичных подзадач с неравенствами читатель найдет в работе Мюррея и Райта (1980).)

Известно немало различных путей пррополения описанных выше трудностей. Так, например, для за а в стор и i ограничениями на переменные Брайтон и Kt.....aM 197/, 1979) предложили метод, в котором первое пробное направление поиска определяется из решения упрощенной квадратичной подзадачи. Если оно оказывается неудовлетворительным, решается более сложная подзадача; если и она не дает хорошего направления, вызывается другая процедура расчета рд. не связанная с квадратичным программированием. В экспериментах, проведенных Брайтоном и Каллам, в большинстве случаев первое пробное направление оказывалось удовлетворительным. Однако при знаконеопределенной Bj ни первая, ни вторая квадратичные подзадачи могут не дать подходящего Рд.

Флетчер (1972а) предложил алгоритм, в котором квадратичная подзадача для расчета направления поиска содержит все исходные ограничения плюс дополнительные двусторонние границы для каждой компоненты искомого вектора рд. Этот алгоритм аналогичен методу Гриффита и Стюарта (1961). где роль промежуточной играет задача линейного программирования. Двусторонние ограничения иа переменные подзадачи Флетчер вводит для того, чтобы ее решение не выходило из области, где квадратичная аппроксимация исходной целевой функции F достаточно точна. Значения границ

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

Достаточно полный обзор конкретных методов решения задач с линейными ограничениями читатель найдет в работах Гилла и Мюррея (1974с, 1977а). Метод ньютоновского типа с представлением Zft по схеме исключения переменных описан Мак-Кормиком (1970b). Первый квазиньютоновский метод для задач с неравенствами был разработан Гольдфарбом (1969). Ои опирается на принадлежащую Дэвидону (1959) идею вырожденной квазиньютоновской аппроксимации обращенной матрицы Гессе. Метод Гольдфарба относится к классу алгоритмов, который будет рассмотрен в разд. 5.4. С деталями методов, оперирующих разложениями спроектированной матрицы Гессе, можно познакомиться по трудам Гилла и Мюррея (1973b. 1974d, 1977а). Анализ ошибок методов пересчета ортогонального разложения матрицы ограничений из рабочего списка проведен Пэйгом (1980).

В практических вычислениях вместо обычного /-О-разложення матрицы А удобно использовать так называемое TQ-разложение. Оно определяется формулой

где Тк есть «отраженная» треугольная матрица, характерная тем, что <ij=0 при 1-ЬУ</г. (см. Гилл и др. (1980)). Ее можно интерпретировать как результат расстановки в обратном порядке столбцов нижней треугольной матрицы. Свойства устойчивости у LQ- и ГО-разложений одни и те же. Преимуществом ГО-разложения является то. что в нем матрица образуется первыми nt столбцами Qt,. Это удобно, так как при включении или изъятии ограничения из рабочего списка новый столбец Z или Кд возникает в Од на нужной позиции. Например, описанное в разд. 5.2.4.1 правило модификации спроектированной матрицы Гессе при выводе ограничения из рабочего списка требует, чтобы новый столбец Z стал последним. Когда Zi определяется ТО-разложением, данное тре бование выполняется автоматически.

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



ограничение, для которого оценка выигрыша максимальна. Когда вторые производные не доступны, вместо упомянутых оценок используют их приближения, вычисляемые с помощью подстановочных тестов. Один нз первых методов с предсказанием изменений F на основе подстановочных тестов был предложен Розеноы (1961). Исчерпывающее описание техники подстановочных тестов и некоторые рекомендации по их применению даны в работе Гилла и Мюррея (1974d).

Подробное обсуждение способов контроля точности оценок множителей Лагранжа и условий, при которых обеспечена допусти-мос-гь ньютоновских и квазиньютоновских направлений спуска, приводится в статье Гилла и Мюррея (1979b). Детали различных приемов борьбы с зигзагами в методах нелинейною программирования можно найтн у Вулфа (1966), Мак-Кормика (1969) и Зойтеи-дейка (1970).

5.3. ЗАДАЧИ СПЕЦИАЛЬНЫХ ТИПОВ 5.3.1. ЛИНЕЙНОЕ nPOlPAjMMHPOBAHHE

Одним ИЗ частных случаев общей задачи L1P является задача линейного программирования, в которой целевая функция линейна;

иайти min Л

при ограничениях АхЬ.

(5.42)

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

Мы временно опустим индекс k, помечающий объекты, связанные с текущим шагом. Пусть х - очередное приближение, причем матрица А ограничений из рабочего списка невырожденна. В терминологии линейного программирования такую точку х называют вершиной допустимого множества. Она является решением соответствующей задачи с ограничениями-равенствами, и гютому по схеме активного набора в ней должны быть просмотрены знаки компонент вектора множителей Лагранжа Последний представляет собой

решение невырожденной системы линейных уравнений

АП. = с. (5.43)

Если все компоненты Х больше нуля либо равны ему, х есть решение LP. Если же среди них найдется отрицательная (скажем, ..•<0), то целевую функцию можно уменьшить, двигаясь по направлению, вдоль которого левая часть s-ro ограничения возрастает, а остальные ограничения из рабочего списка остаются равенствами, формально это направление р определяется следующим образом:

I ИрЪ Y>0, (5.44)

t а]р = , (5.45)

Поскольку модуль вектора р значения не имеет, мы можем взять в (5.44) у=1. Тогда пара условий (5.44), (5.45) будет означать, что р есть единственное решение линейной системы вида

Лр = е„ (5.46)

где через е, как обычно, обозначен s-й столбец единичной мат- рицы. Отсюда следует, что р есть s-й столбец матрицы Л". Таким образом, после того как в вершине выделено ограничение, которое надо исключить из рабочего списка, направление поиска определяется однозначно.

Если множитель отрицателен, при движении вдоль направления р нз (5.46) линейная целевая функция неограниченно убывает. Поэтому естественно сделать вдоль р максимально допустимый шаг. Он приведет на границу допустимого множества какого-то ограничения, которого не было в рабочем списке при расчете р, и его надо включить туда. Соответствующая точка снова будет верш]]ной. Таким образом, процедура выбора шага прн решенпй LP предельно проста. Упрощаются и другие вычисления. Например, оценка первого порядка для выигрыша, который сулит вывод ограничения из рабочего списка, становится точной, и, следовательно, нет нужды прибегать к более сложным способам оценивания. Поскольку матрица А всегда невырожденна, метод решения LP с использованием /-С-разложення А можно организовать так, что не придется хранить Q. Можно применить также/.(/-разложение А. Проблем с пересчетом факторов не будет, так как изменения в рабочем списке выражаются в модификациях Л ранга один.

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



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

Решение LP можно искать и «несимплексным» способом, допуская приближения, которые ие являются вершинами. Тогда, если в рабочем списке окажется менее и ограничений, направление поиска надо определять так же, как это делается в общем случае. Например, в качестве такового можно взять направление «наискорейшего спуска» p=-ZZc (ср. с (5.10)). Заметим, что если х не вершина, уменьшить значение критерия наверняка удастся (в отсутствие вырождения) без сокращения рабочего списка.

Наиболее распространенная форма постановки задачи LP отличается от (5.42). Она будет рассмотрена в разд. 5.6.1.

5.3.2. КВАДРАтаЧНОЕ ПРОГРАМЛШРОВАНИЕ

Запись общей задачи квадратичного программирования с огра-инчениями-неравенствами выглядит так:

найти min Л -[- - xCx

при ограничениях АхЬ.

Здесь матрица G и вектор с фиксированы.

Почти все распространенные алгоритмы квадратичного программирования относятся к классу методов активного набора. Мы подчеркиваем это, поскольку даже очень близкие по существу алгоритмы порой описывают в совершенно разных терминах, н это может сбить с толку. К примеру, некоторые вычислительные схемы дли QP основаны на применении «таблицы», в которой обьединены матрица ограничений и матрица С, другие существенно используют понятие «вед\тций элемент» и т. д. Обсуждая технику решения QP, мы сохраним обозначения, введенные в разд. 5.2.1. По-прежнему будет матрицей ограничений нз рабочего списка в точке Хд, а - матрицей, чьи столбцы формируют базис в подпространстве векторов, ортогональных строкам А,.

5.3.2.1. Задачи квадратичного программирования с положительно определенными спроектированными матрицами Гессе. Мы начнем с задач QP, про которые заранее известно, что спроектированная матрица Гессе ZIGZ„ будет положительно определенной па всех итерациях. За исключением особых случаев, соответствующие гарантии можно дать лишь при положительно определенной С. II Специфика рассматриваемых задач обеспечивает наличие конеч- Ч иого единственного минимума целевой функции F на подпростран-

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

ZiCZ,Pz=-Zlg, (5.47)

и положить Pk = Zf.Pz- Б силу квадратнчности F для значения шага вдоль есть только две разумные альтернативы. Единичный шаг приведет в точку минимума задачи минимизации F на нуль-пространстве матрицы А,,. Если он допустим, его и надо сделать. Прн этом очередное приближение будет условно стационарной точкой по отношению к ограничениям нз рабочего списка. Для нее можно вычислить точные значения множителей .Пагранжа, и тогда станет ясно, является ли она решением исходной задачи или критерий можно уменьшить, сократив рабочий список. Если же единичный шаг вдоль Pj недопустим, надо сделать максимальный допустимый шаг, после чего ввести сдерживающее ограничение в рабочий список.

Как и линейная, квадратичная целевая функция сулит целый ряд вычислительных преимуществ, позволяя существенно сократить усилия, затрачиваемые на расчет используемых в процессе поиска величин. В частности, так как матрица С постоянна, вычислять спроектированную матрицу Гессе и строить ее ра.зложение заново на каждой итерации ни к чему: для корректировки факторов при изменениях в рабочем списке можно применить эффективные методы пересчета. Если, например, какое-то ограничение исклю-чаетси из рабочего списка, то в спроектированной матрице Гессе появляются дополнительные столбец и строка (см. (5.40)). При этом для пересчета ее разложения по Холесскому придется вычислить только один новый столбец в верхнем треугольном факторе R. Квадратичность критерия облегчает и другие блоки схемы активного набора. Рассмотрим, например, расчет направления поиска в условно стационарной, но не оптимальной точке хд, причем будем считать, что Z,, строится методом С-факторизации. По определению в Хк выполнено равенство

Zlg, = 0. (5.48)

В соответствии с общей схемой здесь надо вычислить множители .Лагранжа и вывести одно нз ограничений с отрицательным множителем из рабочего списка. Затем следует пересчитать матрицу Z, и результатом этого будет Z вида (5.39). Таким образом, вектор g„ окажется ортогональным всем столбцам Zj, за исключением последнего, т. е.

2Ге.=(?ы

Направление поиска в Хд определяется по решению линейной системы (5.47), куда вместо Zi, надо подставить Zt- Полагая, что для



[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.0009