Xreferat.com » Рефераты по информатике и программированию » Анализ методов определения минимального, максимального значения функции при наличии ограничений

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

Размещено на /

Федеральное агентство по образованию

Московский государственный открытый университет

Чебоксарский политехнический институт


Курсовой проект

по дисциплине: "Оптимальные системы автоматического управления"

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


Выполнил:

студент 5 курса,

ФУИТС, гр. И-52/06,

Терсенидис М. Г.

Проверила:

Изосимова Т. А.


Чебоксары – 2010

Задание


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


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


где a = 1, b = 0.5, c = 1, d = 0, e = 1, f = 0.333.

Дана начальная точка поиска A0(x0, y0), где x0 = 0.5, y0 = 2.5.

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

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

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

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


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


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


1.5x + у – 3.75 ≥ 0;

0.5х + у - 3.75 ≤ 0;

x - у - 2 ≤ 0.


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


Анализ методов определения минимального, максимального значения функции при наличии ограничений, где k = 4, T1 = 10, T2 = 5.

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

провести исследование ОСАУ с применением программного продукта "20-sim Pro 2.3";

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


Содержание


Введение

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

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

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

4. Нахождение экстремума функции при наличии ограничений

5. Синтез оптимальной по быстродействию системы с помощью принципа максимума Понтрягина

Заключение

Список использованной литературы

Приложение

функция переменная экстремум максимум

Введение


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

В настоящее время для решения оптимальных задач применяют в основном следующие методы:

методы исследования функций классического анализа;

методы, основанные на использовании неопределенных множителей Лагранжа;

вариационное исчисление;

динамическое программирование;

принцип максимума;

линейное программирование;

нелинейное программирование.

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

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

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

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


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


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

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

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

градиентные методы, в которых используются точные значения первых производных f (x);

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

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

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

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

не требуют явного выражения целевой функции в аналитическом виде;

может требовать более значительных затрат времени по сравнению с методами, основанными на производных.

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

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

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

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

сравнительная простота логической структуры метода и, соответственно, программы для ЭВМ;

используется сравнительно небольшое число заранее установленных параметров;

невысокий уровень требований к ЭВМ;

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

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

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

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

не существует простого способа расширения симплекса. Требуется перерасчет значений целевой функции во всех точках образца.

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

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

Градиент функции F(x) – это вектор, составляющие которого равны частным производным функции F(x) по соответствующим переменным, т.е.


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


Направление вектора градиента совпадает с направлением наискорейшего возрастания функции. Вектор противоположного знака -F(x) называется антиградиентом, его направление совпадает с направлением наискорейшего убывания функции.

Матрица вторых производных 2F(x) – это симметричная квадратная матрица порядка n вторых частных производных функции F(x). Эту матрицу называют матрицей Гессе и обозначают H(x) 2F(x). Ее элемент, расположенный на пересечении i-й строки и j-го столбца, равен:


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


Пусть хТ=[x1, x2,…, xn] – вектор переменных. Для наличия в точке x* локального минимума (максимума) необходимо, чтобы выполнялось равенство F(x*) 0 и матрица Гессе H(x*) 2F(x*) была положительно (отрицательно) полуопределенной, т.е. xTHx 0 ( xTHx 0).

Достаточным условием существования минимума (максимума) в точке x* является положительная (отрицательная) определённость матрицы Гессе в этой точке, т.е. xTHx >0 ( xTHx<0).

Все методы основаны на итерационной процедуре, реализуемой в соответствии с формулой xk+1 = xk + k s(xk), где

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

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

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

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

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

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


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

xk+1 = xk -  k  f(xk), где


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

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

Недостатки:

необходимость выбора подходящего значения ;

медленная сходимость к точке минимума ввиду малости f(xk) в окрестности этой точки.

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

Свободен от первого недостатка простейшего градиентного метода, т.к. k вычисляется путем решения задачи минимизации  f(xk) вдоль направления  f(xk) с помощью одного из методов одномерной оптимизации xk+1 = xk -  k  f(xk).

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

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

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

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

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

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

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


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


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


xk+1 = xk - k 2 f(xk-1)  f(xk), где


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


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


Дана некоторая функция f(х) на открытом интервале (а, в) изменения аргумента х. Предполагаем, что exst внутри этого интервала существует (нужно сказать, что в общем случае математически заранее это утверждать не могут; однако в технических приложениях очень часто наличие exst внутри некоторого интервала изменения интервала изменения аргумента может быть предсказано из физических соображений).

Определение exst. Функция f(x) заданная на интервале (а, в) имеет в точке x* max(min), если эту точку можно окружить таким интервалом (x*-ε, x*+ε), содержащимся в интервале (а, в), что для всех ее точек х, принадлежащих интервалу (x*-ε, x*+ε), выполняется неравенство:


f(x) ≤ f(x*) → для max

f(x) ≥ f(x*) → для min

