Методы оптимизации в АСКТП

Размещено на http://www.allbest.ru/

Вищій державний навчальний заклад

Приазовський державний технічний університет

Кафедра автоматизації технологічних процесів та виробництв

Конспект лекций

Методы оптимизации в АСКТП

Воротникова З.Е.

Мариуполь 2012



Введение

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

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

Среди различных типов оптимизационных задач особое место занимают задачи оптимизирования невыпуклых детерминированных функций с единственной точкой экстремума.

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

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

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

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

управление оптимизация невыпуклый нелокальность

Лекция 1. Оптимизация в управлении

Основные задачи теории управления

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

Задача стабилизации заключается в поддержании некоторых выходных (управляемых) характеристик объекта управления на заданных уровнях, несмотря на постоянно действующие возмущения о(t): гомеостаз

V(t) = const.

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

Задача выполнения программы, или задача программного управления, возникает, когда необходимо обеспечить наперед заданные траектории V(t). Иначе говоря, необходимо «заставить» объект управления изменять свои управляемые характеристики во времени по заданному закону, по определенной программе V*(t). Например, процесс разработки некоторого технического изделия на заводе должен протекать в соответствии с заранее разработанным временным графиком. Метаморфоза насекомых в живой природе также происходит в соответствии с некоторыми биологическими программами развития. Запускаемый космический аппарат обычно выводится на траекторию в соответствии с заранее заданной расчетной траекторией. Легко видеть, что задача стабилизации является частным случаем задачи программного управления.

В задачах слежения основная проблема сводится к формированию такой выходной траектории V(t) управляемого объекта, которая как можно более точно аппроксимировала бы другую, заранее не известную траекторию V*(t). Например, при управлении пушечной турелью оператор (наводчик орудия) при наводке на цель вращает легкие маховики (задавая траекторию V*(t)), а тяжелая пушечная турель отслеживает движение маховиков, изменяя, ориентацию ствола по углу и по азимуту (реализуя соответствующую траекторию V(t)). Аналогичные задачи слежения возникают, когда антенна радиолокатора отслеживает непредвиденные движения какого-либо летящего объекта. Число подобных примеров легко может быть увеличено.

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

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

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

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

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

В качестве примера можно рассмотреть теперь уже ставший классическим пример задачи об оптимальном в смысле расхода горючего режиме набора высоты и скорости летательным аппаратом, например, самолетом. На рис. 1.2 показано фазовое пространство самолета как объекта управления. Ось абсцисс является осью высот H, а ось ординат -- осью скоростей v Состояние самолета изображается точкой фазового пространства -- плоскости vOH.

Задача о наборе высоты и скорости самолетом

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

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

Основные принципы управления.

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

Жесткое управление. Принцип жесткого (разомкнутого) управления предполагает отсутствие обратной связи в общей схеме управления (см. рис. 1.1). Такие системы управления без обратной связи называются разомкнутыми. Чаще всего они применяются для целей программного управления.

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

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

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

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

В устройстве управления сравнивается желаемое V*(t) и действительное значения функции V(t). Это позволяет определить, насколько состояние объекта отличается от требуемого (задаваемого программой V*(t)). В результате управление строится как функция невязки:

U(t) = f(V(t)-V*(t)).

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

Понятие сложности системы управления

Отметим, что все сложности управления начинаются при попытке управления сложным объектом. Управление простыми объектами обычно не вызывает каких-либо проблем.

Перечислим теперь характерные признаки сложности объекта управления. К ним в первую очередь относятся:

1. Отсутствие описания (в том числе алгоритмического) оператора F*. В то же время, как уже говорилось, для целей управления сложным объектом оно совершенно необходимо.

2. Неожиданное, антиинтуитивное поведение объекта. Иногда это поведение моделируется и объясняется с помощью введения фактора стохастичности. Поэтому для построения систем управления сложными объектами привлекается аппарат статистической или стохастической теории управления.

3. Нестационарность (изменчивость во времени) оператора F*.

Структура современной системы управления сложным объектом.

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

На вход объекта управления поступают вектор управляющих воздействий U, вектор возмущений о₁ и дополнительные «идентифицирующие» входные воздействия d. Измерительная система позволяет при наличии измерительных шумов о₂ измерять доступные (измеримые) характеристики состояния объекта управления (весьма часто сами переменные состояния оказываются непосредственно неизмеримыми). Сам процесс построения оценок V` переменных состояния по измеряемому выходу W реализуется с помощью алгоритма оценивания состояния. Информация о состоянии объекта далее используется для выработки управляющих воздействий, реализуя принцип замкнутого управления.

Алгоритм оценивания состояния настраивается с помощью соответствующего алгоритма оптимизации. Сам алгоритм оценивания состояния и алгоритм его настройки функционируют на основе оценок параметров Р модели объекта управления, получаемых в соответствии с принятым алгоритмом идентификации (построения модели объекта управления). Алгоритм оптимизации устройства управления позволяет с помощью вектора параметров К организовать выбор оптимального алгоритма управления по полученным оценкам вектора состояний V' и по вектору параметров модели Р. На алгоритм управления оказывает влияние алгоритм оптимизации самого объекта управления (оптимизации режимов функционирования объекта). Как правило, это влияние также носит параметрический характер -- через вектор режимных параметров R. На вход алгоритма оптимизации объекта управления поступает информация о параметрах модели, полученной в результате идентификации.

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

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

.

Стратегия управления сложным объектом

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

Идентификация объектов управления.

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

Под моделью объекта управления понимается оператор F, связывающий состояние объекта V с его наблюдаемыми входами:

V=F(X,U).

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

Следует отличать неизвестный оператор объекта F* от оператора модели F. Ненаблюдаемые возмущения о при решении задачи идентификации оператора модели F рассматриваются как случайные помехи, затрудняющие процесс идентификации. Основная задача идентификации состоит в построении такого оператора модели F который был бы в определенном смысле близок к оператору объекта F*. При этом близость операторов оценивается исключительно по близости их реакций на одно и то же входное воздействие.

При построении оператора модели необходимо определить структуру S оператора F и вектор неизвестных параметров модели Р:

P = ‹S.P›.

Так, например, при построении модели динамического объекта может выбираться система обыкновенных дифференциальных уравнений в нормальной форме, правые части которой заданы с точностью до вектора неизвестных параметров Р. Именно за счет подбора этих параметров производится «подгонка» этой модели под имеющиеся экспериментальные зависимости и тем самым обеспечивается близость реакций модели и реального объекта на идентичные входные воздействия.

Задача построения структуры S и параметров Р оператора модели F называется идентификацией в широком смысле. Если структура оператора модели уже задана и необходимо определить только вектор неизвестных параметров модели Р, то имеем задачу идентификации в узком смысле, или задачу параметрической идентификации.

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

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

Таким образом, для задания оператора модели, вообще говоря, необходимо задавать две группы параметров:

F = ‹D, Р›.

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

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

V=F(X,U,P).

Различают два подхода к реализации процесса параметрической идентификации: пассивный и активный. Пассивная идентификация проводится в режиме нормального функционирования объекта управления -- без оказания на него специальных идентифицирующих воздействий в виде специальным образом подобранных сигналов U и X (идентифицирующие, или, как иногда говорят, «раскачивающие», воздействия часто реализуются только по каналам управления). Идентифицирующие сигналы d показаны на рис. 1.7.

Предположим для простоты, что задача идентификации решается для построения будущей системы управления и объект пока не управляется. При этом модель объекта управления упрощается и принимает вид [51]

V=F'(X,P).

Управляемый вход U объекта здесь отсутствует.

Сама идентификация, то есть определение параметров Р, осуществляется на основе информации о наблюдениях входов X и выходов V объекта в режиме нормальной эксплуатации. После получения необходимой информации о поведении объекта формируется функция невязки ш выходов модели и объекта. Например, в простейшем случае можно принять:



.

Здесь через V_i(t) обозначена реакция реального объекта на заданное входное воздействие X(t) по r-му выходу, а через V_iM(t,P) -- соответствующий (расчетный) выход модели (на вход модели поступает измеренный сигнал X(t) -- разумеется, его модельное представление). В данном выражении указаны i-е компоненты векторов V и V_M. Далее задача параметрической идентификации сводится к задаче поиска минимума некоторого целевого функционала, например, вида

.

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

В результате определяется искомый оптимальный вектор параметров Р. Сведение задачи идентификации к задаче минимизации функции многих переменных отнюдь не решает все проблемы идентификации. Хорошо известно, что возникают новые проблемы, например: как сформировать функции невязки и целевые функционалы в конкретном случае и как решить полученную задачу минимизации? Здесь нам важно подчеркнуть, что в конечном итоге задача идентификации может быть сведена к задаче минимизаций. Далее в основном тексте учебника мы более подробно рассмотрим важнейшие схемы параметрической идентификации и их реализации. Более подробно и полно проблема идентификации изложена в книге [52].

Обратимся теперь к активной идентификации. Активная идентификация предполагает подачу на вход объекта управления специальных идентифицирующих воздействий, вынуждающих объект управления «проявить себя» в максимальной степени. Такой подход по самой сути позволяет более эффективно по времени и точности получать оценки идентифицируемых параметров по сравнению с методом пассивной идентификации. При этом используются практически те же выражения для функций невязки и целевых функционалов. К сожалению, не все объекты допускают такое активное вмешательство в их работу, и это ограничивает область применимости метода активной идентификации.

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

Оценивание состояний объектов управления.

Алгоритм оценивания состояния (см. рис. 1.7) по наблюдаемому (зашумленному) выходу объекта W и модели объекта управления, построенной алгоритмом идентификации, строит наилучшую в некотором смысле оценку V' состояния V. В свою очередь, алгоритм оценивания состояния зависит от вектора параметров S, изменяя которые, мы можем влиять на эффективность алгоритма оценивания. Иногда задача оценивания состояния называется задачей о наблюдении. Объект называется наблюдаемым, если по измерениям выходного сигнала можно определить его состояние. Задача оценивания состояний является сложной самостоятельной проблемой, и ей посвящены многочисленные публикации.

Принято различать три типа оценок состояния динамического объекта: сглаживание, фильтрацию и прогноз.

При решении задачи сглаживания требуется построить оценку вектора состояния объекта в момент времени t по наблюдениям за выходом объекта вплоть до момента t' причем t'>t Таким образом, состояние определяется с некоторым запаздыванием (t'-t).B задачах фильтрации t' = t , а в задачах прогноза t' <t.

Рассмотрим в качестве примера задачу сглаживания.

Пусть движение некоторой динамической системы (объекта управления) определяется уравнением

где -- вектор переменных состояния, f-- известная функция.

Предполагается, что компоненты вектора состояния z непосредственно не измеряются. Измеряемым и непосредственно наблюдаемым является другой вектор связанный с z линейной зависимостью

где H(t) -- известная прямоугольная матрица размерности {s х г). Матрица H характеризуется конструкцией измерительного устройства.

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

Очевидно, для однократного вычисления значения функционала при заданном х необходимо вначале проинтегрировать приведенную систему дифференциальных уравнений с начальным условием х. Далее полученная расчетная траектория в выбранных точках дискретности t_j сравнивается с соответствующими измеренными значениями у(t_j). Полученная в соответствии с методом наименьших квадратов невязка и является значением целевого функционала в выбранной точке X. Минимизация целевого функционала может быть выполнена одним из представленных в этой книге методов параметрической оптимизации. Забегая вперед, уже здесь отметим, что поиск минимума полученного функционала с помощью традиционного «библиотечного» математического обеспечения может быть сопряжен с весьма значительными вычислительными проблемами. Тем не менее, сведение задачи оценивания состояния к задаче параметрической оптимизации является для нас принципиальным.

Алгоритмы оптимизации объектов управления.

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

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

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

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

Идентификация нелинейных детерминированных объектов.

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

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

Пусть оператор модели f задан с точностью до вектора х неизвестных параметров

где G{t) -- входной сигнал модели и объекта; H_м() -- выходной сигнал модели;

H(t) -- выходной сигнал объекта (рис. 1.9).

Подстройка параметров модели осуществляется в дискретные моменты времени

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

В (1.8) отсчет времени t производится от начала i-ro интервала наблюдений. Предполагается, что оператор модели задан алгоритмически. Алгоритм работы блока А основан на реализации принятой стратегии параметрической оптимизации.

Схема параметрической идентификации детерминированного объекта

Выводы

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

2. Большое число задач теории управления могут быть сформулированы как конечномерные оптимизациоршые задачи. К таким задачам, в частности, относятся:

* задачи параметрической идентификации нелинейных детерминированных объектов;

* задачи идентификации стохастических объектов;

* задачи экстремального регулирования;

* задачи синтеза адаптивных систем управления;

* задачи синтеза статистически оптимальных систем управления;

* задачи оптимального проектирования.

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

Лекция 2. Основные понятия теории оптимизации

Классификация оптимизационных задач по виду критерия оптимальности

1. Задачи математического программирования

,

где - скалярная функция на конечномерном множестве :

- задачи линейного программирования (ЛП): - линейная, допустимое множество Х - выпукло, задается линейными уравнениями и неравенствами. (Ядро ЛП - сиплекс-метод; теория двойственности, функция Лагранжа, существование седловой точки)

- задачи целочисленного ЛП (оптимальные решения Z);

- задачи квадратичного программирования;

- задачи дискретного программирования (допустимое множество - конечно);

- задачи выпуклого программирования (Х - выпукло, - выпуклая; теорема Куна-Таккера - аналог теории двойственности в ЛП);

- задачи невыпуклого программирования.

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

3. Задачи вариационного исчисления.

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

4. Задачи оптимального управления.

Классический пример задачи ОУ - задача о полете ракеты.

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

Для задачи ОУ характерны разные типы переменных: фазовые (положение в пространстве) и параметры управления ( - множество допустимых управлений, которое обычно является множеством кусочно-непрерывных функций).

Кроме того, обычно , .

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

Постановка классической задачи оптимизации

- целевая функция, значение которой характеризуют степень достижения цели (во имя которой поставлена или решается задача);

Х - множество допустимых решений, среди элементов которого осуществляется поиск; - n-мерное евклидово пространство.

Определение 1. Точка называется точкой локального минимума [максимума] функции на множестве Х, если существует окрестность точки такая, что справедливо .

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

Следует заметить, что сама функция может не иметь экстремума, но иметь условный экстремум.

Определение 2. Точка называется точкой глобального (абсолютного) минимума [максимума] функции на множестве Х, если функция достигает в этой точке своего наименьшего [наибольшего] значения, т.е. .

Замечания.

1) Задача сводится к задаче поиска минимума следующим образом: .

2) Если , то задача (1) называется задача безусловной оптимизации. Если Х задается условиями (ограничениями), накладываемыми на x, то задача (1) называется задачей условной оптимизации.

3) Обозначим - множество точек глобального минимума функции на множестве Х.

Тогда решить задачу (1) означает:

- найти множество и значение целевой функции в точках этого множества ;

- если , то найти ;

- убедиться, что функция не ограничена снизу на Х;

- убедиться в том, что .

Определение 1. Градиентом непрерывно дифференцируемой функции в точке x называется столбец-вектор, элементами которого являются частные производные первого порядка, вычисленные в данной точке:

Определение 2. Матрицей Гессе дважды непрерывно дифференцируемой в точке x функции называется матрица частных производных второго порядка, вычисленных в данной точке:

,

где .

Матрица Гессе является симметрической матрицей размера .

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

Вектор антиградиента - вектор, равный по модулю вектору градиента, но противоположный по направлению.

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

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

,

,

- евклидова норма вектора

,

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

Выражение называется квадратичной формой от переменных .

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

Определение 3. Квадратичная форма (а также соответствующая матрица Гессе ) называется:

положительно определенной (>0), если для любого ненулевого выполняется неравенство ;

отрицательно определенной (), если для любого ненулевого выполняется неравенство ;

положительно полуопределенной (), если для любого выполняется неравенство 0 и имеется отличный от нуля вектор , для которого =0;

отрицательно полуопределенной (), если для любого выполняется неравенство 0 и имеется отличный от нуля вектор , для которого ;

неопределенной (), если существуют такие векторы , , что выполняются неравенства , ;

тождественно равной нулю (), если для любого выполняется .

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

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

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

Пример:

,

тогда

положительно определена при любом Х, поэтому точка (2, 4, 6) является точкой локального минимума, а так как это единственная стационарная точка, то она же является и точкой глобального минимума.

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

Методы одномерной оптимизации

Аналитические методы решения.

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

Стационарные точки непрерывной функции

Из рисунка 1 видно, что в точках и касательная к графику функции будет параллельна оси OX, а это означает, что производная функции в этих точках будет равна нулю. Следовательно, и будут решениями уравнения .

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

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

Теорема 1(необходимое и достаточное условие существования экстремума функций одной переменной).

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

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

Понятие о численных методах оптимизации.

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

Любой численный метод имеет два этапа:

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

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

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

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

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

нулевого порядка - в них используется информация только о значениях минимизируемой функции;

первого порядка - использующие информацию также и о значениях первых производных;

второго порядка - использующие, кроме того, информацию о вторых производных;

и так далее.

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

В зависимости от способа выбора точек вычисления, алгоритмы делятся на пассивные и активные(последовательные).

В пассивных алгоритмах все точки выбираются одновременно до начала вычислений.

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

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

при этом

На практике обычно используются наиболее простые виды зависимости, например:

то есть выбор точки очередного вычисления зависит лишь от точки предыдущего вычисления и полученного результата или

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

В дальнейшем для нахождения будем пользоваться соотношением вида

При этом конкретный алгоритм определяется:

заданием точки ;

правилами выбора векторов и чисел на основе полученной в результате вычислений информации;

условием остановки.

Правила выбора и чисел могут предусматривать вычисления характеристик не только в точках , но и в других точках, отличных от . Именно поэтому в формулах (3 и (4) употреблены различные индексы.

Вектор определяет направление -го шага метода минимизации, а коэффициент - длину этого шага.

Обычно название метода минимизации определяется способом выбора , а его различные варианты связываются с разными способами выбора .

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

Среди методов минимизации можно условно выделить:

конечношаговые методы;

бесконечношаговые методы.

Конечношаговыми (или конечными) называются методы, гарантирующие отыскание решения задачи за конечное число шагов.

Для бесконечно шаговых методов достижение решения гарантируется лишь в пределе.

Сходимость методов оптимизации.

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

Метод сходится если , где - решение задачи .

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

Пример:

В данном примере минимизирующая последовательность не сходится к точке минимума .

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

Пусть .

Говорят, что:

1) последовательность сходится к точке линейно (с линейной скоростью, со скоростью геометрической прогрессии), если существуют такие константы и , что при ( 5 )

2) последовательность сходится к точке сверхлинейно(со сверхлинейной скоростью), если:

, при ( 6 )

3) последовательность сходится к точке с квадратичной скоростью сходимости, если существуют такие константы и , что

при

Иногда, сохраняя ту же терминологию, неравенства ( 5 ) - заменяют соответственно на неравенства

при

при ,

Большинство теорем о сходимости методов оптимизации доказывается в предположении о выпуклости целевой функции.

Для невыпуклых задач численные методы оптимизации позволяют отыскивать лишь локальные решения.

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

На практике часто используют следующие условия остановки:

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

Лекция 3. Методы одномерной минимизации

Основные понятия

Постановка задачи.

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

- наименьшее значение на ;

, удовлетворяющее ( 0 ) называется точкой минимума на ;

- множество точек минимума на ;

может быть пустым, содержать конечное или бесконечное число точек.

Замечание. Задача поиска максимума сводится к задаче поиска минимума :

Задача одномерной минимизации состоит из двух частей:

локализации точек минимума, то есть указания отрезков, содержащих единственную точку минимума;

поиска точки минимума на заданном отрезке при наличии информации о том, что на этом отрезке заведомо существует единственный минимум.

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

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

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

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

Затем, если , определяют следующие точки до тех пор, пока не будет получено В этом случае полученный интервал "накрывает" искомую точку минимума.

Если же, то выбирается противоположное направление. Точки строятся по правилу до тех пор, пока не будет получено

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

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

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

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

Классический подход.

Напомним 2 важные для данного рассмотрения теоремы из классического анализа.

Теорема Вейерштрасса. Если непрерывна на , то существует.

Теорема Ферма. Пусть дифференцируема в точке . Если доставляет локальный минимум , то

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

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

Тогда точками минимума могут быть такие точки, в которых:

- терпит разрыв;

- непрерывна, но не существует;

-

- либо , либо .

Рисунки ниже иллюстрируют эти 4 случая.

терпит разрыв в точке

непрерывна, но производной не существует

.

Методы решения задачи минимизации для унимодальных функций.

Понятие унимодальной функции.

Определение. унимодальна на , если существуют такие, что

строго монотонно убывает на ,

строго монотонно возрастает на,

для

Если ,то строго унимодальна.

Унимодальная функция не обязательно должна быть непрерывной и дифференцируемой. Ниже представлены примеры унимодальных функций.

Строго унимодальная, непрерывная, дифференцируемая функция

Нестрого унимодальная, непрерывная, дифференцируемая функция

При имеет разрыв I - го рода, при , производной у не существует.

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

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

Определение 2. Под численным методом одномерной минимизации понимается процедура получения вложенных отрезков, покрывающих точное решение:

.

Порядок метода.

Метод имеет порядок k, если он использует информацию о производных до k - порядка включительно. Обычно применяются методы 0-го, 1-го и 2-го порядков.

Сходимость метода.

Численный метод сходится, если последовательность сходится к точному решению, то есть (скорость сходимости характеризуется ) или метод сходится, если ; (скорость сходимости характеризуется разностью ).

Критерии останова.

Процесс вычислений желательно прервать, если

достигнута требуемая точность вычислений;

хорошее приближение не найдено, но скорость продвижения к оптимуму так упала, что нет смысла продолжать дальше;

метод начал расходится или зациклился.

Часто на практике критерием прерывания по 2-й или 3-й причине является выполнение предельно допустимого числа получений приближенных решений.

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

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

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

Поэтому, наряду с этим критерием обычно применяют один из двух следующих или даже сразу два:

...