Главная Методы условной оптимизации [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.6), мы будем далее работать то с Рд, то с р. Важно, однако, помнить, что направление поиска Рд-это п-мервый вектор из подпространства в Ы" размерности п-t, в то время как р по определению является (п-0-мерным вектором. Сначала будут рассмотрены способы вычисления р при заданной матрице Z, а два метода построения Z описаны позже в разд. 5.1.3. 5.1.2. РАСЧЕТ НАПРАВЛЕНИЯ ПОИСКА 5.1.2.1. Методы наискорейшего спуска. Разбор методов решения задачи LEP мы начнем с простейших, являющихся обобщениями метода наискорейшего спуска для задач безусловной минимизации (см. разд. 4.3.2.2). Выводятся они по той же схеме, что и последний, но только теперь направление наискорейшего спуска надо искать среди представнмых в виде (5.7). Рассмотрим разложение f в ряд Тейлора в окрестности вдоль прозвольного допустимого направления 2р; F (х„ + Zp) = fд -Ь gJZp2 -f plZkPz +.... (5.8) Здесь f д, gk и Од- значения функции F, ее градиента и матрицы Гессе в точке х,,. Пренебрегая в правой части (5.8) всеми слагаемыми поридка выше перюго, можно построить два аналога задачи (4.11) со наискорейшем спуске». Первый получается, если нормировать сами направления Рд; выглядит он следующим образом: HafiTH min f 1 f . Решение этой задачи дает формула (4.12), в которую вместо gl надо подставить glZ, а вместо С-произведение ZZ. Соответствующим направлением поиска будет Pk-ZiZ-ZrZg,. (5.9) Если же нормировать р, задача «о наискорейшем спуске» принимает такой вид: найти min Связанное с ней направление рд задается формулой Pk-Z2?g„. (5.10) За.метим, что при ортонормальной Z векторы (5.9) и (5.10) совпадают. Обе приведенные формулы расчета рд дают направления спуска, причем углы между этими натгравлениями и градиентом целевой функции Строго отделены от прямо10. Поэтому комбинирование (5.9) или (5.10) с подходящей процедурой выбора длины шага дает глобально сходящийся алгоритм. Это доказывается в точности по той же схеме, что и в случае без ограничений. Аналогия с методом наискорейшего спуска для безусловной минимизации имеется и в отношении быстродействия. Обе формулы (5.9), (5.10) гарантируют лишь линейную сходимость (см. разд. 4.3.2.2), причем относительный пошаговый прогресс может быть сколь угодно малым. Чтобы добиться более высокой скорости сходимости, при выборе направления поиска надо принимать во внимание кривизну целевой функции. 5.1.2.2. 1Иетоды вторых производных. Для тех задач LEP, целевые функции которых таковы, что вычисление аналитических значений их вторых производных затруднений не вызывает, можно предложить модифицированные ньютоновские алгоритмы, подобные рассмотренным в разд. 4.4. Они базируются на понятии ньютоновского направления для LEP. Последнее представляет собой решение задачи вида найти т1пд--[р-Ьр0дР при ограничениях Лр = 0. (5.11) В силу эквнваленттюсти (5.6) вектор р, отвечающий это.му решению, доставляет минимум квадратичной функции, которая по- лучится из правой части (5.8), если отбросить все слагаемые порядка выше второго. Эта функция является локальной аппроксимацией F в подпространстве, натянутом на столбцы Z. Обозначим через 0 спроектированную матрицу Гессе ZCtZ, а через gt спроектированный градиент 2"§д. Тогда решением задачи (5.11) будет вектор Zp, где р-решение уравнения GzPz = -gz- (5-2) Оно аналогично уравнению (4.17). определяющему ньютоновское направление в случае без ограничений (и совпадает с ни-ч при Z=/). Пример 5.2. Возьмем задачу вида найти min х1>А -(- 4ха: -(- xixl -(- Ъхх, -(- ix-x, -(- SxjXj -f ад при ограничении л-,--Xa-J-Xg = 3. В допустимой точке х„ = (-1, 5, -1) решением (5.12) (с Z из (5.4)) будет / 0.72450\ Pz = \ 0.32483> и, следовательно, 0.23075\ р„= -0.64004 . 0.40929 (Все величины подсчитаны с пятиразрядной точностью.) Заметьте, что точка х„-(-ур„ допустима прн любом у. Еслн матрица положительно определена, то система (5.12) разрешима единственным образом и вдоль ньютоновского направления Zpz, построенного по ее решению, функция F убывает. В самом деле, прн положительно определенной таковой будет и Gi, откуда следует, что В отсутствие положительной определенности спроектированной матрицы Гессе ситуация осложняется. Тогда квадратичная модель функции F в пространстве векторов р, полученная из разложения (5.8). либо не ограничена снизу, либо имеет целое многообразие точек минимтча (см. разд. 3.2.3). Как выбрать на ее основе направление поиска рд, не ясно. Значит, надо ее заменить другой, а проще говоря, надо как-то модифицировать систему (5.12) для расчега р. Здесь подойдет любой нз приемов, описанных в разд. 4.4.2 применительно к задачам безусловной минимизации. В частности, «скорректированное» ньютоновское направление для LEP можно строить, вьгансляя р, как решение системы OzPz = ~gz с положительно определенной матрицей G, генерируемой по G процедурой модифицированной факторизации Холесского (см. разд. 4.4.2.2). Прн условиях, аналогичных выдвигаемым в случае без ограничений (т. е. при достаточной близости начального приближения к точке минимума и прн положительной определенности в ней спроектированной матрицы Гессе), ньютоновский алюритм, в котором направления поиска задаются формулами (5.7) и (5.12), а шагн вдоль рд равны единице, оказывается квадратично сходящимся. Если же осуществляется регулировка длин шагов, то на квадратичную сходимость можно рассчитывать только тогда, когда последовательность этих длин {«ь} будет достаточно быстро стремиться к единице. 5.1.2.3. Дискретные ньютоновские методы. Имея в распоряжении лишь первые производные от Р, для решения задачи LEP можно применить аналог дискретного метода Ньютона из разд. 4.5.1. Прн этом, так как уравнения расчета ньютоновского направления для LEP содержат только (п-0-мерную спроектированную матртщу Гессе Gz и не содержат матрицы G, конечно-разностная аппрокси- мавдя последней сама по себе не нужна. Без нее можно обойтись и при построении приближения матрицы G. Поскольку справедливы соотношения 6(xj-bi,z,)«ft+>Az,., матрицу Gz можно оценивать непосредственно, используя в качестве конечно-разностных векторов столбцы Z. В самом де.те, введем векторы i = l, .... п-t, вида Wl=J(g{Xt+hi!i) - gb). где ft;-подходящие конечно-разностные интервалы. Эти ш, приближают произведения Gz,. с точностью до О (/г,.). Составим нз них пх(п-0-матрнцу W. Тогда в качестве симметричной конечно-разностной аппроксимации для G можно будет взять G-i-(Z\i7-bU72). Отметим, что для построения требуется только (n-t) вычислений градиента. Таким образом, если ограничений в LEP много, расчет приближения спроектированной матрицы Гессе оказывается очень недорогой процедурой. При знаконеопределенной Gz система уравнений для вычисления pz должна быть модифицирована, и здесь, как и в случае с обычным методом Ньютона, можно использовать технику, описанную в предыдущей главе. Сходится дискретный метод Ньютона практически так же, как обыкновенный (см. разд. 4.5.1). 5.1.2.4. Квазиньютоновские методы. К задаче LEP можно приспособить и квазиньютоновскую схему оптимизации из разд. 4.5.2. Известны разные способы обобщения этой схемы на случай с линейными ограничениями-равенствами. Первым был предложен подход, который состоит в том, чтобы использовать для определения направлений поиска п-мерные вырожденные квазиньютоновские приближения обращенной матрицы Гессе, генерируемые по стандартным формулам. Если столбцы исходной квазнньютоновской матрицы ортогональны строкам Л, эти фор.мулы теоретически гарантируют сохранение данного свойства у всех последующих квазиньютоновских матриц. Тем самым обеспечивается автоматическая допустимость направлений поиска, вычисляемых по обычной формуле (4.4.3). Однако на практике дела обстоят не столь гладко. Из-за ошибок округления в процессе пересчета квазиньютоновских приближений упомянутое свойство ортогональности быстро теряется, и вычисляемые направления поиска становятся непригодными. Более успешный прием обобщения квазнньютоновской схемы безусловной минимизации на задачи LEP состоит в применении фиксированной матрицы Z (способы ее задания будут рассмотрены в разд. 5.1.3) и использовании квазиньютоновских формул для ап- проксимации (п--мерной спроектированной матрицы Гессе. В данном случае направление поиска будет определяться по решению аналогичной (4.28) системы вида BzPz = ~Bz. (5.13) в которой Bz-очередное квазнньютоновское приближение матрицы Су. Для построения можно взять любую из квазиньютоновских формул разд. 4.5.2.1, заменив в ней обычные векторы и матрицы спроектированными. В качестве примера приведем результат такого преобразования над BFGS-формулой (4.37). Обозначим через Bz квазиньютоновскую аппроксимацию для Cj в точке х„, и пусть Sz = ZSi„ yz = Zilk- Тогда приближением 0 в x+i, вычисляемым по BFGS-формуле, будет Bz=Bz+-gzei+-~ gzPz lulZPZ iJzA- (5.14) Аналогично преобразуются и другие квазиньютоновскне формулы. Представленный подход привлекателен тем. что позволяет естественно перенести на случай с ограничениями полезное свойство сохранения положительной определенности. Наличие этого свойства у приближений спроектированной матрицы Гессе Cz согласуется с необходимыми условиями оптимальности, в силу которых в точке минимума LEP по меньшей мере положительно полуопределена. В то же время сама матрица Гессе в этой точке, вообще говоря, будет знаконеопределенной, и поэтому любой метод решения LEP с квазиньютоновской аппроксимацией С положительно определен-ньши матрицами выглядел бы искусственно. В сравнении с первым способом обобщения квазиньютоновского поиска в LEP, сводящимся к применению вырожденных приближений обращенной матрицы Гессе, рассматриваемая схема существенно выигрывает в том, что гарантирует постоянную (зависящую от способа задания матрицы Z) точность соблюдения равенства (5.5) для вычисляемых направлений поиска. Как и в случае без ограничений, для повьпнения быстродействия и численной устойчивости процедуры решения LEP с использованием квазиньютоновскнх приближений матрицы Cz можно применить факторизацию Холесского (см. разд. 4.5.2.2). Храня и пересчитывая от шага к шагу не саму Bz, а ее факторы Холесского, легко предусмотреть корректировки, которые обеспечат положительную определенность Bz и тем самым правильную ориентацию направлений поиска независимо от неточностей машинной арифметики. К задаче LEP применимы также квазиньютоновскне методы без вычисления производных (см. разд. 4.6.2). Поскольку в формулах расчета pz и обновления Bz фигурирует только спроектированный градиент Zgj и отсутствует обычный, квазиньюто- новский поиск решения LEP с конечно-разностной аппроксимацией производных (проблема выбора конечно-разностных интервалов обсуждается в разд. 8.6) можно организовать так. что на каждой итерации потребуется лишь п-( дополнительных вы-чис.пений функции F. Для этого надо непосредственно оценивать произведение Zg по разностям F вдоль п-t столбцов Z. Как и дискретные методы Ньютона, данный подход будет тем эффективнее, чем больше число ограничений в задаче. 5.1.2.5. Методы с использованием схемы сопряженных градиентов. Среди рассмотренных в разд. 4.8 приемов безусловной минимизации функций больцгого числа переменных для LEP лучше всего приспосабливается техника сопряженных градиентов. Что же касается способов эксплуатации слабой заполненности, описанных в разд. 4.8.1 и 4.8.2, то к LEP их применяют редко, так как спроектированная матрица Гессе в общем случае сильно заполнена даже при разреженных А и С, (исключение составляют задачи с ограничениями очень специальной структуры), а строить процедуру решения LEP на основе аппроксимации самой матрицы Гессе, как правило, неэффективно. Одна из возможностей приложения схемы сопряженных градиентов к задаче LEP состоит в том, чтобы взять ее в качестве алгоритма решения системы (5.12) (имеется в виду линейный метод сопряженных градиентов из разд. 4.8.6). При этом явно формировать матрицу Cz не нужно: если в памяти поместятся разреженная Сд и разреженное представление Z, вычисление произведений вида ZCfZv экономнее реализовать в три этапа, последовательно определяя о, = Zo, v. = GjO, и = Zv,. Если вторые производные недоступны, вектор fg можно заменить его конечно-разностной аппроксимацией. Последняя строится по приращению градиента целевой функции, отвечающему малому шагу из Хд вдоль fj- Рассматриваемую технику решения LEP, представляющую собой обобщение усеченного метода Ньютона (см. разд. 4.8.6), нередко комбинируют с приемами улучшения обусловленности, описанными в разд. 4.8.5. Делают это разными способами в зависимости от того, какая информация доступна и какое значение придается ускорению сходимости .пинейного метода сопряженных градиентов. Наибольшего эффекта удается достичь, когда памяти машины хватает для хранения (п-t)x(n-t) чисел. В этом случае в качестве матрицы, улучшающей обусловленность, используют квазиньютоновское приближение Bz спроектированной матрицы Гессе. 5.3.1. ПРЕДСТАВЛЕНИЕ НУЛЬ-ПРОСТРАНСТВА ОГРАНИЧЕНИЙ В данном разделе описаны два способа построения матрицы Z, фигурирующей в приведенных выше формулировках методов решения LEP. Отметим, что эту матрицу вовсе ие обязательно форми- В J» 2564 [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.0011 |