Необходимые и достаточные признаки

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

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

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

(2.1)

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

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

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

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

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

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

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

ОПТИМАЛЬНОСТИ ДОСТАТОЧНЫЕ УСЛОВИЯ

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

(1) при граничных условиях. y. (x 0) = y 0 ,y(x 1) = y 1 , достаточно, чтобы выполнялись следующие условия.

1) Кривая должна быть экстремалью, т. е. удовлетворять Эйлера уравнению

2) Вдоль кривой , включая ее концы, должно выполняться усиленное Лежандра условие

Fy"y" ( х, у, y" ) > 0.

3) Кривая должна удовлетворять усиленному Якоби условию, требующему, чтобы уравнения Якоби

(2) с начальными условиями

h(x 0)=0, h"(x 0) = 1

Функция Вейерштрасса, а и( х, у ) - наклон поля. экстремалей, окружающего

На самой экстремали условие (3) принимает

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

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

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

при условиях

где U - заданное замкнутое множество р-мерного пространства.

При использовании метода динамического программирования О. д. у. формулируются следующим образом. Для того чтобы управление u(t).было оптимальным управлением в задаче (5)-(8), достаточно, чтобы:

1) существовала такая S(x), к-рая имеет непрерывные частные производные при всех х, за исключением, быть может, нек-рого кусочно гладкого множества размерности меньше п, равна нулю в конечной точке х 1 , S (x 1 )=0, и удовлетворяет уравнению Беллмана

2) u(t)=v (x(t)), при , где v(х) - синтезирующая функция, определяемая из уравнения Беллмана:

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

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

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

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

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

Для того чтобы пара , доставляла абсолютный минимум в задаче (5) - (8), достаточно существование такой функции j(x), что

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

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

Лит. : Лаврентьев М. А., Люстерник Л. А., Курс вариационного исчисления, 2 изд., М.- Л., 1950; Блисс Г. А. Лекции по вариационному исчислению, пер. с англ., М., 1950; Беллман Р., Динамическое , пер. с англ., М., 1960; Болтянский В. Г., Математические методы оптимального управления, М., 1966; Кротов В. Ф., "Автоматика и телемеханика", 1962, т. 23, № 12, с. 1571-83; 1963, т. 24, № 5, с. 581-98; Бутковский А. Г., Теория оптимального управления системами с распределенными параметрами, М., 1965. И. Б. Вапнярский.

Математическая энциклопедия. - М.: Советская энциклопедия . И. М. Виноградов . 1977-1985 .

Смотреть что такое "ОПТИМАЛЬНОСТИ ДОСТАТОЧНЫЕ УСЛОВИЯ" в других словарях:

В теории оптимизации условия Каруша Куна Таккера (англ. Karush Kuhn Tucker conditions, KKT) необходимые условия решения задачи нелинейного программирования. Чтобы решение было оптимальным, должны быть выполнены некоторые… … Википедия

Решение задачи оптимального управления математической теории, в к рой управляющее воздействие u=u(t).формируется в виде функции времени (тем самым предполагается, что по ходу процесса никакой информации, кроме заданной в самом начале, в систему… … Математическая энциклопедия

В Википедии есть статьи о других людях с такой фамилией, см. Кротов. Вадим Фёдорович Кротов Дата рождения: 14 февраля 1932(1932 02 14) (80 лет) Место рождения … Википедия

Численные методы раздел вычислительной математики, посвященный методам отыскания экстремальных значений функционалов. Численные методы В. и. принято разделять на два больших класса: непрямые и прямые методы. Непрямые методы основаны на… … Математическая энциклопедия

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

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

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

- (род. 21 октября 1926, Новосибирск) российский математик. Заведующий кафедрой теоретической кибернетики математико механического факультета Санкт Петербургского государственного университета, член корреспондент Российской Академии Наук, академик… … Википедия

Владимир Андреевич Якубович (род. 21 октября 1926, Новосибирск) российский математик. Заведующий кафедрой теоретической кибернетики математико механического факультета Санкт Петербургского государственного университета, член корреспондент… … Википедия

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

Замечания:

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. Рассмотреть функцию, определенную на всей действительной оси и определить особые точки:

.

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

Представим критерий (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 через - искомое оптимальное управление.

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

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

Заметим, что если при введении обозначений (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). А это и означает, что условия оптимально­сти по форме останутся неизменными.