Содержание к диссертации
Введение
ГЛАВА I. Вариация допустимого упрашенйя и необхо димые условия оптимальности 19
1.1. Постановка задачи 19
1.2. Вариация управления 21
1.3. Необходимые условия оптимальности 30
1.4. Дополнительные слагаемые вариации управления 42
ГЛАВА 2. Численные алгоритмы 58
2.1. Алгоритм вычисления матрицы \^(К) 59
2.2. Построение измененного управления 65
2.3. Формулировка алгоритма оптимизации и до казательство его сходимости 82
2.4. Алгоритмы оптимизации для управлений, не являющихся вполне регулярными 89
2.5. Локальное исследование скорости сходимо сти алгоритмов метода возможных направ лений 95
2.6. Алгоритмы оптимизации для других типов задач дискретного оптимального управ ления 105
ГЛАВА 3. Приложения численного метода
3.1. Математические постановки задач оперативного планирования добычных работ на
карьерах в режиме усреднения НО
3.2. Численное решение задач 116
3.3. Исследование контурных моделей карьера . 126
3.4. Постановка и решение задач оптимизации контуров карьеров 135
Заключение 145
Литература
- Вариация управления
- Дополнительные слагаемые вариации управления
- Формулировка алгоритма оптимизации и до казательство его сходимости
- Исследование контурных моделей карьера
Введение к работе
Задачи дискретного оптимального управления с ограничениями, зависящими от фазовых переменных, представляют собою класс экстремальных задач, имеющий многочисленные практические приложения. К этому классу относятся задачи планирования развития народного хозяйства в рамках многоотраслевых макроэкономических моделей, задачи управления запасами, расчета химических реакторов и т.п. В настоящей работе рассматриваются также новые примеры задач данного класса, возникающие при оптимизации открытых горных разработок. Задачи дискретного оптимального управления, называемые часто также многошаговыми задачами оптимизации, естественно возникают при моделировании детерминированных процессов, состояния которых измеряются через дискретные промежутки времени, а управляющие воздействия могут принимать всевозможные вещественные значения в некотором диапазоне. При этом случай, когда некоторые из ограничений задачи зависят не только от переменных управления, но и от фазовых переменных, кажется наиболее распространенным.
Исследование задач дискретного оптимального управления началось на рубеже 1960-х гг. К этому времени важнейший результат теории непрерывного оптимального управления - принцип максимума Л.С. Понтрягина - получил строгое математическое обоснование [42,54] . Поэтому ряд авторов (например, Л.-Ц.Фан и Ч.-С.Вань [62^ ) формулировали и для нелинейных задач дискретного оптимального управления необходимые условия оптимальности в виде принципа максимума. Л.И.Розоноэр [54j показал, что для линейных задач дискретного управления принцип максимума является необходимым и достаточным условием оптимальности и пришел к выводу, что для нелинейных задач
- 5 -принцип максимума, вообще говоря, не имеет места. Пример задачи, в которой функция Гамильтона имеет лишь локальный максимум на множестве допустимых управлений, был построен А.Г.Бутковским [б] . Условия, при которых в задаче дискретного оптимального управления справедлив принцип максимума, были изучены А.И.Пропоем 44J , Р.Габасо-вымрё}, Г.Халкиным[7б], Б.Н.Пшеничным\48J, наиболее общие условия были найдены А.Я.Дубовицким[22]. А.И.Пропоем(45,46Jбыли установлены необходимые условия оптимальности в терминах возможных направлений посредством применения специальных допустимых вариаций, т.е. допустимых вариаций управления, отличных от нуля только на одном шаге. А.М.Тер-Крикоров [59]рассмотрел задачи дискретного оптимального управления с бесконечным числом шагов.
Задачи дискретного оптимального управления возникают также, когда для решения задач непрерывного оптимального управления используется конечноразностная аппроксимация. Такой подход обоснован в работах Ю.М.Ермольева и В.П.Гуленко [25J , Б.М.Будака, Е.М.Берко-вича и Е.Н.Соловьевой [б] и других. Он широко применяется при численном решении задач (см., например, монографию Р.П.Федоренко \Ьз\ и работы Н.И.Грачева и Ю.Г.Евтушенко [l8,I9j , описывающие пакет программ оптимизации, разработанный в ВЦ АН СССР).
Библиография по дискретному оптимальному управлению весьма обширна (см.монографии [4,47,62) ),и поэтому во введении далее рассматриваются только работы, имеющие непосредственное отношение к предмету диссертации.
Для численного решения задач дискретного оптимального управления могут использоваться методы собственно дискретного управления и методы смежных областей математики. Прежде всего, задачу дискретного управления можно считать задачей математического программирования специального вида.Ее можно рассматривать как задачу минимизации по переменным управления целевой функции, заданной в неявном виде
- б -
посредством разностных уравнений, при ограничениях на управляющие воздействия, заданных как в явном, так и в неявном виде. Но ту же задачу можно рассматривать как задачу условной оптимизации, в которой независимыми переменными являются переменные управления и фазовые переменные, а разностные уравнения являются ограничениями типа равенства J47,c.I20J . Для численного решения получающихся задач могут употребляться методы математического программирования без существенной модификации, причем специфика задачи для некоторых методов приводит к уменьшению объема вычислений по сравнению с общей задачей математического программирования с тем же числом переменных.
С другой стороны, ряд методов решения задач непрерывного оптимального управления легко переносится на случай задач с дискретным временем. Наконец, некоторые методы разработаны специально для дискретного оптимального управления. Среди последних в первую очередь возникли методы, основанные на поиске управления, удовлетворяющего необходимому условию оптимальности - принципу максимума. Таковы четыре алгоритма, опубликованные без обоснования в работе ЛгЦ.Фана и Ч.-С.Ваня [бз] . Обоснование сходимости аналогичных методов для задач непрерывного управления, предложенных в работах И.А.Крылова и Ф.Л.Черноусько [зз] , Ф.Л.Черноусько и Н.В. Баничука [67] , опубликовано А.А.Любушиным в 1979г. в статье зб]. Из [Зб] следует, что алгоритм, гарантирующий сходимость для нелинейной задачи непрерывного управления, не может быть перенесен на случай дискретного управления. Как отмечается в статье Ю.М.Волина, Г.М.Островского и Б.В.Тандита [l5] , применение методов данного типа резко усложняется, если гамильтониан многоэкстремален.
Для задач непрерывного управления с ограничениями типа равенства Т.М.Энеевым Гб9І предложен метод параболического спуска, ко-
_ 7 -торый, очевидно, может быть применен и для задачи дискретного управления. Метод Т.М»Энеева основан на поиске управления, удовлетворяющего необходимым условиям слабого относительного экстремума. В работе [б9| предлагается преобразовывать ограничения-неравенства в равенства с помощью введения дополнительных компонент управления. Однако известно [24,c.35l] , что хотя преобразованная задача формально эквивалентна исходной, но в ней множество управлений, удовлетворяющих необходимым условиям слабого экстремума, существенно шире, чем в исходной, что приводит к "прилипанию" управ-: ления к границе допустимой области.
К прямым методам для рассматриваемого класса задач относятся различные варианты метода возможных направлений и метода проекции градиента, а также динамическое программирование. Метод динамического программирования, разработанный Р.Беллманом [З] , принципиально имеет весьма широкую область применения. Однако экспоненциальная зависимость времени счета от размерности фазового вектора препятствует его использованию в задачах оптимального управления, и, как отмечает Ю.Г.Евтушенко [24,c.285j , никаких практических задач, кроме самых элементарных, решить с его помощью не удалось. Дцея динамического программирования используется в методе вариаций в фазовом пространстве, разработанном в ВЦ АН СССР Н.Н.Моисеевым и его сотрудниками. Этот метод пригоден для задач с фазовыми ограничениями, в которых целевой функционал аддитивен. При его использовании область изменения фазового вектора заменяется дискретной "шкалой состояний" [~37J , так что если диапазон изменения одной фазовой переменной содержит X. значений, то для П--мерного фазового вектора шкала состояний содержит пІл-Ч* значений. Поэтому исходный вариант метода [37J , для которого время решения задачи пропорционально /V-j , а объем машинной памяти -/V,,
практически может быть использован только в задачах небольшой размерности. Локальные минимумы можно получить с помощью метода "блуждающей трубки" \2д\ , в котором на очередной итерации находится решение, оптимальное в окрестности траектории, полученной на предыдущей итерации. Но и для этого варианта имеет место экспоненциальный рост времени счета от размерности фазового вектора, хотя и значительно более медленный. Наиболее широкое распространение получил метод локальных вариаций [34j , который можно применять для задач любой размерности. Р.П.Шедоренко [63,c.I3I-I32j приводит пример задачи,в которой метод локальных вариаций не гарантирует получения локального оптимума. Перечисленные методы пригодны, когда размерность фазового вектора и размерность управления совпадают. Для более общей задачи И.А.Вателем и А.Ф.Кононенко
[I2j разработан метод бегущей волны, являющийся обобщением метода локальных вариаций.
Метод возможных направлений представляет собой дальнейшее развитие симплекс-метода линейного программирования применительно к нелинейным задачам. Этот метод для решения общей задачи нелинейного программирования с ограничениями типа неравенств предложен в работах Г.Зонтендейка [2б] и С.И.Зуховицкого, Р.А.Поляка и М.Е. Примака J27J . Различные алгоритмы метода разработаны также Д.М. Топкисом и А.Ф.Вейноттом [81] , Э.Полаком [4l| . Для задач выпуклого программирования локальное исследование скорости сходимости проведено О.Пиронно и Э.Полаком [80j , а глобальное - Дж.Олрайтом
\у6] . Для невыпуклых задач линейная скорость сходимости доказана Р.У.Чейни [72J при ряде специальных предположений; в частности, для алгоритма Г.Зойтендейка в [72J предполагается, что оптимальное решение является угловой точкой множества допустимых решений.
Для задач дискретного оптимального управления численные мето-
да возможных направлений разработаны А.И.Пропоем [45-47] . Для задач без фазовых и смешанных ограничений направления спуска в пространстве управлений определяются независимо для разных шагов процесса. Если число активных фазовых или смешанных ограничений невелико (например, если ограничения наложены только на конечное состояние процесса), целесообразно воспользоваться методами декомпозиции для нахождения направления спуска [47] . Для остальных случаев предлагалось использовать специальные допустимые вариации управления общего вида \4&] . Возможности такого подхода рассматриваются и в настоящей работе в 2.2 и 3.2.
Другой вариант метода возможных направлений применительно к конечноразностным аппроксимациям задачи непрерывного оптимального управления предложен Р.П.Федоренко [бз] под названием "метод последовательной линеаризации". Этот метод цригодіен в первую очередь для задач с ограничениями на конечное состояние. Для решения задачи выбора направления Р.П.Федоренко разработал специальный двойственный метод линейного программирования.
Метод проекции градиента является довольно близким к методу возможных направлений, но применяется в первую очередь к задачам с ограничениями типа равенств. Использованию этого метода для задач оптимального управления посвящены многочисленные работы А. Миеле с соавторами (например, [75J ); другой вариант метода изложен в работе Р.П.Федоренко [63J . Общим достоинством прямых методов является то, что они строят минимизирующие последовательности допустимых (или близких к допустимым) управлений. С другой стороны, если начальное допустимое управление не задано, его получение может оказаться трудной задачей.
В математическом программировании широкое распространение получили методы преобразования, сводящие решение задачи условной оп-
тимизации к решению последовательности задач безусловной минимизации или реже задач условной оптимизации с меньшим числом ограничений (см. монографии А.Фиакко и Г.Мак-Кормика [65] , К.Гроссмана и А.А.Каплана [20] и сборник обзорных статей под редакцией Ф. Гилла и У.Мюррэя [68J ). К методам этой группы относятся двойственные методы, методы штрафных и барьерных функций, модифицированных функций Лагранжа и ряд других.
Двойственные методы в дискретном оптимальном управлении были разработаны Б,Н.Пшеничным [49J , а также ^с.Уилсоном [82] . В этих работах разностные уравнения трактуются как ограничения типа равенств. Задача определения значений переменных управления и фазовых переменных при заданных величинах двойственных переменных распадается на несколько задач невысокой размерности, число которых равно числу шагов процесса /V . Благодаря этому время выполнения одной итерации зависит от j\j линейно. Двойственные методы пригодны, однако, не для любых задач многошаговой оптимизации, а только для тех, в которых значение целевого функционала в прямой и двойственной задаче совпадают.
Методы штрафных функций и модифицированных функций Лагранжа формально применимы к любым задачам. Однако они требуют нахождения на каждой (внешней) итерации глобального минимума в задаче безусловной минимизации. Но для невыпуклых функций невозможно гарантировать нахождение глобального минимума. Известны [20,с. 55-57 и C.I38-I42J следующие условия, при которых нахождение локального минимума во вспомогательных задачах приводит к нахождению локального минимума в исходной задаче: известна область, в которой находится искомый локальный минимум; точки локального минимума во всех вспомогательных задачах принадлежат этой области и доставляют в ней абсолютный минимум в своих задачах. Не требу-
- II -
ется глобальной минимизации в методе простой итерации, предложенном в статье А.И.Голикова и Ю.Г.Евтушенко [l7J . Специально для динамических задач методы преобразования были разработаны В.В.Ве-личенко рЗ,14] и позднее Б.С.Разумихиным [5ІІ . В работах В.В. Величенко получены оценки близости приближенного решения к точному при заданных коэффициентах штрафа.
Каждая внешняя итерация рассмотренных методов преобразования состоит в минимизации некоторой функции, зависящей от всех переменных управления, общее число которых равно IYI-/V , где ffl -размерность управления. Широко распространенным быстросходящимся методом безусловной минимизации является метод сопряженных направлений, для которого, однако, решение задачи не может быть гарантированно получено менее чем за ІП- /V итераций даже в случае, когда минимизируемая функция является квадратичной. Каждая (внутренняя) итерация требует вычисления градиента минимизируемой функции, что может быть сделано с помощью сопряженных переменных за (ГП+Ю)* П * /V умножений, не считая вычисления производных всех ограничений. Таким образом, одна внешняя итерация методов преобразования требует по крайней мере ГУЬП'/М+ГОтУ умножений. Не менее чем квадратичная зависимость времени счета от числа шагов /V неблагоприятна для применения методов преобразования в задачах с большим /V .
Особое место занимают алгоритмы дифференциального динамического программирования (метод впервые был предложен Д.К.Мейном
\7д\ ), применяющиеся как в дискретном, так и в непрерывном оптимальном управлении. В задачах, содержащих ограничения, зависящие от фазовых переменных (С.Б.Гершвин и Д.Х.^Зжекобсон L74J , К.Оно L79J ), вводятся двойственные переменные, и эти переменные, так же как и переменные управления, пересчитываются на каждой
итерации с целью все более точного соблюдения условий оптимальности Беллмана в дифференциальной форме. Метод не требует решения каких-либо вспомогательных задач оптимизации и является очень экономным в отношении объема вычислений: одна итерация требует порядка (fW+fl) -А/ умножений. Наиболее общим является алгоритм К.Оно, который пригоден для решения задач, содержащих одновременно смешанные ограничения-равенства и неравенства. Недостаток метода состоит в том, что функция Беллмана предполагается дважды непрерывно дифференцируемой. Однако, как отмечает В.Г.Болтянский [AJ , функция Беллмана, как правило, не обладает этим свойством на всей области определения. Поэтому алгоритмы К.Оно сходятся не с любого начального приближения. Если же алгоритм сходится, то он может сходиться даже сверхлинейно. Предполагается также, что оптимальное управление удовлетворяет некоторому условию регулярности, которое в настоящей диссертации называется условием вполне регулярности, но не всегда это предположение оправдывается .
Таким образом, задача создания вычислительных алгоритмов с гарантированной сходимостью, учитывающих специфику динамических задач и за счет этого обеспечивающих уменьшение объема вычислений, является актуальной. Целью диссертационной работы является разработка и теоретическое и экспериментальное исследование таких алгоритмов, а также математическая формализация прикладных задач, которые могут быть решены с их помощью. Разработанные в ней алгоритмы оптимизации строятся для задач со смешанными ограничениями типа равенств и неравенств без каких-либо предположений о линейности или выпуклости функций, входящих в постановку задачи.
В работе рассматриваются два вида прикладных задач: задачи оперативного планирования добычных работ на карьерах и задачи оп-
- ІЗ -ределения конфигурации карьеров. Рассмотрение таких задач как оптимизационных стало традиционным (см. библиографию в работе С.Я.Арсеньева и А.Д.Прудовского [i] , обзорную статью С.Д.Коробова [Зі] и работу И.Б.Табакмана [57j ), накоплен большой опыт их практического решения. Однако для известных автору работ характерным является определенное упрощение решаемых задач в целях их приспособления к использованию вычислительных методов, известных постановщикам задач (более подробно эти вопросы обсуждаются в 3.1, 3.3). Целью прикладной части диссертационной работы прежде всего является разработка более адекватных математических моделей для рассматриваемых задач горного производства, а также способов решения этих задач.
Диссертационная работа состоит из введения, трех глав, заключения, списка литературы и приложений.
В первой главе вводится и изучается новая конструкция вариации допустимого управления. В І.І определяется изучаемый класс задач. В 1.2 дается определение вариации управления. В приращении управления на К-ом шаге выделяются два основных слагаемых: "оптимизационное" и "компенсационное". Вводится матрица Сек) , обладающая тем свойством, что при любом приращении фазового вектора ЛХ(К) основное компенсационное слагаемое ССК)-ЛХСЮвместе с АЭС(К) не изменяют в линейном приближении значений ограничений из заданного активного набора, включающего все ограничения, обращающиеся в равенство. Достаточное условие существования матрицы С(К) состоит в линейной независимости градиентов активных ограничений по переменным управления на К -ом шаге. Если это условие справедливо направлении Щ при любом /< , то матрицы С(К) могут быть определены при любом К ; такое управление называется в работе вполне регулярным. В 1.3 для вполне регулярных управле-
- 14 -ний формулируются и доказываются необходимые условия оптимальности, по форме напоминающие условия оптимальности для задач без смешанных ограничений и поэтому простые для проверки. Устанавливается также, что введенные условия оптимальности для вполне регу лярных управлений равносильны условиям оптимальности для вариаций управления общего вида.
В 1.4 рассматривается обобщение предложенной вариации управления на случай задач, в которых оптимальное управление удовлетворяет более слабым условиям регулярности. Формулируются и доказываются необходимые условия оптимальности и для этого случая.
Вторая глава является центральной в работе - в ней формулируются и обосновываются итерационные алгоритмы для рассматриваемого класса задач. В 2.1 формулируется алгоритм вычисления матрицы основанный на идее -разложения с помощью Гауссовых исключений. Алгоритм гарантирует ограниченность норм на последовательностях управлений, сходящихся к вполне регулярному управлению.
В 2.2 рассматривается вычисление измененного допустимого управления. Предлагаются два способа вычисления направления спуска для разработанного метода, а также изучается задача нахождения "специальных" (по определению А.И.Пропоя [46] ) направлений спуска для рассматриваемого класса задач. Формулируется итерационный алгоритм нахождения дополнительного компенсационного слагаемого, обеспечивающего соблюдение ограничений-равенств, исследуются условия его сходимости.
В 2.3 формулируется оптимизационный алгоритм в целом. Алгоритм имеет ряд вариантов. Доказывается, что у последовательности управлений, построенной согласно алгоритму, имеется сходящаяся подпоследовательность и если предельное управление для подпо-
- 15 -следовательности является вполне регулярным, то это управление удовлетворяет необходимым условиям оптимальности, сформулированным в 1.3.
В 2.4 рассмотрены два способа решения задач без предположения о вполне регулярности оптимального управления. Первый из них основан на рассмотрении нескольких последовательных шагов процесса как одного укрупненного шага, второй - на использовании расширенной вариации управления, введенной в 1.4.
В 2.5 проводится исследование скорости сходимости метода возможных направлений. Способ исследования тесно связан с идеей, положенной в основу определения вариации управления, и опирается на преобразование направления спуска. Показывается, что при незначительной модификации одного правила алгоритма Г.Зойтендейка обеспечивается линейная скорость сходимости при вполне естественных предположениях. Доказывается также линейная скорость сходимости предложенного алгоритма при определенном выборе одного из параметров.
В 2.6 рассмотрены возможности использования предложенного численного метода для решения других видов задач: с целевым функционалом нетрадиционного вида, с вектором параметров, а также аналогов задачи о быстродействии.
Третья глава посвящена вопросам решения конкретных задач с помощью предложенного вычислительного метода.
В 3.1 показывается, что многие характерные постановки задачи оперативного планирования добычных работ на карьерах в режиме усреднения качества формализуются в классе задач дискретного оптимального управления со смешанными ограничениями. Эти задачи не обладают свойством выпуклости.
В 3.2 описываются вычислительные эксперименты по решению
задач с помощью предложенного алгоритма. Рассматриваются вопросы точности полученного решения, зависимости времени счета от размерности управления /D и числа шагов Л/ , приводятся результаты сравнения с решениями, полученными при использовании специальных допустимых вариаций управления, по методу К.Оно Г^э] и с помощью пакета программ для решения задач оптимального управления, разработанного в ВЦ АН СССР [24] .
В 3.3 вводятся и изучаются новые контурные модели карьера. Формулируется модель карьера, в которой его контуры считаются замкнутыми гладкими кривыми ограниченной кривизны. Модель более традиционного типа получается путем конечномерной аппроксимации непрерывной модели.
В 3.4 показывается, что задачи оптимизации контуров карьеров, в основу которых положены сформулированные модели, могут быть приведены к виду, удобному для применения разработанного численного метода. Обсуждаются вычислительные трудности решения таких задач. В конце основного текста формулируются основные результаты работы. Приводится список литературы из 84 наименований. Работа содержит 3 приложения. В приложении I показывается, что сопряженные траектории, введенные в 1.2 и 1.4, могут быть вычислены с помощью множителей Лагранжа, и приводятся конкретные выражения для этих множителей. На оптимальном управлении полученные множители Лагранжа удовлетворяют обычным условиям неотрицательности и дополняющей нежесткости. Приложение 2 содержит доказательства вспомогательных утверждений из второй главы. В приложении 3 доказывается, что основная конечномерная модель карьера аппроксимирует непрерывную модель с первым порядком, а модифицированная - со вторым порядком.
- 17 -Научная новизна работы состоит в следующем. В теоретической части работы для задач дискретного оптимального управления со смешанными ограничениями предложена новая форма вариации допустимого управления, основанная на представлении приращения управления в виде суммы оптимизационного и компенсационных слагаемых.
На основе введенной формы вариации управления в классе алгоритмов метода возможных направлений построены алгоритмы оптимизации с гарантированной сходимостью, для которых построение оптимизационных направлений производится независимо на разных шагах процесса, учитывая явно лишь ограничения на текущем шаге. При установленных в работе условиях для задач с ограничениями типа неравенств имеет место линейная локальная скорость сходимости.
С помощью модификации сопряженной системы условия оптимальности первого порядка приведены к виду условий оптимальности для задач, в которых ограничения не зависят от фазовых переменных.
Предложена модификация алгоритма Г.Зойтендейка для задачи математического программирования с ограничениями типа неравенств, для которой впервые установлена линейная локальная скорость сходимости в общем случае.
В прикладной части работы методы дискретного оптимального управления ..впервые применены к задачам открытых горных работ, в том числе и статическим.
4. Характерные постановки задачи оперативного планирования
добычных работ на карьерах и задачи оптимизации геометрии открытых
разработок пластовых месторождений с применением железнодорожного
или автомобильного транспорта формализованы в виде нелинейных за
дач дискретного оптимального управления со смешанными ограничения
ми. Возможность решения этих задач с помощью разработанных алгорит
мов оптимизации доказана расчетами на ЭВМ.
~ 18 -5. Построена математическая модель геометрии открытых горных разработок с применением железнодорожного или автомобильного транспорта, основанная на описании контуров уступов карьера в виде замкнутых ломаных. В построенной модели многоугольные контуры впервые рассматриваются как аппроксимации гладких, ограниченной кривизны контуров уступов, удовлетворяющих основным технологическим требованиям. Доказана корректность аппроксимации и установлен ее порядок.
Перечисленные научные положения выносятся на защиту
Основные результаты диссертации докладывались на ХХУТ,ХХУП и ХХУШ научных конференциях Московского физико-технического института (1980«1982гг.), конференции молодых ученых и специалистов "Применение ЭВМ в управлении угольной промышленностью" (Быково, 1982г.), научных семинарах Вычислительного центра Ж СССР (1982г.), кафедры теоретической механики ШТИ (1983г.) и кафедры вычислительных машин МГЙ (1979-1982гг.) и опубликованы в работах автора [7-IoJ.
Вариация управления
Если последнее условие справедливо, то оно справедливо для всякого управления и не должно учитываться, а если нарушается, задача неразрешима.
Пусть - допустимое управление в задаче I. Известны различные способы построения допустимых управлений, близких к 1 (будем называть эти управления измененными и обозначать (Лы). Мож но использовать вариации по направлениям [б0,с.604] общего вида, т.е. рассматривать семейства измененных управлений в форме UJd=U+o(-Su . Направление 5ы {Sll(0) ...; Su f/v-Добычно также называют вариацией управления. Проверка условий, которым должна подчиняться вариация управления oU f чтобы измененные управления при малых положительных ОС были допустимыми, для задач высокой размерности довольно трудна.В работах А.И.Пропоя [45,46] рассматривались также специальные вариации управления, т.е. вариации управления по направлениям, для которых $и(К)і=0 при единственном К . Условия допустимости для специальной вариации существенно проще; правда, множество измененных управлений, полученное с помощью специальных вариаций, существенно беднее. А.И.Пропой рассматривал задачи с чисто фазовыми ограничениями; однако условия, которым должна подчиняться специальная допустимая вариация в задаче I со смешанными ограничениями, мало отличаются от случая задачи с фазовыми ограничениями,
В настоящей работе рассматривается другая конструкция измененного управления. В качестве параметров, определяющих вариацию управления, по-прежнему выбираются направления в пространстве управлений , которые будем обозначать 5J U = {5 Ц (0)?. & U(/v"i)} Приращение управления на каждом шаге, кроме обычного слагаемого
A U (К) = L U(К) , содержит еще компенсационный член, зависящий от приращения фазового вектора АХ (Ю . Это слагаемое обеспечивает соблюдение всех ограничений из задан leL) ного активного набора для шага К , каково бы ни было АХ (К). Введение дополнительного компенсационного слагаемого позволяет назначать & Ы(К) независимо для разных шагов процесса и значительно сократить число условий, которым должно подчиняться QjU(K.) . Предложенная конструкция расцространяется и на задачу 2 путем вве hi) дения еще одного дополнительного слагаемого оЛС (Ю , имеющего более высокий порядок малости.
Для дальнейшего изложения понадобятся некоторые обозначения. В различных вариантах метода возможных направлений при построении направления спуска на t -ой итерации учитываются не все ограничения, а только те, которые с точностью до некоторой неотрицательной величины up обращаются в равенство.
Определение 1.2. Пусть № - допустимое управление в задаче I и 2, которому соответствует траектория Ос , а о,Z-Q . Назовем ограничение (1.3) с номером I и (1.4) с номером і и -активным, если соответственно
Ограничения, обращающиеся в равенство, назовем просто активными. Ограничения (1,6) и (1.7) активны на любом допустимом управлении и считаются ff" -активными при любом б % 0 Множества -активных ограничений на шаге К обозначим соответственно 1а$ (1((кї) І
В дальнейшем часто будем опускать аргументы .2), Udy и писать просто i -ftj и т,п, в тех случаях, когда не будет сомнений, о какой точке jpC(N (l o идет речь.
Пусть (М - допустимое управление, порождающее траекторию X . Измененные управления Ыц - 11 + АЫ , которым соответствуют измененные траектории %ц-0Сч-&Х , определим через прира щение управления Д± U fd,!/ %»,..., А ШЫ Щ..., d $jUW-i))no формулам причем член До Ц (Ю = 0(йлИ ) » конкретный вид которого будет приведен ниже, для задачи I может быть опущен. Для каждого шага задается активный набор ограничений. Матрица С(К) размерности fftxfl определяется независимо от Д К ; она обладает тем свойством, что при любом ёЕ. приращение фазового вектора2Ш=2? вместе с приращением управления AqUQQ CfifO Z не изменяет в линейном приближении значений всех ограничений из активного набора J(K) .
Дополнительные слагаемые вариации управления
Замечание. В условиях теоремы I.I фигурирует сопряженная траектория Я , которая при заданном управлении U определяется набором матриц t(K)t являющихся решениями уравнений (I.I3). Но матрицы ЦК) определяются из уравнений (I.I3) не всегда однозначно. Пусть управление (Я является стационарным (т.е. удовлетворяет необходимым условиям оптимальности) в смысле теоремы I.I при некотором наборе матриц C ift),..., C (l\/-1) . Тогда оно является стационарным в смысле теоремы 1.3 в силу доказанной эквивалентности условий оптимальности. Пусть матрицы Ц(О/,... ц Ш і) также удовлетворяют уравнениям (1,13). Тогда из стационарности управления Ц. в смысле теоремы 1.3 вытекает, что оно является стационарным в смысле теоремы 1,1 и при этом наборе матриц.
Дополнительные слагаемые вариации управления Предложенная в 1.2 вариация управления применима для вполне регулярных управлений. Здесь рассматривается ее обобщение для управлений, удовлетворяющих более слабым условиям регу - 43 лярности.
Функции %СШ(Ю7Ю , Чу(ХД0,(Л/О,К) в силу разностных уравнений (I.I) - (1.2) являются функциями векторов управления U(0) ...?U(K) $ которые мы объединим в вектор U.(К) . Введем обозначения
Положим, как и прежде, #«)= %(K)U (K) ММ ДОЛ Л Если /V = / . !\l(h) (K+l)-IM , то система уравнений Rjity№0 (jc-JJtU-O,..., "« как правило, не имеет решения. Если же І\І$(М) № , то система уравнений (І.4І), как правило, разрешима и векторы как правило, линейно независимы. Всякое допустимое управление Щ удовлетворяет системе уравнений (І.4І) при jn (-fc)=L (Ц(І)) Определение 1.5. Допустимое управление (X удовлетворяет первому условию регулярности, если при любом / Nun и, кроме того, - 44 -Определение 1,6. Множество активных ограничений J = =3(0)U...№i) г«е !b)=] UJx(K) "р"60» К , удовлетворяет первому условию регулярности, если при любом/С Ng(K№vi i=0
Если на некотором шаге с номером К число активных ограни чений No (№ превысит размерность управления, то разделим ак тивные ограничения на две группы: "правильные" ограничения об щим числом Ю и "избыточные". Все активные ограничения на уп равление отнесем к числу "правильных". С помощью приращения уп равления можно обеспечить допустимость из мененного управления (в линейном приближении) только по правиль ным ограничениям. Допустимость по избыточным ограничениям дости гается за счет дополнительных компенсационных слагаемых. Пусть J - множество активных ограничений, удовлетворяю щее первому условию регулярности. Для любого введем три мно жества: множество правильных ограничений Jf (К) , множество из быточных ограничений , множество дополнительных компен сационных членов f\(fc) . Число элементов этих множеств обоз начим соответственно : положим л/,= ли л= &Ч« At-%Ч »
Каждый дополнительный компенсационный член формально свяжем с определенным избыточным ограничением на шаге f K ; таким образом, і -му элементу множества А 00 соответствует пара ( і к » tiH ), причем ІДікЬ Подмножества Р(к)и L(K) , состоящие из ограничений типа неравенства, будем обозначать г 00 , ц ) , а подмножества ограничений типа равенства - р (К) , [_ СЮ » число элементов этих множеств - соответственно /vp-j 00 Л/ (К) , Дір. (К) , A/L2 м . Аналогично множества дополнительных компенсационных членов разбиваются на подмножества
Множество шагов процесса разделим на три непересекающихся подмножества и введем (К) , 1 (Ю Iм К) следующим образом: Ї) & 7 » если І\(КУІ) І/У1 Разделим активный набор смешанных ограничений ХС/ ) на два подмножества: l dU) и Ц( ) , так что Л/рг ) + Л/дСй)-ГО -Положим Р(К4)= - V UРх (к ) , UK4) = Ц «4) , Kft4)=j ; 2) для некоторых / , таких, что Nfe) » определим Г\(Ко)Ф$ так чт0 Nft№2)+r l(&2)$№ Эти шаги процесса образуют множество . Положим гГ )= J ) , L-, ) —0 3) остальные шаги процесса образуют множество 7 . Для лю бого къ Тъ №къ) ч го, Р(къ) 7(х3). L(Kt)=tf . Определение 1.7« Систему множеств X , X t X » і JLC/O t L»(K) t/иЮ, К= І у » построенную указанным способом, назовем правильной по отношению к множеству активных ограничений J . если любому избыточному смешанному ограничению соответствует один и только один дополнительный компенсационный член.
В силу первого условия регулярности правильная система множеств всегда существует.Факт существования правильной системы множеств докажем с помощью простого алгоритма ее построения.
Обозначим (Ю разность между числом избыточных ограниче - 46 ний и числом дополнительных компенсационных членов на шагах К , і 41,... , Л/-1 . Положим . Будем вводить множества правильных и избыточных ограничений и компенсационных членов при / =Л/-І, Л/-2,...7 0 . Пусть /VC/O ҐЇЇ . Тогда к правильным ограничениям на шаге К отнесем все ограничения из множества (К) и первые № ограничений из множества J (fc); остальные ограничения отнесем к избыточным. Положим 2YK) = Пусть (\/(К)=т или /\{Ш т , Ы)=0 . Тогда положим /UK) = jzf , HflO- ZYfc+i) . Наконец, если [ (К) ЇЇ), Z.(fct\) 0 » положим
Из алгоритма следует, что при любом / 2(К) 0 Если занумеровать избыточные ограничения от последнего шага к первому и таким же образом занумеровать дополнительные компенсационные члены, то в силу того, что ZzCtQZO при любом / , каждое избыточное ограничение относится к более позднему шагу, чем компенсационный член с тем же номером. Осталось показать, что/ =/1( .
Формулировка алгоритма оптимизации и до казательство его сходимости
Существуют поло жительные числа Аь , /Мь и Д) » такие, что измененное управление, построенное по формуле Ми = W+d IT» rfleir/k)-(AJ#0 \W )f является допустимым и удовлетворяет неравенству (2.25а) при любом \/\%-() для которого справедливы неравенства oU Мз CU И, " Я, Ny-1 (2.26а) Величины М,і МІ. М5 зависят от К и Функций/ (tf,K), j(M,K) . ifj(i,u,K),. Fx).
Доказательство леммы вполне аналогично доказательству леммы 2.5.
Таким образом, нижняя оценка оС имеет одинаковый характер для-обоих методов. Отличие состоит, однако, в том, что специальных возможных направлений спуска, отличных от нуля, может и не существовать для управления, не являющегося стационарным для предлагаемого метода. Если же управление является стационарным (удовлетворяет необходимым условиям оптимальности теоремы 1,1), то для него не существует специальных возможных направлений спуска, поскольку не существует и возможных направлений спуска общего вида, как было доказано в 1.3.
Рассмотрим пример задачи, в которой это различие существенно (см. рис. 2.1). В задаче/\р 2» П- W\-i , и она описывается так:
Допустимая область в задаче есть пятиугольник 0ABCD , а .оптимальное управление изображается точкой С . На отрезке ОС специальных допустимых вариаций нет при любом 0 . Действительно, смешанное ограничение преобразуется к виду iJ(0)ti(i) i S » и на ВС оно превращается в равенство. Специальные допустимые вариации при / - И должны удовлетворять соответственно условиям
В предыдущих параграфах были исследованы отдельные детали предлагаемого алгоритма: способ построения матрицы )(к) , выбор величин , ІЇр , , определение направления спуска. Здесь да ется полная формулировка численного алгоритма и доказывается его сходимость в предположении, что оптимальное управление является вполне регулярным. Алгоритм формулируется для задачи 2, посколь ку задача I является ее частным случаем. Для задачи I матрица Т)( (К) представляет собой матрицу с приписанным спра ва столбцом (л (К) . Для задачи 2 матрица I) (К) содержит также столбцы Другие отличия алгоритма для задачи I от алгоритма для задачи 2 формулируются в тексте алгоритма.
Пусть дано допустимое вполне регулярное управление U и числа о 0, jf U - вообще говоря, произвольные. Последовательность допустимых вполне регулярных управлений {(J J строится согласно следующему алгоритму. 0. Полагаем 1. Полагаем = . 2. Полагаем J %) = Iffxtyfyu tfa, К=Ог.М і . Если при некотором К rle(lO Wl% полагаем S = и возвРа1Даемся к п. 2. 3. При К- 0}...; А/"/ вычисляем матрицы = /\(Х%и%,У%)), F% FlA\d%/lk затем матрицу Т) (Ю- и (ОС (к) U (К) J (НІ) согласно алгоритму, сформулированному " /7 f iP)
Если для некоторого К в процессе вычисления Jj (К) выяс -няется,что строки матрицы /і (К) линейно зависимы либо liDwII t то полагаем = 1 и возвращаемся к п.2; иначе переходим к п. 4.
4. Строим сопряженную траекторию 0) по формулам (I.2I) (1.22), в которых полагаем 0С(М=ЭС{О(К); ЫСЮ=И{Щ C(KhC%. Полагаем 3{ - fy 5. При U}...yN l находим пару { ЩМ {Ю} из решения задачи (2.10) или по формуле (2.13). 6. (Первый вариант). При К Qt...7vl i полагаем 00 ( )- / . 6. (Второй вариант). При /(-0,,, /ІМ полагаем (ЖЮ=Ш(К).( кия iffflfli).- f кЦ...,ЛАІ 6. (Третий вариант).
Исследование контурных моделей карьера
Если K f\l , возвращаемся к п. 10, иначе переходим к п. 14. 14. Если выполнено условие F(x! 4№4F(x" №+l«-!t, полагаем X( = ? u M " ; C-i+J и переходим к п.I, иначе полагаем = и возвращаемся к п.9.
Теорема 2.1. Пусть для любого числа К множество допустимых управлений U , для которых фМ Ф , ограничено либо пусто, и пусть функции $ (ЦК), $i (Xt[AtK)} tj{XtUfK\ r(X) принадлежат классу Пусть последовательность вполне регулярных допустимых управлений lu / построена согласно алгоритму. Тогда у последовательности jli ) существует сходящаяся подпоследовательность и если предельное управление Ц для подпоследовательности является вполне регулярньм, то для него выполнены необходимые условия оптимальности, сформулированные в теоремах I.I и 1.2.
Доказательство. Существование сходящейся подпоследовательности \U (Lj следует из того, что значение целевого функционала на последовательности {W } монотонно убывает, поэтому последовательность принадлежат ограниченному замкнутому множеству
Из непрерывности функций $6 4 {ОС, U\ К) следует, что существует число S U и окрестность V управления U , такие, что при любом ЦЄ V» о о для любого к -L$ (X(K\U(K)) 10(Х(Ю?йМ)(сМш доказательство леммы 2.2). Из сходимости сле дует, что существует число ij , такое, что при всех /ё/j tzd У. ъ\[ м будет удобно доказывать справедливость утверждения теоремы I.I, если векторы W W находятся из решения задачи (2.10), и справедливость необходимых условий оптимальности теоре мы 1.2, когда векторы вычисляются по формулам (2.13). До пустим, что утверждение теоремы I.I для U не выполнено. Тогда для любого множества активных ограничений J- J(0)0,.,0J(N"l)» для которого при любом К справедливо включение причем точка {Х(ЦЩК)} J (К) -регулярна, и любого соответ ствующего ему набора множеств главных элементов p-jр(0),.. 5//r/JJ существует сопряженная траектория Cj, ty(U?J;P)n найдутся номер шага К - KI(U;J,?)K вектор Ц( І) = (K{ Ы} J р) , такие, что ($iu(u( iW утнО, ttI]0(u(Kt\ (ЦіиїйсщіСі), Ц( ІЇ) = 0, Цщ Взяв достаточно малое 5 0 имеем для вектора Wfl i) (ш ШІЩ к,), WW 4 - Щ /61}о №,)),
В силу J(kj) -регулярности точки {X(l i)tii( i)} существует матрица ограниченная в окрестности Положим W( i; W)= W%) + Q(Ki ХЩиЮіІЇ-ТСкцІл), потребовав, чтобы были выполнены условия (%ы Ш(к), h) w(h\u »-Q іьі(кА\ 1 (2 27)
Тогда, согласно определению toff j XCK±) U(K )), компоненты вектора T%;W) выражаются следующими формулами Существует число (п , такое, что при/ Л, i L управление 0 Т / " U \ Очевидно, что при любом 5Vfr для оптимального решения задачи (2.IO) при %, [ справедливо неравенство ) $ Рас смотрим последовательно первый, второй и третий варианты п. 6 алгоритма. Для первого варианта для второго К=0 К=У;.../И ДЛЯ Третьего .її Итак, во всех трех случаях I % 0 и» следовательно., fy 2 Ч{ ч /" ч? 3 если» разумеется, 0{4 5 . Но если f2, fe/,, 545 и 5V ff у то заведомо Ъ4Щл и, следовательно, условие п. 7 алгоритма выполнено. Следовательно, при
С другой стороны, согласно след ствию леммы 2.3, , 0 Полученное противоречие доказывает теорему для случая, когда направление спуска есть решение задачи (2.10). Доказательство теоремы для случая, когда W (К) вычисляет ся по формулам (2.13), в основном аналогично. Допустим, что ут верждение теоремы 1.2 по отношению к 66 несправедливо. Тогда для любых найдется номер шага К\ - для которого одно из неравенств (1.35) - (1.36) несправедливо.
С помощью совершенно аналогичных рассуждений нетрудно показать, что должно существовать такое число L , что при С L» I Ъ і з при любом 6V $ () справедливо неравенство Чр $ 7\Y) =y 0 »и поэтому ty 2 WW f r 1 что противоречит сходимости последовательности jf(L (&Lj к нулю. Теорема доказана.
Обсудим некоторые другие варианты алгоритма. Ряд условий алгоритма был сформулирован на тот случай, когда у последовательности управлений не одно предельное управление. Заметим, что монотонно убывающая последовательность значений целевого функционала / ф(и )(является сходящейся, ее предел
Поэтому, если у последовательности [К і несколько предельных управлений, то для каждого из них значения целевого функционала одинаковы, причем все они являются стационарными. Такая ситуация кажется крайне маловероятной во всех случаях, когда целевой функционал ф[и) не является независимым от какой-либо компоненты управления в окрестности одного из стационарных управлений.
