Xreferat.com » Рефераты по математике » Сравнительный анализ методов оптимизации

Сравнительный анализ методов оптимизации

Министерство образования и науки Республики Казахстан

Карагандинский Государственный Технический Университет

Кафедра САПР


ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовой работе

по дисциплине "Теория принятия решений"

Тема: "Сравнительный анализ методов оптимизации"


Руководитель:

(подпись) (дата)

Студент:

(группа)

_____________________

(подпись) (дата)


Караганда 2009

Сравнительный анализ методов оптимизацииСодержание


Введение

1. Формулировка математической задачи оптимизации. Основные понятия

1.1 Формулировка математической задачи оптимизации

1.2 Минимум функции одной переменной

1.3 Минимум функции многих переменных

1.4 Унимодальные функции

1.5 Выпуклые функции

2. Прямые методы безусловной оптимизации

2.1 Прямые методы одномерной безусловной оптимизации

2.1.1 Метод деления отрезка пополам (дихотомии)

2.1.2 Метод золотого сечения

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

2.2 Методы безусловной минимизации функций многих переменных

2.2.1 Метод циклического покоординатного спуска

2.2.2 Алгоритм Хука-Дживса

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

2.2.4 Минимизация по правильному симплексу

2.2.5 Поиск точки минимума по деформируемому симплексу

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

3. Условная оптимизация

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

Заключение

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

Введение


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

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

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


1. Формулировка математической задачи оптимизации. Основные понятия


1.1 Формулировка математической задачи оптимизации


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

Под минимизацией (максимизацией) функции n переменных f (x) = (x1,.., xn) на заданном множестве U n-мерного векторного пространства Еn понимается определение хотя бы одной из точек минимума (максимума) этой функции на множестве U, а также, если это необходимо, и минимального (максимального) на множестве U значения f (x). При записи математических задач оптимизации в общем виде обычно используется следующая символика:


f (x) ®min (max),

хО U


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

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

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

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


1.2 Минимум функции одной переменной


Пусть функция f (x) определена на множестве U вещественной оси R.

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

Значение f * = f (x*) = Сравнительный анализ методов оптимизации называют глобальным (абсолютным) минимумом или просто минимумом функции f (x) на множестве U.

Множество всех точек минимума f (x) на U в дальнейшем будет обозначено через U*.

2. Число Сравнительный анализ методов оптимизации ОU называется точкой локального минимума функции f (x), если Сравнительный анализ методов оптимизациидля всех xОU, достаточно близких к Сравнительный анализ методов оптимизации, т.е. если существует e > 0 такое, что это неравенство выполняется для любогоСравнительный анализ методов оптимизацииСравнительный анализ методов оптимизации.

Глобальный минимум f (x) является и локальным минимумом, а обратное неверно.


1.3 Минимум функции многих переменных


Будем рассматривать функции многих переменных f =f (x1, …, xn) как функции, заданные в точках х n-мерного евклидова пространства Еn: f =f (х).

1. Точка х*ОЕn, называется точкой глобального минимума функции f (х), если для всех х*ОЕn выполняется неравенство f (x*) Ј f (х). Значение f (x*) = =Сравнительный анализ методов оптимизации называется минимумом функции. Множество всех точек глобального минимума функции f (х) будем обозначать через U*.

2. Точка Сравнительный анализ методов оптимизации называется точкой локального минимума функции f (х), если существует e-окрестность точки Сравнительный анализ методов оптимизации: Un (Сравнительный анализ методов оптимизации) ={x | r (x, Сравнительный анализ методов оптимизации) < e} такая, что для всех х*ОUn (Сравнительный анализ методов оптимизации) выполняется неравенство f (Сравнительный анализ методов оптимизации) Ј f (х).

3. Если допустимое множество U в задаче минимизации (максимизации) функции n переменных совпадает со всем пространством En, то говорят о задаче безусловной оптимизации

Сравнительный анализ методов оптимизации, x О En.


1.4 Унимодальные функции


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

Функция f (x) называется унимодальной на отрезке [а; b], если она непрерывна на [а; b] и существуют числа a и b, Сравнительный анализ методов оптимизации, такие, что:

