Оптимальности необходимые условия. Достаточные причины, объединенные логикой «или-или»

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

Представим критерий (4.2) как некоторую функцию искомого управления

Здесь под и и £ понимаются последовательности , , записанные для определенности в виде расширенных векторов с размерностями (N+l)m и (N+l)r соответственно. Зависимость функции конечного состояния J от и и неявная и проявляется через уравнение (4.1). Формально, задача оптимизации состоит в отыскании среди допустимых такого вектора и, который обращает в минимум критерий . А это - обычная задача математического программирования. Необходимое условие оптимальности в такой задаче сводится к выполнению условия неотрицательности производной в искомой точке и по любому допустимому направлению , т. е.

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

где через в свою очередь обозначен градиент функции J по отдельному вектору .

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

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

для всех допустимых т. е. удовлетворяющих условию

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

Физический смысл каждого из условий (4.4) заключается в том, что вариация терминального критерия (4.2) за счет вариации управления в i -й момент, вычисленная относительно оптимального управления, есть величина неотрицательная.

Условия оптимальности (4.4) в явном виде пока не связаны с исходной математической моделью. Установим эту связь. С этой целью раскроем производные , связав последние с уравнением (4.1). Сначала покажем, каким образом может быть вычислена производная при любом управлении и и любом возмущении . Для этого продифференцируем функцию J = F(x N + l) по вектору с учетом связи (4.1). Можно записать следующую цепочку соотношений:

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

получаем более компактное выражение для производной

Введем теперь в рассмотрение также формально следующую скалярную функцию:

которая представляет собой по сути скалярное произведение вектора , определяемого в соответствии с рекуррентным соотношением (4.5), и вектора , являющегося правой частью исходного уравнения (4.1). Функция Н i определяемая согласно (4.7), называется гамильтонианом. Подчеркнём, что в общем случае гамильтониан является случайной функцией, так как зависит от возмущения . Как увидим в дальнейшем, гамильтониан является удобной конструкцией при формировании как условий оптимальности, так и реализации различных численных методов оптимизации. Начнем с условий оптимальности. Нетрудно установить, что частные производные гамильтониана по своим аргументам имеют следующий вид:

С учетом этого исходные уравнения движения (4.1), а также соотношения (4.5), определяющие вектор , могут быть приведены к следующей канонической форме:

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

Если теперь вернуться к выражению (4.6), то с использованием понятия гамильтониана его можно записать в виде

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

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

которые должны выполняться для всех допустимых .

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

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

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

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

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

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

Решение задачи программирования при этом сводится к использованию условия (4.11) на каждом шаге управления с целью выявления структуры управления и последующего решения системы (4.8) с найденной структурой.

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

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

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

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

где через , обозначено любое допустимое управление , a через - искомое оптимальное управление.

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

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

Условия оптимальности решения бывают двух типов: необходимые и достаточные.

Необходимые условия оптимальности.

Общая формулировка необходимых условий: если из утверждения А всегда следует утверждение В, то В необходимо для А.

Применительно к задаче оптимизации: из утверждения А (- лучший элемент множестваD ) следует утверждение В (- лучший элемент множестваL , принадлежащего D и образующего окрестность
) (рис.1.7).

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

Достаточные условия оптимальности.

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

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

Иными словами, для того, чтобы X  был оптимальным решением на множестве D , достаточно чтобы X  был оптимальным решением на множестве V , включающем множество D , и принадлежал множеству D .

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

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

(см. рис. 1.8)

2. Определение максимума функции одной переменной.

2.1. Постановка задачи. Методы решения оптимизационных задач.

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

(2.1)

(2.2)

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

Где

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

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

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

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

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

2.2. Аналитический метод решения задачи. Условия максимума функции одной переменной.

Пусть
- непрерывная и дважды дифференцируемая функция при
иX 0 - точка предполагаемого маусимума функции. Для того, чтобы при X 0 функция достигала max необходимо, чтобы при любом другом Х , сколь угодно близком к X 0 , т.е.
, выполнялось соотношение(2.3)

Разложим
в ряд Тейлора в окрестности точкиX 0

При небольших  Х , членами, содержащими приращения в степени больше единицы можно пренебречь и тогда из (2.4) следует:

Подставляя (2.5) в (2.3) окончательно получаем необходимое условие максимума функции одной переменной:

(2.6)

При использовании этого условия могут возникнуть два варианта:

1.
- внутренняя точка интервала допустимых значений (рис. 2.3). В этом случае знак Х не определен и для выполнения условия (2.6) необходимо

(2.7)

При этом знак разности (2.3) определяется знаком первого отброшенного члена ряда Тейлора, т.е. знаком
. Поэтому необходимое условие max (2.7) дополняется условием

