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

Если отвлечься от экономического, физического, химического или иного содержания этих задач, то все они сводятся к следующей оптимизационной задаче:

Найти минимум (или максимум) функции или функционала на некотором множестве U некоторого пространства В, т.е.

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

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

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

.

Напомним некоторые определения из курса математического анализа [1]-[3].

Определение 1. Точку называют точкой минимума функции на U, если для любой точки ; величину называют наименьшим значением или минимальным значением на U и обозначают .

Множество всех точек минимума на U будем обозначать через .

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

Пример 1. Пусть при и . На множестве

а) минимальное значение равно 0, множество состоит из одной точки ;

б) множество содержит три точки ;

в) множество

есть счетное множество;

г) функция не имеет наименьшего значения на . В самом деле, (например, при достаточно большом ) такая, что . Это значит, что .

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

В примере 1 функция ограничена снизу на рассматриваемых множествах, а в примере 2 функция не ограничена.

Определение 2. Функция называется ограниченной снизу на множестве , если существует число такое, что . Функция не ограничена снизу, если существует последовательность , для которой .

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

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

1) при всех ;

2) Для любого сколь угодно малого числа найдется точка , для которой . Если функция не ограничена снизу на , то в качестве нижней грани на принимается . Нижнюю грань на обозначают через .

В примере 1 нижняя грань , в примере 2 нижняя грань .

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

Введем еще два определения.

Определение 4. Последовательность называется минимизирующей для функции на , если .

Из определения и существования нижней грани следует, что минимизирующая последовательность всегда существует.

Определение 5. Скажем, что последовательность сходится к непустому множеству , если , где - расстояние от точки до множества .

Заметим, что если , то всегда существует минимизирующая последовательность, сходящаяся к ; например, можно взять стационарную последовательность , где - какая-либо точка из . Однако при не всякая минимизирующая последовательность будет сходиться к .

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

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

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

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

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

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

2) Сформулируйте определение функции ограниченной сверху, определение верхней грани функции на заданном множестве и определение функции ограниченной на заданном множестве.

Рис. 1. Задача максимизации

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

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

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

1) строго монотонно убывает при (если );

2) строго монотонно возрастает при (если );

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

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

Если все точки задаются заранее, до начала вычислений, - это пассивная стратегия.

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

Последовательную стратегию можно реализовать следующими способами:

а) применением квадратичной и кубической интерполяции, где по нескольким вычисленным значениям функции строится интерполяционный полином, а его минимум указывает на очередное приближение искомой точки экстремума;

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

Стратегия поиска включает в себя:

1. Выбор начального интервала. Границы интервала неопределенности должны быть такими, чтобы функция была унимодальной.

2. Уменьшение интервала неопределенности.

3. Проверку условия окончания. Поиск заканчивается тогда, когда длина текущего интервала неопределенности

оказывается меньше установленной величины.