Основные определения и классификация методов безусловной оптимизации

Методы безусловной оптимизации изложены в большом количестве учебной и научной литературы [1,5-10, 13, 15, 20-23, 25- 26, 34, 36-37, 40, 43, 46, 50-52, 54]. Создано и используется десятки методов и сотни вариантов алгоритмов их реализующих. Нами за основу выбрана классификация этих методов, приведенная в учебнике А.Г.Трифонова [46]. Кроме того добавлена дополнительная информация из других перечисленных выше источников. Причем в целях наглядности добавлены имеющиеся и нарисованные нами графические схемы сходимости процессов отыскания экстремума функции двух переменных. Алгоритмы описаны на основе этих схем.

Основные определения. Решение многих теоретических и практических задач сводится к отысканию экстремума (наибольшего или наименьшего значения) скалярной функции f(х) n-мерного векторного аргументах. В дальнейшем под x будем понимать вектор-столбец (точку в n-мерном пространстве). Этот вектор-столбец путем применения операции транспонирования становится вектором-строкой

.

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

f(x ) --> min.

Вектор х*, сообщающий минимум целевой функции, называют оптимальным.

Отметим, что задачу максимизации f(x) можно заменить эквивалентной ей задачей минимизации или наоборот. Рассмотрим это на примере функции одной переменной (рис. 1.1). Если х* - точка минимума функции y = f(x), то для функции y =- f(x) она является точкой максимума, так как графики функций f(x) и - f(x), симметричны относительно оси абсцисс. Итак, минимум функции f(x) и максимум функции - f(x) достигаются при одном и том же значении переменной х*. Минимальное же значение функции f(x), равно максимальному значению функции - f(x), взятому с противоположным знаком, т.е. min f(x) =-max(f(x)).

Рис. 1.1. Экстремумы функции одной переменной

Рассуждая аналогично, этот вывод нетрудно распространить на случай функции многих переменных. Если требуется заменить задачу минимизации функции f(x1, …, xn) задачей максимизации, то достаточно вместо отыскания минимума этой функции найти максимум функции f(x1, …, xn). Экстремальные значения этих функций достигаются при одних и тех же значениях переменных. Минимальное значение функции f(x1, …, xn) равно максимальному значению функции - f(x1, …, xn), взятому с обратным знаком, т.е. min f(x1, …, xn) =max f(x1, …, xn). Поэтому ниже рассматриваем только о задачу минимизации.

В реальных условиях на сами переменные xj, i=1, …. n, и некоторые функции от этих переменных gi (х), hi(х), характеризующие качественные свойства объекта, системы, процесса, могут быть наложены ограничения (условия) вида

a <= x <= b,

где вектор x ограничивается соответствующими векторами констант

, ; ,

а кроме того возможны ограничения в виде выражений

gi (х) = 0, i=1, …. n,

hi (х) <= 0, i=1, …. n,

Такую задачу называют задачей условной оптимизации. При отсутствии ограничений имеет место задача безусловной оптимизации.

Каждая точка х в n-мерном пространстве переменных х1, …, хn, в которой выполняются ограничения, называется допустимой точкой задачи. Множество всех допустимых точек называют допустимой областью G. Решением задачи (оптимальной точкой) называют допустимую точку х*, в которой целевая функция f(х) достигает своего минимального значения.

Точка х* определяет глобальный минимум функции одной переменной f(x), заданной на числовой прямой Х , если x * X и f(x*) < f(x) для всех x* X (рис. 1.2, а). Точка х* называется точкой строгого глобального минимума, если это неравенство выполняется как строгое. Если же в выражении f(х*) <= f(x) равенство возможно при х, не равных х*, то реализуется нестрогий минимум, а под решением в этом случае понимают множество х* = [x* X: f(x) = f(x*)] (рис. 1.2, б).

Рис. 1.2. Глобальный минимум. а - строгий, б - нестрогий

Точка х* Х определяет локальный минимум функции f(x) на множестве Х , если при некотором достаточно малом  > 0 для всех х, не равных х*, x X, удовлетворяющих условию ¦х - х*¦<= , выполняется неравенство f(х*) < f(х). Если неравенство строгое, то х* является точкой строгого локального минимума. Все определения для максимума функции получаются заменой знаков предыдущих неравенств на обратные. На рис.1.3 показаны экстремумы функции одной переменной f(х) на отрезке [a, b] . Здесь х1, х3, х6 - точки локального максимума, а х2, х4 - локального минимума. В точке х6 реализуется глобальный максимум, а в точке х2 - глобальный минимум.

Рис. 1.3. Экстремумы функции

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

Кроме того задача оптимизации функции двух переменных позволяет наглядно представлять схемы сходимости на плоском рисунке с поверхностями равного уровня. Поверхностью уровня (на плоскости - линией уровня) является поверхность, получаемая приравниванием выражения функции f(х) некоторой постоянной величине С, т. е. f(х) = С . Во всех точках этой поверхности функция имеет одно и то же значение С. Давая величине С различные значения С1, ..., Сn, получают ряд поверхностей, геометрически иллюстрирующих характер функции. В качестве примера на рис.1.4 приведена поверхность функции двух переменных f(x1,x2), имеющая минимум. Эта поверхность рассечена серией плоскостей, соответствующих различным значениям функции f(x1,x2) Если спроецировать линии пересечения таких плоскостей на плоскость координат x1x2 , по получаем серию линий равного уровня.

Рис. 1.4. Схема получения линий равного уровня в плоскости двух координат

Классификация методов безусловной оптимизации. Возможны два подхода к решению задачи отыскания минимума функции многих переменных f(x) = f(x1, ..., хn) при отсутствии ограничений на диапазон изменения неизвестных. Первый подход лежит в основе косвенных методов оптимизации и сводит решение задачи оптимизации к решению системы нелинейных уравнений, являющихся следствием условий экстремума функции многих переменных. Как известно, эти условия определяют, что в точке экстремума х* все первые производные функции по независимым переменным равны нулю:

, i=1, …, n.

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

,

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

Решение систем нелинейных уравнений - задача весьма сложная и трудоемкая. Вследствие этого на практике используют второй подход к минимизации функций, составляющий основу прямых методов. Суть их состоит в построении последовательности векторов х [0], х [1], …, х [n], таких, что f(х[0])> f(х [1])> f(х [n])>… В качестве начальной точки x[0] может быть выбрана произвольная точка, однако стремятся использовать всю имеющуюся информацию о поведении функции f(x), чтобы точка x[0] располагалась как можно ближе к точке минимума. Переход (итерация) от точки х [k] к точке х [k+1], k = 0, 1, 2, ..., состоит из двух этапов:

· выбор направления движения из точки х [k];

· определение шага вдоль этого направления.

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

Математически методы спуска описываются соотношением

x[k+1] = x[k] + akp[k], k = 0, 1, 2, ...,

где p[k] - вектор, определяющий направление спуска; ak - длина шага. В координатной форме:

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

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

или функции

.

Здесь k - номер итерации; справа заданные точности решения задачи.

Методы поиска точки минимума называются детерминированными, если оба элемента перехода от х[k] к x[k+l] (направление движения и величина шага) выбираются однозначно по доступной в точке х [k] информации. Если же при переходе используется какой-либо случайный механизм, то алгоритм поиска называется случайным поиском минимума.

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

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

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