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

 

В данном параграфе рассматриваются задачи одномерной минимизации, т.е. задачи вида

.

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

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

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

                                                   

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

Большинство известных методов одномерной минимизации применяется для класса унимодальных функций.

Определение 1. Функцию  будем называть унимодальной на отрезке , если она определена во всех точках отрезка  и существует точка , в которой функция достигает глобального минимума на , причем слева от этой точки функция не возрастает, а справа не убывает.

Заметим, что в данном определении не предполагается ни гладкость, ни непрерывность функции. Приведем некоторые графические иллюстрации унимодальных функций

 

 

 

                                                                         

 

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

Существуют две принципиально различные стратегии выбора точек, в которых осуществляются вычисления. Если все точки задаются заранее, до начала вычислений, - это пассивная стратегия. Если все точки выбираются последовательно в процессе поиска с учетом результатов предыдущих вычислений, - это последовательная стратегия. Примером реализации пассивной стратегии является метод перебора или равномерного поиска.

 

Метод перебора

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

Алгоритм

Шаг 1. Задать начальный промежуток неопределенности ,  - количество вычислений функции.

Шаг 2. Вычислить точки , равностоящие друг от друга.

Шаг 3. Вычислить значения функции в  найденных точках: .

Шаг 4. Среди точек  найти такую, в которой функция принимает наименьшее значение: .

Шаг 5. Точка минимума  принадлежит промежутку: , на котором в качестве приближенного решения может быть выбрана точка .

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

 

Пример 1. Найти минимум функции  методом перебора.

Решение. Воспользуемся алгоритмом перебора.

1. В качестве начального промежутка неопределенности возьмем промежуток . Зададим  так, чтобы  содержал  равных промежутков.

2. Определим точки вычисления функции: .

3. Вычислим значения функции в полученных точках: , , , , , , , , .

4. В точке  функция принимает наименьшее значение: .

5. Искомая точка минимума после девяти вычислений принадлежит промежутку: , в котором выбирается точка . При этом характеристика относительного уменьшения начального промежутка неопределенности .