Материал: Бородакий Нелинейное программирование в современных задачах оптимизации 2011

На рис. 1.1.1 приведены некоторые варианты унимодальных функций.

Рис. 1.1.1. Варианты унимодальных функций

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

Заметим, что предположение об унимодальности функции в окрестности точки экстремума весьма естественно. Получение информации о таком промежутке является важным предварительным этапом процедуры минимизации.

16

1.2. Методы одномерной минимизации

Рассмотрим с общих позиций ряд методов, позволяющих найти минимум функции f (x) при ограничениях x [a,b] .

1.2.1. Методы нахождения глобального минимума унимодальных функций

1.2.1.1. Прямые методы минимизации

Данные методы основаны на вычислении значений функции f(x) в некоторых точках; они не используют значений производных оптимизируемой функции.

Метод перебора – простейший, но редко используемый в серьезных задачах.

Согласно этому методу отрезок [a,b] делится на п равных частей

в этих точках, и путем сравнения определяется точка минимума хт:

Метод перебора, предполагающий предварительный выбор точек xi, называется также пассивной стратегией поиска точки минимума x*. На практике точки xi выбираются заранее, когда удобно провести (n +1) независимый эксперимент по измерению

значений функции f(x), а последовательное измерение этих значений трудоемко или невозможно по каким-либо причинам.

Однако использование информации о функции f(x) для выбора очередной точки xi измерения (вычисления) функции f(x), уже

полученной в предыдущих экспериментах, приводит к более эффективному поиску точки x*.

18

Методы минимизации, в которых точки xi определяются в

процессе поиска с помощью найденных ранее значений f(x), называются последовательными методами. Практически все рассматриваемые ниже методы относятся к этому классу.

Метод золотого сечения. Метод состоит в том, что исходный отрезок [a, b] уменьшается по определенному закону, постепенно

стягиваясь к точке минимума (рис. 1.2). Сокращение отрезка происходит за счет его деления и отбрасывания частей, не содержащих экстремальной точки. Отрезок делится в отношении «золотого сечения» (отсюда название).

Рис. 1.2. Схема разбиения отрезка для поиска экстремума

Прежде всего, при реализации этого метода необходимо задать желаемую точность ε вычисления точки x*. Количество вычислений функции заранее не задается и полностью определяется точностью ε.

Метод Фибоначчи. Этот метод почти полностью совпадает с методом золотого сечения, но есть два отличия:

1)отрезок делится с помощью чисел Фибоначчи –

γ0 = γ1; γn = γn−1 + γn−2 , n ≥ 2,

врезультате получаем следующую последовательность чисел:

1, 1, 2, 3, 5, 8, 13, 21,…;

2) требуется до начала работы метода задать число шагов n (так

как на первой итерации отрезок делится пропорционально γn−2 и

γn

γn−1 , а величина п изменяется в обратную сторону к нулю).

γn

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

19

Следует отметить, что как в методе «золотого сечения», так и в методе с использованием чисел Фибоначчи легко аналитически рассчитать количество вычислений функции на отрезке [a, b] , если

желаемая точность вычисления x* – ε, и, наоборот, какая будет точность при п вычислениях функции.

Метод золотого сечения имеет несколько меньшую скорость сходимости, чем метод Фибоначчи.

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

В этом отношении более предпочтительными оказываются методы, основанные на полиномиальной аппроксимации.

Идея метода такова: если на отрезке [a, b] с внутренней точкой минимума есть основание полагать, что функция f (x) достаточно

хорошо аппроксимируется многочленом (2-й, 3-й степени), то за приближенное значение x* целесообразно взять точку минимума этого многочлена.

1.2.1.2. Методы минимизации, основанные на использовании производных функции

Во многих случаях эти методы обладают более высокой скоростью сходимости по сравнению с прямыми методами поиска экстремума.

Метод дихотомии. При использовании этого метода вычисляется середина отрезка, в которой находится производная функции f (x) ; в зависимости от знака производной отбрасывается

одна из половин отрезка. За счет чего отрезок стягивается. Скорость сходимости данного метода выше, чем у методов

«золотого сечения» и с использованием чисел Фибоначчи.

Метод касательных. Данный метод используется только для выпуклых функций и имеет простой геометрический смысл: находят абсциссу c точки пересечения касательных к графику функции f (x) , проведенных в граничных точках отрезка (рис. 1.3),

для этого нужны производные в этих точках.

20