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

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

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

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

Характеристические свойства, которыми обладает оптимальная точка (вектор) в задаче программирования математического. Форма О. н. у. определяется формой, в которой задается допустимое множество. Впервые общие О. н. у. для экстремальных задач при наличии ограничений в виде равенств сформулировал Лагранж (см. Лагранжа правило множителей). В 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

не обращалось в нуль в точках замкнутого справа интервала

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

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

4) Существует окрестность кривой , в каждой точке (x, у).к-рой при любом у" выполняется неравенство

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

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

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

при условиях

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

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

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

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

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

- условия правильности утверждения А, без выполнения к-рых утверждение Азаведомо не может быть верным, и, соответственно, при выполнении.к-рых утверждение Азаведомо верно...
Математическая энциклопедия
- формальные описания различных представлений об оптимальном. Обычно О. п. отражают те или иные черты интуитивного понимания устойчивости, выгодности и справедливости...
Математическая энциклопедия
- условия, устанавливающие зависимость истинностик...
Словарь логики
- См.: необходимые и достаточные условия...
Экономический словарь
- применения принципов поглощения наказаний и сложения наказаний регламентированы в ч. 2 и 3 ст. 69 УК РФ. Однако в законе не урегулирован вопрос назначения наказания по совокупности преступлений, в которую входят...
Словарь-справочник уголовного права
- в математике, см. Необходимые и достаточные условия...
Естествознание. Энциклопедический словарь
- наиболее существенный признак оценок, определяющих условия достижения цели какой-либо деятельности...
Строительный словарь
- English: Work conditions Совокупность значений параметров электрооборудования, характеризующих его работу в чанный момент и при заданных условиях эксплуатации Источник: Термины и определения в электроэнергетике...
Строительный словарь
- критерий, согласно которому функционирование системы признается наилучшим из всех возможных вариантов...
Словарь бизнес терминов
- признак, по которому функционирование системы признается наилучшим из возможных вариантов...
Большой бухгалтерский словарь
- см. Необходимые и достаточные условия...
- признак, на основании которого производится сравнительная оценка возможных решений и выбор наилучшего. Содержание К. о. объективно обусловлено многими факторами: характером общественного строя,...
Большая Советская энциклопедия
- Необходимыми условиями правильности утверждения А называются такие условия, без соблюдения которых утверждение А заведомо не может быть верным, а достаточными условиями правильности утверждения А...
Большая Советская энциклопедия
- количественный или порядковый показатель, выражающий предельную меру экономического эффекта принимаемого решения для сравнительной оценки возможных решений и выбора наилучшего...
Большой энциклопедический словарь
- в математике...
Большой энциклопедический словарь

"ОПТИМАЛЬНОСТИ ДОСТАТОЧНЫЕ УСЛОВИЯ" в книгах

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

Из книги Экономический анализ. Шпаргалки автора Ольшевская Наталья

83. Классификация экономикоматематических методов по признакам оптимальности По классификационному признаку оптимальности все экономико-математические методы (задачи) подразделяются на две группы: оптимизационные и неоптимизационные. Если метод или задача позволяет

Достаточные причины, объединенные логикой «или-или»

Из книги Теория ограничений Голдратта. Системный подход к непрерывному совершенствованию автора Детмер Уильям

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

Глава 4. Необходимые и достаточные условия возникновения жизни во Вселенной

Из книги Неоднородная Вселенная автора Левашов Николай Викторович

Глава 4. Необходимые и достаточные условия возникновения жизни во Вселенной 4.1. Постановка вопроса Вопрос о возникновении жизни на нашей планете всегда был «камнем преткновения». С древних времён философы, учёные пытались разгадать тайну жизни. Создавались разные

Третья производственная революция. Необходимые и достаточные условия

Из книги автора

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

Из книги Большая Советская Энциклопедия (НЕ) автора БСЭ

11.4. Замечания относительно поиска в графах, оптимальности к сложности

Из книги Программирование на языке Пролог для искусственного интеллекта автора Братко Иван

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

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

Из книги Организация времени. От личной эффективности к развитию фирмы автора Архангельский Глеб

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

Из книги Введение в психологическую теорию аутизма автора Аппе Франческа

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

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

Замечания:

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

Условия оптимальности

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

Замечания:

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)

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

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

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

Кроме того:

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

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

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