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

[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.43) для множителей можно будет записать так: /Вг О

«=С 1.)(ЗЧ»";.)ч:;>

Здесь Св и суть векторы, образованные из компонент с, отвечающих соответственно базисным и небазисным переменным.

Из (5.68) вндно, что вектор л будет решением невырожденной линейной системы

ВГп = Св. (5.69)

Заметим, что знаки компонент л в условиях оптимальности для исходной задачи не оговариваются. После того как л вычислен, множители зафиксированных перемегшых легко определяются по второй группе уравнений в (5.68). Ее решение дается формулой

o = cv-Nsi.

В терминологии линейного программирования множители Oj называются оценками замещения нли приведенными ценами.

В оптимальрюй точке компоненты вектора о должны иметь определенные знаки. Точнее, те из них, которые соответствуют переменным, зафиксированным на нижних границах, должны быть неотрицательны, а остальные - неположительны. Коль скоро это требование в X выполнено, можно утверждать, что х - решение задачи. В противном случае одна из небазисных переменных будет освобождена, т. е. одно из простых ограничений будет выведено из рабочего списка. Предположим, что такой переменной является х,, имеющая нижнее граничное значение, и представим очередное направление поиска р в виде (рл p,v). Тогда компонента вектора рд., отвечающая

должна быть единичной, и это - его единственная ненулевая компонента. Что же касается рв, то он определится из уравнений типа (5.44), (5.45), которые в рассматриваемой ситуации выглядят так:

(5.70)

Соответственно рв есть решение системы Врв=-о„

где через а, обозначен s-fi столбец матрицы А.

Двигаться вдоль р, уменьшая значение целевой функции, надо до тех пор, пока какая-то из базисных переменных не примет свое граничное значение, т. е. пока не проявится какое-то из отсутствующих в текущем рабочем списке простых ограничений. Оно войдет в рабочий список для следующей итерации. Как следствие, матрицы Вч N изменятся, а точнее, они будут набираться из других столбцов А. В результате полной итерации симплекс-метода происходит обмен ролями для некоторой пары базисной и небазисной переменных.

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

В большинстве современных реализаций симплекс-метода, рассчитанных на большие задачи линейного программирования, для решения систем (5.69) и (5.70) используется /.{/-факторизация матрицы В. На первом шаге она дает представление

L-iB = iM„.i...MjM,B = t/, (5.71)

где каждая М,. есть элементарная нижняя треугольная, at/ - верхняя треугольная матрицы (ради простоты мы предположили, что перестановок строк и столбцов, которые могли бы понадобиться для обеспечения численной устойчивости процедуры факторизации, не потребовалось; ср. с (2.40)). Имея (5.71), для поиска решения системы типа Вх=Ь надо вычислить y=M-i. .ММЬ, а затем подстановками назад решить систему Ux=y. (Здесь уместно отметить, что подстановки вперед и назад организуются одинаково просто независимо от того, как в памяти машины хранится матрица - по столбцам или по строкам.) Расчет вектора у состоит в прямом поочередном применении преобразований Mj. Расчет х чо у требует обратного прохода по столбцам или строкам матрицы U. (Аналогичные процедуры используются также для решения систем типа Bz=c.)

Возможность эффективного решения задачи линейного программирования с очень большим числом переменных существует только тогда, когда матрица А достаточно разрежена (т. е. число ее ненулевых позиций достаточно мало). В этом случае для записи ненулей факторов /. -разложения матрицы В потребуется разумный объем памяти. Надо иметь в виду, что количество зггих ненулей сильно зависит от расстановки строк и столбцов В. Следовательно, есть смьшл тратить определенные усилия иа поиск такой нумерации переменных и ограничений, при которой число дополнительных ненулей в /. -разложении В будет умеренным. Соответствующие процедуры иногда называют подбором упорядочения ведущих элементов. В идеале хотелось бы, чтобы перестановкой строк и столбцов матрицу В можно было преобразовать в нижнюю треугольную - тогда для решения систем (5.69) и (5.70) никакой факторизации не понадобится. В действительности же базисные матрицы прикладных задач обычно «почти» преобразуемы в треугольные, что и используется существующими методами упорядочения ведущих элементов.

При обмене столбцами (в результате смен базиса) между В н N факторы /. -разложения В должны пересчитываться. Во время таких пересчетов в список определяющих L элементарных матриц добавляются новые {.Mj] и формируются новые столбцы типа LOj.



Как правило, каждый пересчет приводит к появлению в U новых ненулевых позиций. Память, отводилгую для хранения (/, организуют так, чтобы вновь возникающие ненули помещались в конец текущей записи и, но при этом были легко доступны на соответствующих этапах решения систем (5.69) н (5.70) (познакомиться с такими способами хранения U можно по литературе, указанной в замечаниях).

По мере выполнения итераций симплекс-метода и связанных с ними пересчетов /.(/-разложения базисной матрицы объем памятн, занимаемой факторами этого разложения, растет. Обычно после серии пересчетов он оказывается много больше того, который потребовался бы для записи факторов /.(/-разложения, построенного в текущей точке «с нуля» на какой-нибудь из разумных схем с выбором упорядочения ведущих элементов. Поэтому через определенные промежутки времени возникает необходимость построить разложение заново. Как правило, такие обновления, именуемые повторными обращениями, осуществляются с фиксируемой частотой, но могут выполняться и раньше намеченного срока, если память, отведенная для записи факторов разложения В, исчерпывается.

5.6.2. большие задачи с линейными ограничениями И нелинейными критериями

В этом разделе рассматриваются задачи вида

найти rain F {х)

*e3i"

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

1:хи.

(5,72)

Будем считать, что количество переменных в (5.72) «велико», а матрица А разрежена. Заметьте, что структура ограничений из (5.72) точно такая же, как в стандартной форме LP. Соответственно и описанные ниже методы будут сильно опираться на технику, разработанную для решения линейных задач большой размерности.

Как правило, возможности выбора способов решения большой задачи относительно небогаты. Дело в том, что многие вычислительные процедуры, применимые для широкого круга малых задач, при увеличении размерности становятся чрезмерно трудоемкими илн требуют слишком много памятн. В то же время оптимальная среди оставшихся возможностей становится менее очевидной, поскольку специфика конкретной задачи и детали реализации доступных схем приобретают существенно больший вес.

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

относительной трудоемкости разных этапов процесса поиска решения. Например, мерой эффективности обычного алгоритма безусловной оптимизации принято считать количество обращений к программируемым пользователем процедурам вычисления функций (целевой функции, ее градиента), необходимое для отыскания решения с заданной точностью. Хотя такой способ измерения эффективности может показаться чрезмерно упрощенным, для большинства малых задач он вполне пригоден. Это обьясняется тем, что для них объем не связанных с подсчетом функций арифметических операций, выполняемых на каждом шаге, относительно мал (его максимальный порядок есть п) и трудоемкость манипуляций с памят1>ю незначительна. Однако уже для задач средних размеров затраты чисто алгебраических блоков оптимизационных схем н процедур организации доступа к данным становятся существеинымн.

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

Л=(В S N). (5.73)

Здесь N есть тХг-матрица, столбцы которой отвечают небазисным переменным; В - «базисная» невырожденная mxm-матрица, набранная нз столбцов А, соответствующих базисным переменньм; S - матрица, состоящая из п-т-г столбцов А, отвечающих остальным переменным, которые впредь будем назьшать супербазисными. Число супербазисных переменных представляет собой количество степеней свободы, остающихся после закрепления небазисных (поскольку в рабочем списке будет т-Ьг ограничений). В лтшейном случае, рассмотренном в разд. 5.6.1, матрица S отсутствует, а число столбцов всегда равно п-т.

На рассматриваемой итерации ограничения из рабочего списка (записанные в удобной форме) будут выглядеть следующим образом:

« )0=(1>

Компоненты вектора Ьк совпадают с соответствующими компонентами / или и в зависимости от того, на каком из граничных значений фиксируется переменная.



Чтобы получить способ расчета направления спуска Zpz для задачи (5.72), надо задать формулы вычисления его базисной, небазиснон и супербазисной составляющих. Матрицу Z, ортогональную строкам Л, определяют так:

(5.75)

Ни саму Z, ни В" в явном виде не вычисляют. Для подсчета матрично-векторных произведений с Z и Z достаточно иметь треугольное разложение квадратной матрицы В.

При построении Z по формуле (5.75) расчленение вектора переменных на три составляющие находит прямое отражение в процедуре вычисления направления поиска р. Представив P = Zpz в виде (рв ps Рд), из (5.75) получим, что р« = 0 и

Bp„ = -Sps. (5.76)

Равенство (5.76) показывает, что рв однозначно выражается через Ps. Таким образом, минимизацию можно организовать как поиск в подпространстве супербазисных переменных. В рассматриваемой схеме расчета р вектор ps играет в точности такую же роль, которая была у Pz в методах, описанных выше, и полностью определяет р. После того как р построен, рв находят решением системы (5.76).

5.6.2.1. Выбор супербазисиой составляющей направления поиска. Соображения, лежащие в основе методов выбора «хорошего» вектора ps, аналогичны приведенным в разд. 5.1.2 относительно вектора pz. В наиболее эффективных методах ps определяется по квадратичной аппроксимации целевой функции с учетом ограничения (5.76). Точнее говоря, ps подбирается так, чтобы построенное по нему направление поиска было решение,м квадратичной задачи вида

найти inin ер--ггРИр

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

где Н-некоторая аппроксимация матрицы Гессе функции F {х). Для вычисления такого вектора ps нужна только спроектированная матрица ZHZ. Он будет решением линейной системы

ZHZp-Zg, (Ъ.Щ

где Z определена формулой (5.75). Заметим, что Zf = =-SrB-rg„+gs.

Реальная возможность решить систему (5.78) с помощью факторизации ее матриць! существует лишь при условии, что размерность

матрицы достаточно мала. Дело в том, что, как правило, она будет сильно заполненной даже при разреженных Л и Я. Значит, предлагаемый способ расчета Ps практичен только в случаях, когда заранее известно, что число ограничений в рабочем списке будет достаточно велико на каждой итерации. К счастью, для многих больших задач згго условие соблюдается, причем можно дать априорную нижнюю оценку количества ограничений, которые будут выполнены в решении как равенства. Предположим, к примеру, что целевая функция нелинейна по малому числу переменных (эта ситуация типична, когда нелинейности возникают в результате уточнения изначально линейной задачи). Такая F(ii) будет выглядеть следующи.м образом:

f () = /(.) + Л,

где x=(Xi, .....x„)r -вектор небольшой размерности и /(х)-

некоторая дифференцируемая нелинейная функция. Если известно, что в рассматриваемом случае оптимальная точка удовлетворяет достаточным условиям второго порядка, то можно утверждать, что в ней размерность спроектированной матрицы Гессе не превзойдет q.

Даже при умеренных размерностях систем (5.78) методы ньютоновского тнпа с факторизацией Gz для больших задач, как правило, оказываются непрактичными; слишком много вычислений требуется для построения спроектированных матриц Гессе заново на каждом шаге (напомним, что всякая операция с Z предполагает решение системы уравнений с матрицей В). В отличие от них квазиныот01юв-ские методы адаптируются к большим задачам очень эффективно. Имеется в виду обсуждавшаяся в разд. 5.2.4.2 схема расчетов с пошаговой корректировкой разложения по Холесскому квазиньютоновского приближения спроектированной матрицы Гессе.

Среди прикладных задач большой размерности встречаются и такие, в решениях которых число активных ограничений значительно меньше числа переменных. Например, иногда большая часть ограничений вводится, чтобы исключить «неразумные» решения, и оказывается неактивной в «разумном». Если па-мятн для факторизации (п - 0-мериой матрицы из (5.78) не хватает, решение (5.78) можно искать методами сопряженных градиентов типа рассмотренных в разд. 5.Г2.5. В частности, если вторые производные доступны и матрица Гессе G разрежена, реально воспользоваться схемой нькгтоновского тнпа, в которой р определяется в результате итерационного поиска решения системы (5.78) с Я = С. Надо только, чтобы подсчет значительного числа произведений вида ZGZv при поэтапной организации, когда сначала вычисляется tij = Zv. затем = и наконец = Zv = = ZGZv, не был слишком трудоемок. Аналогичную процедуру можно использовать и в случаях, когда доступна не сама матрица Гессе, а ее разреженная аппроксимация. К итерационному



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