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

[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.28) к равенству

Л- = gt + GtP + 0 (II ? IP + II р-<? II).

(5.29)

Оно позволяет, в частности, предложить в качестве оценки для X* вектор i]l- решение задачи мнии-мизацни суммы квадратов невязок переопределенной системы уравнений

A-rii. = gk + GkP- (5.30)

Если при достаточно малых а будет i7 = 0(e) и р-1? = 0 (е-), то иа основании (5.29) можно утверждать, что % окажется оценкой второго порядка, т. е. t]j - ?.* = 0(е).

Важно отметить, что качество оценки 1) существенно определяется выбором р. Правая часть (5.30) при любом р является линейным приближением величины g(xu+p), и это приближение хорошо оценит g{x*) только тогда, когда р достаточно мало отличается от

Х*-Хк.

В примере 5.2 решением будет х*=(-0.14916, 3.20864, -0.05948), а соответствующий вектор множителей Лагранжа равен г.* =0.46927 (все числа даны с пятиразрядной точностью). В точке л:„-(2.0, -1.0. 2.0), где F(ji:„)=74.000, оценки для к* получились равными ?.L=51.000 и i]l=33.093: обе имеют правильный знак, но сильно отличаются от ?.* по модулю. Интересно, что в улучшенной точкеXi=:{0.\S79O, 2.66681, 0.14529) (где F(xi)=5.2632) были получены такие оценки; Я,=15.910 г)=-323.14. Не точна ни та, ИИ другая, но при этом оценка второго порядка имеет еще и неверный знак (хотя спроектированная матрица Гессе полонительно определена). Только совсем вблизи от решения, в точке хз=(-1.50П0, 3.20998, -0.05998), квадратичная оценка iii, оказалась лучше, чем линейная (Xj,=0.40869, t]i,=0.46922).

Когда в качестве р берется решение подзадачи (5.11) из схемы ньютоновского поиска, система (5.30) будет совместтюй по определению. В данном случае, чтобы получить 1). достаточно решить какие-нибудь t линейно независимых уравнений из (5.30). В частности, если Z строится методом исключения переменных, квадратичную оценку для X* даст решение системы вида

где через Р обозначен вектор, состоящий из первых t компонент суммы gt+Gkp.

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

Идея представления решения задач с линейными ограничениями-равенствами в терминах двух подпространств явно или неявно присутствует практически во всех посвященных им публикациях. Полное изложение различных способов задания матрицы Z читатель найдет в работеГилла и Мюррея (1974с) (см. также Флетчер (1972b)).

(5.31)

где V - некоторая (n-<) X «-матрица, обеспечивающая невырожденность Т. При решении задач с неравенствами в качестве строк V естественно брать векторы коэффициентов части неактивных ограничений. Построение Z на основе ортогональной факторизации А эквивалентно применению схемы Вулфа, если V в (5.31) составить из последних п-t столбцов Q (см. Гилл и Мюррей (1974с)).

