Оптимизация дискретных систем
Пусть система может находиться в одном из состояний дискретного множества S. S* - дискретное фазовое пространство.
Для любого из возможных состояний Si определим множество допустимых управлений S. Система может переходить из одного состояния в другое. При этом будем считать, что система обладает марковским свойством, т.е. будущее состояние системы зависит только от состояния, в котором система находится в настоящий момент времени, и используемого в этот момент управления. В соответствии с этим введём функцию переходов, используя которую запишем рекуррентное соотношение, определяющее эволюцию системы
(12)
Здесь - состояние системы на i-м шаге.
Методы решения экстремальных задач при отсутствии ограничений.
Градиентные методы.
Пример отыскания максимума функции одной переменной.
Пусть y=f(x) (Рис. 28).
Рис. 28
Выберем произвольную точку х из области определения функции y=f(x). Заметим, что если точка выбрана слева от точки максимума (х = х1), то производная от f(x) в точке х1 и следовательно точка при разумном выборе величины параметра k находится ближе к экстремальной точке х0.
Если же выбранная точка оказалась правее точки х0 (х = х2), то та же конструкция по прежнему приближает решение к экстремальной точке.
Таким образом, может быть построена последовательность точек
x(1), x(2), …, x(l), x(l+1), … , (1)
вычисляемых по рекуррентному правилу
, (2)
стягивающаяся к искомой экстремальной точке х0.
Сходимость последовательности (1) к точке х0 обеспечивается рациональным выбором численного значения k, определяющего длину шага. Рекурсивное соотношение (2) легко обобщается на случай отыскания экстремума функции многих переменных.
Пусть X*T=(x*1, x*2, …, x*n) - вектор, доставляющий максимальное значение функции F(x1, x2, …, xn). Введём вектор-столбец значений частных производных от оптимизируемой функции F(X) в точке Xl , называемый градиентом, т.е.
(39)
и матрицу K(Xl).
Теперь вычисление точки Xl+1 на очередном шаге градиентной процедуры осуществим по формуле
(40) (3)
В соответствии с (3) вектор-градиент определяет направление перемещения от Xl к Xl+1, а матрица K(Xl) - длину шага.
Длина шага выбирается из следующих соображений:
её не следует выбирать слишком большой, чтобы не «проскочить» экстремум, т.к. при этом появляется опасность зацикливания;
её нежелательно выбирать слишком малой, т.к. при этом итерационная процедура последовательного приближения к экстремальной точке может оказаться очень медленно сходящейся.
В вычислительной практике широкое применение находит метод наискорейшего спуска Коши, в котором шаг выбирается из условия максимизации (минимизации) оптимизируемой функции при движении в направлении градиента.
При этом (3) записывается в виде
,
где скаляр kl определяется из условия
Метод наискорейшего спуска очень прост в реализации, но в ряде случаев не обеспечивает быстрой сходимости, т.к. используется информация о поведении в определённой пробной точке Xl лишь первых производных оптимизируемой функции.
В результате проведения некоторого числа шагов в соответствии с (3) обеспечивается попадание внутрь произвольно малой окрестности экстремальной точки.
Критерием для останова может служить величина модуля вектора-градиента
Градиентную процедуру считаем законченной, как только численное значение модуля окажется < .
Существенный недостаток: при реализации каждая итерация выполняется независимо от других, т.е. информация, которая могла бы ускорить сходимость, не накапливается и не используется.
«Метод переменной метрики» использует информацию о поведении оптимизируемой функции в уже пройденных точках.
Достоинство: не требуется наличия аналитического представления производной от оптимизируемой функции и умение решать систему уравнений (7.1).
Необходимо уметь вычислять частные производные от функции F(X) в отдельных точках области определения.
В особо сложных случаях оценку численного значения производной можно получить, используя конечные приращения функции в нужных точках.