Это определение не накладывает никаких ограничений на класс функций f(x), что, конечно, очень ценно.

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

Теорема Ферма. Пусть функция f(x) определена в некотором интервале (а, в) и в точке "с" этого интервала принимает наибольшее (наименьшее) значение. Если существует в этой точке двухсторонняя конечная производная Анализ методов определения минимального, максимального значения функции при наличии ограничений, то существования необходимо exst Анализ методов определения минимального, максимального значения функции при наличии ограничений.

Примечание. Двухсторонняя производная характеризуется свойством Анализ методов определения минимального, максимального значения функции при наличии ограничений иными словами, речь идет о том, что в точке "с" производная в пределе одна и та же при подходе к точке "с" слева и справа, т.е. f(x) – гладкая функция.

*В случае Анализ методов определения минимального, максимального значения функции при наличии ограничений имеет место min, а при Анализ методов определения минимального, максимального значения функции при наличии ограничений → max. Наконец, если при х=х0 Анализ методов определения минимального, максимального значения функции при наличии ограничений, то использование 2-ой производной не помогает и нужно воспользоваться, например, определением exst.

При решении задачи I необходимые условия exst (т.е. теорема Ферма) используется очень часто.

Если уравнение exst Анализ методов определения минимального, максимального значения функции при наличии ограничений имеет вещественные корни, то точки, соответствующие этим корням, являются подозрительными на exst (но не обязательно самыми экстремумами, ибо имеем дело с необходимыми, а не с необходимыми и достаточными условиями). Так, например, в точке перегиба Хп имеет место Анализ методов определения минимального, максимального значения функции при наличии ограничений, однако, как известно, это не экстремум.


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


Заметим ещё, что:

из необходимых условий нельзя сказать, какой вид экстремума найден max или min: для определения этого нужны дополнительные исследования;

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

Поэтому, когда находят точки подозрительные на exst, их дополнительно исследуют, например, на основе определения exst или 2-ой производной.

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

Метод наискорейшего спуска является градиентным методом с переменным шагом. На каждой итерации величина шага ak выбирается из условия минимума функции f(x) в направлении спуска, т.е.


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


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


j (a)=f (x(k)-aСf (x(k)))


Воспользуемся для этого методом золотого сечения.

Алгоритм метода наискорейшего спуска состоит в следующем.

Задаются координаты начальной точки x(0).

В точке x(k), k = 0, 1, 2, …, вычисляется значение градиентаСf (x(k)).

Определяется величина шага ak путем одномерной минимизации по a функции


j (a)=f (x(k)-aСf (x(k))).


Определяются координаты точки x(k):


xi(k+1)= xi(k)-akСfi (x(k)), i=1, …, n.


Проверяется условие останова итерационного процесса:


||Сf (x(k+1))||Јe .


Если оно выполняется, то вычисления прекращаются. В противном случае осуществляется переход к п. 1. Геометрическая интерпретация метода наискорейшего спуска представлена на рис. 1.


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

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

Рис. 2.1. Блок схема метода наискорейшего спуска.


Реализация метода в программе:

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

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

Рис. 2.2. Реализация метода наискорейшего спуска.


Вывод: В нашем случае метод сошёлся за 7 итераций. Точка А7 (0,6641; -1,3313) является точкой экстремума. Метод сопряженных направлений. Для квадратичных функций можно создать градиентный метод, при котором время сходимости будет конечным и равно числу переменных n.

Назовем некоторое направление Анализ методов определения минимального, максимального значения функции при наличии ограничений и Анализ методов определения минимального, максимального значения функции при наличии ограничений сопряженными по отношению к некоторой положительно определенной матрице Гесса H, если выполняется:


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


Тогда Анализ методов определения минимального, максимального значения функции при наличии ограничений т.е. Анализ методов определения минимального, максимального значения функции при наличии ограничений. Значит при единичной H, сопряженное направление означает их перпендикуляр. В общем же случае H неединичная. В общем случае сопряженность - это применение матрицы Гесса к вектору Анализ методов определения минимального, максимального значения функции при наличии ограничений - означает поворот этого вектора на некоторый угол Анализ методов определения минимального, максимального значения функции при наличии ограничений и его растяжение или сжатие.


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


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


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


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

Рис. 2.3. Блок-схема метода сопряженных направлений.


Реализация метода в программе: Метод сопряженных направлений.


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

Рис. 2.4. Реализация метода сопряженных направлений.

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

Рис. 2.5. График метода сопряженных направлений.


Вывод: Точка А3 (0,6666; -1,3333), была найдена за 3 итерации и является точкой экстремума.


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


Напомним, что общая задача условной оптимизации выглядит так

f(x)  min, x 

где  — собственное подмножество Rm. Подкласс задач с ограничениями типа равенств выделяется тем, что множество  задается ограничениями вида


