1. Мера положения изображающей точки

Основная задача управления заключается в выборе управляющих переменных u_j в системе (2) или системе (19), принадлежащих допустимой области U и обеспечивающих выполнение совокупности требований к управляющему процессу



Эти ограничения выделяют в 2n-мерном пространстве некоторую область А. При n=1 область А представлена на рис. 7.

Рис. 7.

При заданных управляющих переменных g_s принимают некоторое конкретное значение, т. е. управляющему процессу будет соответствовать некоторая изображающая точка r. ОЗУ будет решена, если изображающая точка окажется в области А. Дать метод решения ОЗУ - значит дать метод целенаправленного перевода изображающей точки в область А. Численные методы решения любых задач представляют собой методы последовательного улучшения решения в смысле некоторой меры. Так, в задачах приближенного построения оптимального управления такой мерой служит минимизируемый или максимизируемый функционал. Чем меньше (или больше) значение функционала, тем лучше управление и тем ближе оно к оптимальному. Численные методы теории оптимального управления могут быть использованы и для решения ОЗУ если ввести меру, характеризующую удаление изображающей точки от области А. Чем меньше значение этой меры, тем ближе изображающая точка к области возможных решений ОЗУ, тем лучше решение. Использую эту меру, можно построить улучшенную последовательность решений.

Из. рис. 7 видно, что величина



является мерой положения изображающей точки. В простейшем случае все a_s=1. Если все , то r₁=0. Таким образом, абсолютный минимум меры r₁ равен нулю и он достигается тогда, когда изображающая точка попадает в область А. Если ОЗУ не имеет решения, то абсолютный минимум достичь невозможно. Мера r₁ известна в теории оптимального управления как функция 'штрафа'.

В первой главе было отмечено, что на практике представляет интерес найти такое управление, такие проектные параметры, при которых гарантируется наибольшее удаление изображающей точки от границ области А. Используя меру r₁, нельзя найти такое решение, т. к. r₁=0, как только изображающая точка попадает в область А. Можно было бы, например, выбрать меру

где , а при . Тогда r₂=0 в области , что позволяет определить некоторую совокупность решений ОЗУ. Однако здесь остается неясным определение a.

Более эффективной мерой является:



Если ОЗУ поставлена корректно, то минимизируя меру r, можно достичь на каком-то шаге области А и тем самым найти какое-то решение. Так как минимум r может быть меньше единицы, то продолжая спуск по r, можно найти некоторое множество решений ОЗУ, а нахождение минимакса гарантирует наибольшее удаление от границ области А.

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

Рассмотрим некоторые численные методы решения задачи минимизации функционалов, зависящих от совокупности постоянных (независящих от времени) параметров u_j, j=1,2:r. Если в исходной постановке управление является функцией времени , то используя различные методы аппроксимации, необходимо предварительно задать с точностью до параметров. Так, например, управление можно представить (аппроксимировать) косочно-линейной функцией на отдельных участках или в виде разложения с неизвестными параметрами. Для этого потребуется дополнительная информация о физической стороне задачи.

Для минимизации r используем методы нелинейного программирования.

2. Общий анализ дискретных методов

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

(28)

Переход из m¥^-ой точки в (m+1) назовем успешным, если выполняется условие (28), а в противном случае - неуспешным.

Аналитически переход от точки записывается в виде

(29)

где: - вектор, определяющий направление движения из точки к точке ;

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

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

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

В градиентном методе направление совпадает с направлением антиградиента функции r, т. е.:

(30)

где: - градиент функции r в точке ;

.

¥Èтерационный процесс:

(31)

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

В координатной форме процесс (31) записывается в виде:

.

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

Приведем здесь простейший алгоритм уменьшения :

.

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

.

Закон изменения запишем в виде:



где: связаны с числами следующим образом:



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

Замечание 1. Можно добиться некоторого ускорения процесса решения, если после выбора направления двигаться по нему до минимума r в направлении или до тех пор, пока не будет выполнено условие .

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

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

В этих методах направление определяется следующим образом



Различные варианты этого метода различаются способом выбора параметра . Если =0 для всех n, то рассматриваемый метод совпадает с градиентным методом. Более подробно этот метод изложен в работах [], [].

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



4. Поиск при наличии 'оврагов' у минимизируемой функции

Характерной особенностью решения ОЗУ является наличие оврагов у функции r, которые совпадают с оврагами функции g_s, или с линиями пересечения поверхностей g_s. Дать точное определение 'оврага' трудно. Можно сказать, что у 'овражной' функции имеются области, в которых по какому-нибудь направлению или нескольким направлениям функции r меняется очень медленно, и есть такие направления быстрого изменения r. Типичная карта линий уровня овражной функции приведена на рис. 7.

Рис. 7.

Здесь линии уровня сильно растянуты по направлению CD и сильно сжаты вдоль направления CE. Следовательно, по направлению CE функция меняется быстро, а по направлению СD - медленно.

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

Процесс поиска можно ускорить следующим образом. Пусть изображающая точка в результате применения какого-либо метода спустилась к оврагу и совершила несколько переходов с одного склона на другой, рис. 8. Этим самым обнаруживаем направление оврага. Проведем через средние точки В₁ и В_i отрезков АА_i и А_iА_i+1 прямую. Если кривизна оврага невелика, то прямая В₁В_i укажет примерное направление оврага. По этому направлению можно сделать большой шаг в некоторую точку С₁, откуда начинается новый цикл спуска по описанной процедуре.

Рис. 8.

Опишем здесь еще один метод поиска минимума овражных функций. В начале выберем две точки u⁽⁰⁾, u⁽¹⁾ из которых производим спуск на дно оврага, (рис. 9), в результате чего находим точки А⁽⁰⁾ и А⁽¹⁾. Затем проводим прямую А⁽⁰⁾А⁽¹⁾ и вдоль нее делаем большой шаг в сторону убывания r в некоторую точку u⁽²⁾. Из точки u⁽²⁾ опять произведем спуск в точку А⁽²⁾ на дно 'оврага'. Далее по направлению А⁽¹⁾А⁽²⁾ делаем шаг в точку u⁽³⁾ и т. д. В заключение отметим, что минимизация функций, имеющих овраги, почти всегда приводит к увеличению счета.

Рис. 9

5. Определение градиента функции

При выборе того или иного численного решения ОЗУ необходимо оценивать его с точки зрения удобства программирования, требуемой памяти и количества операций при реализации указанных методов на ЭВМ. Анализ описанных методов спуска показывает, что наиболее трудоемкой частью расчета является определение производных функций r(u). Эти производные вычисляются либо на каждом шаге, либо через несколько шагов.

1. Метод конечных разностей.

Здесь:



где: - малая величина, называемая пробным шагом.

Этот метод чрезвычайно прост для программирования и требует меньшего объема памяти машины. Недостатком его является то, что он может давать большие погрешности.

2. Метод интегрирования уравнений чувствительности.

Дифференцируя эти уравнения по параметрам u_i, получим систему для определения функций чувствительности

где:

Используя уравнения (32) можно с высокой точностью определить частные производные . Пусть, например, Тогда , при этом находятся аналитически, а - из решения уравнения (32).

1. Метод случайного поиска

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

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

Итерационный алгоритм поиска оптимальных параметров представим в виде: .

Различные методы случайного поиска отличаются способами определения приращения , [].

1. Алгоритм случайного спуска с линейной тактикой

Обозначим . Алгоритм записывается следующим образом:

где случайные пробы предполагаются достаточно малыми по модулю, чтобы вероятность получения положительной реакции (Dr⁽ⁿ⁾<0) была достаточно большой.

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

1. Чисто случайная оценка направления. Здесь s=s, где - единичный случайный вектор.
2. Оценка направления s по наилучшей из нескольких проб. В этом случае s=s*, где s* удовлетворяет условию:

. Здесь g - величина пробного шага;

m - число случайных шагов, из которых выбирается наилучшее.

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

, где - единичный вектор, определяющий интересующее направление. Имеются и другие модификации оценки направления спуска.