Формулировка Статистической Задачи Оптимизации Реферат
Формулировка Статистической Задачи Оптимизации Реферат
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
студентка 5 курса математического факультета
специальность 032100.01 – «Математика» с дополнительной
Научный руководитель: доцент, кандидат технических наук
Зав. кафедрой математического анализа _________________________
«___» _______ 2010 г., протокол №__
Глава I. Задача отыскания экстремума функций многих
переменных…............................................................................................
1.2 Необходимые условия второго порядка. Достаточные
В настоящее время оптимизация находит применение в науке, технике и в любой другой области человеческой деятельности.
Оптимизация
- целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях .
Поиски оптимальных решений привели к созданию специальных математических методов и уже в 18 веке были заложены математические основы оптимизации (вариационное исчисление, численные методы и др). Однако до второй половины 20 века методы оптимизации во многих областях науки и техники применялись очень редко, поскольку практическое использование математических методов оптимизации требовало огромной вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев - невозможно.
Оптимизация как раздел математики существует достаточно давно. Оптимизация - это выбор, т.е. то, чем постоянно приходится заниматься в повседневной жизни. Термином "оптимизация" в литературе обозначают процесс или последовательность операций, позволяющих получить уточненное решение. Хотя конечной целью оптимизации является отыскание наилучшего или "оптимального" решения, обычно приходится довольствоваться улучшением известных решений, а не доведением их до совершенства. По этому под оптимизацией понимают скорее стремление к совершенству, которое, возможно, и не будет достигнуто.
На первоначальном этапе решения принимались без специального математического анализа, просто на основе опыта и здравого смысла.
Практика порождает все новые и новые задачи оптимизации причем их сложность растет. Требуются новые математические модели и методы, которые учитывают наличие многих критериев, проводят глобальный поиск оптимума. Другими словами, жизнь заставляет развивать математический аппарат оптимизации.
Из всего выше сказанного можно сделать вывод об актуальности темы дипломной работы.
Объект исследования:
методы оптимизации как раздел математики.
Предмет исследования:
методы оптимизации первого порядка (градиентные методы) и второго порядка: методы Ньютона и Ньютона- Рафсона.
Цель работы:
изучить вопросы отыскания экстремума функции нескольких переменных, а также рассмотреть алгоритмы численных методов отыскания безусловного экстремума.
1. Изучить теорию нахождения безусловного и условного экстремумов функции нескольких переменных;
2. Рассмотреть задачи минимизации функции нескольких переменных;
3. Изучить численные методы решения задач поиска безусловного минимума функции.
В первой главе сделан анализ теоретического материала, посвященного пониманию природы задач оптимизации — выведены необходимые и достаточные условия, которым должна удовлетворять функция в экстремальных точках. Рассмотрен метод множителей Лагранжа.
Во второй главе изложены численные методы отыскания безусловного экстремума, рассмотрены алгоритмы и примеры градиентных методов оптимизации: градиентного спуска с постоянным шагом, наискорейшего градиентного спуска, покоординатного спуска. Также рассмотрены методы второго порядка: метод Ньютона и метод Ньютона-Рафсона.
Глава
I
. ЗАДАЧА ОТЫСКАНИЯ ЭКСТРЕМУМА ФУНКЦИИ
Одной из важных задач анализа является задача отыскания экстремума (наибольшего или наименьшего значения) скалярной функции f
(х)
n
-мерного векторного аргумента х
при некоторых ограничениях. Эту задачу мы будем записывать следующим образом:
Здесь X
—
некоторое подмножество n
-мерного евклидова пространства Е п
.
Будем называть X
допустимым множеством
задачи (1)—(2), а точки, принадлежащие X, — ее допустимыми точками.
Заметим, что задачу максимизации функции f
(х)
тоже можно записать в виде (1)-(2), заменив f
(х)
на
.
В этой главе будут последовательно рассмотрены задача нахождения безусловного экстремума функции нескольких переменных (Х=Е п
)
и задача на относительный экстремум,
т. е. задача минимизации функции нескольких переменных при наличии ограничений типа равенств, когда X
- множество решений уравнения
где g
(
x
)
есть m
-мерная вектор-функция, т<п.
Задача (1) - (2) является классической и рассматривается во всех курсах анализа. Теория решения таких задач развивалась еще в трудах Эйлера, Лагранжа, Бернулли, Лейбница. Она не потеряла своего значения и в настоящее время, несмотря на то, что с тех пор разработаны более общие методы, включающие классические, как частый случай. Классическая теория содержит значительную часть идей, лежащих в основе современных методов оптимизации.
1.1
Необходимое условие экстремума.
Рассмотрим задачу безусловной минимизации, будем теперь считать, что f
(х) —
скалярная функция векторного аргумента размерности п,
т. е. X
=
E n
. Если - точка ее безусловного локального экстремума, в
j
будет достигаться экстремум функции
одной переменной x j
,
которая получается из функции f
(
x
),
если зафиксировать все переменные, кроме x j
,
положив х
i
=
i
для .
Для функции же одной переменной
Теорема 1. Для того чтобы функция
f
(
x
), определенная на вещественной оси, имела безусловный локальный экстремум в точке
, необходимо, чтобы выполнялось условие
Проведя это рассуждение для всех j
= 1, ..., п,
приходим к следующей теореме.
Теорема 2. Для того чтобы в точке
функция
f
(
x
1
,
..., х п
) имела безусловный локальный экстремум, необходимо, чтобы все ее частные производные обращались в
в нуль:
Условие стационарности (4) мы будем записывать еще в одной из следующих эквивалентных форм:
где —
n
-мерный вектор с компонентами ,
i
=l, ..., п,
который принято называть градиентом
функции f
(х)
в точке .
Заметим, что необходимое условие экстремума (4) эквивалентно равенству нулю дифференциала функции f
(
x
)
в точке :
В самом деле, если выполнено условие (4), то для любых dx l
,
i
=
l, ..., n
, имеем
Справедливо и обратное утверждение, так как из последнего равенства в силу произвольности независимых приращений dx i
, i
=
l, ..., n
, следует, что все частные производные в точке равны нулю:
Условия (4) образуют систему п
уравнений для определения п
компонент вектора .
Эти уравнения могут иметь различную природу и допускать любое количество решений, в частности, не иметь ни одного. Как и выше, точки ,являющиеся решениями системы уравнений (4), будем называть стационарными, а условие (4) - необходимым условием экстремума первого порядка.
1.2
Необходимое условие второго порядка. Достаточные условия.
После того как решение системы уравнений (4) будет найдено, необходимо еще определить характер стационарной точки .
Для этого нужно исследовать поведение функции f
(
x
)
в окрестности стационарной точки .
Снова воспользуемся разложением функции f
(х)
в ряд Тейлора, предполагая ее дважды непрерывно дифференцируемой по всем переменным х 1
,
..., х
n
.
Тогда получим
Здесь через мы обозначили элементы матрицы вторых производных функции f
(
x
)
в стационарной точке ,
а через - какую-нибудь норму вектора , например, .Далее матрицу вторых производных мы будем обозначать так:
Характер стационарной точки функции f
(
x
)
связан сознакоопределенностью квадратичной формы
Напомним, что квадратичная форма называется неотрицательно определенной
в точке ,
если
Соответственно, симметричная матрица вторых производных f
"(х)
называется неотрицательно определенной в точке ,
если выполнено (8), и положительно определенной, если выполнено (9). Неположительно определенным и отрицательно определенным квадратичным формам и матрицам соответствуют противоположные знаки в неравенствах (8), (9).
Таким образом, с учетом разложения (5), приходим к следующей формулировке условий второго порядка экстремальности функции f
(
x
1
,
..., х п
).
Теорема 3. Для того чтобы дважды непрерывно дифференцируемая функция п переменных
f
(
x
) имела в стационарной точке
безусловный локальный минимум (максимум), необходимо, чтобы матрица ее вторых производных была неотрицательно (неположительно) определенной, и достаточно, чтобы она была положительно (отрицательно) определенной
.
Проверка знакоопределенности матриц может быть осуществлена, например, с помощью критерия Сильвестра
. Согласно этому критерию, необходимым и достаточным условием положительной определенности квадратичной формы (х, Ах),
где А = {
a ij
}
— симметричная
матрица, является выполнение п
неравенств:
Необходимым и достаточным условием отрицательной определенности квадратичной формы (х, Ах)
является выполнение цепочки следующих п
неравенств:
Если квадратичная форма не меняет знака, но обращается в нуль при ненулевых значениях аргумента, то для определения характера стационарной точки требуется исследование производных более высокого порядка.
Пример.
Определить экстремальные значения функции
Поэтому , - стационарная точка. Коэффициенты квадратичной формы (7), вычисленные в ней, равны
Тогда, согласно теореме 3, имеем следующие случаи:
1) а>0, b
>0
- функция f
(х)
имеет в точке = {0, 0} T
минимум;
4) а<0, b<0 - функция f
(х)
имеет в точке ={0, 0} T
максимум. Отметим, что случаи 1) и 4) соответствуют поверхности, являющейся эллиптическим параболоидом, а случаи 2) и 3) - гиперболическому параболоиду, имеющему стационарную точку типа «седло».
Замечание:
Здесь и далее { x
1
,
..., х п
} T
– вектор-столбец.
§ 2. Относительный экстремум. Метод множителей Лагранжа
2.1
Метод исключения.
Рассмотрим теперь задачу на относительный экстремум. Как мы видели в § 1, решение задачи об отыскании экстремумов функции п
переменных f
(х)
на всем пространстве Е п
может быть сведено с помощью необходимых условий к решению системы уравнений (4), в результате чего определяются стационарные точки функции f
(
x
).
Оказывается, что аналогичное сведение возможно и для задачи отыскания экстремумов функции f
(
x
)
при наличии ограничений типа равенств
g i
(
x
) = 0,
i
= 1, 2, ..., т.
(10)
Условия (10) принято еще называть уравнениями связи
.
Точку х
, удовлетворяющую условиям (10), будем называть допустимой.
Определение .
Допустимая точка доставляет относительный локальный минимум
функции f
(х),
если можно указать такое число , что для всех х,
удовлетворяющих уравнениям связи (10) и условию || х -
||< , имеет место неравенство
Рассмотрим случай, когда уравнения связи (10) могут быть разрешены относительно части переменных. Будем предполагать, что функции g i
(
x
),
i
=l,..., т
,имеют в окрестности рассматриваемой допустимой точки непрерывные частные производные по всем аргументам до второго порядка включительно и, кроме того, ранг матрицы Якоби для функций g i
(
x
),
i
= l, ..., m
, рассматриваемой в точке ,равен т
.Не нарушая общности, предположим, что отличен от нуля определитель (якобиан), составленный из частных производных по первым т
аргументам, т. е.
Тогда по теореме о неявных функциях в некоторой окрестности точки система уравнений (10) разрешима относительно х 1
,
..., х т
,т. е. представима в виде
где - непрерывно дифференцируемые в рассматриваемой окрестности функции. Переменные х т+1
,..., х п
естественно назвать «независимыми», в отличие от «зависимых»— x
1
, ..., х т
.
Подставляя выражения (12) в функцию f
(
x
),
получим задачу отыскания безусловного экстремума функции п — т
переменных
Однако провести исключение части компонент вектора х
обычно бывает трудно или даже невозможно. Поэтому мы используем другой путь определения точки ,который не предполагает наличия явных выражений типа (12), хотя использует существенно условие (11).
2.2
Метод множителей Лагранжа.
Как мы видели в замечании к теореме 2, в точке ,
доставляющей безусловный экстремум функции, ее полный дифференциал равен нулю, т. е.
где dx j
, j
=1, ..., m
, — дифференциалы «зависимых» переменных, связанные с дифференциалами «независимых» переменных dx k
,
k
=
m
+1,
..., n
, следующим образом:
Метод Лагранжа состоит из следующих этапов:
1) составляется функция п+т
переменных, которая называется функцией Лагранжа:
2) вычисляются и приравниваются нулю ее частные производные по х
и :
3) решается система (16) п+т
уравнений относительно п+т
неизвестных x
1
, ..., х п
,
1
,
..., т
.
Система уравнений (16) представляет собой необходимые условия первого порядка в задаче на относительный экстремум, а ее решения 1
, ..., п
принято называть условно-стационарными точками.
Как и в случае задач на безусловный экстремум, необходимые условия первого порядка не определяют характера условно-стационарной точки. Для выяснения этого вопроса следует привлечьпроизводные более высоких порядков функций f
(х)
и g
(
x
).
Заметим, что требование неравенства нулю якобиана (11) является существенным.
Пример 1.
Условие (11) может быть не выполнено, если решение задачи на относительный экстремум реализуется, например, в точке касания поверхностей ограничений (10) (начало координат на рис. 1).
Допустимая точка должна одновременно удовлетворять уравнениям g
1
(
x
) = 0
, g
2
(
x
) = 0
и является единственной: х 1
=
0, x
2
=
0. Очевидно, что точка 1
=0, 2
=0 и будет решением задачи на относительный минимум функции f
(х) =
x
2
при ограничениях g
1
(
x
) =
g
2
(
x
) = 0.
Составим для этой задачи функцию Лагранжа:
Метод множителей Лагранжа приводит к уравнениям
Этим уравнениям точка относительного минимума 1
=0, 2
=0не удовлетворяет ни при каких значениях 1
, 2
,т. е. в данном случае метод множителей Лагранжа не работает.
Функция Лагранжа для этой задачи имеет вид
Соответственно, правило множителей Лагранжа приводит к уравнениям
решением которых будет , 1
=0, 2
=0. Чтобы понять, доставляет точка =0 относительный минимум функции f
(х)
илинет, надо выяснить характер поведения квадратичной формы
При , как функция одной переменной , эта форма положительно определена. Значит, в точке =0
имеем относительный минимум.
2.3
Седловая точка функции Лагранжа.
Рассмотрим функцию двух переменных z
= Ф(х, у)
,где х,
y
—скаляры или векторы.
Определение.
Назовем пару {х*,
y
*}
седловой точкой
функции Ф (х, у),
если для любых х,
y
справедливо неравенство
Очевидно, что неравенство (17) эквивалентно выражению
Снова рассмотрим задачу отыскания относительного экстремума функции f
(
x
)
при ограничениях g
(
x
) = 0
. Необходимые условия экстремума (3.10) можно записать в виде
т. е. пара является стационарной точкой функции Лагранжа
Однако в этой точке функция не может достигать максимума или минимума по х
и одновременно. В самом деле, пусть в точке достигается максимум функции по х
и . Так как условия связи в точке выполнены, то Пусть, далее, в некоторой точке нарушено одно из ограничений, например Тогда в силу линейности функции L
по мы можем за счет выбора добиться бесконечно большого значения L
(число имеет знак, противоположный знаку g k
(
x
)).
Следовательно, в точке функция Лагранжа не может иметь максимума по . Аналогично можно показать, что в точке не может одновременно достигаться минимум функции Лагранжа по х
и .
Покажем теперь, что в точке достигается либо , либо в зависимости от того, является точкой максимума или минимума. В самом деле, при каждом фиксированном х
Таким образом, по х
и функция Лагранжа имеет экстремум противоположного характера. Если при этом оказывается, что
то точка ,
по определению, является седловой точкой функции Лагранжа.
Пример 3.
Исследуем на экстремум функцию
Решение.
Координаты x
,
y
,
z
критической точки гладкой функции u
должны удовлетворять системе:
Отсюда получаем пять критических точек:
Исследуем поведение функции u
в стационарных точках с помощью достаточного условия экстремума:
Отсюда получаем . Так как является отрицательно определенной квадратичной формой, то в точке функция u
имеет строгий локальный максимум.
Применим критерий Сильвестра. Матрица этой формы:
Распределение знаков этих миноров показывает, что данная квадратичная форма знакопеременная, следовательно, в точке М 1
функция u
не имеет экстремума: точка М 1
есть седловая точка функции u
.
Точно так же устанавливается, что точки М 2
, М 3
, М 4
также седловые точки функции u
.
Глава
II
. ЧИСЛЕННЫЕ МЕТОДЫ ОТЫСКАНИЯ БЕЗУСЛОВНОГО ЭКСТРЕМУМА
§ 1. Методы первого порядка (градиентные методы)
Как известно из курсов анализа, градиент скалярной функции f
(х)
в некоторой точке x k
направлен в сторону наискорейшего возрастания функции и ортогонален линии уровня (поверхности постоянного значения функции f
(
x
),
проходящей через точку х
k
) .
Вектор, противоположный градиенту f
' (
x k
)
, антиградиент, направлен в сторону наискорейшего убывания функции f
(
x
).
Выбирая в качестве направления спуска р
k
в
антиградиент функции f
(х)
в точке x k
,
мы приходим к итерационному процессу вида
В координатной форме этот процесс записывается следующим образом:
Все итерационные процессы, в которых направление движения на каждом шаге совпадает с антиградиентом (градиентом) функции, называются градиентными методами
и отличаются друг от друга способами выбора шага Рассмотрим некоторые из них.
1.1 Метод градиентного спуска с постоянным шагом
Пусть дана функция f
(х)
, ограниченная снизу на множестве R n
и имеющая непрерывные частные производные во всех его точках.
Требуется найти локальный минимум функции f
(х)
на множестве допустимых решений X
= R n
, т.е. найти такую точку , что
Стратегия решения задачи состоит в построении последовательности точек {х
k
}
, k
=
0,1,..., таких, что k
= 0,1,... . Точки последовательности {х
k
}
вычисляются по правилу
где точка х 0
задается пользователем; - градиент функции f
(
x
)
, вычисленный в точке х
k
; величина шага задается пользователем и остается постоянной до тех пор, пока функция убывает в точках последовательности, что контролируется путем проверки выполнения условия или
Построение последовательности { х
k
} заканчивается в точке х
k
, для которой , где - заданное малое положительное число, или , где М -
предельное число итераций, или при двукратном одновременном выполнении двух неравенств , где - малое положительное число. Вопрос о том, может ли точка х
k
рассматриваться как найденное приближение искомой точки минимума, решается путем проведения дополнительного исследования, которое описано ниже.
Геометрическая интерпретация метода для п
=2приведена на рис. 2.
1. Используя алгоритм градиентного спуска с постоянным шагом, найти точку х
k
в которой выполнен по крайней мере один из критериев окончания расчетов.
2. Провести анализ точки х
k
с целью установить, является ли точка х к
найденным приближением решения задачи. Процедура анализа определяется наличием у функции f
(х)
непрерывных вторых производных. Если , то следует провести проверку выполнения достаточных условий минимума: матрица Гессе Если то точка х
k
есть найденное приближение искомойточки х *
.
Если ,
то следует провести проверку функции f
(х)
на выпуклость в Q
-окрестности точки х
k
, используя критерий выпуклости для функций : функция
f
(
x
) выпукла (строго выпукла) в том и только в том случае, если
. Если функция f
(
x
)
выпукла (строго выпукла), то х
k
есть найденное приближение точки х *
.
Определение: Матрицей Гессе Н(х)
дважды непрерывно дифференцируемой в точке х
функции f
(
x
)
называется матрица частных производных второго порядка, вычисленной в данной точке:
Определители , , …, называются угловыми минорами.
Пример 1.1.
Найти локальный минимум функции
□ I. Определение точки х
k
, в которой выполнен по крайней мере один из критериев окончания расчетов.
1. Зададим х 0
, , , М
: х 0
= (0,5; 1) T
, = 0,1; = 0,15 ; М =
10. Найдем градиент функции в произвольной точке
4 0
. Вычислим : = 3,9 > 0,1. Переходим к шагу 5.
5 0
. Проверим условие : k
= 0 < 10 = M
. Переходим к шагу 6.
7 0
. Вычислим х 1
: х 1
=
(0,5; 1) T
-0,5(3; 2,5) T
= (-1; -0,25) T
; f
(х 1
)
= 2,31.
8 0
. Сравним f
(х 1
)
с f
(х 0
)
= 2. Имеем f
(х 1
)
> f
(х 0
)
. Вывод: условие для k
= 0 не выполняется. Зададим = 0,25, переходим к повторению шагов 7, 8.
Банк рефератов содержит более 364 тысяч рефератов , курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Название: Методы оптимизации
Раздел: Рефераты по математике
Тип: реферат
Добавлен 23:01:41 22 июля 2011 Похожие работы
Просмотров: 3335
Комментариев: 13
Оценило: 2 человек
Средний балл: 5
Оценка: неизвестно Скачать
Введение………………………………………………………………………
§1. Функция многих переменных………………………………………….
1.1 Необходимые условия экстремума…………………………….
§2. Относительный экстремум. Метод множителей Лагранжа…………
2.1 Метод исключения………………………………………………
2.2 Метод множителей Лагранжа………………………………….
2.3 Седловая точка функции Лагранжа……………………………..
Глава II. Численные методы отыскания безусловного экстремума…….
§1. Методы первого порядка (градиентные методы)……………………..
1.1 Метод градиентного спуска с постоянным шагом……………
1.2 Метод наискорейшего градиентного спуска………………….
1.3 Метод покоординатного спуска……………………………….
§2. Методы второго порядка………………………………………………
2.1 Метод Ньютона………………………………………………….
2.2 Метод Ньютона-Рафсона……………………………………….
Заключение……………………………………………………………………
Литература…………………………………………………………………….
Реферат : Методы оптимизации - BestReferat.ru
Реферат : Решение оптимизационной задачи ... - BestReferat.ru
Задачи оптимизации и методы их решения. Обзор
Формулировка статистической задачи оптимизации
Задачи оптимизации | Рефераты KM.RU
Сочинение Почему Хочу Стать Военным
Питание Беременных И Кормящих Женщин Реферат
Эссе На Тему Роль Наставника
Динамография Метод Исследования Реферат
Сочинение Буря У Мыса Айя 9 Класс