MATLAB.Exponenta
MATLAB и Simulink на русском
Технологии разработки и отладки
		сложных технических систем

Optimization Toolbox 2.2 Руководство пользователя

А.Г.Трифонов. Алгоритмы большой размерности

В данном разделе приводится описание используемых в тулбоксе Optimisation методов, предназначенных для решения оптимизационных задач большой размерности. Приводится описание следующих основных тем:

Методы на основе использования доверительных областей в задачах нелинейной оптимизации

Вводится понятие доверительных областей, приводится описание использование понятия доверительных областей для решения задач нелинейной оптимизации без наличия ограничений

Сопряженные градиенты с предварительной обработкой данных

Приводится описание алгоритма использования сопряженных градиентов с предварительной обработкой данных (PCG) для решения больших симметричных положительно определенных систем линейных уравнений.

Задачи с линейными ограничениями

Приводится анализ решения задач минимизации с ограничениями в виде линейных равенств и боксовым ограничениями.

Нелинейный метод наименьших квадратов

Приводится описание решения нелинейных задач на метод наименьших квадратов

Квадратичное программирование

Приводится описание решения задач минимизации с квадратичной целевой функцией.

Линейный метод наименьших квадратов

Приводится описание решения линейных задач на метод наименьших квадратов

Линейное программирование задач большой размерности

Приводится описание метода LIPSOL (Линейный решатель с внутренними точками) для решения задач линейного программирования в случае большой размерности

Избранная библиография

Приводится список опубликованных материалов в поддержку принятых для реализации алгоритмов для задач большой размерности

Методы на основе использования доверительных областей в задачах нелинейной оптимизации

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

Для пояснения подхода при решении задач оптимизации при использовании доверительных областей рассмотрим задачу оптимизации без наличия ограничений, , где функция воспринимает векторные аргументы и возвращает и скалярные величины. Предположим, что мы находимся в точке некого n-мерного пространства и необходимо улучшить решение, т.е. перейти в точку с более меньшим значением функции. Основная идея состоит в том, что функцию необходимо представить в виде некой аппроксимации посредством более простой функции которая достаточно правдоподобно отображает поведение функции в окрестности вблизи точки x. Эта окрестность и называется доверительной областью. Пробный шаг рассчитывается посредством минимизации (или приблизительной минимизации) в выбранной окрестности N. Такой подход составляет так называемую подзадачу доверительной области,

(4-1)

при выполнении условии текущая точка переходит в новое значение , в противном случае текущая точка остается без изменения и область доверия N претерпевает некое сокращение и расчет пробного шага повторяется.

Ключевыми моментами в определении специфического подхода доверительных областей для минимизации являются вопросы как

  • выбрать и рассчитать апроксимационную функцию (определенную в текущей точке ),

  • выбрать и откорректировать доверительную область N,

  • точно решить подзадачу доверительной области.

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

В стандартном методе доверительных областей ([8]) квадратичная аппроксимация определяется через использование двух первых членов разложения Тейлора функции в точке x, При этом окрестность , как правило, принимается сферической или эллипсоидальной формы. В математической форме подзадача на метод доверительных областей ставится как

(4-2)

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

Существуют хорошие алгоритмы для решения уравнения 4-2 (см. [8]), подобные алгоритмы обычно включают в себя расчет полной системы собственных значений, а так же метод Ньютона применительно к вековому уравнению

Подобные алгоритмы приводят к точному решению уравнений типа 4-2. Однако необходимо учитывать, что при их решении требуется время, пропорциональное числу членов от разложения матрицы Гессе H. Именно поэтому для решения задач большой размерности требуется поиск различных типов решения. Несколько аппроксимационных подходов и эвристических стратегий применительно к уравнению 4-2 можно найти в соответствующей литературе ([2], [10]). Принятый в данном тулбоксе Optimization указанный аппроксимационный подход заключается в сведении принятой подзадачи с доверительной областью к некому двумерному подпространству ([1], [2]). Как только подпространство будет определено, то проблема по решению уравнения 4-2 становится достаточно тривиальной задачей, даже, несмотря на то, что необходимо знать полную информацию о собственных значениях и собственном векторе (поскольку в выбранном подпространстве данная задача является однозначно двумерной). Вся основная деятельность теперь сводится к определению необходимого подпространства.

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

(4-3)

или направление отрицательной кривизны

(4-4)

Внутренний подтекст подобного выбора состоит в том, что бы обеспечить глобальную сходимость (через направление наискорейшего спуска или через направление с отрицательной кривизной) и достигнуть быстрой локальной сходимости (через шаг Ньютона, если тот конечно существует).

Основные особенности данного подхода в тулбоксе Optimization применительно к минимизации без наличия ограничений путем использования положения о доверительных областях на данный момент можно представить как:

  • Сформулировать двумерную подзадачу на основе метода доверительных областей.

  • Решить уравнение 4-2 с целью определения пробного шага .

  • Если , то .

  • Установить .

Все эти четыре шага повторяется до тех пор, пока не будет достигнута требуемая сходимость. Размерность доверительной области устанавливается согласно стандартным правилам. В частности, она уменьшается, если пробный шаг не принимается, т.е. . Детальное обсуждение данного аспекта можно найти в работах [3], [9].

В тулбоксе Optimization задействовано несколько важных специфических случаев специализированных функций f:

  • нелинейная задача на основе метода наименьших квадратов,

  • квадратичная и линейная на основе метода наименьших квадратов.

Однако основополагающие алгоритмические идеи есть те же самые, как и в общем случае. Эти специфические случаи обсуждаются далее.

Сопряженные градиенты с предварительной обработкой данных

Одним из наиболее распространенных путей решения симметричной положительно определенной системы линейных уравнений большой размерности является метод сопряженных градиентов с предварительной обработкой данных (PCG). В данном итерационной процедуре требуется наличие возможности расчета произведения матричных векторов вида , где есть некий произвольный вектор. Симметричная положительно определенная матрица M является предварительным подготовителем для H. Таким образом, , где хорошо обусловленная матрица или матрица с кластеризованными собственными значениями.

Алгоритм

Данный алгоритм PCG нашел применение в тулбоксе Optimization и далее он называется как Алгоритм PCG.
 
% Инициализация

r = -g; p = zeros(n,1); 

% предварительная подготовка
 
z = M\r; inner1 = r'*z; inner2 = 0; d = z;

% Итерация с сопряженными градиентами

for k = 1:kmax
   if k > 1
       beta = inner1/inner2;
       d = z + beta*d;
   end
   w = H*d; denom = d'*w;
   if denom <= 0 
       p = d/norm(d); 

%Направление с отрицательной/нулевой кривизной

break 

% Выход если определена отрицательная/нулевая кривизна

   else
       alpha = inner1/denom;
       p = p + alpha*d;
       r = r - alpha*w;
   end
   z = M\r;
   if norm(z) <= tol 

% Выход если уравнение Hp=-g разрешено в пределах заданной точности

       break
   end
   inner2 = inner1;
   inner1 = r'*z;
end

В контексте процедуры минимизации можно предположить, что матрица Гессе является симметричной. Однако матрица гарантировано является положительно определенной только в окрестности с заметно определенным процессом минимизации. Алгоритм PCG используется тогда, когда обнаруживается направление с отрицательной (или нулевой) кривизной, т.е. . Результирующее направление PCG, p, есть или направление с отрицательной кривизной или является аппроксимационным (параметр tol определяет вид аппроксимации) решением системы Ньютона .

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

Задачи с линейными ограничениями

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

  • Метод проекций используется в случае ограничений типа линейных равенств;

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

Ограничения типа линейных равенств

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

(4-5)

Где матрица размерностью m-х-n (). В тулбоксе Optimization производится предварительная обработка матрицы с целью определения неких определенных линейных зависимостей посредством применения процедуры на основе использования LU факторизации матрицы [6]. Здесь предполагается, что матрица имеет ранг m.

Используемый для решения уравнения 4-5 метод отличается от подхода при наличии ограничений по двум аспектам. Во-первых, начальная допустимая точка рассчитывается путем использования некого шага для разреженного метода наименьших квадратов, так что . Во-вторых, Алгоритм PCG заменяется на метод сопряженных градиентов с приведенной предварительной обработкой данных (RPCG), для примера смотри работу [6], и который используется для расчета аппроксимационного приведенного шага Ньютона (или направления с отрицательной кривизной в нуль пространстве матрицы ). Ключевым моментом в применении линейной алгебры является решение системы уравнений в форме

(4-6)

где является некой аппроксимацией от (небольшие ненулевые значения матрицы устанавливаются в ноль, что обеспечивает сохранение имеющегося ранга) и будет разреженная симметричная положительно определенная аппроксимация матрицы H, т.е., . Детали данной процедуры можно найти в работе [6].

