Оптимизация дискретных систем

Пусть система может находиться в одном из состояний дискретного множества S. S* - дискретное фазовое пространство.

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

(12)

Здесь - состояние системы на i-м шаге.

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

Градиентные методы.

Пример отыскания максимума функции одной переменной.

Пусть y=f(x) (Рис. 28).

Рис. 28

Выберем произвольную точку х из области определения функции y=f(x). Заметим, что если точка выбрана слева от точки максимума (х = х₁), то производная от f(x) в точке х₁ и следовательно точка при разумном выборе величины параметра k находится ближе к экстремальной точке х₀.

Если же выбранная точка оказалась правее точки х₀ (х = х₂), то та же конструкция по прежнему приближает решение к экстремальной точке.

Таким образом, может быть построена последовательность точек

x(1), x(2), …, x(l), x(l+1), … , (1)

вычисляемых по рекуррентному правилу

, (2)

стягивающаяся к искомой экстремальной точке х₀.

Сходимость последовательности (1) к точке х₀ обеспечивается рациональным выбором численного значения k, определяющего длину шага. Рекурсивное соотношение (2) легко обобщается на случай отыскания экстремума функции многих переменных.

Пусть X*^T=(x*₁, x*₂, …, x*_n) - вектор, доставляющий максимальное значение функции F(x₁, x₂, …, x_n). Введём вектор-столбец значений частных производных от оптимизируемой функции F(X) в точке X^l , называемый градиентом, т.е.

(39)

и матрицу K(X^l).

Теперь вычисление точки X^l+1 на очередном шаге градиентной процедуры осуществим по формуле

(40) (3)

В соответствии с (3) вектор-градиент определяет направление перемещения от X^l к X^l+1, а матрица K(X^l) - длину шага.

Длина шага выбирается из следующих соображений:

её не следует выбирать слишком большой, чтобы не «проскочить» экстремум, т.к. при этом появляется опасность зацикливания;

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

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

При этом (3) записывается в виде

,

где скаляр kl определяется из условия

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

В результате проведения некоторого числа шагов в соответствии с (3) обеспечивается попадание внутрь произвольно малой окрестности экстремальной точки.

Критерием для останова может служить величина модуля вектора-градиента

Градиентную процедуру считаем законченной, как только численное значение модуля окажется < .

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

«Метод переменной метрики» использует информацию о поведении оптимизируемой функции в уже пройденных точках.

Достоинство: не требуется наличия аналитического представления производной от оптимизируемой функции и умение решать систему уравнений (7.1).

Необходимо уметь вычислять частные производные от функции F(X) в отдельных точках области определения.

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