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

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

 


 

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

29932. Природные чрезвычайные ситуации гидрологического происхождения: наводнения, сели, цунами и их последствия; мероприятия, проводимые по защите населения 38.5 KB
  Цунами это гигантские океанские волны возникающие чаще пито в результате подводных и островных землетрясений или извержений вулканов. Наиболее опасны цунами для населенных пунктов расположенных на низких океанских берегах. Вторичными последствиями цунами являются пожары возникающие в результате повреждения пожароопасных объектов.
29933. Лесные и торфяные пожары и их последствия. Профилактика лесных и торфяных пожаров 32.5 KB
  Лесные пожары бывают низовыми верховыми и подземными. Верховые пожары уничтожают верхний полог леса и распространяются со скоростью 825 км ч. Подземные пожары случаются на торфяных грунтах распространяются со скоростью 210 м в день.
29934. Чрезвычайные ситуации техногенного характера. Общие понятия и определения. Классификация чрезвычайных ситуаций по масштабам их распространения и тяжести последствий 35 KB
  Правила ухода за кожей зубами и волосами: регулярно менять белье носки чулки колготки гольфы; У мыться ежедневно теплой водой с туалетным или детским мылом; если кожа чешется смазать ее кремом или мазью; не выдавливать прыщи не вскрывать гнойники так как на их месте может начаться воспаление; при обнаружении на теле сыпи сразу же сказать об этом родителям; употреблять в пищу больше свежих овощей и фруктов молока; в них достаточно витаминов и минеральных веществ необходимых для кожи; зимой защищать кожу от...
29935. Радиационно-опасные объекты. Аварии на радиационно-опасных объектах и их возможные последствия. Обеспечение радиационной безопасности населения 39 KB
  Это поражение может произойти следующими способами: внешнее облучение при прохождении радиоактивного облака; внешнее облучение обусловленное радиоактивным загрязнением почвы и местных предметов; внутреннее облучение при вдыхании воздуха зараженного радиоактивными веществами; внутреннее облучение при употреблении загрязненной воды пищи; контактное облучение в результате попадания на кожу и одежду радиоактивных веществ.
29936. Химически опасные объекты. Аварии на химически опасных объектах и их возможные последствия. Обеспечение безопасности населения 43 KB
  Аварии на химически опасных объектах и их возможные последствия. Обеспечение безопасности населения Ответ: Химически опасный объект это такой объект при аварии на котором или при разрушении которого могут произойти массовые поражения людей животных и растений опасными химическими веществами. Поэтому аварии на таких объектах очень опасны. Эти аварии классифицируются следующим образом: аварии с выбросом или угрозой выброса аварийно химически опасных веществ АХОВ при их производстве переработке в хранении; аварии на...
29937. Пожаро - и взрывоопасные объекты. Возможные последствия аварий на пожаро- и взрывоопасных объектах. Правила поведения при пожаре и угрозе взрыва 33 KB
  Возможные последствия аварий на пожаро и взрывоопасных объектах. Правила поведения при пожаре и угрозе взрыва Ответ: Пожаро и взрывоопасные объекты это предприятия на которых в производственном процессе применяют взрывчатые и легковоспламеняющиеся вещества а также железнодорожный и трубопроводный транспорт используемый для перевозки перекачки пожаро и взрывоопасных веществ. К таким объектам относятся предприятия химической газовой нефтеперерабатывающей целлюлознобумажной пищевой лакокрасочной промышленности производства...
29938. Гидротехнические сооружения, возможные аварии на них и их последствия 38.5 KB
  Защита населения от последствий гидродинамических аварий Ответ: Гидродинамически опасные объекты это сооружения и естественные образования создающие разницу уровней воды до и после них верхний бьеф и нижний бьеф. Этому способствует также скопление населения на ограниченных площадях при значительном ухудшении материальнобытовых условий жизни людей. Защита и безопасность населения при гидродинамических авариях обеспечивается организационными инженернотехническими и другими мероприятиями. Меры по защите населения при...
29939. Криминогенные ситуации, которые могут возникнуть в повседневной жизни. Общие правила личной безопасности в криминогенных ситуациях 36 KB
  Инфекции передаваемые половым путем меры по их профилактике Ответ: Вступление в половые отношения в подростковом возрасте чаще всего происходит по следующим обстоятельствам: алкогольное опьянение насилие скука материальная выгода желание привлечь к себе внимание партнера для самоутверждения как средство доказать свою взрослость. Как правило эти связи приводят к таким последствиям: ранняя беременность которая обычно заканчивается абортом со всеми вытекающими отсюда последствиями; воспалительные заболевания половых путей и...
29940. Действия населения по сигналу «Внимание всем!» 31.5 KB
  2 вопрос: Понятие о ВИЧинфекции и СПИДе. Способы передачи ВИЧинфекции и меры ее профилактики Ответ: В 1981 г. Вирус вызывающий болезнь получил название ВИЧ вирус иммунодефицита человека. Применяемые препараты только продлевают состояние ВИЧинфицированности не давая человеку заболеть СПИДом и погибнуть.