9892

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

Реферат

Математика и математический анализ

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

Русский

2013-03-18

101 KB

10 чел.

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

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

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

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

     

0

      

   

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

- градиент,

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

- элемент -  частная производная второго порядка.

Напомним, что - симметрическая матрица.

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

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

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

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

=  .   H = (h1, h2, . . . , hn)T.

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

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

  .

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

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

- положительно определена.

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

- отрицательно определена.


Пример:

, тогда

положительно определена при любом Х,

поэтому точка (2, 4, 6) является точкой локального минимума, а так как это единственная стационарная точка, то она же является и точкой глобального минимума.

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

 


 

А также другие работы, которые могут Вас заинтересовать

40136. Пределы и непрерывность. Числовая последовательность и ее предел. Определение функции, ее непрерывность на языке эпсилон-дельта и языке пределов, равномерная непрерывность 165 KB
  Обратное не верно: xn=nsin n неограниченная не бесконечно большая Функция Функцией y = fx называется закон по которому каждому значению xDfR ставится в соответствие единственное действительное число yR. Функция может быть задана аналитически то есть формулой таблично или графически. y=x2 Если функция задана таблично то чтобы найти значение функции для промежуточных значений аргумента применяют интерполяцию заменяя функцию линейной квадратичной на участке между двумя значениями аргумента. Например fx0=0 = 3  O1...
40137. Производная функции одной переменной. Определение, ее геометрический смысл, простейшие правила вычисления производной (производная от функции, умноженной на константу, от суммы функций, от произведения функций, частного и степени). Производная сложной фун 140 KB
  Производная функции одной переменной. Определение ее геометрический смысл простейшие правила вычисления производной производная от функции умноженной на константу от суммы функций от произведения функций частного и степени. Производная сложной функции. Если предел  и конечен то его значение называют производной функции f в т.
40138. Дифференцирование функций многих переменных: производная по направлению, частные производные, дифференциал, Производная от сложных функций, градиент, направления убывания, геометрический смысл градиента 141 KB
  Если то функция называется дифференцируемой по x в точке x0 y0. 1 2  для  0  0:  x yDz  Ox0 y0 {x0 y0}: zx y  O Значение lim не должно зависеть от способа стремления точки x y к точке x0 y0: на плоскости для функции нескольких переменных При разных  получаем разные значения lim  lim не . Непрерывность Функция zx y называется непрерывной в точке x0 y0 если: 1. Если функция z = zx y дифференцируема в точке по совокупности аргументов то она непрерывна в этой точке.
40139. Определенный интеграл и его геометрический смысл (задача о площади криволинейной трапеции). Приближенное вычисление определенных интегралов, формулы трапеций и Симпсона 165.5 KB
  Пусть функция у = fx определена на отрезке [а b]. Обозначим через На каждом из сегментов выберем произвольные точки и составим интегральную сумму: Обозначим диаметр разбиения если  конечный не зависящий от способа разбиения отрезка [а b] и выбора точек то его значение называется определенным интегралом от функции fx его обозначение а функция fx называется интегрируемой по Риману на [а b]. Если функция fx интегрируема на [а b] то она ограничена на этом сегменте. ДОКВО Если функция fx не ограничена на [а b] то...
40140. Приведение задач линейного программирования к каноническому виду. Методы искусственного базиса 66 KB
  Основная теорема ЛП: если задача ЛП имеет решение то целевая функция достигает экстремального значения хотя бы в одной из угловых точек многоугольника решений. Таким образом с теоретической точки зрения решение задачи ЛП выглядит следующим образом: можно найти все угловые точки многоугольника решения высчитать в них значение ЦФ выбрать наибольшее наименьшее. процесс нахождения угловых точек сравним по трудности с решением исходной задачи. В этом заключается основная идея СМ которая предполагает: 1 уметь находить первоначальное базисное...
40141. ОПТИМАЛЬНЫЕ ЛИНЕЙНЫЕ ФИЛЬТРЫ СИГНАЛОВ НА ФОНЕ ПОМЕХ 1.62 MB
  Смысл слова выделение сигнала совпадает с понятием оценки сигнала. Пусть имеется сумма сигнала и шума: 6.1 Требуется чтобы оценка сигнала являющаяся откликом на воздействие t рис.
40142. ОПТИМАЛЬНОЕ ОБНАРУЖЕНИЕ ДЕТЕРМИНИРОВАННЫХ СИГНАЛОВ 231.5 KB
  3 Тема №3 Основы теории обнаружения и различения сигналов ОПТИМАЛЬНОЕ ОБНАРУЖЕНИЕ ДЕТЕРМИНИРОВАННЫХ СИГНАЛОВ Обнаружение сигналов как статистическая задача Пусть на вход обнаружителя поступает сумма сигнала st и шума nt представляющая собой случайный непрерывный процесс 7. Дискретизация проводится в соответствии с теоремой Котельникова: для дискретизации аналогового сигнала без потерь информации частота отсчетов должна быть в...
40143. ОПТИМАЛЬНОЕ ОБНАРУЖЕНИЕ КВАЗИДЕТЕРМИНИРОВАННЫХ СИГНАЛОВ 241 KB
  Для этого потребуется определить распределение вероятностей достаточной статистики у поступающей на пороговое устройство а именно распределение вероятностей корреляционного интеграла y при отсутствии  = 0 и наличии  = 1 сигнала st на входе обнаружителя.5 рассчитываются характеристики оптимального обнаружения детерминированного сигнала в белом шуме.1 сплошными линиями показаны характеристики оптимального обнаружения детерминированного сигнала в белом шуме. Характеристики обнаружения позволяют определить минимальную энергию...
40144. ОПТИМАЛЬНОЕ РАЗЛИЧЕНИЕ ДЕТЕРМИНИРОВАННЫХ СИГНАЛОВ 360 KB
  5 Рош а б ОПТИМАЛЬНОЕ РАЗЛИЧЕНИЕ ДЕТЕРМИНИРОВАННЫХ СИГНАЛОВ Различение двух детерминированных сигналов. Постановка задачи и правило принятия решения Задача различения сигналов находит широкое распространение в дискретной радиосвязи когда передача символа 1 связана с излучением сигнала s1t а передача символа 0 связана с излучением другого сигнала s2t отличающегося от s1t хотя бы одним какимнибудь своим параметром. Поэтому решение о том какой из сигналов принимается может осуществляться с ошибкой. Отсюда возникает задача...