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

[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» мы, по существу, подразумеваем те алгоритмические приемы, которые применяются в процедурах решения LEP для обеспечения допустимости генерируемых напракпений поиска (и определения допустимого начального приближения).

6.1.3.1. LQ-факторизация. Первый метод построения Z сводится к /.(Э-факторизации матрицы А (см. разд. 2.2.5.3). Допустим, что известна ортонормальная пХ/г-матрица Q, такая, что

Л0 = (0), (5.15)

где L есть невырожденная нижняя треугольная /X/-матрица. Тогда в качестве Y можно взять матрицу, составленную из первых t столбцов С а Z набрать из ее последних п-t сто.1бцов. При этом будет справедливо равенство ZZ = /„ ,, И.плюстрацией применения данного подхода служит матрица Z из примера 5.1.

Для методов решения задачи LEP как таковой нумерация столбцов в Z роли не играет, и поэтому для них расстановка соответствующих столбцов Q не существенна. Однако, если LEP решается как подзадача в методе поиска минимума при ограничениях-неравенствах, столбцы Q гголезно рассматривать в определенном порядке (см. разд. 5.2.4,1 и замечания к разд. 5.2).

Еслн матрица Y задается предлагаемым способом, для нее справедливо равенство AY = L, и, следовательно, вектор ху будет решением системы

Lxrb. (5.16)

Последняя хороша тем, что число обусловленности ее матрицы не бо-пьше числа обусловленности А. Определив ху нз (5.16), в качестве начального приближения для LEP можно взять Yxy.

Рассматриваемый подход к построению матрицы Z не связан с каким-либо ухудшением обусловленности в процессе решения LEP, н в этом его существенное достоинство. Поясним сказанное на примере ньютоновского поиска. Для чиста обусловленности cond (Gz) фигурирующей в нем матрицы справедливо соотношение

cond (Gz) < cond (Сд) (cond (Z))=.

Из него видно, что при большом cond (Z) матрши Gz может оказаться очень плохо обусловленной даже когда G обусловлена хорошо. Если же Z определяется посредством Z-Q-фактори-зацин, то обеспечено равенство cond(Z)=l, и соответственно

cond (Gz) cond (Gj).

Это означает, что обусловленность исходной задачи не ухудшается в процессе ее решения.

Л = (У V).

(5.17)

где V есть < х невырожденная матрица. (Для простоты мы предположили, что V образована t первы.мн столбцами Л; в общем же случае V может включать любой подходящий набор столбцов Л.)

Представляя в соответствии с (5.17) вектор х в вит (х ХцУ, ограничения LEP можно записать так:

или, что то же самое.

Поскольку V по определению невырожденна, отсюда стедует равенство

XyV-(b-Uxu). (5.18)

Оно позволяет расценивать (-мерный и (п--мерный векторы Ху и Хц как «зависимый» и «независимый» соответственно. Суть в том, что ограничения LEP будут автоматически соблюдены прн любом Хц, если только Ху вычисляется по формуле (5.18). Такой способ учета ограничений типа линейных равенств называют методом исключения переменных. Начальная допустимая точка в данном случае определяется следующим образом: Х£/=0, Xy=V-b.

Определяя Z методом /.О-разложения, пхп-матрицу (J можно формировать явно как произведение ортогональных преобразований, используемых для трнангуляризацни А. Однако, когда число ограничений в LEP относительно мало, это скорее всего неэкономно с точки зрения как требуеьюй памяти, так н трудоемкости последующих вычислений. Многие алгоритмы поиска решения LEP используют только матрично-векторные произведения с Z, Z и К, а их можно вычислять и не имея явных представлений Z, Y: достаточно хранить компактные записи ортогональных преобразований, используемых в процессе С-фактори-зации, и тогда искомые матрично-векторные произведения определятся последовательным применением этих преобразований к соответствующим векторам. Будет ли этот подход эффективнее, чем метод с явным формированием Q, зависит от отношения между п и t.

5.1.3.2. Метод исключения переменных. Второй способ формирования Z исходит из расчленения матрицы ограничений А на две составляющих:



Методу исключения переменных отвечает ортогональная к А матрица Z вида

/-V- и\

(Б. 19)

-(-7")-

Для примера 5.1 эта формула дает

/-1 -1 Z= I

Определяя матрицу Z по формуле (5.19), ее практически никогда не формируют явно. Величины, необходимые для расчета направлений поиска, - это матрично-векторные произведения с Z и Zr. Они всегда могут быть получены из решения уравнений с V и V. Значит, для реализации схемы исключения переменных достаточно построить подходящее разложение V, и тогда Z не понадобится. Представление (5.19) в основном применяется прн решении задач большой размерности (см. разд. 5.6).

5.1.4. СПЕЦИ.АЛЬНЫЕ ФОРМЫ ЦЕЛЕВОЙ ФУНКЦИИ

5.1.4.1. Линейная целевая функция. Если функция F (х) линейна (скажем, F(x) = cx, где с -некоторый фиксированный вектор), то условие оптимальности (5.1) выполнимо лишь в том случае, когда с является линейной комбинацией строк А. При произвольном с это предполагает невырожденность Л, т. е. наличие п линейно независимых ограничений. Последние полностью определят решение задачи, которое будет ее единственной допустимой точкой. Совпадение допустимого и оптимального множеств разрешимой задачи LEP с линейной F имеет место и при меньшем чиспе ограничений. Этот факт используется при построении алгоритмов решения линейных задач с ограничениями-неравенствами.

5.1.4.2. Квадратичная целевая функция. Задачи с линейными ограничениями и квадратичной целевой функцией называют задачами квадратичного программирования. В этом разделе мы рассмотрим одну из них;

иайти ттсх-\-х Сх (5.20)

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

Здесь с и с-постоянные матрица и вектор.

Когда матрица ZCZ положительно определена, задача (5.20) имеет конечное решение, причем это решение единственно. В данном случае шаг р из произвольной допустимой точки х (с градиентом g = Cx-\-c) в оптимальную х* будет решением

задачи вида

найти min ер -)- pGp

пет 2

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

(5.21)

Последнее, как показано в разд. 5.1.1.2, строится по {п - t)-мерному вектору pz - решению следующей задачи безусловной минимизации:

найти min gZPz-hPzZGZpz.

(5.22)

Этот вектор в свою очередь является решением линейной системы

ZrGZpz-Z-rg.

Соответственно шаг р в точку минимума (5.20) определяется так:

p = -Z{ZrGZ)-Zrg. (5.23)

В разд. 3.3.1 показано, что необходимым условием оптимальности X* в задаче (5.20) служит равенство

g(x*)=gH-Cp = ?.«, (5.24)

где ?.* есть (-мерный вектор множителей Лагранжа для задачи (5.21). Система (5.24) будет разрешимой относительно X* независимо от ранга А.

Случаи, когда спроектированная матрица Гессе не является положительно определенной, разбираются применением к (5.22) рассуждений разд. 3.2.3. В частности, при знаконеопределенной ZrCZ конечного решения задачи (5.20) не будет.

5.1.5. ОЦЕНКИ МНОЖИТЕЛЕЙ ЛАГРАНЖА

Если X*- решение задачи LEP, то должно выполняться равенство

й(х) = Лг.«, (5.25)

где >.*- некоторый -мерный вектор множителей Лагранжа. По определению аналогичные равенства будут иметь место и во всех других условно стационарных точках. Что же касается остальных допустимых точек, то в них система (5.25) (с неизвестным X*) несовместна, и поэтому для ннх множители Лагранжа ие определены. Тем не менее, как будет показано в разд. 5.2.3, важно иметь некие средства оценивания этих множителей в точках, где (5.25) не выполнено. Ниже кратко рассмотрены возможные способы построения соответствующих оценок Xtt для произвольного хд. При это.м нас будут интересовать только состоятельные оценки, т. е. оценки Яд,



обладающие тем свойством, что

из х-х* следует Kj-K*. (5.26)

Кроме того, важно, чтобы в методах оценивания множителей Лагранжа использовались те же матричные разложения, на которые опиракяся способы представления Z.

5.1.5.1. Линейные оценки множителей. Если матрица Z строится LQ-факторнзацией Л, в качестве оценки для К* удобно использовать вектор Я,- решение задачи

найти minii АЧ.-gfL.

(5.27)

В аналитических выкладках его определяют формулой Х, = (ЛЛ-Мг,.

Однако в алгоритмах данную формулу лучше не применять; поскольку чиспо обусловленности матрицы Л Л равно квадрату числа обусловленности Л, это чревато большими ошибками вычислений. Значительно надежнее строить так, как описано в разд. 2.2.5.3. Тогда огнибка вычисления Х. в окрестности стационарной точки не превысит величины, пропорциональной числу обуслов.пенности Л.

Еслн для представления Z используется метод иск.пючения переменных, схему построения оценок множителей Лагранжа естественно ориентировать на доступное разложение матрицы V. В предположении, что V состоит из первых t сто.пбцов Л, подходящей оценкой будет решение первых t уравнений из (5.25):

Здесь gv- вектор, образованный первыми i компонентами градиента gh. Заметим, что при Хц=х* и Tij,, и Ху совпадут с точным вектором множителей Лагранжа.

Оба описанных способа расчета приближений ?.* дают оценки первого порядка. Последнее означает, что прн малых х-х* уклонения ?.i и Х, от ?.* будут величинами порядка Цхд-х*). Таким образом, еслн в х* все множители Л§граижа отличны от нуля, в малой окрестности х* как так и Ху оценят ?.* с хорошей относительной точностью. Размер этой окрестности, очевидно, зависит от кривизны функции F. Она определяет величину нормы §д-g(x*). Кроме того, не претендуя на абсолютную строгость, в отношении оценки можно утверждать, что окрестность х*, в которой она хороша, тем меньше, чем больше число обусловленности матрицы Л; когда строки Л почти линейно зависимы, эта окрестность будет исчезающе малой. Что же касается оценки Ху, то для нее размер окрестности

Пример 5.3. Рассмотрим задачу, в которой \ / 2 X

l-t-E 1

о -1/

g(n =

2-t-e v-1/

2-Ьб 2

-1-1-е.

Заметим, что число cond (Л) мало и что мала также норма lg(x*)-gtli. Точный вектор множителей Лагранжа равен ?.* = = (1, 1). Посмотрим, чему равны оценки ?.j и Г.у, вычисленные в Хд, причем составим из двух первых строк А. Для е= 10- получается, что (1.0000), 0.999990) и ?. = (-1.0, 3.00001) (обе оценки округлены до шести значащих цифр). Таким образом, малое уклонение от х* нз-за плохой обусловленности V привело к совершенно неудовлетворительной оценке Ху.

5.1.5.2. Квадратичные оценки множителей. Прн определенных условиях множители Лагранжа можно оценивать и с ошибкой второго порядка малости. Д.т1я этого нужно использовать информацию о вторых производных F в Xft. Обозначим через q шаг из Хд в х*. По определению вектор точных множителей Лагранжа X* является решением системы

g{>f) = g(x, + q)=AX:

Разлагая g(x) в ряд Тей-пора в окрестности Хд, отсюда получим

Agh + Ga + OHqf). (5.28)

Эта формула и лежит в основе мегодов построения квадратичных оценок для X*.

Поскольку вектор q не известен, непосредственно использовать (5.28) для вычисления оценок X* нельзя. Однако, располагая его

обратно пропорционален числу обусловленности матрицы V, которое может быть сколь угодно большим даже при хорошо обусловленной А. В произвольной точке Хд норма невязки AXt-gi, ограничена сверху величиной Hgj-g (х*). Аналогичная невязка AXi-для оценки Х имеет первые / компонент равными нулю, а норма вектора, состав.11енного из остальных компонент, зависит от числа обусловленности V. Мы хотим подчеркнуть, что указанное выше относилось к точный значениям оценок Xi, и На деле все будет обстоять хуже. В частности, хотя теоретически Ху в х* должны совпасть с ?.*, из-за ошибок округления нх численно найденные значения скорее всего будут иными. Прн этом ошибки вычисления Х и Ху пропорциональны числам обуслов.тенности А и V соответственно.

Представленный ниже при.мер иллюстрирует некоторые нз высказанных положений.



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