(2.8)

2.
- граничная точка интервала
. В этом случае знак Х определен (рис. 2.4) и для расчетов будем использовать выражение (2.6).

Рис.2.3. Х * Х * Х

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

Пример. Определить максимум функции
при

а)
, б)
, в)
;

а) X 0 = 0.6, внутренняя точка отрезка
, следовательно, знак ΔX не определен и необходимо проверить выполнение условия (2.8).

0

Условие (2.8) выполняется.

б)
, проверим
- нижняя граница отрезка
, следовательно, Х  0 .

Проверяем выполнение условия (2.6).

Условие (2.6)
выполняется, т.е..

в)
. ПроверимХ = 0.5 – верхняя граница отрезка
, следовательно, Х  0 .

Проверяем выполнение условия (2.6):  0

Условие (2.6) выполняется, т.е.

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

Замечания:

1. Если функция обладает свойством унимодальности, то локальный минимум автоматически является глобальным минимумом.

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

Теорема 4.1. (необходимое условие минимума первого порядка): Пусть функция ¦ дифференцируема в точке . Если – локальное решение задачи (4.1), то

(4.5)

где – градиент функции.

Точка х *, удовлетворяющая условию (4.5), называется стационарной точкой функции ¦ или задачи (4.1). Ясно, что стационарная точка не обязана быть решением, т.е. (4.5) не является достаточным условием оптимальности. Такие точки являются подозрительными на оптимальные.

Пример 4.1 . Рассмотрим, например, функцию f (x ) = x 3 (рис. 4.4). Эта функция удовлетворяет необходимому условию оптимальности, однако, не имеет ни максимума, ни минимума при х * = 0, т.е. и точка х * – стационарная точка.

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

x* x

Рис. 4.6. График функции, имеющей точку перегиба

Теорема 4.2. (необходимое условие минимума второго порядка): Пусть функция ¦ дважды дифференцируема в точке . Если х * – локальное решение задачи (4.1), то матрица неотрицательно определена, т.е.

h E n , (4.6)

где – гессиан функции ¦ в точке .

Достаточное условие локальной оптимальности содержит характерное усиление требований на матрицу .

Теорема 4.3. (достаточное условие минимума второго порядка): Пусть функция ¦ дважды дифференцируема в точке . Предположим, что , а матрица положительно определена, т.е.

, h E n , h ≠ 0. (4.7)

Тогда х * – строгое локальное решение задачи (4.1). Для функции числового аргумента (n = 1) условия (4.6) и (4.7) означают, что вторая производная как скалярная величина не отрицательна и положительна соответственно.

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

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

Теорема 4.4 . Пусть в точке х * первые (n −1) производные функции обращаются в нуль, а производная n -го порядка отлична от нуля:

1) Если n − нечетное, то х * – точка перегиба;

2) Если n − четное, то х * – точка локального оптимума.

Кроме того:

а) если эта производная положительная, то х * – точка локального минимума;

б) если эта производная отрицательна, то х * – точка локального максимума.

Для того чтобы применить эту теорему 4.4 к функции f (x ) = x 3 (пример 4.1) , вычислим:

Так как порядок первой отличной от нуля производной равен 3 (нечётное число), точка х = 0 является точкой перегиба.

Пример 4.2. Рассмотреть функцию, определенную на всей действительной оси и определить особые точки:

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

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

(2.1)

обращается в нуль.

Векторы , удовлетворяющие условию

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

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

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

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

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

Представим критерий (4.2) как некоторую функцию искомого управления

где через в свою очередь обозначен градиент функции J по отдельному вектору .

для всех допустимых т. е. удовлетворяющих условию

получаем более компактное выражение для производной

Введем теперь в рассмотрение также формально следующую скалярную функцию:

Если теперь вернуться к выражению (4.6), то с использованием понятия гамильтониана его можно записать в виде

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

которые должны выполняться для всех допустимых .

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

где через , обозначено любое допустимое управление , a через - искомое оптимальное управление.

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

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

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

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

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

Покажем теперь, что в задаче управления дискретной системой (4.1) с целью минимизации интегротерминального критерия (4.3)

полученные условия оптимальности (4.10) или соответственно (4.11), (4.12) сохраняются. Однако вместо соотношений (4.7) и (4.5), определяющих гамильтониан и сопряженный вектор удовлетворяют следующим уравнениям:

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

несмотря на то, что гамильтониан теперь определяется согласно (4.14) вместо (4.7). А это и означает, что условия оптимальности по форме останутся неизменными.

Уравнения прямой в пространстве - это уравнения двух пересекающихся плоскостей Как найти прямую пересечения двух плоскостей

Переподготовка увольняемых военнослужащих II