Методы сокращения промежутков

 Рассмотрим далее примеры методов, которые реализуют последовательную стратегию. В основе данных методов лежит последовательное сокращение промежутка неопределенности. Сокращение промежутка неопределенности производится в большинстве методов на основе вычисления функции в точках текущего промежутка. Данные точки разбивают промежуток неопределенности на несколько частей. Свойство унимодальности функции позволяет на основе вычисления функции в произвольных двух точках, принадлежащих промежутку, определить, каким из полученных отрезков точка минимума не принадлежит. Действительно, поскольку унимодальная функция на промежутке  не возрастает, а на промежутке  не убывает, то если выбрать две точки  и для этих точек , то это может быть либо ситуация, изображенная на рисунке 7 или рисунке 9, и в том и в другом случае . Случаю же  может соответствовать только ситуации, изображенные на рисунках 8, 10, и поэтому в данном случае . Рассмотренные ниже несколько методов последовательной одномерной минимизации отличаются способом выбора точек . При этом различные способы выбора точек приводят к разной скорости сокращения промежутка неопределенности и к различному числу необходимых вычислений функции. 

 

                                                                     

 

 

 

                                                        

 

                           Рис. 7                                                    Рис. 8

 

                                                                 

 

 

 

                                                             

 

 

                            Рис.9                                                      Рис. 10

Метод деления промежутка пополам

 

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

 

Алгоритм

Шаг 1. Задать начальный промежуток неопределенности  и  - требуемую точность. Положить .

Шаг 2. Вычислить: .

Шаг 3. Вычислить: , , .

Шаг 4. Сравнить значения  и :

а) если , исключить промежуток , положив . Средней точкой нового промежутка становится точка . Перейти к шагу 6.

       б) если , перейти к шагу 5.

Шаг 5. Сравнить  и :

а) если , исключить промежуток  положив . Средней точкой нового промежутка становится точка . Перейти к шагу 6.

б) если      , исключить промежутки , положив . Средняя точка нового промежутка не изменится .

Шаг 6. Вычислить . Если , алгоритм завершает свою работу, и делается вывод, что , а в качестве приближенного решения можно, например, взять середину данного промежутка. Если же  , то положить  и перейти к шагу 3.

Следует заметить, что для данного метода на каждой итерации, начиная со второй, вычисляется значение функции только в двух точках, так как средняя точка нового промежутка всегда совпадает с одной из точек рассматриваемых на предыдущей итерации. Таким образом, для данного метода , где  - количество вычислений функции. Нумерация промежутков неопределенности подчеркивает тот факт, что на каждой итерации вычисляется два значения функции.

 

Пример 2. Найти минимум функции  методом деления промежутка пополам.

Решение. В качестве начального промежутка неопределенности рассмотрим промежуток  и положим .

1. Положим .

2. Вычислим: .

3. Вычислим , , .

4. , поэтому положим , .

5. Получим . Положим  и перейдем к шагу 3.

6. Вычислим , , .

7. , поэтому перейдем к шагу 5.

8. , поэтому положим , , .

9. Получим . Положим  и перейдем к шагу 3.

После третьего прохода алгоритма, получим . Достигнута требуемая точность, поэтому алгоритм заканчивает свою работу с . Характеристика относительного сокращения промежутка . В качестве решения можно взять среднюю точку последнего промежутка .

 

Метод золотого сечения

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

В методе золотого сечения на промежутке  симметрично относительно его концов выбираются точки  и , такие что

При этом точка  производит золотое сечение промежутка , а точка -промежутка .

 

Алгоритм

Шаг 1. Задать начальный промежуток неопределенности  и  - требуемую точность. Положить .

Шаг 2. Вычислить: .

Шаг 3. Вычислить .

Шаг 4. Сравнить  и :

а) если , то положить  и . Перейти к шагу 5.

б) если , то положить  и , . Перейти к шагу 5.