1) если а < a, то на отрезке [a; a] функция f (x) монотонно убывает;

2) если b < b, то на отрезке [b; b] функция f (x) монотонно возрастает;

3) при х О [a; b] f (x) =f * = Сравнительный анализ методов оптимизации.

Множество унимодальных на отрезке [а; b] функций мы будем обозначать через Q [а; b]. Отметим, что возможно вырождение в точку одного или двух отрезков из [a; a], [a; b] и [b; b]. Некоторые варианты расположения и вырождения в точку отрезков монотонности и постоянства унимодальной функции показаны на рисунке 1.


Сравнительный анализ методов оптимизации

Рисунок 1 - Некоторые варианты расположения и вырождения в точку отрезков монотонности и постоянства унимодальной функции


Основные свойства унимодальных функций:

1. Любая из точек локального минимума унимодальной функции является и точкой ее глобального минимума на отрезке [а; b].

2. Функция, унимодальная на отрезке [а; b], является унимодальной и на любом меньшем отрезке [с; d] Сравнительный анализ методов оптимизации [а; b].

3. Пусть f (x) Сравнительный анализ методов оптимизацииQ [а; b] и Сравнительный анализ методов оптимизации. Тогда:


если Сравнительный анализ методов оптимизации, то x* Сравнительный анализ методов оптимизации [a; x2] ;

если Сравнительный анализ методов оптимизации, то x* Сравнительный анализ методов оптимизации [x1; b],


где х* - одна из точек минимума f (x) на отрезке [a; b].


1.5 Выпуклые функции


Функция f (x), заданная на отрезке [a; b], называется выпуклой на этом отрезке, если для всех х', х" Сравнительный анализ методов оптимизации [а; b] и произвольного числа Сравнительный анализ методов оптимизации [0; 1] выполняется неравенство


f [ax'+ (1- a) x"] Ј af (x') + (l - a) f (x"). (1)


Перечислим основные свойства выпуклых функций.

Если функция f (x) выпукла на [a; b], то на любом отрезке [х'; х"] М [a; b] ее график расположен не выше хорды, проведенной через точки графика с абсциссами х' и х" (рисунок 2).


Сравнительный анализ методов оптимизации

Рисунок 2 - Взаимное расположение Сравнительный анализ методов оптимизации


Пусть х' и х" - произвольные точки отрезка [a; b], причем х' < х". Легко проверить, что при любом a О [0; 1] точка xa = ax’ + (1-a) x" лежит на отрезке [x’; х"] и при непрерывном изменении a от 0 до 1 пробегает этот отрезок от точки х" (при a = 0) до точки x' (при a = 1).

Рассмотрим хорду графика f (x), проходящую через точки (х',f (х')) и (х",f (х")). Ордината ya точки этой хорды, соответствующая абсциссе c, равна. Поэтому неравенство (1) графика выпуклой функции и хорды означает, что f (xa) Ј ya, т.е. при любом расположении xa, на отрезке [х'; х"] точка графика функции f (x) лежит не выше соответствующей точки хорды.

2. Из курса математического анализа известны следующие условия выпуклости функции:

а) для того чтобы дифференцируемая на отрезке [а; b] функция f (x) была выпуклой на этом отрезке, необходимо и достаточно, чтобы производная f ' (x) не убывала на [а; b] ;

б) для того чтобы дважды дифференцируемая на отрезке [а; b] функция f (x) была выпуклой на этом отрезке, необходимо и достаточно, чтобы при всех хО [а; b] выполнялось неравенство f " (x) і 0.

3 Условие выпуклости для дифференцируемой на отрезке [а; b] функции f (x) означает, что на этом отрезке любая касательная к графику f (x) лежит не выше этого графика (рисунок 3).


Сравнительный анализ методов оптимизации

Рисунок 3 - условие выпуклости


Уравнение касательной к графику f (х) в точке (x0, f (x0)), x0 О [а; b] имеет вид: у (х) =f (x0) +f ’ (x0) (x-x0). По формуле конечных приращений для любого хО [а; b] имеем: f (х) =f (x0) +f ’ (x) (x-x0), где точка x лежит между x и x0. Поэтому


f (х) - у (х) = [f ’ (x) - f ’ (x0)] (x-x0), хО [а; b],


откуда с учетом того, что производная f ’ (x) выпуклой функции не убывает, получаем:


f (x) -y (x) і 0 (2)


для всех хО [а; b].

4. Если f (x) - выпуклая дифференцируемая на отрезке [а; b] функция и в точке х* О [а; b] выполняется равенство


f ’ (x*) = 0 (3)


то х* является точкой глобального минимума f (х) на [а; b].

С учетом (3) уравнение касательной у (х) =f (х0) +f ’ (х0) (х-х0) к графику f (x) для точки x0 =х* принимает вид у (х) =f (x*). Поэтому из (2) следует, что f (x) Сравнительный анализ методов оптимизацииf (x*) для всех хО [а; b], т.е. х* - точка глобального минимума f (x).

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

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

5. Можно показать, что всякая выпуклая непрерывная на отрезке [а; b] функция является и унимодальной на этом отрезке. Обратное, вообще говоря, неверно (рисунок 4).


Сравнительный анализ методов оптимизации

Рисунок 4 - график унимодальной, но не выпуклой функции


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

2. Прямые методы безусловной оптимизации


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

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

Рассмотрим наиболее распространенные на практике прямые методы поиска точки минимума. Самым слабым требованием на функцию f (х), позволяющим использовать эти методы, является ее унимодальность. Поэтому далее будем считать функцию f (х) унимодальной на отрезке [а; b].

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

2.1 Прямые методы одномерной безусловной оптимизации


Методы исключения отрезков

Пусть а < x1<х2<b. Сравнив значения f (x) в точках x1 и х2 (пробных точках), можно сократить отрезок поиска точки х *, перейдя к отрезку [а; х2], если Сравнительный анализ методов оптимизации или к отрезку m [x1; b] если Сравнительный анализ методов оптимизации (рисунок 5). Описанную процедуру можно повторить необходимое число раз, последовательно уменьшая отрезок, содержащий точку минимума. Когда длина последнего из найденных отрезков станет достаточно малой, следует положить Сравнительный анализ методов оптимизации, где Сравнительный анализ методов оптимизации - одна из точек этого отрезка, например, его середина. Методы минимизации, основанные на этом принципе, называются методами исключения отрезков.

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


Сравнительный анализ методов оптимизации

Рисунок 5 - Уменьшение отрезка поиска точки минимума методами исключения отрезков


2.1.1 Метод деления отрезка пополам (дихотомии)

Суть метода заключается в том, что заданный отрезок [а; b] делится пополам:


Сравнительный анализ методов оптимизации.


Затем в каждой из половин отрезка [а; с] и [с; b] выбираются по одной точке x1 и х2, в них вычисляются значения функций, производится сравнение полученных значений, и в результате сравнения устанавливается отрезок, в котором минимума быть не может. Откинув его, продолжаем ту же процедуру с полученным отрезком до тех пор, пока вновь полученный отрезок не станет меньше по длине некоторой наперед заданной величины:


Сравнительный анализ методов оптимизации.


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


Сравнительный анализ методов оптимизации (4)


где d > 0 - малое число.

В конце вычислений по методу дихотомии в качестве приближенного значения х* берут середину последнего из найденных отрезков [а; b], убедившись предварительно, что достигнуто неравенство Сравнительный анализ методов оптимизации.

Опишем алгоритм метода деления отрезка пополам.

Шаг 1. Определить середину отрезка и значения x1 и х2 по формулам (4). Вычислить f (x1) и f (x2).

Шаг 2. Сравнить f (x1) и f (x2). Если Сравнительный анализ методов оптимизации, то перейти к отрезку [а; x2], положив b = x2, иначе - к отрезку [x1; b], положив а = x1.

Шаг 3. Найти достигнутую точность Сравнительный анализ методов оптимизации. Если Сравнительный анализ методов оптимизации то перейти к следующей итерации, вернувшись к шагу 1. Если Сравнительный анализ методов оптимизации, то завершить поиск х*, перейдя к шагу 4.

Шаг 4. Положить


Сравнительный анализ методов оптимизации.


Замечания:

1. Число d из (4) выбирают на интервале (0; 2e) с учетом следующих соображений:

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

б) при чрезмерно малом d сравнение значений f (x) в точках x1 и х2, отличающихся на величину d, становится затруднительным. Поэтому выбор d должен быть согласован с точностью определения f (x) и с количеством верных десятичных знаков при задании аргумента х.

Пусть Сравнительный анализ методов оптимизации - погрешность счета. Тогда следует учитывать следующее условие:


Сравнительный анализ методов оптимизации.


2.1.2 Метод золотого сечения

Рассмотрим такое симметричное расположение точек x1 и х2 на отрезке [а; b], при котором одна из них становится пробной точкой и на новом отрезке, полученном после исключения части исходного отрезка. Использование таких точек позволяет на каждой итерации метода исключения отрезков, кроме первой, ограничиться определением только одного значения f (x), так как другое значение уже найдено на одной из предыдущих итераций.

Найдем точки x1 и х2, обладающие указанным свойством.

Рассмотрим сначала отрезок [0; 1] и для определенности предположим, что при его уменьшении исключается правая часть этого отрезка. Пусть х2 = t, тогда симметрично расположенная точка х1 = 1-t (рисунок 6).


Сравнительный анализ методов оптимизации

Рисунок 6 - Определение пробных точек в методе золотого сечения


Пробная точка х1 отрезка [0; 1] перейдет в пробную точку х2ў = 1-t нового отрезка [0; t]. Чтобы точки х2 = t, и х2ў = 1-t делили отрезки [0; 1] и [0; t] в одном и том же отношении, должно выполняться равенство Сравнительный анализ методов оптимизации или Сравнительный анализ методов оптимизации, откуда находим положительное значение


Сравнительный анализ методов оптимизации…


Таким образом,


х1 = 1-t = Сравнительный анализ методов оптимизации, Сравнительный анализ методов оптимизации.


Для произвольного отрезка [а; b] выражения для пробных точек примут вид


Сравнительный анализ методов оптимизации; Сравнительный анализ методов оптимизации. (5)


Замечания:

1. Точки x1 и х2 из (5) обладают следующим свойством: каждая из них делит отрезок [а; b] на две неравные части так, что отношение длины всего отрезка к длине его большей части равно отношению длин большей и меньшей частей отрезка. Точки с таким свойством называются точками золотого сечения отрезка [а; b]. Это и объясняет название рассматриваемого метода.

2. На каждой итерации исключения отрезков с пробными точками (5) одна из них Сравнительный анализ методов оптимизации переходит на следующий отрезок и значение f (x) в этой точке вычислять не следует. Если новым отрезком становится [а; х2], то на него переходит пробная точка Сравнительный анализ методов оптимизации исходного отрезка, становясь его второй пробной точкой (х2’= х1) (рисунок 6). В случае перехода к отрезку [х1; b] пробная точка Сравнительный анализ методов оптимизации исходного отрезка становится первой пробной точкой отрезка [х1; b].

3. Легко проверить, что х1=а+b-х2, и x2=а+b-х1. Поэтому на каждой итерации метода золотого сечения недостающую пробную точку нового отрезка можно найти по перешедшей на него пробной точке с помощью сложения и вычитания, не используя формул (5).

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


Сравнительный анализ методов оптимизации.


Опишем алгоритм метода золотого сечения.

Шаг 1. Найти х1 и х2 по формулам (5). Вычислить f (x1) и f (x2).

Шаг 2. Определить Сравнительный анализ методов оптимизации. Проверка на окончание поиска: если en > e, то перейти к шагу 3, иначе - к шагу 4.

Шаг 3. Переход к новому отрезку и новым пробным точкам. Если f (x1) Ј f (x2) то положить b=x2, x2=x1, f (x2) Ј f (x1), x1=b-t (b-a) и вычислить f (x1), иначе - положить a=x1, x1= x2, f (x1) = f (x2), x2=b+t (b-a) и вычислить f (x2). Перейти к шагу 2.

Шаг 4. Окончание поиска: положить


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

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

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

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