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) является точкой локального минимума, а так как это единственная стационарная точка, то она же является и точкой глобального минимума.

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

 


 

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

19022. Матрицы операторов. Унитарные преобразования базиса. Соотношения коммутации. Одновременная измеримость физических величин 650 KB
  Лекция 4 Матрицы операторов. Унитарные преобразования базиса. Соотношения коммутации. Одновременная измеримость физических величин. Соотношение неопределенностей Гейзенберга Рассмотрим некоторый линейный оператор :. Выберем в рассматриваемом линейном пространст...
19023. Временное уравнение Шредингера. Общее решение уравнения Шредингера в случае ста-ционарного гамильтониана. Стационарные состояния 380 KB
  Лекция 5 Временное уравнение Шредингера. Общее решение уравнения Шредингера в случае стационарного гамильтониана. Стационарные состояния. Плотность потока вероятности Как следует из постулатов квантовой механики волновая функция удовлетворяет уравнению Шрединг
19024. Зависимость средних от времени. Интегралы движения. Законы сохранения и симметрии. Сохранение четности 614 KB
  Лекция 6 Зависимость средних от времени. Интегралы движения. Законы сохранения и симметрии. Сохранение четности Эволюция квантовой системы во времени определяется временным уравнением Шредингера 1 Поскольку это уравнение является уравнением первого пор...
19025. Общие свойства стационарных состояний одномерного движения для дискретного спек-тра. Квантование энергии в потенциале притяжения. Осцилляционная теорема 1.32 MB
  Лекция 7 Общие свойства стационарных состояний одномерного движения для дискретного спектра. Квантование энергии в потенциале притяжения. Осцилляционная теорема Пусть потенциальная энергия частицы зависит только от координаты : Тогда поскольку потенциальн
19026. Бесконечно глубокая прямоугольная потенциальная яма. Спектр, стационарные состоя-ния, разложения по собственным функциям гамильтониана, средние 434.5 KB
  Лекция 8 Бесконечно глубокая прямоугольная потенциальная яма. Спектр стационарные состояния разложения по собственным функциям гамильтониана средние Пусть потенциальная энергия частицы равна бесконечно глубокая потенциальная яма шириной см. рисунок. Най...
19027. Гармонический осциллятор. Уровни энергии и волновые функции (решение в виде ряда) 615.5 KB
  Лекция 9 Гармонический осциллятор. Уровни энергии и волновые функции решение в виде ряда Одномерным гармоническим осциллятором называется частица движущаяся в потенциале где масса частицы число имеющее размерность сек1 в случае классического движения ча
19028. Гармонический осциллятор. Уровни энергии и волновые функции (решение с помощью операторов рождения и уничтожения) 1.04 MB
  Лекция 10 Гармонический осциллятор. Уровни энергии и волновые функции решение с помощью операторов рождения и уничтожения Сегодня мы рассмотрим другой способ решения задачи о гармоническом осцилляторе. Вопервых этот способ и сам по себе поучительный а вовторых ...
19029. Вычисления с осцилляторными функциями 156 KB
  Лекция 11 Вычисления с осцилляторными функциями В различных задачах связанных с гармоническим осциллятором приходится вычислять интегралы типа или 1 где собственные функции гамильтониана осциллятора везде в этой лекции под будет подразумеваться б...
19030. Общие свойства стационарных состояний одномерного движения в случае непрерывного спектра. Прохождение потенциальных барьеров 334 KB
  Лекция 12 Общие свойства стационарных состояний одномерного движения в случае непрерывного спектра. Прохождение потенциальных барьеров Рассмотрим теперь решения уравнения Шредингера отвечающие непрерывному спектру собственных значений. Эти решения не затухают п...