Шаг 5. Вычислить  и проверить условие окончания. Если , то процесс поиска завершается и . В качестве приближенного решения можно взять середину последнего промежутка . Если , положить  и перейти к шагу 3.

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

Для метода золотого сечения характеристика относительного уменьшения промежутка неопределенности  равна , где  - количество вычислений функции,  -округленное значение числа .

Пример 3. Найти минимум функции  методом золотого сечения.

Решение. В качестве начального промежутка неопределенности возьмем промежуток , положим .

1. Положим .

2. Вычислим ;

                    .

3. Вычислим .

4. Так как , то ;

.

5. Получим . Положим  и перейдем к шагу 3.

6. Вычислим .

7. Так как , то .

8. Получим . Положим  и перейдем к шагу 3.

9. Вычислим .

10.  Так как , то .

11.  Получим ; . В качестве решения можно взять .

Для данного примера характеристика относительного уменьшения начального промежутка неопределенности равна .

 

Метод хорд (секущих)

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

.

 Для приближенного решения данного уравнения можно использовать метод хорд. Этот метод основан на сокращении отрезков путем определения точки  пересечения с осью  хорды графика функции . Координата точки  определяется по формуле .

     

                                                                          

 

 

                                       

                               

              

 

 

 

Отрезок дальнейшего поиска  или  выбирается в зависимости от знака . Если , то выбирается , если  - .

    Таким образом, метод используется при наличии информации об отрезке  таком, что , а .

    Условие достижения требуемой точности в данном алгоритме накладывается не на длину промежутка неопределенности, а на величину .

 

Алгоритм

    Шаг 1. Задать начальный промежуток неопределенности  и  - требуемую точность. Положить .

Шаг 2. Вычислить .

Шаг 3. Вычислить .

Шаг 4. Если , то положить  и поиск завершить, иначе перейти к шагу 5.

Шаг 5. Если , то положить , иначе положить . Положить  и перейти к шагу 2.

В данном методе мы предполагали, что . При нарушении этого условия точку  можно указать сразу. Так, если  и , то  возрастает на , следовательно, , если  и , то  убывает на , следовательно, . В случае, если производная равна 0 на одном из концов отрезка , то этот конец и является решением задачи.

Пример 4. Найти минимум функции  методом хорд.

Решение. В качестве начального промежутка неопределенности возьмем промежуток , положим .

1. Проверим условие . Условие выполнено.

2. Положим .

3. Вычислим точку .

4. Так как , то переходим к шагу 3.

5. Поскольку   положим , .

6. Присваиваем  и переходим к шагу 2.

7. Вычислим точку .

8. Так как , то переходим к шагу 3.

9. Поскольку   положим , .

10. Присваиваем  и переходим к шагу 2.

На 6-й итерации получаем промежуток с концами . На данном промежутке метод генерирует точку , в которой . Алгоритм завершает работу, поскольку достигнута требуемая точность .

 

Метод Ньютона

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

Уравнение касательной к графику  в точке  имеет вид , поэтому точка , найденная из условия , определяется формулой .

Процедура нахождения точек  продолжается до тех пор, пока не будет достигнута требуемая точность, т.е. .

Алгоритм

Шаг 1. Задать начальную точку ,  - требуемую точность. Положить .

Шаг 2. Вычислить .

Шаг 3. Если , то положить  и поиск завершить, иначе перейти к шагу 4.

Шаг 4. Вычислить .

Шаг 5. Положить . Перейти к шагу 2.

Исследования метода Ньютона показывают, что при достаточно близком к точке минимума  выборе начального приближения , гарантируется скорость сходимости последовательности ,  к   вида

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

    Пример 5. Найти минимум функции  методом Ньютона.

Решение. Данная функция дважды дифференцируема и . В качестве начального приближения возьмем точку , положим .

1.    Вычислим .

2. Поскольку , то перейдем к шагу 4.

3. Вычислим .

4. Положим . Перейти к шагу 2.

5. Вычислим .

6. Поскольку , то перейдем к шагу 4.

7. Вычислим .