Боксовые ограничения

Задача с боксовыми ограничениями имеет вид

(4-7)

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

Модифицированный шаг Ньютона с учетом масштабных эффектов происходит из рассмотрения условий необходимости Куна-Таккера для уравнения 4-7.

(4-8)

где

и вектор далее определяется для каждого :

Если и , то

Если и , то

Если и , то

Если и , то .

Система нелинейных уравнений 4-8 является всюду не дифференцируемой. Свойство недифференцируемости имеет место при условии . Такие точки можно обойти путем поддержания строгой допустимости, т.е. путем соответствующего ограничения .

Модифицированный шаг Ньютона с учетом масштабных эффектов применительно к уравнению 4-8 определяется как решение следующей системы линейных уравнений

(4-9)

где

(4-10)

и

(4-11)

В данном случае играет роль Якобиана для каждой диагонали для диагональной матрицы равен или 0, или -1, или 1. В случае, если компоненты векторов l и u являются конечными, то . В некой точке, где , величина может быть и не дифференцируемой. В таких точках производится определение . Недифференцируемость данного типа не может быть причиной беспокойства, поскольку для этих компонентов принимаемые значения не являются существенными. Далее хотя и величина в этих точках может быть и прерывистой, но функция является непрерывной.

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

Нелинейный метод наименьших квадратов

Важным специфическим случаем для функции f(x) является нелинейная задача на метод наименьших квадратов

(4-12)

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

(4-13)

(где J есть Якобиан от ) используется для улучшения определения двумерного подпространства. Вторые производные компонент функции не используются.

На каждой итерации данный метод сопряженных градиентов с предварительной подготовкой данных используется для аппроксимационного решения нормализованных решений, т.е.

хотя нормализованные уравнения и не сформированы в явном виде

 

Квадратичное программирование

В данном случае искомая функция f(x) представляет собой квадратичное уравнение

Метод с подпространством доверительных областей используется для направления поиска. Тем не менее, вместо сведения шага поиска до (если это возможно) шага с отражением, как это было в случае нелинейной минимизации, на каждой итерации проводится покусочный линейный поиск с отражением. Детали описания линейного поиска можно найти в работе [5].

Линейный метод наименьших квадратов

В данном случае искомая функция f(x) представляет собой следующий вид

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

хотя нормализованные уравнения в явном виде и не формируются.

<Метод с подпространством доверительных областей используется для направления поиска. Тем не менее, вместо сведения шага поиска до (если это возможно) шага с отражением, как это было в случае квадратичной минимизации, на каждой итерации проводится покусочный линейный поиск с отражением. Детали описания линейного поиска можно найти в работе [5]. В конечном счете, линейные системы представляют собой реализацию метода Ньютона применительно к решению в рамках оптимальности первого порядка, что приводит к определенным строго локальным скоростям сходимости.

Линейное программирование для задач большой размерности

Линейное программирование можно определить следующим образом

(4-14)

Метод для задач большой размерности основе на методике LIPSOL [11], которая является разновидностью преложенного Меротра ([7]) предиктор-корректор алгоритма, а именно метод одновременного решения прямой и двойственной задачи для внутренних точек.

Далее в разделе продолжается обсуждений следующих положений:

  • Основной алгоритм

  • Этапы предварительной обработки данных

Основной алгоритм

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

(4-15)

Верхние границы ограничений в неявном виде входят в матрицу ограничений A. С учетом сложения с простыми фиктивными переменными s уравнения 4-15 примут вид

(4-16)

Что носит название прямой задачи: x состоит из простых переменных и s состоит из простых фиктивных переменных. Под двойственной задачей понимается следующая трактовка

(4-17)

Где y и w состоят из двойственных переменных, а z состоит из двойственных фиктивных переменных. Условие оптимальности для задачи линейного программирования - прямой, согласно уравнениям 4-16, и двойственной, согласно уравнениям 4-17, будет:

(4-18)

Где обозначения и указывают на покомпонентное умножение.

Квадратичные уравнения и называются как взаимодополняемыми условиями для задачи линейного программирования, другие (линейные) уравнения как условия достижимости. Величина

представляет собой двойной интервал, который служит мерой невязки для доли взаимодополняемости величины F при .

