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

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

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

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

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

Характеристические свойства, которыми обладает оптимальная точка (вектор) в задаче программирования математического. Форма О. н. у. определяется формой, в которой задается допустимое множество. Впервые общие О. н. у. для экстремальных задач при наличии ограничений в виде равенств сформулировал Лагранж (см. Лагранжа правило множителей). В 1951 амер. математики Г. Кун и А. Таккер сформулировали необходимые и достаточные условия оптимальности точки х в задаче программирования выпуклого, т. е. в задаче отыскания

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

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

Осн. матем. аппаратом, используемым при построении О. н. у. для задач матем. программирования в конечномерном пространстве, являются теоремы отделимости выпуклых множеств и теория линейных неравенств. Исследование необходимых условий экстремума для задач матем. программирования в бесконечномерных простр. приобрело особое значение в связи с задачами оптим. управления. Впервые необходимые условия экстремума функционала на мн-ве банахова простр. сформулировал сов. математик Л. В. Канторович в 1940. В середине 50-х годов сов. математик Л. С. Понтрягин сформулировал в форме

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

Сущность общей теории О. н. у. заключается в следующем. Пусть требуется отыскать

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

для достаточно малых t и для которых Далее будем считать, что существует касательное к L подпростр. , т. е. для всякого найдется такой вектор что для достаточно, малых t, причем при Кроме того, пусть существует выпуклый конус Ко, для любого элемента которого выполняется условие (4) для Тогда выполняется следующее утверждение (теорема Дубовицкого - Милютина): для того, чтобы точка х являлась решением задачи (3), необходимо, чтобы

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

Помимо самостоятельного значения, О. н. у. играют важную роль при создании вычислительных алгоритмов для эффективного отыскания оптим. точки х. На основе теории О. н. у. удалось с новой точки зрения осмыслить некоторые классические результаты теории чебышевских приближений, проблемы моментов И др. Р. А. Поляк, М. Е. Примак.

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

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

(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, Новосибирск) российский математик. Заведующий кафедрой теоретической кибернетики математико механического факультета Санкт Петербургского государственного университета, член корреспондент… … Википедия

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

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

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

(2.1)

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

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

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

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

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

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

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

Предыдущая статья: Чему равна скорость света Следующая статья: Чему равна скорость света