fi(x) = 0, где fi: Rm R (i = 1, …, k).


Таким образом, = {x  Rm: fi(x) = 0, i = 1, …, k}.

Нам будет удобно писать у функции f индекс "0". Таким образом, задача оптимизации с ограничениями типа равенств записывается в виде


f0(x)  min, (3.1)

fi(x) = 0, i = 1, …, k. (3.2)


Если обозначить теперь через f функцию на Rm со значениями в Rk, координатная запись которой имеет вид f(x) = (f1(x), …, fk(x)), то (3.1)–(3.2) можно также записать в виде


f0(x)  min, f(x) = .


Геометрически задача с ограничениями типа равенств — это задача о поиске наинизшей точки графика функции f0 над многообразием  (см. рис. 3.1).


Рис. 3.1.

Точки, удовлетворяющие всем ограничениям (т. е. точки множества ), обычно называют допустимыми. Допустимая точка x* называется условным минимумом функции f0 при ограничениях fi(x) = 0, i = 1, ..., k (или решением задачи (3.1)–(3.2)), если при всех допустимых точках x f0(x*)  f0(x). (3.3)

Если (3.3) выполняется только для допустимых x, лежащих в некоторой окрестности Vx* точки x*, то говорят о локальном условном минимуме. Естественным образом определяются понятия условных строгих локального и глобального минимумов.

Правило множителей Лагранжа

Описываемый ниже необходимый признак локального условного минимума был сформулирован Лагранжем. Определим F: Rm  Rk+1, положив F(x) = (f0(x), f1(x), ..., fk(x)). Заданная на RmЧRk+1 скалярная функция Лагранжа M по определению принимает значения в R и задается равенством


M(x, ) = (, F(x)) = Анализ методов определения минимального, максимального значения функции при наличии ограничений i fi(x) (x  Rm,  Rk+1).


Координаты вектора , т. е. числа k называются множителями Лагранжа или двойственными переменными. Оказывается, имеет место следующая теорема, часто именуемая правилом множителей Лагранжа:

Теорема. Пусть F  C1 и x* — локальный условный минимум функции f0 при ограничениях fi(x) = 0 (i = 1, ..., k). Тогда найдется ненулевой вектор * такой, что x* является стационарной точкой функции x M(x, *):


Mx(x, *)|x=x*=Анализ методов определения минимального, максимального значения функции при наличии ограничений*i f i(x*)= .


Правило множителей Лагранжа доставляет необходимое условие локального условного минимума и поэтому позволяет искать точки, "подозрительные" на экстремум. В самом деле, для нахождения точки (x*, *)  Rm+k+1, т. е. для нахождения m + k + 1 неизвестных, мы имеем m + k уравнений


f(x) = , Mx(x, )= .


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

Регулярные точки

Допустимая точка x задачи (3.1)–(3.2) называется регулярной, если векторы {f i(x)}ki=1линейно независимы. Оказывается, что если x* — регулярная точка минимума, то в векторе * можно считать *0 ненулевым, а поскольку множители Лагранжа определяются с точностью до множителя, можно считать, что *0 = 1. Чтобы сформулировать это утверждение более точно, введем следующие обозначения. Пусть   Rk, а функция Лагранжа в регулярном случае определяется равенством


L(x, Анализ методов определения минимального, максимального значения функции при наличии ограничений


Очевидно, L(x, где

Теорема (правило множителей Лагранжа в регулярном случае)

Пусть F  C1, а x* — регулярное локальное решение задачи (3.1)–(3.2). Тогда найдется ненулевой вектор *  Rk такой, что


L


Одно достаточное условие локального минимума

Говорят, что линейный оператор A положительно определен на подпространстве E, если (Ax, x) > 0 при всех x  E. Касательным подпространством к многообразию  в точке y называется множество Ty = {x  Rm: (f (y), x) = 0, i = 1, ..., k}. Касательной гиперплоскостью к многообразию  в точке y называется множество


y = {x  Rm: fi(y) + (f (y), xy) = 0, i = 1, ..., k}.


Теорема (достаточное условие минимума)

Пусть F  C2, а x* — регулярная стационарная точка функции Лагранжа, т. е., в частности, L(x*, *) =  при некотором ненулевом *  Rk. Тогда, если Lxx(x*, *)положительно определен на Tx*, то точка x* является локальным решением задачи (3.1)–(3.2).

Методы решения задач с ограничениями типа равенств

Мы будем рассматривать ниже только регулярный случай. Один из естественных подходов к решению задач типа (3.1)–(3.2) основывается на необходимом условии экстремума — правиле множителей Лагранжа. Если бы можно было утверждать, что решению x* задачи (3.1)–(3.2) соответствует экстремум (x*, *) функции Лагранжа L, то к функции L можно было бы применять разработанные методы решения безусловных задач. Однако, так утверждать нельзя. В самом деле,

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту

Похожие рефераты: