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

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

 


 

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

4344. Расширенный язык разметки XML 244.5 KB
  Расширенный язык разметки XML Общие сведения об XML Особенности XML Стандарты XML Структура и элементы языка разметки XML Таблицы стилей Расширяемый язык создания ссылок Спецификация XForms 1.0 Области использования языка XML Общие сведения об XML К...
4345. Базовый процесс технологии проектирования веб-сайта и его фазы 87 KB
  Базовый процесс технологии проектирования веб-сайта и его фазы Базовый процесс - это всесторонний план работы для групп любых типов и компаний всех видов с различными бюджетами. Базовый процесс - это всего пять фаз, каждая фаза включает три переплет...
4346. Классификация веб-сайтов 84.5 KB
  Классификация веб-сайтов Корпоративные сайты Промо презентационные сайты Электронные магазины Онлайн-сервисы Контент-проекты Порталы Коммьюнити. Средство общения. Интернет-форумы Литература Корпоративные сайты Корпоративный сайт - это официальное ...
4347. Информационная архитектура лекционные материалы по курсу Интернет-технологии 1.02 MB
  Введение Разрабатывая Web-сайты, каждый из нас не первый год старается идти по кратчайшему пути. Это особенно характерно для работы над проектами с небольшим бюджетом. И из всех кратчайших путей самым дорогим оказывается тот, когда мы пропускаем эта...
4348. Графический пользовательский интерфейс. Лекционный материал 770 KB
  Введение Итак, мы подошли через построение структуры контента и проектирование интерактивного процесса к последней части архитектуры – интерфейсу. Графическому пользовательскому интерфейсу /3/: графический – в нем применяются как рис...
4349. Интернет технологии: история, возможности, средства 202 KB
  Интернет технологии: история, возможности, средства История Интернет Возможности Интернет Как работает Интернет Web-приложения Инструменты создания web – сайтов и приложений История Интернет В 1969 году в США была создана компьютерная сеть ARPA...
4350. Архитектура интернет-технологий 260 KB
  Как работает Интернет Основные компоненты HTML - протоколы Адресация в сети Интернет Схема поиска IP-адреса по доменному имени Сервисы Интернет (основные службы) Утилиты Как работает Интернет Поддержка функционирования Web-серверов предусматривает с...
4351. Создание WEB – САЙТА 201 KB
  Классификация сайтов Организационно- технические вопросы создания сайта Основные этапы создания Web сайта Рекомендации по созданию сайта Проблемы создания сайта Что нужно, чтобы создать эффективную сеть сайтов Классификация сайтов В настоящее время ...
4352. Раскрутка WEB-Сайтов 256.5 KB
  Термины. Методы раскрутки сайта. Регистрация в поисковых системах и каталогах. Регистрация на поисковых сайтах и директориях. Что такое индекс цитирования Ссылочное ранжирование. Влияние собственных ресурсов поисковых машин. Перспективы развития...