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

UptoLike

ВУЗ: 

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

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

Рубрика: 

который носит имя метода Ньютона. Фундаментальное исследование этого
метода провел В.Л. Канторович [?]. Теория этого метода весьма интересна,
а его глобальное поведение ди сих пор не вполне изучено.
Здесь мы ограничимся лишь локальным исследованием.
Теорема 17 Пусть — дважды дтфференцируемая функия и удов-
летворяет условию Липшица ( в евклидовой норме ) с константой ,
— сильно выпуклая функция с константой сильной выпуклости и нача-
льная точка удовлетворяет соотношению
Тогда 26 сходится к точке минимума с квадратичной скоростью:
Д о к а з а т е л ь с т в о. Из условия Липшица и теоремы о среднем
получаем
(27)
Полагая из 27 получаем
Из сильно выпуклости следует, что , в том смысле, что
для любого . Отсюда , т.е.
Итерируя, получаем
С другой стороны для сильно выпукых функций
что завершает доказательство.
Приведенная теорема утверждает сходимость метода Ньютона лишь при
достаточно хорошем начальном приближении. Полученная в ней оценка для
этого приближения приводит к курьезным результатам при решении плохо
обусловленных задач. Рассмотрим, например, применение метода барьеров
для решения простейшей задачи
Мето логарифмического барьера рекомендует решение безусловной задачи
18
который носит имя метода Ньютона. Фундаментальное исследование этого
метода провел В.Л. Канторович [?]. Теория этого метода весьма интересна,
а его глобальное поведение ди сих пор не вполне изучено.
   Здесь мы ограничимся лишь локальным исследованием.
                                                                                                            >>
Теорема 17 Пусть     — дважды дтфференцируемая функия и      удов-
                                                              
летворяет условию Липшица ( в евклидовой норме ) с константой ,                                                        
                                                          
— сильно выпуклая функция с константой сильной выпуклости и нача-

                                                   / >   *
льная точка   удовлетворяет соотношению
                                                                               *!
                                                                             :
                                        :  *    
Тогда 26 сходится к точке минимума                                               с квадратичной скоростью:
                                              



               / >   '0  >    > >  Q#  1W
Д о к а з а т е л ь с т в о. Из условия Липшица и теоремы о среднем
получаем                                     

           ' < 
                                                                (27)


                  0  >    S # L? > >     / >  1
Полагая                   из 27 получаем
                                                                                          


           5             O
                            
Из сильно выпуклости следует, что
                                 >  >   "   #
                                                   > >?  6
                                                    
                                                                                  , в том смысле, что   5  >>  5   5  
                                                                                                                       


                               0  >    Q #   /  >   
для любого . Отсюда                                                 , т.е.
                                                                                     



                           / >    Q#    / >  "5(  
Итерируя, получаем
                                                          



                                   / >     6     : 
С другой стороны для сильно выпукых функций
                                                                       

что завершает доказательство.
   Приведенная теорема утверждает сходимость метода Ньютона лишь при
достаточно хорошем начальном приближении. Полученная в ней оценка для
этого приближения приводит к курьезным результатам при решении плохо
обусловленных задач. Рассмотрим, например, применение метода барьеров
для решения простейшей задачи
                                                      =  D

                                                             0DH 2
Мето логарифмического барьера рекомендует решение безусловной задачи
                                          =  0         


                                                          18

Страницы