close

Вход

Забыли?

вход по аккаунту

?

Установочные лекции 1 часть

код для вставкиСкачать

Установочные лекции. Часть 1
Тема1. Классификация задач оптимизации: (4ч, СРС 2ч)
Одним из важнейших этапов синтеза любой системы является нахождение ее оптимальных параметров. Обычно исследователь вынужден разрабатывать модель для синтеза системы совместно с алгоритмом оптимизации, иначе задача оптимизации может оказаться неподдающейся решению. В настоящее время арсенал методов оптимизации настолько обширен, а сами алгоритмы в большинстве своем настолько сложны, что приходится тратить немало усилий, чтобы, с одной стороны, найти подходящий алгоритм решения своей оптимизационной задачи, а с другой стороны, грамотно реализовать его на современной ЭВМ. В данном курсе излагаются особенности различных методов оптимизации с целью помочь исследователю выбрать наилучший среди них. Успешному выбору наиболее рационального метода решения конкретной задачи оптимизации в значительной степени может способствовать классификация встречаемых задач оптимизации.
Постановка любой задачи оптимизации предполагает наличие следующих обязательных компонентов:
- математической модели объекта оптимизации;
- области определения или существования модели (другими словами, всех ограничений, которые требуют своего учета); - критерия оптимальности (или целевой функции); - собственно формулировку задачи (что требуется найти и в каком виде).
По характеру объекта оптимизации и соответственно по характеру искомого решения различают статические и динамические задачи оптимизации. К первой группе относятся задачи оптимизации так называемых статических объектов, математические модели которых могут быть представлены в виде некоторой зависимости целевой функции от искомых параметров. Такие задачи обычно называют задачами математического программирования. Вторую группу составляют задачи оптимизации управления объектами, эволюционирующими во времени, т.е. динамическими объектами. Как правило, математические модели таких объектов представляют собой систему дифференциальных уравнений. Условием оптимальности в таких задачах служит некоторый функционал, устанавливающий связь искомого управления (зависящего теперь также от времени) с целевой функцией опосредовано через систему дифференциальных уравнений. В современной теории управления такие задачи принято называть задачами оптимального управления. Следует заметить, что не всегда удается провести четкую грань между статическими и динамическими задачами оптимизации. Так, например, при оптимизации динамического объекта с целью выбора ограниченного количества каких-либо параметров этого объекта естественно задачу оптимизации трактовать как задачу математического программирования, т.е. как статическую.
Статические задачи оптимизации
При синтезе сложных систем, как правило, задачи оптимизации формулируются как задачи математического программирования. Начнем обсуждение именно с этих задач. Сформулируем сначала саму задачу оптимизации. В достаточно общем виде она сводится к определению такого вектора x* из допустимого множества X, который обеспечивает минимум некоторой целевой (критериальной) функции f(x)
Как правило, допустимое множество Х задается совокупностью неравенств (или равенств, или неравенств и равенств одновременно) вида
где g(x) - в общем случае вектор-функция, называемая функцией ограничений.
Одним из основных признаков, который может быть положен в основу классификации задач оптимизации, является тип целевой функции f(x) и функции ограничений g(x). Именно тип функций f(x), g (x) является часто определяющим при выборе соответствующего метода решения задачи оптимизации.
Наиболее распространенными типами как целевой функции f(x), так и функции ограничений g(x) являются следующие: линейная, нелинейная, дифференцируемая, недифференцируемая функции. Что касается функции ограничений, то здесь целесообразным является выделение дополнительных случаев, когда ограничения либо вообще отсутствуют, либо имеют место ограничения на отдельные компоненты вектора вида x j а j (так называемые простые ограничения). В соответствии со сказанным можно выделить, например, такие задачи оптимизации, как задачи оптимизации дифференцируемой целевой функции при отсутствии ограничений (классическая задача оптимизации), дифференцируемой целевой функции при наличии простых ограничений, дифференцируемой целевой функции при наличии линейных ограничений, недифференцируемой целевой функции и т.д.
Тема2. Классификация задач и методов математического программирования. (2ч, СРС 1ч )
Среди огромного многообразия получаемых при этом задач особо выделяют несколько классов задач оптимизации, для каждого из которых развиты свои специальные достаточно эффективные методы решения. Рассмотрим некоторые из них. Классические задачи безусловной оптимизации. В данном случае требуется найти минимум дифференцируемой целевой функции при отсутствии каких-либо ограничений, накладываемых на вектор искомых параметров,
Для классических задач оптимизации характерным является возможность использования при получении решения, с одной стороны, классического аппарата дифференциального исчисления (например, в виде необходимых и достаточных условий оптимальности), а с другой стороны, богатейшего арсенала численных методов безусловной оптимизации, лежащих в основе решения и более сложных задач оптимизации.
Задачи линейного программирования. В этом случае как целевая функция f(х ), так и функция ограничений g(х) являются линейными
где векторы c, b и матрица А считаются заданными. Поэтому задача линейного программирования в общем случае имеет следующий вид:
Обычно среди прочих ограничений принято выделять простые ограничения (на отдельные компоненты вектора х). Так, например, в случае неотрицательности всех компонент вектора х задача принимает более привычную форму
Для решения задач линейного программирования в настоящее время разработаны весьма эффективные численные алгоритмы. В основе их лежит симплекс-метод и его различные модификации.
Задачи квадратичного программирования. В данном случае целевая функция f(х) является квадратичной, а функция ограничений g (х) - линейной. В достаточно общем случае эта задача имеет вид
где матрица Н считается заданной и, как правило, положительно полуопределенной. Именно использование линейности ограничений, с одной стороны, и свойства выпуклости квадратичной целевой функции, с другой стороны, позволяет на основе теории двойственности в данном случае сформировать достаточно эффективные методы решения задач оптимизации такого класса.
Задачи оптимизации с аддитивными целевыми функциями и линейными ограничениями. Аддитивной целевой функцией f(x) принято называть такую функцию многих переменных, которая может быть представлена в виде суммы отдельных функций, каждая из которых является функцией одной переменной,
Типичной постановкой задачи оптимизации рассматриваемого класса является следующая
К задачам этого класса сводятся многие распределительные задачи исследования операций. Они могут быть успешно решены методами последовательной оптимизации, основанными либо на идеях динамического программирования в общем случае, либо на идеях теории двойственности в случае выпуклых (квазивыпуклых) целевых функций.
До сих пор при обсуждении различных задач оптимизации мы предполагали, что целевая функция f(x) и функция ограничений g(x) однозначно определялись в зависимости от вектора параметров х. Однако в действительности, как правило, наряду с вектором интересуемых нас параметров x приходится учитывать целый ряд дополнительных неопределенных (возмущающих, неконтролируемых) факторов, влияющих на обе эти функции. Учитывая это и обозначая вектор возмущающих факторов через , можно записать
f=f(x, ), g=g{x, ).
Задача оптимизации в первоначальном виде с целью достижения минимума функции f (х, ) при условии g (x, )0 теперь становиться некорректной (неопределенной), так как не оговорен способ учета возмущающих факторов при выборе оптимального решения.
В качестве второго признака классификации задач оптимизации выберем способ учета возмущающих (неконтролируемых) факторов. Существуют три таких способа (подхода): детерминированный, стохастический и минимаксный. Аналогично называются и соответствующие задачи оптимизации. При детерминированном подходе возмущающие факторы принимаются просто равными некоторым заранее заданным (из тех или иных соображений) значениям = зад. Тем самым устраняется первоначальная неопределенность, и задача оптимизации становится обычной детерминированной с целевой функцией f(х, = зад) и Функцией ограничений g (х, = зад ). Заметим, что задачи оптимизации при отсутствии возмущений, которые рассматривались ранее, естественно могут трактоваться как частный случай при = 0.
При стохастическом подходе все возмущающие факторы трактуются как случайные ( - случайный вектор) с заданными статистическими характеристиками. Так как в этом случае целевая функция f(x, ) является случайной величиной, то имеющая место неопределенность по отношению к ней может быть устранена путем перехода от первоначальной (первичной) целевой функции f(x, ) к какой-либо ее статистической характеристике, которая теперь будет трактоваться в качестве вторичной целевой функции f(x). В простейшем случае такой характеристикой может быть математическое ожидание
здесь символ М означает операцию статистического осреднения по совокупности всех случайных факторов . При этом, конечно, следует иметь в виду, что использование математического ожидания в качестве целевой (вторичной) функции обеспечит оптимальность искомому решению х* лишь в среднем, по совокупности всех реализации. В отдельных реализациях такое решение может оказаться просто неприемлемым. Учитывая это и стремясь контролировать не только среднее значение целевой (первичной) функции, но и возможные ее отклонения от этого значения, часто рассматривают ее дополнительные статистические характеристики, например дисперсию
вводя последние либо в число дополнительных ограничений, либо в число дополнительных целевых функций. Сказанное в отношении целевой функции может быть полностью отнесено и к каждой из функций ограничений g(x,). Правда, здесь необходимо подчеркнуть, что часть ограничений может и не носить стохастический характер, т.е. быть детерминированными.
Из сказанного следует, что при наличии случайных факторов для исходной постановки задачи (в терминах первичных целевой функции и функции ограничений) можно предположить различные постановки задач оптимизации (в терминах вторичных целевых функций и функции ограничений). Таким образом, постановка окончательной стохастической задачи оптимизации является неформальным актом. В каждом конкретном случае вопрос об окончательном способе учета случайных факторов должен решаться по-своему. В простейшем случае, когда допускается использование в качестве вторичных целевой функции и функции ограничений их математических ожиданий, постановка стохастической задачи оптимизации принимает следующий вид
В данном случае условием х Х подчеркнут лишь факт наличия дополнительного жесткого (детерминированного) ограничения на вектор х.
Нетрудно заметить, что использование отдельных статистических характеристик в окончательной постановке задачи оптимизации не может гарантировать (в вероятностном смысле) приемлемого результата во всех реализациях. Это становится возможным, если в самой постановке стохастической задачи потребовать выполнение всех ограничений, в том числе и непревышение целевой функцией своего наименьшего значения по вероятности. Итак, рассмотрим событие, заключающееся в том, что первичная целевая функция f(x, ) не превысит некоторого своего гарантированного уровня fв и одновременно все ограничения будут выполнены. Потребуем, чтобы вероятность этого события была не менее заданной Р*, т.е.
Очевидно, что для каждого фиксированного х Х можно найти свой (наименьший) уровень f в (x), при котором вероятностное условие будет еще выполнено. Задача оптимизации теперь может быть сформулирована как задача поиска такого вектора х *, который обращает в минимум f в (x),
при условии Таким образом, функция f в (x) в данном случае играет роль вторичной целевой функции. По сути дела, задача сводится к поиску такого вектора параметров х*, который обращает в минимум нижний уровень целевой функции f(x, ) и одновременно гарантирует выполнение всех исходных ограничений с вероятностью Р*.
При минимаксном подходе все возмущающие факторы трактуются как неопределенные, для которых никакой статистической информации нет, а известны лишь пределы их изменений, , где - заданное множество допустимых векторов . Как и при стохастическом подходе, неопределенность первичной целевой функции устраняется путем перехода ко вторичной целевой функции. Однако, в виду того, что о векторе ничего теперь не известно, кроме допустимого множества , то естественно в качестве вторичной целевой функции f м (x) принять наихудшее по всем допустимым неопределенным факторам значение первичной целевой функции, т.е. функцию максимума
Тогда задача поиска оптимального решения x* в простейшем случае принимает вид следующей минимаксной задачи
Если неопределенные факторы содержатся и в функции ограничений g (х,), формирующих допустимое множество для х, то сами ограничения теперь принимают вид
Таким образом, при минимаксном подходе задача оптимизации формулируется как задача поиска такого наилучшего решения, которое гарантирует достижение результата при любых наборах неопределенных факторов из числа допустимых. Поэтому само оптимальное решение в этом случае принято называть гарантирующим, а достигаемый при этом результат, определяемый в свою очередь величиной первичной целевой функции, гарантированным.
Помимо названных возможны и другие признаки классификации оптимизационных задач. Так, по количеству целевых функций различают однокритериальные и многокритериальные задачи оптимизации.
К задачам однокритериальной оптимизации относят такие задачи, в которых целевая функция единственная, т.е. f(x) является скалярной функцией. Все рассмотренные до этого задачи были однокритериальные.
К задачам многокритериальной оптимизации относят задачи, в которых существует несколько целевых функций, или, другими словами, f(x) является вектор-функцией.
По типу искомого решения различают также задачи непрерывного и задачи дискретного (целочисленного) программирования. Задачи целочисленного программирования содержат дополнительные ограничения либо на отдельные переменные, либо на все одновременно в виде условия целочисленности. Для решения этих задач требуются специальные методы. В настоящее время наиболее успешно могут быть решены задачи линейного целочисленного программирования, а также задачи целочисленного программирования с аддитивными целевыми функциями.
Иногда в качестве одного из признаков классификации предлагают использовать размерность задачи, которая оказывает существенное влияние на процесс поиска оптимального решения. Однако применение этого признака является малоконструктивным, так как на его основе практически можно выделить лишь один своеобразный класс задач оптимизации, а именно, задачи одномерной оптимизации, для которых удается создать высокоэффективные алгоритмы поиска. Что касается задач более высокой размерности (начиная с двух), то, как правило, простота (или сложность) решения их зависит не только от размерности задачи, но и от многих других факторов одновременно, к числу которых, как уже указывалось, относятся и свойства целевой функции, и свойства ограничений и многое другое.
Сказанное выше можно наглядно представить в виде следующей схемы Количество критериев
Класс решения
Динамические задачи оптимизации
В отличие от задач математического программирования задачи оптимального управления (динамические задачи оптимизации, вариационные задачи) характеризуются наличием дифференциальных связей. Вместо целевой функции используется функционал. Типичной постановкой вариационных задач является следующая: дана динамическая система
,
где x - вектор состояния, u - вектор управления. На x и u накладываются ограничения x X, uU, t [0,T].
Требуется найти такое управление системой (вектор u), которое обращает в минимум функционал
где F[x(T)] - функционал от конечного состояния.
Помимо рассмотренных ранее признаков классификации теперь появляется еще один - по характеру обратной связи. Различают задачи программирования оптимального управления u(t) и задачи синтеза оптимального управления (ищется оптимальный закон управления u(x,t)). Но это предмет отдельного обсуждения.
Тема 3. Теоретические основы математического программирования (6ч, СРС 2ч )
Некоторые определения
Говорят, что функция f(x), определённая на множестве X, достигает в точке x абсолютного (глобального) минимума, если f(x*) f(x) для любого x X.
Функция f(x) достигает в точке x относительного (локального) минимума, если неравенство f(x*) f(x) имеет место для любого допустимого x из -окрестности точки x*, то есть для x, удовлетворяющего
|x - x*| , x X, > 0.
Определения для абсолютного и относительного максимума аналогичны с той лишь разницей, что в знаке неравенства для максимума будем иметь f(x*) f(x).
Минимум и максимум называются экстремумами. Различают сильный и слабый экстремумы. Если в соответствии с определением неравенство является строгим
f(x*) < f(x) или f(x*) > f(x),
то соответствующий экстремум называют сильным (строгим). В противном случае - слабым (нестрогим).
Если в точке x* функция f(x) имеет минимум, то функция -f(x) в этой же точке имеет максимум. На рис. показаны экстремумы функции f(x).
1 - сильный относительный минимум,
2, 4 - сильные относительные максимумы,
3 - абсолютный минимум,
5 - слабый относительный минимум,
6 - точка перегиба (касательная к функции параллельна оси x).
Необходимые условия оптимальности
Рассмотрим задачу минимизации функции f(x) при условии, что x X ,где X - некоторое допустимое множество. Выясним условия, которым должна удовлетворять f(x) в точке относительного минимума. Будем полагать, что f(x) имеет непрерывные частные производные первого порядка по всем компонентам вектора x. Пусть x* - точка относительного минимума, тогда f(x*) f(x), x X, | x - x*| < . Зададим x в виде
x = x* + r, x X, > 0, где r - допустимое (возможное) направление. По определению .
При 0 получим . Таким образом, для точки x* относительного минимума функции f(x) на множестве X производная по любому допустимому направлению r неотрицательна. Это условие является необходимым условием оптимальности в задаче математического программирования. Точка x*, удовлетворяющая необходимым условиям оптимальности, называется стационарной. Появление этого термина связано с тем, что необходимые условия оптимальности в общем случае лишь выделяют точки, подозреваемые как точки минимума, но не определяют их. Для окончательного решения задачи необходимо воспользоваться дополнительными условиями, например, достаточными условиями оптимальности.
Если f(x) имеет абсолютный минимум в точке x*, то эта функция в этой точке имеет также и относительный минимум. Поэтому, для определения точки, в которой f(x) достигает абсолютного минимума, необходимо вычислить f(x) во всех стационарных точках. Наименьшее из полученных значений и будет абсолютным минимумом.
Достаточные условия оптимальности
Достаточные условия оптимальности в задачах математического программирования тесно связаны с понятием выпуклых множеств и выпуклых функций.
Множество X называется выпуклым, если отрезок, соединяющий две его любые точки, полностью принадлежит этому множеству
x1 X, x2 X , x = x1 + (x2 - x1) X, 0 1.
Функция называется выпуклой на выпуклом множестве X, если для любых точек x1 X, x2 X имеет место следующее неравенство
f(x) = f[ x1 + (x2 - x1)] f(x1) + [f(x2) - f( x1)], 0 1.
Пример выпуклой функции представлен на рисунке. Определение вогнутой (выпуклой вверх) функций аналогично. Достаточно изменить только знак в соответствующем неравенстве на противоположный.
Чтобы точка x*, удовлетворяющая необходимым условиям оптимальности, была точкой минимума на выпуклом множестве, достаточно потребовать выпуклости функции f(x) на множестве X. Действительно, предположим противное. Пусть существует точка x1 X, такая, что f(x1) < f(x*). Тогда в силу выпуклости функции f(x), имеем
f(x) = f[ x1 + (x2 - x1)] f(x1) + [f(x2) - f( x1)], 0 1.
Введем обозначения a = f(x*) - f(x1), r = x1 - x* .
Очевидно, что a>0,а r - допустимое в силу выпуклости множества X направление.
Тогда .
При 0 получим, что противоречит необходимому условию оптимальности. Таким образом, необходимое условие оптимальности в случае выпуклости функции f(x) является и достаточным условием достижения в точке x* минимума. 1.4. КЛАССИЧЕСКИЕ ЗАДАЧИ ОПТИМИЗАЦИИ Необходимые условия оптимальности в задачах на безусловный экстремум
Рассмотрим классическую задачу на безусловный экстремум, а именно задачу минимизации функции f(x), когда на x не накладывается никаких ограничений
Так как в данном случае любое направление r является допустимым, в том числе противоположные, например, r = r1 и r = -r1 одновременно, то необходимое условие оптимальности принимает более простой вид
Ñf(x*) = 0.
Другими словами, градиент функции f(x) в точке минимума при отсутствии ограничений равен нулю. Нетрудно убедиться, что равенство нулю градиента функции f(x) имеет место и в точке относительного максимума.
Достаточные условия оптимальности в задачах на безусловный экстремум
Получим теперь достаточные условия оптимальности в данной задаче, связав понятие выпуклости функции с понятием гессиана. Так как необходимые условия оптимальности в точке x* предполагаются выполнимыми, то описание f(x) в e-окрестности точки x* с помощью ряда Тейлора можно представить в следующем виде .
Отсюда получаем следующие выводы:
1. Чтобы точка x* была точкой слабого минимума, достаточно положительной полуопределённости гессиана Hf(x*), то есть выполнение условия
DxTHf(x*)Dx ³ 0, для любого x ¹ 0.
2. Чтобы точка x* была точкой сильного минимума, достаточно положительной определённости гессиана Hf(x*), т.е.
DxTHf(x*)Dx > 0.
Аналогично можно получить, что в задаче на безусловный максимум функции f(x) достаточное условие слабого (сильного) максимума сводится к требованию отрицательной полуопределённости (определённости) гессиана в подозреваемой точке x*.
Пример. Требуется исследовать на экстремум функцию
f(x) = x12 + x22 + x32 + x1x2 - 2x3 + 2.
В данном случае имеем
,
откуда следует, что гессиан - положительно-определённая матрица, а следовательно точка x* является точкой минимума.
Необходимые условия оптимальности в задачах на условный экстремум
Рассмотрим теперь задача на условный экстремум, состоящую в минимизации функции f(x) при наличии ограничения g(x) = 0
Здесь g - вектор-функция размерности m, x - вектор размерности n, (n > m). Получим сначала необходимые условия оптимальности для частного случая, рассматривая задачу с двумя переменными и одним ограничением:
Пусть условный экстремум достигается в точке x*(x1*, x2*). Предположим, что в этой точке существуют частные производные первого порядка для функций f(x) и g(x). Тогда в e-окрестности ограничение может быть заменено его линейным приближением:
.
Полагая, что одна из производных не равна нулю, получим:
где .
Тогда целевую функцию f(x1, x2) можно представить в виде сложной функции f[x1(x2), x2] одного аргумента, который необходимо минимизировать по x2 без учёта ограничения. Таким образом, задача на условный экстремум функции двух переменных свелась к задаче на безусловный экстремум. Необходимые условия оптимальности при этом примут вид:
.
Учитывая, что в данном случае имеет место соотношение
,
получим
.
Введём обозначение: . Тогда условия оптимальности можно представить в виде ,
где одно из условий определяет собстенно l*. Таким образом, если точка (x1*, x2*) является точкой условного экстремума, то она должна удовлетворять соотношениям g(x1*, x2*) = 0.
Полученные необходимые условия экстремума могут быть записаны более компактно, если ввести в рассмотрение, так называемую, функцию Лагранжа
F(x1 x2, l) = f(x1, x2) + lg(x1, x2),
где l - множитель Лагранжа.
Рассмотрим частные производные функции Лагранжа по x1, x2 и l, ;
;
.
Нетрудно убедиться, что необходимые условия оптимальности могут быть представлены в следующем виде
,
или в векторном виде:
.
Точку x*, удовлетворяющую необходимым условиям оптимальности, будем по-прежнему называть стационарной точкой.
Рассмотрим геометрическую интерпретацию задачи на условный экстремум для функции двух переменных x1 и x2. На рисунке представлены линии уровня f(x)=C, причем
C1 < C2 < C3 < C4
Из рисунка видно, что точки касания кривой g(x1, x2) с линиями уровня, а именно точки 1, 2, 3, 4 являются стационарными, то есть удовлетворяют необходимым условиям оптимальности. В точке 1 функция достигает относительного минимума; точка 2 является точкой относительного максимума; точка 4 точкой абсолютного минимума; точка 3 не является ни минимумом, ни максимумом. Для отыскания точки абсолютного условного минимума, необходимо вычислить значения функции во всех стационарных точках и выбрать наименьшее из них.
Рассмотрим теперь задачу в общем случае n переменных и m ограничений, полагая n > m.
Здесь x - вектор размерности (n ´ 1), g - вектор-функция размерности (m ´ 1). Пусть условный экстремум достигается в точке x*, а функции f(x) и g(x) в точке x* имеют частные производные первого порядка. В e-окрестности точки x* ограничение может быть заменено его первым приближением
,
Здесь - якобиан функции g(x) в точке x*, матрица размерности n ´ m. Представим вектор x и матрицу в блочном виде
x1 - вектор размерности m ´ 1, x2 - вектор размерности (n- т) ´ 1,
- якобиан функции g по x1, квадратная матрица (m ´ m); ,- якобиан функции g по x2, матрица (n-m) ´ m.
Перепишем выражение для ограничения в следующем виде
.
Полагая, что - неособенная матрица, получим выражение для x1
.
Подставляя x1 в выражение для целевой функции, мы сводим задачу на условный экстремум функции n переменных по вектору x к задаче на безусловный экстремум функции f[x1(x2),x2] n-m переменных по вектору x2.
Воспользуемся необходимым условием оптимальности
.
Матрицу определим, дифференцируя выражение для .
Учитывая это, необходимое условие оптимальности примет вид
.
Введём в рассмотрение вектор l размерности m
,
l* - вектор множителей Лагранжа. Можно считать, что вектор l* определяется как решение уравнения
.
Само условие оптимальности при этом примет вид
.
Последние два соотношения можно объединить в одно
.
Именно оно совместно с условием g(x) = 0 и представляет собой необходимое условие оптимальности в задаче на условный экстремум.
Аналогично двумерному случаю введем в рассмотрение функцию Лагранжа следующего вида
.
Так как имеют место соотношения ,
то формально необходимые условия оптимальности могут быть представлены в следующей компактной форме
или в развернутом виде
,
.
Достаточные условия оптимальности в задаче на условный экстремум
В теории оптимального управления важное место занимают, так называемые, прямая и двойственная задачи.
Прямой задачей принято называть минимаксную задачу по отношению к функции Лагранжа следующего вида
.
Введём обозначение Тогда решение прямой задачи сводится нахождению .
или .
Нетрудно убедиться, что решение прямой задачи совпадает с решением исходной задачи на условный экстремум по минимизации функции f(x) при условии g(x)=0. Действительно,
.
Поэтому Двойственной задачей будем называть максиминную задачу по отношению к функции Лагранжа, которая имеет вид
.
Введём обозначения .
Тогда решение двойственной задачи сводится к нахождению
: .
Если сравнивать прямую и двойственную задачи, то можно отметить, что решение двойственной задачи может быть получено более простыми методами, так как при этом фактически следует решить две задачи на безусловный экстремум. Прямая же задача сводится к задаче на условный экстремум.
Двойственная задача имеет большое значение, так как во многих случаях её решение совпадает с решением прямой задачи. В частности это имеет место в случае, когда F(x,l) имеет единственный минимум по x при любом l. Действительно, предположим, что функция Лагранжа F(x,l) имеет единственный для любого l безусловный относительный минимум по x, тогда необходимым условием такого безусловного относительного минимума является условие:
. Обозначим решение этого уравнения через . Другими словами,
.
Если l =l* - множитель Лагранжа, который соответствует задаче на условный экстремум, то , и получаем
Для произвольного l
.
Поэтому ,
что означает или .
Таким образом, решение задачи на условный экстремум функции f(x) при ограничении g(x) = 0 свелось к решению задачи на максимин функции Лагранжа.
В этом случае ,
или в развёрнутом виде:
.
Это равенство эквивалентно следующему условию
.
Точка (x*,l*), удовлетворяющая последнему условию, называется седловой точкой функции Лагранжа.
Наличие седловой точки является достаточным условием оптимальности в задаче на условный экстремум функции f(x) при ограничении g(x) = 0. Покажем это. Пусть (x*,l*) - седловая точка функции Лагранжа F(x*,l*). Тогда для любого l
Отсюда следует .
Для любых l это будет выполняться, только тогда, когда .
С другой стороны, для любого x
.
И если g(x) = 0, то f(x*) £ f(x). Следовательно точка x* является решением задачи на условный экстремум.
Пример. Исследовать функцию f(x) = x12 + x12 на экстремум при условиях x1 + x2 =1. Составим функцию Лагранжа
.
Из необходимых условий оптимальности следует
; .
Обратимся к достаточным условиям оптимальности, исследуем F(x, l) на безусловный экстремум по x для любого l. Необходимое условие оптимальности примет вид
.
Запишем достаточное условие оптимальности
.
В точке функция Лагранжа имеет единственный минимум при любом l, так как Hf положительно определены. Это означает, что функция Лагранжа F(x, l) имеет седловую точку типа (1.31). В соответствии с достаточными условиями оптимаьлности точка является точкой минимума в задаче на условный экстремум. К решению задачи можно подойти иначе. Если допустить заранее наличие седловой точки функции Лагранжа, то можно сразу перейти к решению двойственной задачи
.
На первом этапе нужно найти безусловный минимум функции Лагранжа по x
;
.
На втором этапе двойственной задачи необходимо найти безусловный максимум функции h(l) по l
.
Из необходимых условий оптимальности получим
.
На основе достаточных условий оптимальности устанавливаем, что точка l* = 1 является точкой максимума. Таким образом, решение двойственной задачи имеет вид
.
И оно совпадает с решением прямой (исходной) задачи.
Направление наибольшего убывания функции
Рассмотрим задачу определения направления наибольшего убывания функции f(x) в заданной точке x. В данном случае целевой функцией является производная по направлению
.
Необходимо найти такой вектор r* , который обращает целевую функцию в минимум.
Для решения задачи можно применить два похода: первый основан на использовании необходимых условий оптимальности с последующей проверкой достаточных условий оптимальности. Второй подход базируется на сведении прямой задачи к двойственной и решением последней.
Функция Лагранжа в данном случае имеет вид
.
Рассмотрим сначала первый подход. Согласно необходимым условиям оптимальности вектор r* должен быть решением следующей системы уравнений
,
.
Отсюда находим ,
.
Чтобы ответить на вопрос, достигает ли целевая функция в стационарной точке минимума или максимума, исследуем функцию Лагранжа на безусловный экстремум. Из необходимых условий оптимальности получаем Так как гессиан
является положительно-определённым при l > 0, а при l < 0 отрицательно-определённым, то при l > 0 функция Лагранжа имеет по r единственный минимум, а при l < 0 - единственный максимум. Таким образом, при l > 0 функция Лагранжа имеет седловую точку вида
,
и в соответствии с достаточными условиями оптимальности определяет направление наибольшего убывания функции f(x) в точке x. Аналогично показывается, что направление наибольшего возрастания функции совпадает с направлением ее градиента.
При втором подходе сразу рассматривается двойственная задача. Так как функция Лагранжа при l > 0 имеет по r единственный минимум, то решение двойственной задачи совпадает с решением прямой (исходной) задачи.
При l > 0 двойственная задача сводится к следующей
.
Так как из условия минимума F по r, получаем
,
то подставляя последнее в выражение для функции Лагранжа, находим
.
Из необходимых условий оптимальности для h получаем
.
Отсюда находим стационарную точку
.
На основе достаточных условий оптимальности для h
,
получаем, что h(l) в точке l* достигает своего максимума. Отсюда получаем
.
Полученное значение r* и определяет направление наибольшего убывания функции f(x) в точке x.
Для направления наибольшего возрастания двойственная задача сводится к следующей
.
Минимум функции h(x) достигается в точке определяет направление наибольшего возрастания функции f(x).
Интерпретация множителей Лагранжа
Пусть скалярная функция z =f(x) в точке x* достигает условного экстремума при ограничении g(x) = b, b - вектор. Пусть l* - множитель Лагранжа, соответствующий значению x*. Очевидно, что x*,l* зависят от вектора параметров b. Предположим, что x*,l* являются непрерывными дифференцируемыми функциями по b. Вычислим градиент функции z* = f(x*)=f[x*(b)] по вектору b:
.
Продифференцируем векторную функцию g[x*(b)] по вектору b.
,
где .
Умножим это выражение на l* и сложим с выражением для градиента
.
В силу необходимых условий оптимальности имеем:
,
отсюда
. Таким образом, антиградиент экстремума целевой функции по вектору b равен вектору множителей Лагранжа l*, вычисленному при заданном b.
Если под z понимать стоимость, а под b - затраты некоторых ресурсов, то li* характеризует скорость изменения минимальной стоимости z при изменении i-го вида ресурсов.
Условия оптимальности Куна и Таккера
Рассмотрим некоторое обобщение классических условий оптимальности на случай задачи нелинейного программирования, в которой имеют место ограничения типа неравенств. Итак, рассмотрим задачу минимизации функции f(x) при условиях .
Покажем, что необходимые условия оптимальности и в этом случае могут быть сформированы с помощью функции и множителей Лагранжа. С этой целью введём дополнительные переменные
.
Тогда исходная задача формально принимает вид задачи на условный экстремум при условиях неотрицательности дополнительных компонент
.
Введем в рассмотрение два множества .
Рассмотрим функцию Лагранжа следующего вида
.
Тогда необходимое условие для искомого оптимального вектора x* имеют вид
Согласно интерпретации множителей Лагранжа
.
Так как по определению оптимальности ,
получаем
для для .
Введём в рассмотрение функцию Лагранжа в привычном для классических задач виде
.
Учитывая, что , необходимые условия оптимальности для рассматриваемой задачи представим в виде
(случай )
(случай ).
Полученные условия оптимальности называются условиями Куна-Таккера. Смысл этих условий заключается в том, что для оптимального решения рассматриваемой задачи существуют такие множители Лагранжа li*, которые удовлетворяют соотношениям
,
или в развёрнутом виде
.
Можно показать, что если целевая функция и множество допустимых значений X выпуклы, то выполнение необходимых условий оптимальности является достаточным, следовательно, условия Куна-Таккера являются необходимыми и достаточными в случае выпуклости функции f(x) при ограничении g(x).
В задаче минимизации функции f(x) при ограничении gi(x) £ 0, xi ³ 0, необходимые условия оптимальности принимают вид
.
Тема 4. Линейное программирование (6ч, СРС 3ч )
Постановка задачи Обсуждение методов решения задач при наличии ограничений целесообразно начать с простейшей задачи этого класса, а именно, с задачи линейного программирования.
В общем случае задача линейного программирования заключается в минимизации (максимизации) линейной целевой функции при наличии линейных ограничениях. Не нарушая общности, постановку задачи линейного программирования можно представить в так называемой канонической форме:
Важным свойством задач линейного программирования является выпуклость целевой функции и допустимого множества. Поэтому, если задача линейного программирования не вырождена, то для ее решения достаточно применить необходимые условия оптимальности.
Пример задачи линейного программирования Рассмотрим задачу об использовании сырья. Пусть для изготовления продукции вида П1, П2, П3, ..., Пp используется сырьё вида S1, S2, S3, ...,Sm. Запасы каждого вида сырья ограничены и составляют b1, b2, b3, ...,bm условных единиц. Пусть aij означает количество единиц сырья Si, необходимое для изготовления единицы продукции вида Pj, и пусть Cj означает доход от сбыта единицы продукции Пj. Все исходные данные могут быть сведены в следующую таблицу.
Требуется составить такой план выпуска продукции П1, П2, ..., Пp, при котором доход в результате сбыта всей этой продукции будет наибольшим.
Пусть xj - количество единиц продукции Пj, тогда доход от сбыта всей продукции будет равен
Так как имеется всего bi сырья вида Пi, то должны выполняться следующие неравенства:
.
Кроме того Таким образом, мы получили типичную задачу линейного программирования. Среди неотрицательных решений необходимо выбрать такое, которое обращает целевую функцию z(x) в максимум.
Зададимся численными значениями: p = 2, m = 4.
В соответствии с приведенными исходными данными ограничения задачи имеют вид
Целевую функцию можно представить в виде
или Рис.0.1Геометрическая интерпретация задачиГеометрически задача может быть сформулирована следующим образом (см.рис. 3.1): среди точек, принадлежащих заштрихованному многограннику найти такую, для которой функция f(x) принимает минимальное значение. Из этого рисунка видно, что решением задачи является вершина многогранника с координатами x1 = 5, x2 = 3, при этом целевая функция достигает своего минимума f = -50.
Решим теперь задачу аналитически. Для этого проделаем следующие операции.
1. Сведём задачу к канонической форме. Для этого введём дополнительные переменные, с использованием которых ограничения задачи и сама целевая функция примут следующий вид
x1 0, x2 0, x3 0, x4 0, x5 0, x6 0 f = -7x1 - 5x2 Особенность канонического вида задачи состоит в том, что все ограничения типа неравенств представлены в виде условий неотрицательности отдельных или всех компонентов. Наряду с этим в задаче присутствуют ограничения типа равенств. Ввиду того, что количество этих равенств меньше числа переменных, образованную систему уравнений можно решить относительно части переменных. Число этих решений должно равняться числу уравнений. Такое решение при нулевых значениях оставшихся переменных принято называть базисными. Нас будут интересовать только допустимые базисные решения, то есть решения из неотрицательных значений переменных.
2. Выберем начальное допустимое базисное решение. Для этого
а) Разобьем все переменные на две группы: первая - основные (базисные) x3, x4, x5, x6; вторая - неосновные (свободные) x1, x2. К базисным отнесём ровно столько компонент, сколько равенств в задаче.
б) Выразим базисные переменные и целевую функцию через свободные переменные. При данном выборе базисных и свободных переменных этого делать не требуется.
в) Полагая свободные переменные равными нулю x1 = 0, x2 = 0, найдём допустимое базисное решение: x3 = 19, x4 = 13, x5 = 15, x6 = 18 и соответствующее значение целевой функции f= 0.
3. Перейдём к новому допустимому базисному решению с меньшим значением целевой функции (первая итерация). Для этого
а) Выберем такую свободную переменную (например, x1), за счёт увеличения которой можно уменьшить целевую функцию.
б) Определим максимально возможное значение выбранной компоненты x1, при котором все переменные будут удовлетворять условиям неотрицательности. Таким значением будет x1 = 6, при этом x6 = 0. в) Выберем новые базисные переменные x3, x4, x5, x1, в качестве свободных принимаются x2, x6.
г) Выразим базисные переменные и целевую функцию через новые свободные переменные д) Опять, полагая свободные переменные равными нулю x6 = 0, x2 = 0, найдём допустимое базисное решение: x3 = 7, x4 = 1, x5 = 13, x1 = 6. Получим значение целевой функции f = -42.
4. Перейдём к новому допустимому базисному решению с меньшим значением целевой функции (вторая итерация). Вся последовательность действий повторяется: а) Выберем свободную переменную x2, за счёт увеличения которой можно уменьшить целевую функцию.
б) Определим максимально допустимое значение этой переменной x2 = 1, при этом x4 = 0.
в) Сформируем новые базисные переменные x3, x5, x1, x2 и новые свободные переменные x6, x4,. г) Выразим новые базисные переменные и целевую функцию через новые свободные переменные
д) Полагая новые базисные переменные равными нулю, получаем новые решения x4 = x6 = 0, x3 = 4, x5 = 12, x1 = 6, x2 = 1, f = -42.
5. Третья итерация:
а) Функция f может быть увеличена за счёт x6.
б) Предельное значение этой переменной x6 = 3 при x3 = 0.
в) Новые базисные переменные x6, x5, x1, x2, новые свободные x3, x4,. г) Выразим новые базисные переменные и целевую функцию через новые свободные переменные
д) Полагая свободные переменные равными нулю x3 = x4 = 0, найдём допустимое базисное решение
x5 = 6, x6 = 3, x1 = 5, x2 = 3 и значение целевой функции f = -50.
Из последнего выражения для целевой функции заключаем, что дальнейшее уменьшение её невозможно, так как обе свободные переменные входят в это выражение с положительными коэффициентами. Поэтому полученное базисное решение является искомым оптимальным. Симплекс-метод
Приведенный аналитический метод решения задачи линейного программирования и заключающий в переходе от одного базисного решения к другому с уменьшением целевой функции представляет собой по существу симплекс-метод, который имеет широкое применение при решении любых задач линейного программирования. Обсудим этот метод в общем виде. Рассмотрим общую задачу линейного программирования в канонической форме, которая состоит в минимизации целевой функции f(x) = cTx при ограничении Ax = b, x 0. Будем считать, что векторы х и b имеют размерности п и т соответственно, п > т, b > 0. Матрицу А( mn ) обычно называют матрицей условий. Сущность симплекс-метода сводится к следующему.
Разделим все компоненты вектора на две группы: базисные и свободные, обозначая их соответственно через xB и xR. Не нарушая общности, можно считать, что базисными компонентами являются первые т компонент вектора x, а свободными - оставшиеся (m - n) компонент. Тогда вектор x можно записать в следующем виде: xT = (xBT,xRT). Аналогично разобьём матрицу условий A и вектор c на следующие блоки
.
B - матрица размера m m, R - матрица размера (m (n - m)), cB - вектор размерности (m 1), cR - вектор размерности ((n - m) 1).
Выразим базисный вектор xB и целевую функцию f через свободный вектор xR
Вводя обозначения получим
Здесь и далее предполагается, что матрица B неособенная. Аналогично получим выражение для целевой функции
f = cBTxB + cRTxR = cBT( + xR) + cRTxR = 0 - TxR;
где 0 = cBT = cBTB-1b; T = - cRT + cBTB-1R.
Полагая xR = 0, получаем опорное базисное решение x = , xR = 0, при этом f = 0. Соотношения для xB и f в скалярной форме могут быть записаны следующим образом:
По полученным соотношениям можно составить таблицу 3.3, называемую симплекс-таблицей.
Тема 5. Целочисленное программирование (4ч, СРС 2ч )
В задачах целочисленного программирования область допустимых решений является невыпуклой и несвязанной. Это существенно затрудняет получение их решения привычными (непрерывными) методами с последующим округлением найденного решения. Необходимы специальные методы. Такими методами являются методы отсечения (или отсекающих плоскостей), ветвей и границ, последовательного анализа вариантов, а также различные приближенные методы.
4.1. Метод ветвей и границ
Метод ветвей и границ относится к группе комбинаторных методов дискретного (целочисленного) программирования, является достаточно общим и позволяет решать как линейные, так и нелинейные задачи дискретного программирования, представляющие собой обобщение целочисленных задач. Сущность метода поясним сначала на задаче общего вида. Пусть требуется найти minf(x) при условии хX, где Х - конечное множество.
В основе метода ветвей и границ лежит разбиение по определенному правилу множества Х на подмножества Хi (ветвление) так, чтобы X=UXi , и определение нижних оценок (границ) ( Хi ) целевой функции f(x) на этих подмножествах, удовлетворяющих условию ( Хi )f(X) для всех х Хi . Если при этом окажется, что для некоторого вектора х* Х будут иметь место условия f(x*)=( Х ) ( Хi ) для всех i, то в силу определения оценок х* - оптимальное решение исходной задачи.
Алгоритм решения задачи сводится к следующему:
1. Определяется оценка ( Х0 ) = ( Х ). Если удается найти такое Х*Х, что f(x*)=(Х0 ), то х* - оптимальное решение.
В противном случае множество Х0 разбивается на конечное число непересекающихся подмножеств Хi1, Х0 =U Хi1.
2. Вычисляются оценки ( Хi1). Если удается найти такое х* Х1, что f(x*)=( Х1) ( Хi1 ) для всех i, то х* - оптимальное решение задачи. В противном случае наиболее перспективное множество Х1 , удовлетворяющее условию ( Х1)=min( Хi1), разбивается в свою очередь на несколько подмножеств. Образовавшиеся при этом подмножества вместе с не подвергавшимися разбиению подмножествами обозначают через Хi2, Х0=U Хi2 . Далее процесс повторяется.
Основная трудность в реализации метода ветвей и границ состоит в разработке конкретных правил ветвления и способов эффективного вычисления оценок.
Рассмотрим возможность применения метода ветвей и границ для решения задачи целочисленного линейного программирования:
Как и в методах отсечения, рассмотрим сначала задачу без учета условия целочисленности Если полученное при этом оптимальное решение х0 оказывается целочисленным, то оно является искомым решением. В противном случае х0 дает нижнюю оценку для искомого решения ( Х0)= сT x0 . Пусть в этом решении некоторая компонента хi оказалась нецелочисленной. Разобьем множество Х на два подмножества:
Оценки ( Х11), ( Х21) можно снова найти в результате решения соответствующих нецелочисленных задач линейного программирования:
Если при этом окажется, что одно из полученных решений х' целочисленно и соответствует минимальной оценке из ( Х11), ( Х21), то х' - искомое решение. В противном случае выбирается наиболее перспективное подмножество из Х11, Х21 и производится дальнейшее его ветвление. Нетрудно заметить, что применение метода ветвей и границ к задачам целочисленного линейного программирования сводится к решению ряда нецелочисленных задач линейного программирования на соответствующих подмножествах Хнц1 "исходного" нецелочисленного множества Хнц1 .
Из описания алгоритма следует, что применение метода ветвей и границ одинаково справедливо как для полностью целочисленных, так и для частично целочисленных задач.
Вводимые на каждой итерации новые ограничения вида xi [ xi0 ] или xi [ xi0 ]+1 играют, по сути дела, роль отсечений. Как и в методах отсечения, при вводе нового ограничения нет необходимости решать задачу линейного программирования заново. Достаточно ее расширить в соответствии с вводимым ограничением.
5. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
Динамическое программирование - это достаточно общий вычислительный метод решения задач математического программирования. Метод основан на использовании приема поэтапной оптимизации, который состоит в сведении задачи минимизации функции многих переменных к последовательному (поэтапному) решению задач минимизации функции лишь одной переменной согласно схеме
Реализация метода в общем случае связана с огромными вычислительными трудностями, состоящими в необходимости запоминания на каждом этапе функции многих переменных. Именно это обстоятельство затрудняет применение метода в явном виде для задач с размерностью выше трех. Однако при определенной структуре целевой функции и ограничений эти трудности устраняются, и мы получаем эффективный метод решения целочисленных задач математического программирования. Сказанное относится, в частности, к задачам с аддитивными целевыми функциями, когда и линейными ограничениями. Поясним сущность метода динамического программирования на примере следующей целочисленной задачи математического программирования: при условиях все компоненты хj - неотрицательные целые числа. Будем считать, что все - также целые числа.
В соответствии с приемом поэтапной оптимизации имеем
где введены обозначения: [ ba1 ] - целая часть отношения b/a1;
Совершенно аналогично получаем, что
По индукции можно записать следующее соотношение:
где Это соотношение принято называть основным рекуррентным соотношением метода динамического программирования. Функцию Rk (k ), равную по ее определению выражению
обычно называют функцией Беллмана. При k=1 и k = b она совпадает с минимальным значением исходной целевой функции и поэтому дает решение задачи. При k=n имеем граничное условие
Основное рекуррентное соотношение совместно с граничным условием и является алгоритмической основой метода динамического программирования для решения задачи. Для получения решения необходимо:
1) в соответствии с основным рекуррентным соотношением метода определить последовательно, начиная k=n и до k=1, значения зависимости Rk (k ) для всех допустимых k =0,1,...,b и соответствующие значения обеспечивающие минимум в правой части;
2) последовательно, начиная с k=1 и до k=n, найти оптимальные значения k* и соответствующие значения хk* .
Так как на каждом этапе оптимизации необходимо запоминать лишь функции Rk(k) и Rk+1(k+1) каждая из которых зависит лишь от одной переменной, реализация метода с помощью ЭВМ не вызывает затруднений. Таким образом, метод динамического программирования представляет собой направленный последовательный перебор вариантов, обязательно приводящий к глобальному минимуму. Нетрудно заметить, что условие целочйсленности не является обязательным для применения метода.
При применении метода, динамического программирования задача фактически интерпретируется как некоторый n-шаговый марковский процесс принятия решения, текущее состояние которого характеризуется параметром k.
Марковское свойство процесса заключается в том, что управление им не зависит от предыстории процесса, а определяется только текущим состоянием k и управлением хk . Отмеченное обстоятельство имеет большое значение, так как именно возможность интерпретации задачи как n-шаговой марковской и является необходимый условием возможности применения метода динамического программирования.
Тема 6. Нелинейное программирование. Методы безусловной оптимизации (6ч, СРС 3ч)
Анализ возможных численных методов оптимизации целесообразно начать с методов, предназначенных для решения однокритериальных детерминированных задач оптимизации при отсутствии ограничений. Такие задачи часто называют задачами безусловной оптимизации. Следует сразу подчеркнуть, что владение этими методами имеет принципиальное значение, ибо методы решения более сложных задач при наличии ограничений в большинстве случаев либо базируются на этих методах, либо практически сводятся к ним с использованием специальных приемов. Прежде всего отметим, что сущность всех численных методов оптимизации состоит в построении такой последовательности векторов {хk }, k = l, 2,..., которая, по крайней мере, удовлетворяет условию
Все методы могут быть разделены на классы в зависимости от максимального порядка производных минимизируемой функции, вычисление которых предполагается в процессе поиска. Так, методы, использующие только значения самой функции, называют методами нулевого порядка. Если, кроме того, в процессе поиска требуется вычисление первых производных, то мы имеем дело с методами первого порядка. Методы второго порядка требуют для своей реализации дополнительно вычисление вторых производных.
2.1. ГРАДИЕНТНЫЕ МЕТОДЫ
С методической точки зрения анализ методов целесообразно начать с методов первого порядка. Основу этих методов составляют, так называемые, градиентные методы, сущность, которых заключается в том, что каждое новое приближение хk+1 к минимуму функции f(x) формируется на основе текущего приближения х по схеме
где через h k обозначена величина шага поиска в направлении антиградиента - f(xk) на k-й итерации. По существу, данная схема основана на линейной аппроксимации функции f(x) в окрестности точки xk. Обоснованием схемы может служить тот факт, что направление антиградиента - f(xk) в точке xk определяет (задает) локально наилучшее направление спуска, так как оно совпадает с направлением наискорейшего уменьшения минимизируемой функции f(x).
В зависимости от способа задания шага поиска различают различные градиентные методы: градиентный спуск, предполагающий задание шага поиска hk на каждой итерации достаточно малым; простой градиентный метод с использованием постоянного "большого" шага поиска; градиентный метод с переменным шагом поиска; метод наискорейшего спуска, предполагающий использование на каждой итерации оптимального шага поиска.
Метод градиентного спуска
Как и в любом градиентном методе на каждой итерации при переходе от точки xk к новой точке xk+1 используется направление спуска, определяемое антиградиентом (см. рис.2.1). Рис.0.1Траектория градиентного спуска
Если предположить, что шаг поиска бесконечно мал, то траектория поиска описывается дифференциальным уравнением
Очевидно, что траектория градиентного спуска ортогональна всем линиям уровня минимизируемой функции, задаваемым уравнениями f(x)=const. Поэтому метод градиентного спуска является локально-оптимальным: в любой точке траектории спуска используется наилучшее направление спуска. Реализовать такую траекторию можно лишь приближённо, полагая шаг поиска малым, но конечным. Недостатком метода является большое количество итераций, необходимых для практической реализации метода, что, как правило, приводит к неприемлемым затратам машинного времени.
Градиентный метод с переменным шагом
Стремление устранить указанный недостаток приводит нас к простому градиентному методу с "большим" шагом поиска на каждой итерации. Под "большим" шагом здесь условно понимается такой шаг поиска hk , который, по крайней мере, существенно превышает шаг поиска в методе градиентного спуска. Наиболее просто метод выглядит при постоянном шаге hk = const. Так как использование постоянного шага может привести на отдельных итерациях поиска к увеличению значения минимизируемой функции f(x), т.е. невыполнению условия f(xk+1) < f(xk), то обычно используют градиентный метод с переменным шагом, осуществляя дробление шага поиска.
В основе лежит стремление использовать постоянным достаточно большой (по сравнению с градиентным методом) шаг итераций. Поэтому предлагается следующая процедура: выбирается некоторая величина h и на каждой k-й итерации, полагая hk = h, проверяется условие f(xk+1) f(xk). Если это условие выполняется, то полагается hk = h и осуществляется переход к следующей точке xk. Если условие не выполняется, то шаг дробится до тех пор, пока условие не будет выполнено. Здесь следует заметить, что условие f(xk+1) < f(xk) в общем случае не гарантирует сходимости метода. Для обеспечения сходимости необходимо выполнение более сильных условий, например неравенства:
f(xk - hkf(xk)) - f(xk) - hk/f(xk)/, где (0,1).
F(xk - hkf(xk)) = f(xk) -f(xk)Thkf(xk).
Градиентные методы с переменным шагом поиска являются более экономными как по количеству итерации, так и по затратам машинного времени.
Метод наискорейшего спуска Данный метод также относится к числу методов с переменным шагом. Однако теперь шаг поиска hk определяется наилучшим образом на каждой итерации из условия обращения в минимум функции f(x) в направлении антиградиента (рис.2.2)
Рис.0.2Траектория наискорейшего спуска
Таким образом, реализация метода предполагает на каждой итерации решение вспомогательной задачи одномерной минимизации. Несмотря на это, как правило, метод наискорейшего спуска дает выигрыш по числу машинных операций, а следовательно, и по затратам машинного времени. При практической реализации схемы градиентных методов, для всех компонент вектора градиента должно выполняться условие:
- некоторое заданное число, характеризующее точность нахождения минимума. Основной недостаток градиентных методов состоит в их слабой скорости сходимости к искомому минимуму при появлении так называемого "эффекта овражности". Этот эффект проявляется в том, что линии уровня минимизируемой функции f(x) часто оказываются сильно вытянутыми, что в свою очередь объясняется резким возрастанием функции f(x) по одним направлениям и слабым изменением по другим. Эффект хорошо интерпретируется геометрически и означает, что топография поверхностей уровня целевой функции f(x) = const имеет овражную структуру (см. рис.2.3).
Рис.0.3Иллюстрация "овражного" эффекта при использовании градиентных методов поиска
Траектория градиентных методов в таких случаях характеризуется достаточно быстрым перемещением ко "дну" оврага и затем медленным зигзагообразным движением вдоль него к точке минимума. Это связано по существу с использованием линейной аппроксимации минимизируемой функции f(х) на каждой итерации. Если же эта функция дважды дифференцируема, то для улучшения процесса поиска можно попытаться использовать ее квадратичную аппроксимацию в окрестности точки х которая учитывает кривизну функции f (х). Но об этом пойдет речь дальше при обсуждении методов второго порядка.
Другим выходом в сложившейся ситуации является изменение масштаба независимых переменных, например, по формулам
Такая замена переменных во многих случаях позволяет исправить топографию функции f(x), уменьшить вытянутость линий уровня, иногда приблизив их к сферам. В общем случае масштабирование переменных приводит к итерационному процессу следующего вида
Bk - некоторая матрица, зависящая от номера итерации.
При Bk = I (I - единичная матрица) имеем обычную схему градиентных методов. Методы, использующие данную схему, иногда называют релаксационными.
Существуют и другие способы преодоления овражных эффектов. Один из них - эвристический, предложенный Гольфандом, состоит в следующем (см. рис.2.4).
Первоначально из двух близлежащих точек с помощью одного из градиентных методов осуществляется спуск на дно оврага. Получаем две точки . В направлении этих точек, определяющих дно оврага, можно сделать достаточно большой (рабочий) шаг поиска, по крайней мере, по сравнению с шагом градиентного поиска. Рис.0.4Схема реализации овражного метода Получим новую точку В окрестности полученной точки выбираем точку и процедуру повторяем. 2.2. МЕТОДЫ ВТОРОГО ПОРЯДКА
Метод Ньютона и его модификации
Основой методов второго порядка является метод Ньютона, сущность которого состоит в отыскании на каждой итерации минимума квадратичной аппроксимации fk(х). Это решение и предполагается принять в качестве нового приближения хk+1
Если предположить, что гессиан функции f(x) в точке xk, т.е. матрица 2 f(xk), является положительно определенной, то указанное решение будет единственным, имеющим вид
Из сказанного ясно, что в случае строго квадратичной функции f(x) метод Ньютона дает решение задачи минимизации за один шаг. В общем же случае этот метод приводит к итерационному процессу поиска на каждом шаге минимума квадратичных аппроксимаций f k(x) функции f(x).
Основное преимущество метода Ньютона перед градиентными методами состоит в том, что при выполнении некоторых условий метод обладает большей скоростью сходимости при минимизации овражных функций. Геометрически это объясняется тем, что вектор имеет большую составляющую вдоль "дна" оврага, чем просто антиградиент -f(xk). В результате для решения задачи требуется меньшее количество итераций, чем при использовании градиентных методов.
К числу недостатков метода Ньютона следует отнести необходимость вычисления вторых производных функции f(x) и обращения гессиана на каждой итерации в процессе поиска, а самое главное, зависимость сходимости метода от начального приближения. Если начальное приближение выбрано неудачно (например, находится далеко от точки минимума), то, метод может даже расходиться.
Для устранения отмеченных недостатков применяют различные модификации метода Ньютона. В частности, вектор sk можно использовать лишь как направление поиска, в котором предполагается сделать очередной шаг. Возможны различные способы выбора этого шага поиска. Один из них, как и в методе наискорейшего спуска, состоит в минимизации функции f(х k - h s k ) в выбранном направлении поиска
Для уменьшения трудностей, связанных с вычислением вторых производных, могут быть применены различные модификации метода, использующие не точные значения, а приближенные аналоги гессиана. Одна из простейших модификаций такого рода имеет вид
Как видно из алгоритма, вычисление гессиана предполагается здесь производить лишь один раз в некоторой заранее выбранной точке х. Другая модификация метода Ньютона предполагает обновление гессиана через определенное количество итераций.
В тех случаях когда гессиан минимизируемой функции не является положительно определенным, метод Ньютона, как уже отмечалось, не может гарантировать сходимость к некоторому минимуму. В этих случаях может быть использована следующая модификация метода:
Здесь I - единичная матрица; k - некоторый дополнительный параметр на k-й итерации. Параметр k и шаг поиска h k должны подбираться эмпирически. Желательно при этом, чтобы метод вдали от минимума работал в основном как градиентный, а по мере приближения к минимуму переходил в обычный метод Ньютона.
Метод сопряженных градиентов
В рассмотренных методах на каждой итерации никак не использовалась информация, полученная на предыдущих итерациях. Очевидно, используя эту информацию, т.е. учитывая "предысторию" процесса поиска, можно рассчитывать на ускорение его сходимости. Методы поиска, в которых новое приближение формируется на основе нескольких предыдущих, называются многошаговыми. Одним из многошаговых методов является двухшаговый метод сопряженных градиентов. Идея метода заключается в построении нового приближения xk+1 по следующей схеме
где параметры hk и k подбираются на каждой итерации оптимальным образом, т.е. из условия минимизации функции f
В общем случае найти решение данной задачи в явном виде не удается. Однако для случая квадратичной функции для параметра k решение удается найти и алгоритму поиска можно придать следующий вид
Характерной особенностью алгоритма является тот факт, что он приводит к точке минимума квадратичной целевой функции за число итераций, не более чем размерность задачи.
Несмотря на то, что данный алгоритм расписан для квадратичной функции f(x), метод успешно может применяться и для неквадратичных функций. Правда, теперь метод уже не будет конечным. При этом оказывается целесообразным через каждые п шагов производить обновление метода, т.е. полагать k = 0 при k = 0, п, 2n, ... Метод сопряженных градиентов, являясь по форме методом первого порядка и поэтому простым в реализации, выгодно отличается от обычных градиентных методов тем, что он обладает, по существу, всеми достоинствами метода второго порядка (в том числе квадратичной сходимостью).
Возможны и другие схемы реализации метода сопряженных градиентов.
Квазиньютоновские методы
Рассмотрим теперь группу методов, называемых квазиньютоновскими, сущность которых состоит в воспроизведении квадратичной аппроксимации функции f(x) по значениям ее градиентов в ряде точек. Тем самым эти методы объединяют достоинства градиентных методов (т.е. не требуется вычисление вторых производных) и метода Ньютона (быстрая сходимость вследствие использования квадратичной аппроксимации). Структура методов этой группы такова:
Здесь, как и ранее, шаг поиска предполагается выбирать из условия а матрица Hk формируется и пересчитывается на основе k-й итерации так, чтобы в пределе она переходила в матрицу, обратную гессиану Hk [2 f(xk)]-1 . Тем самым в пределе методы этой группы переходят в ньютоновские методы.
Обсудим возможные способы формирования матриц Hk, аппроксимирующих матрицу [2f(xk)]-1. Можно, конечно, воспользоваться обычной конечно-разностной аппроксимацией гессиана с последующим обращением этой матрицы. Однако такой подход не всегда является наилучшим. Он требует больших вычислительных затрат. Идея квазиньютоновских методов заключается в построении аппроксимации для обратной матрицы [2 f(xk)]-1 непосредственно, без специальных пробных шагов, с использованием найденных градиентов на предыдущих итерациях. Поясним эту идею для квадратичной функции
Введем обозначения
Можно показать, что в этом случае имеет место равенство или .
Учитывая последнее равенство, потребуем, чтобы оно выполнялось и в общем случае для нового приближения H k+1 , т.е.
Последнее условие принято называть квазиньютоновским. Кроме того, потребуем, чтобы
H n = A-1 .
Оказывается можно предложить различные алгоритмы пересчета матриц Hk, удовлетворяющих сформулированным условиям. Приведем лишь некоторые из них:
алгоритм Давидона - Флетчера - Пауэлла
алгоритм Бройдена
алгоритм Бройдена - Флетчера - Шенно
Можно показать, что все представленные алгоритмы для квадратичных функций f(x) совпадают. Для неквадратичных функций эффективность этих алгоритмов зависит от вида минимизируемых функций. Что касается проведения двух последних экспериментов, то их естественно провести в соответствии с методом дихотомий. Учитывая сказанное, нетрудно установить, что для любого (N-K)-го эксперимента интервал неопределенности определяется формулой
где через FK обозначены числа Фибоначчи, определяемые по правилу F0 = F1 = 1; FK+1 = FK + FK-1. Поэтому данный метод получил также название метода Фибоначчи. Его эффективность характеризуется величиной L0 / LN = FN и является наивысшей из рассмотренных методов. Так, например, при N= 12 она превышает эффективность метода дихотомии более, чем в 3,5 раза. С ростом N преимущество метода еще более возрастает. Недостаток метода Фибоначчи состоит в том, что методом нельзя пользоваться, не зная заранее общего числа экспериментов N. Если же поиск методом Фибоначчи начат, то на любом шаге действия определяются просто - каждый последующий эксперимент располагается симметрично относительно предыдущего, попавшего в этот же интервал неопределенности. Однако для определения места приложения первых двух экспериментов необходимо предварительно найти величину L2 . Сами эксперименты должны быть в соответствии со свойством симметрии проведены на расстояниях L0, от левого и правого концов.
Указанного недостатка лишен метод золотого сечения, который, уступая несколько методу Фибоначчи, все же существенно превосходит по эффективности метод дихотомии. Метод золотого сечения, как и метод Фибоначчи, требует выполнения условия симметрии. Однако в отличие от последнего он предполагает еще и постоянство отношений длин последовательных интервалов неопределенности, т.е. Lj/Lj+1 = c для всех j.
Последнее соотношение и обусловило название метода. "Золотым сечением" принято называть деление отрезка на две части так, чтобы отношение всего отрезка к большей части равнялось отношению большей части к меньшей. С учетом свойства симметрии нетрудно. найти единственное значение параметра Поиск по методу золотого сечения производится так же, как и по методу Фибоначчи. Отличие заключается лишь в проведении двух первых экспериментов. В данном случае они располагаются симметрично на интервале [а, b] и на расстоянии L0/с от его концов. После проведения N экспериментов интервал неопределенности будет равным LN = L0 /cN-1. Эффективность метода характеризуется величиной L0 / LN = cN-1 . Сравнивая величины FN и cN-1 , можно установить, что при больших N эффективность метода золотого сечения приближается к эффективности метода Фибоначчи. Это обстоятельство и обусловило широкое распространение метода золотого сечения.
2.3. МЕТОДЫ ОДНОМЕРНОГО ПОИСКА Как мы видели, большинство методов оптимизации предусматривает поиск минимума функции одной переменной - шага поиска. Этот поиск является составной частью общей процедуры минимизации. От того, насколько хорошо организован такой одномерный поиск, существенно зависит эффективность метода в целом. Рассмотрим этот вопрос подробнее, сравнив между собой различные методы одномерного поиска.
Отметим, что рассматриваемые в данном разделе методы относятся к методам нулевого порядка, которые в общем случае будут обсуждаться в следующем разделе. Здесь мы ограничимся лишь частным случаем, рассматривая лишь функцию одной переменной. Более того, ограничимся рассмотрением, так называемых, унимодальных функций, т.е. функций, имеющих на исследуемом интервале [а, b] единственный минимум. Унимодальные функции не обязательно должны быть гладкими или непрерывными (см.рис.2.5). Выпуклые функции являются частным случаем унимодальных.
Рис.2.5Примеры унимодальных функций Величину интервала [a, b ], называемого также начальным интервалом неопределенности, обозначим через L0. Будем по-прежнему для минимизируемой функции использовать обозначение f(x), считая, однако, теперь, что х - скаляр. В частном случае под х понимается шаг поиска h, который должен быть выбран в рассмотренных выше алгоритмах.
Заметим, что в случае необходимости начальный интервал неопределённости может быть сведен к единичному путём введения новой переменной
Обычный перебор
Простейшим методом одномерного поиска является обычный перебор значений f(xj) минимизируемой функции f(x) в конечном числе точек переменной х, равномерно распределенных на интервале [а, b], с последующим выбором наименьшего значения Значение в силу свойства унимодальности может быть приближенно принято за искомое оптимальное значение. Очевидно, точность такого процесса определяется количеством экспериментов, связанных с измерением функции f(x), и характеризуется интервалом неопределенности после проведения всех экспериментов, равным Таким образом, эффективность процесса поиска можно оценить отношением начального интервала неопределённости L0 к интервалу неопределённости Метод дихотомии
Совершенно очевидно, что равномерное распределение всех экспериментов на интервале поиска [а, b] не является наилучшим. Эффективность поиска можно существенно повысить, если эксперименты проводить попарно, анализируя результаты после каждой пары экспериментов. Наиболее эффективным проведением экспе-, риментов каждой пары является такое, при котором интервал неопределенности сокращается, практически вдвое. Лучшего результата при проведении двух экспериментов получить просто невозможно. Для этого оба эксперимента должны быть расположены в районе середины интервала как можно ближе друг к другу, но так, чтобы все-таки можно было отличить значения функции в этих точках друг от друга. Такой метод поиска получил название метода дихотомии. Схема реализации метода дихотомии изображёна на рис.2.6, где показано проведение первых трех пар экспериментов. Рис.2.6Схема реализации метода дихотомии Оценим эффективность метода. Пусть перед проведением экспериментов величина неопределённости на которой находится искомый минимум равна L0. Проведем первые два эксперимента. Для двух значений переменных x1 и x2 вычисляются значения функций f(x1) и f(x2). Эксперименты x1 и x2 размещаются на этом интервале таким образом, чтобы величина интервала неопределённости после этого стала минимальной. Обозначим через L2 интервал неопределённости после проведения двух экспериментов. Этот интервал будет равен L2 = max{L0 - x1,x2}, предполагается, что x1 < x2. Пусть - наименьший сдвиг эксперимента, при котором можно обнаружить отличие f(x1) от f(x2). Нетрудно сообразить, что минимум L2 достигается при значениях: Это и означает, что наилучшее распределение пары экспериментов - симметричное распределение их внутри первоначального интервала неопределённости на расстоянии друг от друга.
Если требуется провести ещё пару экспериментов, то наилучшее распределение их будет являться также симметричным распределением, но теперь уже внутри интервала, величина которого равняется , при четырёх экспериментах величина интервала неопределённости равна . После проведения n экспериментов интервал неопределённости будет равен .
Потребное число экспериментов определится из соотношения
,
где требуемая точность определения экстремума.
Полагая достаточно малым, интервал неопределенности после проведения n / 2 пар экспериментов можно оценить с помощью упрощенной формулы , а эффективность метода соответственно отношением .
Отсюда видно, что с ростом n эффективность метода дихотомии растет по сравнению с простым перебором. Даже при n = 12 эффективность метода дихотомии примерно в 10 раз выше метода перебора.
Тем не менее метод дихотомии в целом не является наилучшим методом одномерного поиска, так как в нем используется не вся информация о проведенных ранее экспериментах. Метод Фибоначчи
Оптимальную стратегию последовательного поиска дает следующий метод. Его сущность состоит в том, что каждые два соседние эксперимента располагаются на текущем интервале неопределенности на одинаковом расстоянии от левого и правого концов, т.е. симметрично (см. рис.2.7).
Рис.2.7Схема реализации метода Фибоначчи Пусть имеется n экспериментов. Рассмотрим три последних. Из симметричности расположения двух соседних экспериментов следует основное равенство метода
Lj -1 = Lj + Lj+1.
Что касается проведения двух последних экспериментов, то их естественно провести в соответствии с методом дихотомии. Поэтому для последних двух экспериментов имеем
.
Учитываю это, можно последовательно получить Если теперь ввести в рассмотрение последовательность чисел Фибоначчи
то нетрудно с их помощью получить следующую формулу для интервала неопределенности после проведения (n-k)-го эксперимента Полагая k = n-1 и L1 = L0, получим:
Для оценки эффективности данного метода вновь пренебрежем слагаемым, содержавшим . Получим, что отношение начального интервала неопределенности к конечному интервалу неопределенности после проведения всех экспериментов равно числу Фибоначчи с номером, равным числу экспериментов L0 / Ln = Fn.
Поэтому и метод получил название метода Фибоначчи. Метод обладает наивысшей эффективностью среди рассмотренных ранее методов. Так, например, при n = 12 эффективность метода превышает эффективность метода дихотомии более, чем в 3,5 раза, а метода перебора в 35 раз. С ростом n преимущество метода еще более возрастает. Недостаток метода Фибоначчи состоит в том, что методом нельзя пользоваться, не зная заранее общего числа экспериментов n . Если же поиск методом Фибоначчи начат, то на любом шаге действия определяются просто - каждый последующий эксперимент располагается симметрично относительно предыдущего, попавшего в этот же интервал неопределенности. Однако для определения места приложения первых двух экспериментов необходимо предварительно найти величину L2 . Сами эксперименты должны быть согласно свойству симметрии проведены на расстояниях L2 от левого и правого концов начального интервала поиска.
Метод золотого сечения
Указанного недостатка лишен метод золотого сечения, который, уступая несколько методу Фибоначчи, все же существенно превосходит по эффективности метод дихотомии. Метод "золотого сечения", как и метод Фибоначчи, требует выполнения условия симметрии. Однако в отличие от последнего,\ он предполагает еще и постоянство отношений длин последовательных интервалов неопределенности, т.е. Lj/Lj+1 = c для всех j (см. рис. 2.8). Рис.2.8Схема реализации метода золотого сечения Последнее соотношение и обусловило название метода. "Золотым сечением" принято называть деление отрезка на две части так, чтобы отношение всего отрезка к большей части равнялось отношению большей части к меньшей.
Разделим первое соотношение на Lj, получим
Уравнение имеет единственное положительное решение Поиск по методу золотого сечения производится так же, как и по методу Фибоначчи. Отличие заключается лишь в проведении двух первых экспериментов. В данном случае они располагаются симметрично на интервале [а, b] и на расстоянии L0/с от его концов. После проведения n экспериментов интервал неопределенности будет равным Ln = L0 /cn -1.
Поэтому эффективность метода характеризуется величиной L0 / Ln = cn -1 .
Сравнивая величины Fn и cn-1 , можно установить, что при больших n эффективность метода золотого сечения приближается к эффективности метода Фибоначчи. Это обстоятельство и обусловило широкое распространение метода золотого сечения.
2.4. МЕТОДЫ НУЛЕВОГО ПОРЯДКА
Перейдем теперь к рассмотрению методов нулевого порядка для функций многих переменных, требующих для своей реализации лишь значения целевой функции f(x) и не использующих никаких частных производных. Эти методы иногда называют также прямыми. В тех случаях, когда градиенты и гессианы могут быть легко вычислены, прямые методы могут, конечно, оказаться менее эффективными, чем методы первого или второго порядка. Однако в целом ряде случаев прямые методы оказываются единственными практически применимыми методами. Это относится, в частности, к случаям, когда целевая функция имеет разрывы или целевая функция задана не в явном виде, а косвенно через какие-либо уравнения, относящиеся к различным подсистемам некоторой сложной системы и т.д.
В настоящее время предложено много различных прямых методов поиска. Характерным для этих методов является их эвристичность. В связи с этим сходимость и эффективность методов может быть подтверждена лишь экспериментально на примерах решения конкретных задач.
Метод покоординатного спуска Метод является одним из простейших методов этой группы. Сущность метода состоит в последовательной минимизации целевой функции по отдельным переменным. Сначала отыскивается минимум по первой компоненте, при этом считается, что остальные фиксированы, затем по второй (при этом первая компонента принимается равной найденной) и т.д. Метод в общем случае не обеспечивает отыскания минимума функции за один цикл поиска, т. е. после изменения всех переменных. Необходимо многократное повторение таких циклов.
Метод обладает рядом существенных недостатков. Сходимость метода существенно зависит от выбора системы координат, что наглядно отображено на рис.2.9. Рис.2.9Влияние выбора системы координат на сходимость метода Метод может оказаться непригодным при наличии ограничений, либо слабоэффективным в случае минимизации овражных целевых функций, он практически останавливается на дне оврага (см. рис.2.10). Поэтому метод обычно применяют в комбинации с другими методами.
Рис.2.10Влияние ограничений и "овражности" на сходимость метода Метод конфигураций
Данный метод является достаточно общим. Он допускает множество модификаций и является достаточно перспективным для задач оптимизации большой размерности. В соответствии с этим методом вначале происходит обследование окрестности некоторой точки х0 (например, путем изменения значений одной или нескольких компонент вектора х0) . После отыскания приемлемого направления производятся вычисления целевой функции при постепенно увеличивающемся шаге (тем самым устанавливается конфигурация поиска). Увеличение шага продолжается до тех пор, пока поиск в этом направлении приводит к уменьшению функции. Если уменьшения функции не происходит, то шаг уменьшают. После нескольких неудач при сокращении шага от принятой конфигурации отказываются и переходят к новому обследованию окрестности. Таким образом, согласно этому методу делаются попытки найти наилучшее направление поиска с тем, чтобы двигаться вдоль него. Метод прост в реализации. Но и для этого метода характерна возможность (хотя и в меньшей степени) заедания вблизи локального минимума или явно выраженного оврага. Метод линейной аппроксимации
Одним из вариантов реализации метода конфигураций может быть метод, базирующийся на использовании линейной аппроксимации целевой функции. Общий вид алгоритма следующий
xk+1 = xk -hkSk.
Здесь Sk - направление поиска, hk - длина рабочего шага поиска.
Существует различные способы определения направления поиска, например, при использовании односторонней аппроксимации целевой функции в виде ,
или при использовании симметричной аппроксимации в виде
,
где k - длина пробного шага, i - вектор направления пробного шага.
Нетрудно видеть, что одним из частных случаев этого метода является и метод градиентного спуска. Действительно при i = 0, i j, j =e. , где ei - единичный орт, вышеприведенные формулы представляют собой по сути варианты численного отыскания градиента. В частности, при использовании симметричной аппроксимации направление градиента определяется так Длина рабочего шага может быть вычислена методами, изложенными ранее.
Метод деформируемого многогранника
Этот метод является частным случаем метода конфигурации. В этом методе функция n переменных минимизируется с использованием n+1 вершин некоторого деформируемого многогранника в пространстве этих переменных. Вершина, в которой значение f(x) стремится к максимуму, проектируется через "центр тяжести" оставшихся вершин. Улучшенное значение целевой функции находится последовательной заменой точки с максимальным значением f(x) на более "хорошие" точки, пока не будет найден минимум функции f(x) (см. рис 2.11) .
Рис.2.11Схема реализации метода деформируемого многогранника
Алгоритм этого метода может быть представлен в виде следующих основных операций.
1. Формирование в n - мерном пространстве многогранника путём задания n+1 вершины {xj}, j = 1...n+1.
2. Определение среди вершин "наихудшей" xh и "наилучшей" xl, соответствующих максимальному и минимальному значению целевой функции.
3. Определение "центра тяжести" всех вершин, исключая "наихудшую": 4. Отражение "наихудшей" вершины: 5. Растяжение: если выполняется условие ,то вычисляется точка
6. Операция сжатия: проверка условия 7. Если выполняется условие 8. Редукция - проверка условия Если это условие выполняется то в таком случае формируется новый многогранник с уменьшенными вдвое сторонами с вершинами После формирования нового многогранника в соответствии с позициями 5, 6, 7 или 8 процесс поиска повторяется, начиная с позиции 2.
Методы случайного поиска
Большую группу методов прямого поиска, требующих знания лишь значений целевой функции, составляют так называемые методы случайного поиска. В отличие от детерминированных методов поиска, рассмотренных нами ранее, методы случайного поиска предполагают использование элемента случайности (например, при определении направления поиска или длины шага), что приводит к качественно новой картине процесса поиска - траектория движения (спуска) к минимуму становится случайной. Именно это обстоятельство позволяет на базе использования случайного поиска строить алгоритм поиска глобального экстремума. Для алгоритмов случайного поиска характерны простота, универсальность, большая эффективность поиска при оптимизации сложных систем. Рассмотрим лишь некоторые методы случайного поиска.
Метод ненаправленного случайного поиска
Требуется найти абсолютный минимум функции f(x), где x X. Ненаправленный случайный поиск заключается в построении последовательности 1,2,...,n независимых случайных точек, равномерно распределённых в области X и определении минимального значения целевой функции в этих точках. в этих . Чем больше точек, тем ближе значение k к x*. Под x* понимается точка абсолютного минимума. Метод ненаправленного поиска обеспечивает решение задачи отыскания глобального минимума с вероятностью сколь угодно близкой к единице при достаточно большом количестве экспериментов . Метод простой случайной оптимизации
Простейший вариант случайного поиска заключается в следующем. В точке хk формируется направление k с помощью датчика единичных случайных векторов, равномерно распределенных по всем направлениям. Делается пробный шаг в этом направлении hпр k (см. рис.2.12). Рабочий шаг формируется, исходя из условий: Рис.2.12Метод простой случайной оптимизацииВ результате получаем новое приближение хk+1 = xk + xk . Величина рабочего шага hраб определяется (подбирается) экспериментально. Метод оказывается эффективным в случае крутых целевых функций, вдали от точки экстремума. В районе экстремума эффективность его падает.
Метод наилучшей пробы
Смысл данного метода заключается в следующем. Из точки xk делается т реализаций kj единичных случайных независимых векторов, равномерно распределенных по всем направлениям (см. рис.2.13). Рис.2.13Метод наилучшей пробыС их помощью формируется т проб: {hпрkj }, где hпр - величина пробного шага. Выбирается наилучшее направление из условия
Рабочий шаг совершается именно в этом направлении
В данном алгоритме в отличие от предыдущего выбору подлежат два параметра hраб и т. Очевидно, что с увеличением числа проб т наилучшее направление приближается к направлению, обратному градиенту, и в пределе при т совпадает с ним. Преимущество метода по сравнению с градиентным состоит, однако, в том, что здесь может иметь место неравенство т < п, где п - размерность задачи, а это существенно, особенно при больших п . Кроме того, алгоритм, как и другие методы случайного поиска, обладает возможностью определения глобального экстремума.
К недостаткам метода следует отнести возможность неудачного шага, т.е. шага в направлении возрастания целевой функции, и малую эффективность накопления информации. Первый недостаток можно устранить, если использовать, например, следующую модификацию алгоритма:
Однако следует иметь в виду, что выигрыш, полученный за счет исключения возможности неудачного шага, может и не покрыть дополнительных потерь, необходимых для этого исключения, а неудачные шаги как раз являются теми шагами, которые позволяют отыскивать глобальный экстремум (точнее, преодолевать локальные экстремумы).
Малую эффективность накопления информации следует понимать так. Из всех пробных шагов выбирается лишь лучший, все остальные отбрасываются, несмотря на то, что в них содержится информация о поведении целевой функции в районе текущей точки. Очевидно, алгоритм можно улучшить, если принимать решение о направлении рабочего шага не только по результату наилучшей пробы. В простейшем варианте, кроме наилучшей, можно учесть и наихудшую пробу для которой .
Если окажется, что модуль приращения целевой функции при наихудшей пробе больше модуля приращения целевой функции при наилучшей пробе, то рабочий шаг целесообразно сделать в направлении , т.е.
Метод статистического градиента
Как и прежде, из точки хk сделаем т "независимых" проб Вычислим соответствующие приращения целевой функции
и образуем вектор
Вектор называется статистическим градиентом функции f(x) в точке xk. Дело в том, что математическое ожидание направления для линейной целевой функции совпадает с направлением градиента. Следовательно, при конечном числе т направление этого вектора является статистической оценкой градиентного направления. Учитывая сказанное, рабочий шаг выберем как
Данный метод, как и метод наилучшей пробы, может работать при любом т, в том числе, и при т <п, в то время как численная реализация градиентных методов требует проведения п проб для вычисления всех составляющих вектора градиента.
Метод статистического градиента, таким образом, может быть интерпретирован как статистический аналог детерминированного градиентного метода. По отношению к методу наилучшей пробы рассматриваемый метод обладает большой эффективностью накопления информации, что приводит, в частности, к большой стабильности траектории поиска при равном количестве проб.
Метод случайного поиска с направляющей сферой
Эффективность методов поиска часто можно повысить, если наряду с новой информацией, получаемой на каждом шаге, использовать предыдущий опыт. Примером построения такого алгоритма может служить следующий алгоритм, включающий в себя три этапа. 1. Этап анализа. В точке хk делается т независимых проб причем вектор проб kj формируется согласно выражению где Wk - единичный вектор памяти, определяющий среднее направление поиска; kj - j-я реализация единичного случайного вектора с равномерно распределенной по всем направлениям плотностью вероятности; с - константа, характеризующая долю участия случайного направления в формировании вектора проб. При с < 1 все пробные шаги укладываются внутри гиперконуса с осью Wk и углом раскрытия 2 arcsinc (см. рис.2.14).
Рис.2.14Метод случайного поиска с направляющей сферой 2. Этап принятия решения. На этом этапе определяется направление рабочего шага согласно какому-нибудь конкретному принятому методу. Новое приближение хk+1 определяется согласно соотношению хk+1 = хk + хk , где смещение хk находится одним из рассмотренных выше методов. Так, например, для метода наилучшей пробы: для метода статистического градиента
3. Этап обучения. Так как выбранное направление смещения хk в общем случае не совпадает с направлением вектора памяти Wk , то, естественно, Wk необходимо поправить. Это можно сделать различными способами, например так:
где > 0 - параметр, характеризующий долю участия новой информации при корректировке вектора памяти. В начальный момент при k=0 можно принять W0 =0. Основным недостатком алгоритма является необходимость выбора четырех параметров: с, , hраб , m , от которых и зависит эффективность алгоритма. Учитывая, что эти параметры должны подбираться экспериментально, представляют интерес модификации рассмотренного метода. Рассмотрим одну из таких модификаций.
Метод случайного поиска с направляющим конусом
Как и раньше, из точки хk делается т проб но на основе использования случайных векторов с равномерно распределенной плотностью внутри гиперконуса с вершиной в точке хk осью, направленной вдоль вектора памяти Wk , и с углом полного раствора (см. рис.2.15).
Рис.2.15Метод случайного поиска с направляющей сферой Направление рабочего смещения хk определим в соответствии с методом наилучшей пробы:
В качестве обновленного вектора Wk+1 примем вектор наилучшей пробы Таким образом, в данном алгоритме выбору подлежат не четыре, а три параметра , hраб , m. Характерной особенностью двух последних алгоритмов является их "инерционность". Действительно, направление поиска, задаваемое в среднем вектором памяти Wk, не может резко измениться за один шаг. Эта инерционность определяется в одном алгоритме параметрами hраб и , в другом - параметрами hраб и . Наличие инерционности придает глобальный характер процессу поиска, позволяя преодолевать локальные минимумы и осуществлять поиск вдоль "оврагов" и "хребтов" целевой функции. С другой стороны, процесс поиска должен быть достаточно мобильным. Поэтому при выборе параметров алгоритмов приходится прибегать к компромиссному решению. При рациональном назначении этих параметров алгоритм стимулирует поиск вдоль "оврагов" целевой функции независимо от того, поднимаются они или опускаются, позволяя преодолевать "хребты" по "перевалам" и отыскивать новые районы ее локальных минимумов. Эти алгоритмы хотя и не находят самого глобального минимума, но позволяют выделить те области пространства, где этот- минимум может находиться. Комбинированные методы
Эти методы применяются для улучшения сходимости методов случайного поиска, а также для ликвидации ряда недостатков детерминированных методов.
Стохастический вариант метода Гаусса-Зейделя. Основной недостаток метода Гаусса-Зейделя - слабая эффективность в случае овражных функций и при наличии ограничений. Этот недостаток может быть устранён, если движение вдоль координатной оси заменить движением в случайном направлении.
Стохастический вариант метода оврагов. В случае многомерных оврагов полезно в начале поиска взять несколько случайных точек x01, x02, ..., x0n и произвести спуск на дно оврага в точках x11, x12,..., x1n, далее по этим точкам выбрать направление оврага, например с помощью метода статистического градиента.
Алгоритм случайного перебора локальных экстремумов. Для поиска глобального экстремума можно использовать любой детерминированный метод поиска локального экстремума, комбинируя его со случайным подбором начальных условий поиска. Такой алгоритм поиска является по сути дела алгоритмом случайного перебора локальных экстремумов (см. рис.2.16) и применим при большом их числе.
Рис.2.16Случайный перебор локальных экстремумов Блуждающий глобальный поиск. Этот метод является статистическим обобщением метода градиентного спуска. Чтобы придать поиску глобальный характер, на траекторию градиентного спуска накладываются случайные отклонения (t), которые создают режим случайного блуждания. Движение точки x(t) в процессе поиска описывается уравнением:
где h - шаг поиска, а под (t), будем понимать n-мерный случайный процесс типа белого шума с нулевым математическим ожиданием и спектральной плотностью 2. Процесс, описываемый этим выражением, является Марковским случайным процессом диффузионного типа. Плотность распределения вероятности p(x,t) удовлетворяет уравнению Фоккера-Планка-Колмогорова
Максимальное значение p(x) соответствует точке глобального минимума функции f(x), следовательно наиболее вероятное положение точки x в результате достаточно длительного поиска - это положение глобального минимума.
Тема 7. Нелинейное программирование. Методы условной оптимизации (4ч, СРС 2ч)
Перейдем теперь к рассмотрению наиболее распространенных численных методов оптимизации при наличии ограничений в общем случае, когда целевая функция нелинейна. Существует два основных подхода к построению алгоритмов такого рода. Первый состоит в непосредственном учете ограничений задачи (хотя, может быть, и приближенно). Этот подход реализован, например, в методах аппроксимирующего линейного программирования, возможных направлений, проективного градиента. Второй подход состоит в сведении исходной задачи при наличии ограничений к последовательности задач безусловной оптимизации путем использования функций штрафов. Методы, реализующие данный подход, называются методами штрафных функций.
3.1. Методы аппроксимирующего линейного программирования
Сущность всех методов данной группы заключается в том, что нелинейная целевая функция и функции ограничений заменяются последовательностью аппроксимирующих линейных функций и тем самым сводят исходную задачу к задаче линейного программирования.
Один из алгоритмов аппроксимирующего линейного программирования состоит в следующем. Пусть требуется найти minf(x) при условии g(x)0. Произведем замену нелинейных функций f(x) и g(x) их линейными аппроксимациями путем разложения в ряд Тейлора в окрестности точки хk . В результате получим задачу линейного программирования:
Так как решение указанной задачи может вывести вектор х за пределы допустимой области исходной задачи, то необходимо ввести дополнительные ограничения на компоненты вектора х, например, в виде
где jk >0 ограничивают длину шага при перемещении в том или
ином направлении. Решение полученной таким образом задачи и предполагается принять в качестве нового (k+1)-го приближения xk+1. Для ее решения следует воспользоваться соответствующими методами линейного программирования. Основным недостатком рассмотренного метода является слабая сходимость в районе существенно нелинейных ограничений.
Другой метод аппроксимирующего нелинейного программирования (см. рис.32.) предполагает использование линейной интерполяции нелинейных функций f(x) и g(x) в следующем виде:
В итоге, вместо нелинейной задачи получим задачу линейного программирования:
Минимизация осуществляется относительно весов i. Эффективность метода в значительной степени зависит от точек сетки xi и их количеством. Эта процедура в методе наиболее трудоёмкая.
3.2. Метод возможных направлений
Сущность данного метода сводится к следующему: поиск начинается в допустимой точке и реализуется при линеаризованных ограничениях по траектории, обеспечивающей наибольшее улучшение значений целевой функции и вместе с тем не выходящей за пределы допустимой области.
Если через sk обозначить возможное (допустимое) направление поиска из точки хk , то новая точка xk+1 определится соотношением xk+1 = xk + hk s. Подставляя в линеаризованные выражения для f(х) и g(x) вместо вектора х значения xk+1 , приходим к задаче:
Очевидно, что точка хk+1 будет допустимой, а следовательно, и направление sk будет допустимым, если выполняются условия:
Поэтому, решая задачу f(xk)Tsk min при условиях
мы определим вектор допустимых направлений sk, вдоль которого целевая функция f(x) имеет наибольшую скорость убывания.
Что касается величины шага поиска вдоль выбранного направления, то ее можно определить, как и в методе наискорейшего спуска, из решения одномерной задачи минимизации по h:
Основное достоинство представленного метода состоит в его универсальности. К недостаткам следует отнести большой объем вычислений на каждой итерации и невозможность учета ограничений типа равенств.
3.3. Проективный градиентный метод
Одной из модификаций метода возможных направлений является проективный градиентный метод. Данный метод отличается от метода возможных направлений лишь тем, что при попадании точки хk в район границы допустимого множества направление поиска sk определяется путем проектирования антиградиента -f(хk ) на многогранник, являющийся линейной аппроксимацией допустимого множества вблизи точки xk. Тем самым метод позволяет учитывать ограничения как типа неравенств, так и строгих равенств.
Сущность метода поясним на примере задачи нелинейного программирования с линейными ограничениями:
Пусть хk - некоторая допустимая граничная точка, для которой выполняется условие Аk хk =bk . Здесь через Аk , bk обозначены части матрицы А и вектора b, соответствующие активным ограничениям в точке хk . Будем искать новую точку хk+1 = хk +hk sk так, чтобы помимо условия Ах b по-прежнему имело место Аk хk+1 =bk . Очевидно, для этого необходимо выполнение условия Аk sk = 0 . Как и в методе возможных направлений, поставим задачу по определению наилучшего допустимого направления поиска. Таким направлением будет считаться направление, задаваемое единичным вектором sk , вдоль которого функция f(x) имеет наибольшую скорость убывания:
Последняя задача может быть решена аналитически с использованием метода множителей Лагранжа.
Если матрица P положительно определена, то знак " - " соответствует минимуму, а знак " + " - максимуму функции z. В результате получим искомое направление поиска
При этом предполагается, что матрица существует. Геометрически вектор означает проекцию антиградиента на границу, задаваемую условием Ak х=bk. Этим и объясняется название метода. Величину шага hk можно определить, как и прежде, из условия
Метод проективного градиента является достаточно трудоемким методом, так как требует проведения анализа на каждом шаге активных ограничений задачи и соответствующей корректировки матриц Ak и Вk. При использовании метода в общем случае при наличии нелинейных ограничений g(x)0 трудности еще более возрастают.
Во-первых, необходимо вычисление частных производных активных ограничений g(xk)=0 по вектору х, которые играют роль матрицы Ak. Во-вторых, в виду нелинейности ограничений теперь движение вдоль проекции антиградиента уже не может гарантировать пребывание новой точки хk в допустимой области. Поэтому в общем случае приходится несколько корректировать алгоритм поиска (рис.33.), вводя в него с целью невыхода из допустимой области соответствующую компенсационную составляющую.
3.4. Методы штрафных функций
Осуществление минимизации без ограничений представляет собой более лёгкую задачу, чем минимизация с ограничениями, поэтому существуют попытки преобразования задач с ограничениями в задачи без ограничений. Самый простейший способ - замена переменных. Например, если скалярная переменная удовлетворяет ограничениям | x | 1, можно использовать замену переменной x на величину : x = sin, x = cos. Второй вариант x [0,] используется замена: x = ey или x = y2. Или если x [a,b], применяют замену x = a + (b-a)sin2. Более широкое применение получил метод штрафных функций
Методы штрафных функций выгодно отличаются от других методов условной оптимизации простотой реализации. Сводя решение задач условной оптимизации к последовательности решения задачи безусловной оптимизации, методы штрафных функций, по существу, дают в распоряжение исследователя весь тот богатый аппарат, который имеется для решения задач безусловной оптимизации. Именно поэтому методы штрафных функций находят в настоящее время широкое применение. Общую схему построения алгоритмов поиска поясним на задаче минимизации функции f(х) на некотором множестве X. Формально эта задача эквивалентна задаче безусловной минимизации суммы f(х)+(х), где
По сути дела, функция (х) является функцией штрафов (см. рис.34.). Но так как она неприемлема для проведения расчетов, то вместо нее предполагается использовать такие штрафные функции (х,), которое удовлетворяют условию для всех x. В этом случае исходная задача оказывается эквивалентной задаче Если при этом операции минимума и предела окажутся перестановочными, то мы получим последовательность задач безусловной минимизации по отношению к преобразованной целевой функции:
пределом которых при будет точка минимума функции f(x) на множестве X.
Существуют два основных подхода к построению штрафов (х,). В соответствии с этими подходами различают и два метода штрафных функций - метод внутренней точки (барьерных функций) и метод внешней точки.
Метод внутренней точки
Он предполагает построение штрафов таким образом, чтобы при приближении вектора хХ границе области X величина (х,) неограниченно возрастала. В этом случае траектория поиска минимума (если, конечно, поиск начат с внутренней точки множества X) полностью будет лежать внутри множества X. Отсюда и название метода.
Если рассматривается задача минимизации функции f(x) при ограничениях то в качестве штрафов могут быть использованы, например, такие функции: Основные достоинства метода внутренней точки заключаются в следующем. В процессе поиска целевая функция уменьшается без нарушения ограничений. Поэтому нет необходимости отдельно учитывать границу допустимой области (например, пытаться двигаться по границе). Преобразованная целевая функция сохраняет в общем свойства исходных функций f(x) и g(x) (например, непрерывность, дифференцируемость). К недостаткам метода следует отнести необходимость иметь в качестве начальной точки поиска допустимую точку, а также неприменимость метода при наличии ограничений типа равенств.
Метод внешней точки
Этот метод предполагает построение штрафов таким образом, чтобы значения преобразованной целевой функции F(x,) в допустимой области точно или приближенно равнялись значениям исходной целевой функции f(x), а вне допустимой области, существенно превосходили значения f(x). Для задачи отыскания minf(x) при ограничениях наиболее распространены следующие функции штрафов:
Преимущества метода внешней точки заключаются в большей его универсальности: метод применим при наличии различных ограничении (равенств и неравенств), процесс поиска может быть начат из любой точки (допустимой и недопустимой). К недостаткам метода следует отнести тот факт, что элементы последовательности xk () при могут не принадлежать допустимой области, а также невозможность при некоторых функциях штрафа применения методов поиска с использованием вторых производных.
С учетом сказанного на практике может оказаться наиболее эффективным применение комбинированного метода штрафных функций: для части ограничений (типа неравенств) применяется метод внутренней точки, а для другой части ограничений (типа равенств) - метод внешней точки. Преобразованная целевая функция в этом случае может быть представлена, например, в виде
Завершая рассмотрение методов штрафных функций, обратим внимание на одно важное обстоятельство, свойственное всем методам этой группы. Как мы убедились, решение задачи, полученное с помощью того или иного метода штрафных функций, будет тем ' точнее, чем больше параметр штрафа . Однако нетрудно убедиться, что с увеличением OL задача безусловной минимизации функции F(x,) усложняется из-за того, что последняя приобретает все более выраженную овражную структуру. Кроме того, при больших a возрастает роль ошибок счета (округления). В силу этого найти минимум F(x,) по х при больших с высокой точностью оказывается практически невозможным. Поэтому методы штрафных функций обычно используются для получения приближенного решения, при этом задаются небольшие значения параметра штрафов.
303015
72
72
Документ
Категория
Рефераты
Просмотров
727
Размер файла
2 214 Кб
Теги
лекция, установочные, часть
1/--страниц
Пожаловаться на содержимое документа