Нелинейное программирование. Нурминский Е.А. - 15 стр.

UptoLike

ВУЗ: 

ДВФУ | Владивосток

Составители: 

Рубрика: 

2.3 Методы одномерной минимизации
Задача одномерной минимизации состоит в нахождении минимума функц-
ии одной переменной
, обычно на некотором интервале:
или при выполнении одностороннего ограничения .
Определение 16 Функция называется унимодальной, если сущест-
вует такое , что из следует
а из следует
Другими словами, слева от функция монотонно убывает, а справа
— возрастает.
Точка является единственным минимумом и, следовательно, за-
дача
(25)
хорошо определена для унимодальных функций. Далее мы будем предпо-
лагать унимодальность, не оговаривая это особо.
Для задачи (25) вводиться понятие интервала неопределенности ,
относительно которого можно утверждать, что . Разность
определяет точность решения задачи (25).
Методы одномерной минимизации обычно строят последовательность
вложенных интервалов неопределенности, сходящихся к .
2.3.1 Метод дихотомии
Если — дифференцируема, то решение (25) эквивалентно поиску корня
уравнения
Тогда при известном начальном интервале неопределенности с
он может рекуррентно пересчитываться следующим образом:
1. положим
2. вычислим
3. если , то иначе .
4. .
Видно, что этот метод программируется буквально ”в одну строку” и обес-
печивает гарантированное убывание интервала неопределенности вдвое на
каждом шаге, независимо от характеристик таких, например, как скорос-
ть роста или убывания , поорядок значений вторых проиводных и пр. Это
15
2.3          Методы одномерной минимизации


#
ии одной переменной                     &
Задача одномерной минимизации состоит в нахождении минимума функц-
                           , обычно на некотором интервале: 
     или при выполнении одностороннего ограничения                             )# 
                                                                                                           #
                                                       .
                                             
                    :
Определение 16 Функция
                                   : *   * называется
                                                   следует унимодальной, если сущест-
                                         : +*   -*  
вует такое , что из


           :    
                                           +*  -*
а из                         следует
                            :         
Другими словами, слева от  : функция  J монотонно убывает, а справа

   Точка  : является единственным минимумом  и, следовательно, за-
— возрастает.

дача
                                                           (25)

хорошо определена для унимодальных функций. Далее мы будем предпо-
лагать унимодальность, не оговаривая это особо.
   Для задачи (25) вводиться понятие интервала неопределенности   ,                                
                                                                     :    
                                                                                                      
относительно которого можно утверждать, что            . Разность
      определяет точность решения задачи (25).
   Методы одномерной минимизации обычно строят последовательность
вложенных интервалов неопределенности, сходящихся к .                            :
2.3.1        Метод дихотомии
Если — дифференцируема, то решение (25) эквивалентно поиску корня
уравнения
                                                >  <%
             -&%
Тогда при известном начальном интервале неопределенности   с
%' > 
      
                                                                                           >          -*
                   7    L-9
            он может рекуррентно пересчитываться следующим образом:
      1. положим 
      2. вычислим           >  
                                                                
      3. если  *&% , то  
             & <*
                                                           иначе                                    .
      4.               .
Видно, что этот метод программируется буквально ”в одну строку” и обес-
печивает гарантированное убывание интервала неопределенности вдвое на
каждом шаге, независимо от характеристик таких, например, как скорос-
ть роста или убывания , поорядок значений вторых проиводных и пр. Это


                                                  15

Страницы