8. Положим . Перейти к шагу 2.

9. Поскольку , то перейдем к шагу 4.

10.  Вычислим .

11.  Положим . Перейти к шагу 2.

12.  Вычислим .

13.  Поскольку , то перейдем к шагу 4.

14.  Вычислим .

15. Положим . Перейти к шагу 2.

16.  Вычислим .

17.  Поскольку , процесс поиска заканчивается. В качестве решения задачи принимается точка .

Быстрая сходимость метода Ньютона для рассмотренного примера объясняется хорошим выбором начального приближения . Если, например, для данной функции в качестве начального приближения выбрать , то методом будет генерироваться последовательность точек

,

которая расходится.

Задачи для самостоятельного решения

1. Различными численными методами одномерной минимизации (метод перебора, метод деления отрезка пополам, метод золотого сечения, метод хорд, метод Ньютона) найти решение следующих задач.

1) ;

2) ;

3) ;

4) ;

5) ;

6) .

2. Может ли применение методов исключения отрезков привести к неверному определению , если функция  не является унимодальной? Ответ пояснить рисунком.

3. Требуется найти точку минимума унимодальной функции на отрезке длины 1 с точностью . Имеется возможность измерить не более 10 значений функции . Какой из прямых методов минимизации можно использовать для этого?

4. Указать класс функций, для которых точное определение точки минимума гарантировано в результате всего одной итерации метода Ньютона?

1. Общие принципы n -мерной минимизации. 2.Метод покоординатного спуска. 3. Методы градиентного поиска 4. Метод сопряженных направлений 5. Метод сопряженных градиентов 6. Метод Ньютона

Глава 9

                                

 

 

Методы безусловной минимизации в Rⁿ

 

Для численного решения задач безусловной минимизации вида

разработано много алгоритмов, использующих итерационные процедуры , где направление поиска точки x^{k +1} из точки x^k, а число  - величина шага в выбранном направлении. Работа таких алгоритмов на каждой итерации происходит по следующей схеме:

 

Шаг 1. Проверить условия останова и, если они выполнены, вычисления прекратить и взять точку  в качестве искомого решения.

Шаг 2. Зафиксировать ненулевой вектор   в качестве направления поиска.

Шаг 3. Выбрать число величину шага.

Шаг 4. Положить

 

Для проверки условий останова на шаге 1 на практике часто используются следующие критерии:  

|| x ^{k +1} - x^k ||<   , | f(x ^{k +1}) - f(x^k) |<  , ||  ||< ,

где - заданный параметр точности. Кроме того, при практической реализации эти алгоритмы полезно дополнять "дежурным" критерием останова ,

 

где  задаваемое заранее максимальное число итераций.

В качестве вектора  на шаге 2 могут выбираться единичные орты (покоординатный спуск), антиградиент в точке x^k (градиентные методы) и другие направления. Величина шага , как правило, выбирается так, чтобы выполнялось условие . В частности, чтобы гарантировать выполнение этого неравенства, можно выбирать = (будем в дальнейшем это называть правилом наискорейшего спуска). Для численного отыскания  может быть использован один из методов, описанных в предыдущем параграфе.

Рассмотрим примеры алгоритмов, построенных в соответствии с предложенной схемой. 

Метод покоординатного спуска

Этот метод заключается в последовательной минимизации целевой функции f(x) сначала по направлению первого базисного вектора е¹,затем второго е² и т.д. Таким образом, здесь  выбирается в соответствии с правилом наискорейшего спуска. После окончания минимизации по направлению последнего базисного вектора еⁿ цикл может повторяться. Метод покоординатного спуска может быть методом нулевого порядка, т.к. он может не использовать в работе производных функции f(x). Таким образом, он может применяться для оптимизации недифференцируемых функций.

 

Алгоритм

Шаг 0.  Выбрать начальное приближение х⁰ в пространстве ,

задать параметр точности . Найти f(x⁰), положить j=1.

Шаг 1. Pешить задачу одномерной минимизации