Принятый алгоритм является прямодвойственным алгоритмом, что означает, что прямое и двойственное программирования выполняются одновременно. Этот случай можно рассматривать как приложение подобного методу Ньютону подхода к решению линейно-квадратичной системы из уравнения 4-18 при одновременном сохранении положительности для итераций по x, z, w и s, что в свою очередь называется методом внутренних точек. (Данные итерации проводятся непосредственно для внутренней области согласно ограничениям типа неравенств для уравнений 4-16).

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

которое представляет собой направлению Ньютона, далее определяется так называемое поправочное направление

где величина называется центрообразующим параметром и должна выбираться тщательным образом.   есть вектор из нулей и единиц, который соответствует квадратичным уравнениям в F(v), т.е. отклонения относятся только к дополнительным условиям, все которые являются квадратичными, но не к условиям достижимости, все которые в свою очередь являются уже линейными. Эти два направления комбинируются с параметром длины шага и проводится корректировка v с целью образования новой итерации.

где параметр длины шага выбирается таким образом, что бы выполнялось условие

а так же выполнялось условие

При выполнении подготовительных шагов в данном алгоритме проводится расчет прямого разложения (для разреженной матрицы) на поправку коэффициентов Холецкого . Если в матрица A имеются плотно заполненные колонки, то взамен их используется формула Шермана-Моррисона, и если полученное решение не является адекватным (невязка является слишком большой), то для поиска решения используются сопряженные градиенты с предварительной обработкой данных.

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

где

<

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

есть разность между значениями первичной и двойственной целями, а через символ tol обозначена точность. Данная сумма в критерии останова расчета является мерой относительных ошибок в условиях оптимальности согласно уравнению 4-18.

Этапы предварительной обработки данных

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

  • Все переменные ограничены снизу через ноль.

  • Все ограничения имеют форму равенств.

  • Удаляются полученные переменные с равными верхними и нижними границами.

  • Удаляются нулевые строки из матрицы ограничений.

  • Матрица ограничений обладает полностью структуризированным рангом.

  • Удаляются нулевые столбцы из матрицы ограничений.

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

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

Избранная библиография

[1]  Branch, M.A., T.F. Coleman, and Y. Li, "A Subspace, Interior, and Conjugate Gradient Method for Large-Scale Bound-Constrained Minimization Problems," SIAM Journal on Scientific Computing, Vol. 21, Number 1, pp 1-23, 1999.

[2]  Byrd, R.H., R.B. Schnabel, and G.A. Shultz, "Approximate Solution of the Trust Region Problem by Minimization over Two-Dimensional Subspaces," Mathematical Programming, Vol. 40, pp 247-263, 1988.

[3]  Coleman, T.F. and Y. Li, "On the Convergence of Reflective Newton Methods for Large-Scale Nonlinear Minimization Subject to Bounds," Mathematical Programming, Vol. 67, Number 2, pp 189-224, 1994.

[4]  Coleman, T.F. and Y. Li, "An Interior, Trust Region Approach for Nonlinear Minimization Subject to Bounds," SIAM Journal on Optimization, Vol. 6, pp 418-445, 1996.

[5]  Coleman, T.F. and Y. Li, "A Reflective Newton Method for Minimizing a Quadratic Function Subject to Bounds on some of the Variables," SIAM Journal on Optimization, Vol. 6, Number 4, pp 1040-1058, 1996.

[6]  Coleman, T.F. and A. Verma, "A Preconditioned Conjugate Gradient Approach to Linear Equality Constrained Minimization," submitted to Computational Optimization and Applications.

[7]  Mehrotra, S., "On the Implementation of a Primal-Dual Interior Point Method," SIAM Journal on Optimization, Vol. 2, pp 575-601, 1992.

[8]  Moré, J.J. and D.C. Sorensen, "Computing a Trust Region Step," SIAM Journal on Scientific and Statistical Computing, Vol. 3, pp 553-572, 1983.

[9]  Sorensen, D.C., "Minimization of a Large Scale Quadratic Function Subject to an Ellipsoidal Constraint," Department of Computational and Applied Mathematics, Rice University, Technical Report TR94-27, 1994.

[10]  Steihaug, T., "The Conjugate Gradient Method and Trust Regions in Large Scale Optimization," SIAM Journal on Numerical Analysis, Vol. 20, pp 626-637, 1983.

[11]  Zhang, Y., "Solving Large-Scale Linear Programs by Interior-Point Methods Under the MATLAB Environment," Department of Mathematics and Statistics, University of Maryland, Baltimore County, Baltimore, MD, Technical Report TR96-01, July, 1995.

 

Поиск по сайту:

Система Orphus

Яндекс.Метрика