Если размерность задачи с линейными равенствами позволяет применить для построения Z LQ-факторизацию, мы рекомендуем пользоваться именно таким способом; ои является наиболее численно устойчивым. Применительно к задачам с ограничениями-неравенствами эффективнее использовать другое (хотя и тесно связанное с LQ-факгоризацией) разложение (см. замечание к разд. 5.2). Однако, поскольку £.(3-факторизация, по-видимому, лучше знакома читателю, мы будем обращаться к ней и при описании методов решения задач с неравенствами.

Идея обобщения квазиньютоновских методов на задачи с ограничениями-равенствами путем применения вырожденных приближений обращенной матрицы Гессе впервые была высказана в статье Дэвидона (1959). Для задач с неравенствами этот подход был детально проанализирован Гольдфарбом (1969) Схема с пересчетом спроектированной .матрицы Гессе разработана Гиллом и Мюрреем (1973b, 1974(1, 1977а). Более полные сведения относительно оценок первого и второго порядков для множителей Лагранжа читатель найдет в статье Гилла и Мюррея (1979b).

5.2. МЕТОДЫ АКТИВНОГО НАБОРА ДЛЯ ЗАДАЧ С ОГРАНИЧЕНИЯМИ ТИПА ЛИНЕЙНЫХ НЕРАВЕНСТВ

В этом разделе рассматривается задача минимизации функции F на множестве точек, выделенном набором линейных неравенств;

L IP найти min F (х)

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

Здесь Л есть /ихп-матрица. Ради краткости изложения мы не будем касаться задач, среди ограничений которых есть и равенства, и не равенства; алгоритмы их решения получаются прямым обобщением

Метод спроектированного наискорейшего спуска был предложен и исчерпывающе проанализирован Розеном (1960). Авторство иа метод исключения переменных принадлежит Вулфу (1962) (см. также Мак-Кормик (1970а, Ь)). Вулф (1967) предложил также использовать в роли Z матрицу, составленную из последних n-t столбцов результата обращения;



представленных ниже а.т1горитмов. Условия оптимальности для LIP разобраны в разд. 3.3.2. Напомним, что в них значительную роль играют только ежтшные в оптимальной точке х* ограничения. Если их число равно t и через А обозначить матрицу, i-я строка которой состоит из коэффициентов i-ro активного в х* ограничения, то необходимые условия первого порядка можно записать так:

g(x) = V (5.32а)

г.>0. (5.32b)

От аналогичных условий для задач с равенствами их существенно отличает ограничение (5.32b) на знак миожнтелей Лагранжа. Как показано в разд. 3.3.2, появление отрицательного множителя означало бы, что существует допустимое направление спуска, и тем самым противоречило бы оптимальности х*.

Задача L1P по природе своей сложнее задачи с ограничениями-равенствами, так как заранее не известно, какие из ее условий в решении обратятся в равенства. Алгоритмы для LIP, которые нам предстоит обсудить, относятся к классу методов активного набора. Логика их организации опирается на следующие соображения. Если бы правильный список активных ограничений был известен априори, оптимум для LIP можно бьшо бы получить из решения задачи

найти min F (х)

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

(5.33)

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

Рабочий список всегда включает только те ограничения, которые в текущей точке обращаются в равенства; однако не все обращаю-

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

Представленная общая хараттернстика методов активного набора подразумевает, что задача LIP будет решаться в два этапа. На первом оире.теляется начальная допустимая точка, где некоторые нз ограничений Лх>Ь обратятся в равенства. На втором будет сгенерирована последовательность допустимых точек, сходящихся к решению.

5.2.1. людельная схема

Введем обозначения, используемые ниже при изложении общей схемы решения LIP с применением техники рабочего списка. Как всегда, k будет номером очередной итерации, а Хд -текущим допустимым приближением. Рабочий список в Хд зададим рядом атрибутов. Через обозначим число содержащихся в нем ограничений, через -множество их индексов, через Лд-матрицу, составленную из их коэффициентов (правые части этих ограничений соберем в вектор и, наконец, через -матрицу, набранную из векторов базиса подпространства, ортогонального строкам Лд.

Методы активного набора имеют разветвленную логик>, причем правила выбора ветвей для разных методов могут быть существенно различными. Поэтому в предлагаемой ниже универсальной схеме эти правила ие конкретизируются.

Пусть задана некая начальная допустимая точка х„; способы ее отыскания рассматриваются в разд. 5.7. Для того чтобы запустить метод активного набора, надо положить О и определить („, /„, Л„, 6„ и Z„. Последующая процедура поиска жшення будет выглядеть так:

Алгоритм L1 (схема активного набора для решения LIP).

111. [Проверка соблюдепия условий останова.] Еслн в текущей точке Хд условия останова выполнены, вычисления прекращаются и Хц выдается в качестве решения.

L12. [Выбор логической ветви.] Проверяется, стоит ли продач-жать минимизацию в текущем подпространстве илн имеет смысл удалить какое-нибудь ограничение из рабочего списка. Еслн принято решение сохранить рабочий список, осуществляется переход к шагу L13; в противном случае-к шагу LI6.



LI3. [Вычисление направления поиска.] Вычисляется ненулевой (л-/й)-мерный вектор " направление поиска

Pk = Z,Pz. (5.34)

LI4. [Расчет длины шага,] Вычисляется а-максимальный допустимый шаг из Хд вдоль рд. Определяется положительный шаг ctft, такой, что F (Хд Н-сСдрд) < F (Хд) и аа. Если ai,<a, осуществляется переход к шагу LI7; в противном случае-к шагу LI5.

LI5. [Введение ограничения в рабочий список.] Если -шаг, при котором становится равенством г-е ограничение, то индекс л добавляется к множеству /ц. Остальные атрибуты рабочего списка модифицируются соответствующим образом и осуществляется переход к шагу LI7.

L16. [Вывод ограничения из рабочего списка.] Выбирается ограничение (скажем, с номером s), которое надо вывести из рабочего списка. Индекс s исключается из /д. Остальные атрибуты рабочего списка пересчитываются соответствующим образом и осуществляется возврат к шагу L11.

LI7. [Пересчет приближения.] Выполняется присвоение x+i Хд + адРд, k-k + l и осуществляется возврат к шагу

5.2.2. РАСЧЕТ НАПРАВЛЕНИЯ ПОИСКА и длины ШАГА

В методах активного набора направления поиска выбираются из подпространства. вь]делеииого рабочим списком. Точнее говоря, очередное направление должно удовлетворять равенству Лдрй=0, и формула (5.34) есть ие что иное, как удобное средство выражения дайной связи. Заметим, что никакое перемещение вдоль рд не изменит левой части ни одного из Офаипчений, содержащихся в рабочем списке. Для вычисления {п-/й)-мерного вектора р на шаге L13 можно воспользоваться любым из методов, описанных в разд. 5.1.2 применительно к задачам с ограничениями-равенствами.

В методах для задач с равенствами, обсуждавшихся в разд. 5.1, длина шага кд выбирается без оглядки на ограничения; там от требуется талько одно - обеспечить «существенное убывание» F. Иначе дело обстоит с методами для задач с неравенствами. Чтобы очередное приближение было допустимым, шаг, в результате которого оно получается, не должен нарушать ограничений, не содержащихся в рабочем списке. Следовательно, существует оценка сверху для ctft- шаг вдоль рд до первой точки пересечения границы допустимого множества какого-нибудь из этих ограничений.

Для удобства записи мы временно опустим индекс k у величин, связанных с очередной итерацией; таким образом, текущая точка будет обозначаться через х, направление поиска-через р.

множество индексов ограничений рабочего списка -через / и т. д. Пусть i - индекс некоторого ограничения, не содержащегося в рабочем списке в точке х, т. е. iI. Если afpO, любой положительный шаг вдоль р не нарушит этого ограничения. Соответственно, если величины ajp окажутся неотрицательными при всех 1/, никакой верхней границы для длины шага ие будет. В противном случае, когда ajp < О, существует предельный шаг 1>,-, приводящий в точку, где i-e ограничение становится «удерживающим», т. е. реализующий равенство аТ (х-\ у<р)= Значение у; определяется по формуле

(6,-а

iI и аГр<

Введем величину а

min{i>,-f. если оТр<0 для некоторого 11; -I-CXJ, если af>0, для всех 11.

Это-максимальный неотрицательный допустимый шаг вдоль р. Он служит верхней оценкой окончательного шага а. Процедуры одномерного поиска в методах активного набора работают по следующей схеме. Сначала делается попытка отыскать шаг а.р, обеспечивающий существенное убывание F в соответствии с каким-нибудь нз критериев разд. 4.3.2.1 и удовлетворяющий условию а <а. Если такой шаг ctf найден, он и используется в качестве а. Однако может случиться что указанного а,.- ие существует; тогда а полагают равным а, даже если а не удовлетворяет выбранному критерию существенного убывания.

Мы хотели бы предостеречь читателя от применения естественной на первый взгляд схемы выбора шага, когда снача.ла вызывается какая-нибудь процедура одномерного поиска, предназначенная для алгоритмов безусловной миниыпзатши, а затем в качестве а берется минимум из а и шага , найденного этой процедурой. Во-первых, если функция F не ограничена снизу вне допустимой области, шага а, удовлетворяющего критерию останова процедуры одномерной безусловной минимизации, мо-HieT не существовать. Во-вторых, вытасление значений це-иевой функции для шагов, превосходящих а, есть бессмысленная работа, так как онн все равно не реализуются; желательно ограничивать одномерный поиск просмотром только допустимых точек. Разумные процедуры одномерной минимизации при ограничении сверху иа длину шага могут быть получены адаптацией регуляризованных схем разд. 4.3.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.0008