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

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

 


 

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

70041. Молдавия в составе Российской империи 17.28 KB
  В годы Первой мировой войны в Молдавии ускоренными темпами развивалось железнодорожное строительство в сельском хозяйстве начался упадок и разруха. В первые дни Февральской революции 1917 года в Молдавии сформировалось Временное правительство.
70042. Национальный вопрос в России между революциями 1917 16.46 KB
  Национальный вопрос в России между революциями 1917 В историографии сложилась концепция бархатной революции либо революция роз: 14 февраля 1917 года проправительственная демонстрации в поддержку думы и вдруг якобы неожиданно она превращается в антиправительственную за мир хлеб и т.
70043. Понятие Конституционного права 36.5 KB
  Мировой опыт конституционного развития знает два основных вида конституции: писаные и неписаные. Писаные конституции представляют собой единый правовой документ занимающий доминирующее место в правовой системе страны как по своему содержанию регулирование важнейших...
70044. МОРФОЛОГИЧЕСКИЕ НОРМЫ РУССКОГО ЛИТЕРАТУРНОГО ЯЗЫКА 43.34 KB
  Морфология это систематизированная совокупность форм слов парадигм склонения спряжения а также правил их употребления и одновременно это раздел грамматики который изучает и описывает эти формы правила.
70045. Стратегии порождения научных знаний 29 KB
  Иными словами элементы предпосылки ростки будущей науки формировались в недрах другой духовной системы но они еще не выделялись из них как автономное самостоятельное целое. Действительно предпосылки науки создавались в древневосточных цивилизациях Египте Вавилоне Индии Китае...
70047. Теория потребительского спроса 240 KB
  Эластичность спроса и предложения: содержание виды практическое применение. Различают рыночный и индивидуальный спрос а также понятия величина спроса и сам спрос рис. Величина спроса Q d это то количество товаров которое покупатель способен приобрести по определенной цене в данный момент...
70049. Философия познания Ф.Бэкона и ее значение для превращения преднауки в науку 42 KB
  Бэкон дал философское обоснование нового взгляда на цель и предназначение науки разработал основные принципы индуктивного метода исследования. Бэконовский афоризм Знание сила в течение трех веков является символом науки. Бэкон предпринимает Великое восстановление наук в книге...