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

Содержание

 

 

 

Введение

 

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

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

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

 

Задание

 

Вариант 2

Дана несепарабельная функция двух переменных:

 

,

 

где .

Дана начальная точка поиска - , где .

Получим функцию:

 

.

 

1) Найти безусловный экстремум функции f(x,y) методами:

- наискорейшего спуска;

- сопряженных направлений.

Точность вычислений:

 

/xi+1-xi/<0.01

/yi+1-yi/<0.01

/f(xi+1,yi+1)-f(xi,yi)/<0.01

 

2) Найти условный экстремум функции f(x,y) методом симплексных процедур при наличии следующих ограничений:

 

 

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

 

, где K=1, Т=1.

 

- разработать модель для данного типа ОСАУ;

- провести исследование ОСАУ с применением программного продукта

“20 Sim Pro 2.3”;

- снять переходные и импульсные  характеристики.

 

 

1. Анализ методов определения  минимального, максимального значения функции без ограничения

 

В данном разделе будет рассматриваться задача безусловной оптимизации, т.е. данная задача характеризуется тем, что минимум функции f: Rm ® R ищется на всем пространстве:

 

f(x) ® min, x Î Rm.

 

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

1. Методы прямого поиска, основанные на вычислении только значений целевой функции.
2. Градиентные методы, в которых используются точные значения первых производных f (x).
3. Методы второго порядка, в которых наряду с первыми производными используются также вторые производные функции f (x).

 

1.1 Методы прямого поиска

 

Здесь предполагается, что f (x) непрерывна и унимодальная. Если рассматриваемые методы применяются для анализа мультимодальных функций, то приходится ограничиваться идентификацией локальных минимумов. К особенностям этих методов можно отнести:

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

Метод поиска по симплексу

Процедура симплексного метода базируется на регулярном симплексе. Регулярный симплекс в N-мерном пространстве представляет собой многогранник, образованный N+1 равностоящими друг от друга точками - вершинами. Так в задаче с двумя переменными симплексом является равносторонний треугольник, с тремя - тетраэдр.

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

Преимущества метода:

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

Недостатки метода:

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

Метод поиска Хука-Дживса

Процедура поиска Хука-Дживса представляет собой комбинацию "исследующего поиска" и "ускоряющего поиска по образцу".

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

Поиск по образцу заключается в реализации единственного шага из полученной базовой точки xk вдоль прямой, соединяющей эту точку с предыдущей базовой точкой xk-1. Новая точка образца xk+1 определяется в соответствии с формулой

 

xk+1 = xk + (xk - xk-1).

 

Как только движение по образцу не приводит к уменьшению целевой функции, точка xk+1 фиксируется в качестве временной базовой точки и вновь проводится исследующий поиск. Если в результате получается точка с меньшим значением целевой функции, чем в точке xk, то она рассматривается как новая базовая точка xk+1.

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

 

Рис. 1.1 - Метод поиска Хука-Дживса

 

Преимущества метода:

• несложная стратегия поиска;
• невысокий уровень требований к ЭВМ;
• широкое применение в инженерных приложениях.

Недостатки:

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

 

1.2 Градиентные методы.

 

Важность прямых методов неоспорима, т.к. в практических задачах информация о значениях целевой функции является единственно надежной информацией, которой располагает инженер. Однако, если существует и непрерывны целевая функция f(x) и ее первые производные, a также они могут быть записаны в аналитическом виде (или с достаточно высокой точностью вычислены при помощи численных методов), то целесообразно использовать методы, основанные на использовании градиента целевой функции.

Все методы основаны на итерационной процедуре, реализуемой в соответствии с формулой

 

xk+1 = xk + a k s(xk),

 

где xk - текущее приближение к решению x*;

a k - параметр, характеризующий длину шага,

s(xk) - направление поиска в N - мерном пространстве управляемых переменных xi, i = 1, 2,..., N.

Способ определения a k и s(xk) на каждой итерации связан с особенностями применяемого метода. Обычно выбор a k осуществляется путем решения задачи минимизации f(x) в направлении s(xk). Поэтому при реализации градиентных необходимо использовать эффективные алгоритмы одномерной минимизации.

Простейший градиентный метод

В основе метода лежит следующая итерационная модификация формулы

 

xk+1 = xk + a k s(xk),

xk+1 = xk - a k Ñ f(xk),

 

где a - заданный положительный коэффициент;

Ñ f(xk) - градиент целевой функции первого порядка.

Недостатки:

• необходимость выбора подходящего значения a ;
• медленная сходимость к точке минимума ввиду малости Ñf(xk) в окрестности этой точки.

Метод наискорейшего спуска

Свободен от первого недостатка простейшего градиентного метода, т.к. ak вычисляется путем решения задачи минимизации Ñ f(xk) вдоль направления Ñ f(xk) с помощью одного из методов одномерной оптимизации

 

xk+1 = xk - a k Ñ f(xk).

 

Данный метод иногда называют методом Коши.

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

Метод сопряженных направлений

Общая задача нелинейного программирования без ограничений сводится к следующему: минимизировать f(x), xÎEn, где f(x) является целевой функцией. При решении этой задачи мы используем методы минимизации, которые приводят к стационарной точке f(x), определяемой уравнением Ñf(x*)=0.

Метод сопряженных направлений относится к методам минимизации без ограничений, использующим производные. Задача: минимизировать f(x), xÎEn, где f(x) является целевой функцией n независимых переменных.

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

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

 

1.3 Методы второго порядка

 

Метод Ньютона

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

 

xk+1 = xk - Ñ2 f(xk-1) Ñ f(xk).

 

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

 

xk+1 = xk - ak Ñ2 f(xk-1) Ñ f(xk),

 

где ak - параметр, выбираемый таким образом, чтобы f(xk+1) ® min.

 

 

2. Нахождение экстремума  функции без ограничения

 

2.1 Метод наискорейшего  спуска

 

Алгоритм данного метода отражается поисковой формулой:

 

 (2.1)

 

где k – номер итерации, S – направление, в котором делается следующая итерации, - величина шага в этом направлении. Знак « - » берется при поиске минимума. Если двигаться не в произвольном направлении S, а по градиенту, то формула выглядит так:

 

 (2.2)

 

где - градиент функции.

Градиент функции в некоторой точке – вектор, показывающий направление наибольшей скорости увеличения функции

 

.

 

Дана функция:

с начальной точкой .

Воспользуемся теоремой Ферма для определения экстремума:

 

 (2.3)

 

Решим полученную систему:

 

=> , точка - точка безусловного экстремума.

 

1) Найдем градиент функции в точке :

 

 

Оптимальную величину шага можно найти по формуле:

 

, (2.4) где Н – матрица Гессе.

 

Матрицу Гессе определяется по формуле:

 

 (2.5)

 

Тогда получаем: .

Найдем величину оптимального шага:

 

 

 

Подставим все найденные значения в формулу (2.2) и найдем координаты точки :

Получили новую точку с координатами

Проверка:

 

 

2) Точку примем за начальную:

 

 

Найдем оптимальную величину шага:

Находим с помощью величины шага:

 

 

Получили новую точку с координатами

Проверка:

 

 

3) Точку примем за начальную: