Классические методы оптимизации

 

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Алтайская государственная педагогическая академия»

ФГБОУ ВПО «АлтГПА»

Кафедра математического анализа и прикладной математики

Курсовая работа

по дисциплине «Математическое моделирование»

Классические методы оптимизации

Выполнила:

студентка 3 курса, 306 группы

Черпакова Надежда Анатольевна

Научный руководитель:

к. ф.-м. н., доцент

Холодков А.В.

Барнаул - 2013

Оглавление

Введение

.Классические методы безусловной оптимизации

.1Необходимое и достаточное условие существования экстремума функций одной переменной

.2Необходимое и достаточное условие существования экстремума функций нескольких переменных

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

.1Правило множителей Лагранжа. Необходимые условия оптимальности

.2Достаточные условия оптимальности

3.Практическая часть

3.1 Безусловная оптимизация

3.2 Метод Лагранжа

Заключение

Список литературы

Введение

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

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

Цель данной курсовой работы - изучить классические методы оптимизации и разобрать примеры с применением изученных методов.

Задачи:

-описать основную теорию;

-рассмотреть решения некоторых примеров.

1.Классические методы безусловной оптимизации.

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

.1 Необходимое и достаточное условие существования экстремума функций одной переменной

Определение 1.1. Функция f(x) одной переменной имеет локальный минимум в точке x, если существует , такая, что для всех , то есть если существует некоторая окрестность точки , в которой значение функции в любой ее точке больше, чем [1].

Определение 1.2. Функция имеет глобальный минимум в точке , если для всех x из области определения f(x) [1].

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

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

В точках и производная меняет знак с отрицательного на положительный, в - с положительного на отрицательный, в точке производная знак не меняет. Следовательно, в точке минимума производная является возрастающей функцией. Степень же возрастания измеряется второй производной, то есть в нашем случае , , . Однако если , то ситуация остается неопределенной[2].

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

Если - точка минимума, то для любого достаточно малого h.

Если , то отрицательное h сделает отрицательной разность , что невозможно в точке минимума. Если , то произойдет то же самое, если выбрать положительное h. Следовательно, - это необходимое условие существования минимума в точке .

Так как всегда, то при и всегда выполняется , то есть - точка минимума, а при , (h - любое) и - точка максимума. Следовательно, это достаточные условия.

Если же , то рассуждения, аналогичные проведенным для первой производной, можно повторить для и так далее [2].

Это позволяет сформулировать следующее правило:

Теорема 1 (необходимое и достаточное условие существования экстремума функций одной переменной).

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

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

1.2 Необходимое и достаточное условие существования экстремума функций нескольких переменных

безусловный оптимизация лагранж экстремум

Рассмотрим функцию n действительных переменных. Введем матричные обозначения для точки в n-мерном пространстве, градиента (вектора частных производных первого порядка функции f) и гессиана (матрицы частных производных второго порядка):

- точка в n-мерном пространстве,

- градиент,

- гессиан (матрица Гессе).

- элемент G(X) - частная производная второго порядка. G(X) - симметрическая матрица [2].

Определение 3. Функция имеет локальный минимум в точке , если существует окрестность точки , такая, что во всех точках этой окрестности, то есть существует такая d>0, что для всех справедливо [1].

Определение 4. Если для всех X из области определения функции f, то - точка глобального минимума[1].

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

Запишем разложение функции в ряд Тейлора:

.

Тогда, если - точка минимума функции , то каждая первая частная производная , должна обращаться в ноль в точке , иначе соответствующим выбором H можно будет добиться того, что разность , будет отрицательна [2].

Необходимое условие существования минимума в точке :

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

.

Тогда знак разности , определяется членом , который положителен для всех H, если матрица G() положительно определена, и отрицателен при отрицательно определенном гессиане [3].

Достаточное условие:

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

если - положительно определена, то - минимум;

если - отрицательно определена, -максимум.

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

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

Задача условной оптимизации заключается в поиске минимального или максимального значения скалярной функции f(x) n-мерного векторного аргументах при заданных ограничениях[5].

.1 Правило множителей Лагранжа. Необходимые условия оптимальности

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

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

Задача условной оптимизации формулируется следующим образом:

f (x) = f (x1, x2, ..., xn) Þextr, (1)

j i (x) = j i(x1, x2, ..., xn) = 0, , m < n. (2)

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

(3)

(где - множители Лагранжа), а именно: если x* - локальное решение задачи, то существует вектор такой, что

, (4)

где - вектор производных от функции Лагранжа по компонентам вектора х [6].

Любая точка x*, удовлетворяющая при некотором ??* условию (4), а также условиям допустимости (2), называется стационарной точкой задачи (1). Как и в случае безусловной задачи оптимизации, стационарные точки не обязаны быть решениями задачи. Здесь также существуют достаточные условия оптимальности с привлечением вторых производных [6].

2.2 Достаточные условия оптимальности

Если функции f, j1, j2,..., jm дважды дифференцируемы в допустимой точке x* Î Rn (удовлетворяющей системе (2)) и при некотором * выполняются условия:

,

а также условия

(5)

при всех ненулевых hÎ Rn, удовлетворяющих условиям

(6)

то x* - строгий локальный минимум (максимум) задачи (1).

В условиях (5) - матрица вторых производных функции Лагранжа по координатам вектора х [6].

Последовательность решения методом Лагранжа:

) формируем функцию Лагранжа (3);

) находим вектор первых производных функции Лагранжа;

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

) решаем полученную систему (результаты удобно привести в таблице);

) находим матрицу вторых производных функции Лагранжа и вектор h;

) находим произведение матрицы на вектор h. Это вектор, r-й компонент которого равен скалярному произведению r-й строки матрицы на вектор-сомножитель;

) находим скалярное произведение векторов и h для выяснения смысла условия (5).

Таким образом, находим локальный минимум, и локальный максимум [5].

3.Практическая часть

.1 Безусловная оптимизация

Пример 1. Функция Коши f(x)= (f(0)=0) имеет при x=0 производные всех порядков, причем все они равны нулю. Хотя при x=0 эта функция имеет минимум, установить этот факт с помощью правила

максимум при f '(a)=0 и f ''(a)<0,

минимум при f '(a)=0 и f ''(a)>0. (1)

невозможно. С помощью же правила:

Если производная f '(x) при переходе через стационарную точку а меняет

знак + на -, то налицо максимум,

знак - на +, то налицо минимум. (2)

Если f '(x) знака не меняет, то экстремума нет.

это удается сделать:

f '(x)= ,

слева от нуля f '(x)<0, а справа от нуля f '(x)>0.

По правилу (2) в точке x=0 функция f (x) обращается в минимум.

Пример 2. Найти экстремумы функции f(x) = x3(x2 - 1) при -1?x?2.

Необходимое условие оптимальности:

f '(x)=5x4 - 3x2 = x2(5x2 - 3) = 0.

Корни этого уравнения: х=0, . Присоединяя к ним граничные значения х= -1 и х=2, получаем пять стационарных точек:1 = - 1, x2 = - 0,775, x3 = 0, x4 = 0,775, x5 = 2.

Поскольку f '(x1) >0 и f '(x5) >0, в точке x1 - граничный минимум, в точке x5 - граничный максимум. Далее, в точке x2 вторая производная

следовательно, это точка локального максимума, в точке x4 производная''(x4) = 4,66>0,

значит, это точка локального минимума. Далее, в точке x3:''(x3) =0, f '''(x3) ?0

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

Пример 3. Найти экстремумы функции двух переменных= 3x3 - x+ y3 - 3y2 - 1.

Необходимые условия оптимальности:

Решение системы:

Координаты четырех стационарных точек приведены в таблице:

Координаты стационарной точкиНомер стационарной точки j1234xjyj0022

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

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

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

ПараметрНомер стационарной точки, j1234Собственые значенияl?6-666l?-6-66-6Характер extrextr нетmaxminextr нет

3.2 Метод Лагранжа

Пример 1. Найти локальные решения задачи

Последовательность решения:

) формируем функцию Лагранжа

2) находим вектор первых производных функции Лагранжа

3) формируем систему уравнений для отыскания координат стационарных точек

или

4) решаем полученную систему, результаты приведены в таблице:

Координаты стационарной точкиНомер стационарной точки, j123x1j01x2j10y j

5) находим матрицу вторых производных функции Лагранжа

Для стационарных точек 1-3 эта матрица принимает соответственно следующий вид:

, , ;

б) находим вектор h, уравнения в данном случае он выглядит так:

.

Результаты его решения приведены в таблице:

Значения компонентов вектора hНомер стационарной точки, j123h1j¹0=0¹0h2j=0¹0(ah11, 0)(0,bh22)(-ah13, -bh23)

7) находим произведение матрицы на вектор h (см. третью строку таблицы). Это вектор, r-й компонент которого равен скалярному произведению r-й строки матрицы на вектор-сомножитель;

) находим скалярное произведение векторов и h для выяснения смысла условия :

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

Заключение

Цель данной курсовой работы была - изучить методы одномерной оптимизации и разобрать примеры с применением данных методов.

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

-описана основная теория;

-рассмотрены решения некоторых примеров с применением данных методов.

Список литературы

1.Фихтенгольц Г.М., Курс дифференциального и интегрального исчисления <http://www.alleng.ru/d/math/math169.htm>, М.: ФИЗМАТЛИТ, 2001. т.1

.Банди Б. Методы оптимизации. Вводный курс. - М.: Радио и связь, 1988.

.А.В. Аттетков, С.В. Галкин, В.С. Зарубин, «Методы оптимизации», Издательство МГТУ им. Н.Э. Баумана, 2003.

.С.А. Шипилов, Методы безусловной многомерной оптимизации, НФИ КемГУ - Новокузнецк, 2000.

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

.Сухарев А.Г., Тимохов А.В., Федоров В.В., Курс методов оптимизации, 2-е изд., М.:ФИЗМАТЛИТ, 2005.

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

Больше работ по теме: