ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2013, № 6, с. 52-67
ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ
УДК 519.626.2+517.977.5
ГЛОБАЛЬНЫЙ ПОИСК В ОДНОЙ НЕВЫПУКЛОЙ ЗАДАЧЕ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ* © 2013 г. А. С. Стрекаловский, М. В. Янулевич
Иркутск, Институт динамики систем и теории управления СО РАН Поступила в редакцию 05.03.13 г., после доработки 03.06.13 г.
Рассматривается невыпуклая задача оптимального управления с целевым функционалом Больца, задаваемым функциями, которые представлены в виде разности двух выпуклых по состоянию функций (функциями А.Д. Александрова). Доказаны новые необходимые и достаточные условия глобальной оптимальности для минимизизующих последовательностей управлений, на основе которых разработан теоретический метод поиска глобально оптимального управления и доказана его глобальная сходимость.
БО1: 10.7868/80002338813060115
Введение. Как известно, подавляющее большинство прикладных задач оптимизации оказываются невыпуклыми, так что в них существует большое количество локальных решений и стационарных точек (процессов), далеких от глобального как по целевому функционалу, так и по аргументу (состоянию, управлению) [1—11]. Кроме того, в последние десятилетия в приложениях появились новые объекты исследований, такие как поиск равновесий, иерархические структуры, вариационные неравенства, а также разнообразные типы задач дополнительности и другие, которые могут быть рассмотрены как невыпуклые структуры с точки зрения теории и методов оптимизации [1—16].
В то же время существующий математический аппарат (теория и методы) оптимизации оказывается неэффективным в смысле поиска глобального решения, поскольку, например, классические методы оптимизации не позволяют "выскочить" из "локальной ямы" даже в простейших конечномерных задачах оптимизации [7], не говоря о прикладных задачах, например, оптимального управления (ОУ) [1—11]. Как следствие, приобрели широкую популярность такие подходы и методы, как ветвей и границ, отсечений, генетические алгоритмы и другие, которые либо страдают экспоненциальным ростом объема вычислений (с ростом размерности задачи), либо не обладают никакой сходимостью к чему-либо. Идеи подобных методов были привнесены в непрерывные экстремальные задачи из дискретной оптимизации, биологии, генетики, физики и т.д. и объясняются необоснованными попытками улучшения результатов применения классических методов выпуклой оптимизации (градиентных, Ньютона, квазиньютоновских, методов линеаризации и т.д. [6, 9, 11]). Напомним также, что большинство существующих пакетов прикладных программ (ППП), применяемых в том числе и для решения задач ОУ, базируются на методах выпуклой оптимизации, и как следствие, обладают сходимостью в лучшем случае к локальному решению, останавливаясь чаще всего лишь в стационарных (критических) точках.
В [17] был предложен новый математический аппарат, позволяющий охарактеризовать глобальное решение в невыпуклых задачах для весьма общего типа данных с функциями А.Д. Александрова (ё.с.-функциями), представимыми в виде разности двух выпуклых функций. Более того, этот аппарат позволяет выйти из локального решения или просто (вырожденного) стационара в ё.с.-задачах посредством решения семейства линеаризованных выпуклых задач. Это обеспечивает отыскание глобального решения в игровых задачах поиска равновесий [18], иерархических задачах оптимизации [19], а также других невыпуклых задачах оптимизации [17, 20].
В настоящей работе осуществляется развитие разработанной методики на невыпуклые задачи ОУ с общим функционалом типа Больца. Так, после постановки задачи условия глобальной оптимальности обобщаются на минимизирующие последовательности. Затем предлагается теоретическая схема глобального поиска и доказывается ее сходимость. Далее эта схема преобразуется
* Работа выполнена при финансовой поддержке РФФИ (грант № 13-01-92201-Монг_а).
глобальный поиск в одной НЕВЫПУКЛОИ ЗАДАЧЕ 53
в более алгоритмическую форму, доказательство сходимости которой и представляет основной результат работы.
1. Постановка задачи. Рассмотрим следующую управляемую систему:
x(t) = f(x(t), u(t), t), Vt e T = ]to, t1[, x(to) = Xo e R", (1.1)
u(■) e Ш = {u(■) e LU T) \ u(t) e U Vt e T}, (1.2)
где выполнены стандартные предположения для задач ОУ [1, 7, 9, 11], в частности, множество
Uс [Rr является компактом, при этом здесь и далее в работе знак V означает "для почти всех". Также будем предполагать, что вектор-функция (x, u, t) ^ f (x, u, t) непрерывна по совокупности переменных (x, u, t) e [ x [ x Tи
fx, u, t) - f(y, u, t)||< L(t)||x - y\\
при всех (x, u, t), (y, u, t) e x [ x T, где L(t) > 0 и функция L(-) суммируема на T, L(-) e ^1(T). Нетрудно проверить, что все эти условия выполнены для линейной управляемой системы [8].
При сделанных предположениях, как известно [7], для каждого управления u(-) e Ш существует единственное состояние x(t) = x(t, u(-)), t e T, являющееся решением задачи Коши (1.1) из класса абсолютно непрерывных вектор-функцийAC"(T) [7, 9], удовлетворяющих уравнению из (1.1) почти всюду на Т. Далее в работе состояние x(t, u(-)), t e T, соответствующее управлению u(-) e Ш, для краткости будем обозначать x(t, u), t e T.
Цель управления системой (1.1), (1.2) заключается в минимизации следующего функционала Больца:
J(u) := F1 (x(t1, u)) + J[F(x(t, u), t) + f0(u(t), t)]dt i min, u(■) e Ш, (1.3)
T
где x(t) = x(t, u), t e T, — решение системы (1.1), (1.2), соответствующее управлению u(-) e Ш. Далее в работе задачу (1.3) будем называть задачей (^). Предположим, что функции x ^ ^x(x) и (x, t) ^ /(x, t) являются функциями А.Д. Александрова [7, 17], представимыми в виде разности двух выпуклых функций:
F1 (x) = g1 (x) - h1(x) Vx e R", (1.4)
F(x, t) = g(x, t) - h(x, t) Vx e R" Vt e T, (1.5)
где x ^ g1(x) и x ^ A1(x) — выпуклые функции на а функции x ^ g(x, t) и x ^ h(x, t) — выпуклые по x e для любого t e T. Кроме того, пусть функция (u, t) ^f0(u, t): [ +1 ^ R непрерывна по каждой переменной, а функции x ^ h1(x) и x ^ h(x, t) дифференцируемы на достаточно большом открытом выпуклом множестве Q. с
При выполнении данных предположений задача (^), вообще говоря, является невыпуклой, поскольку могут существовать процессы (x^(-), u^(-)), удовлетворяющие принципу максимума
Понтрягина, но при этом отличные от глобально оптимального (z(-), w(-)), скажем, по значению целевого функционала. Примеры таких задач приведены, например, в [20—24].
2. Условия глобальной оптимальности и минимизирующие последовательности. Введем пару параметров (y(-), р), где вектор-функция y: T ^ [ кусочно-непрерывна, а р e R. Далее введем нижнюю и верхнюю оценки числового параметра р соответственно:
Р_(y) = G(y) + inf(F0, Ш), Р+ = sup{ G(x(u)) + F0(u)| u e Ш},
u
где
inf(F0, Ш) A= inf{F0(u)|u e Ш}
u
и функционалы G(-) и /0(') определены равенствами
(2.1)
G(y) =А g1 (У(t1)) + Jg(y(t), t)dt,
и) = ¡/0(и(г), г)йг, (2.2)
т
Кроме того, скалярное произведение в К" будем обозначать через
п
< а, Ь> = ^ а1Ь1,
г = 1
где а, Ь е К". Тогда справедлива следующая теорема, обобщающая результаты из [21, 23].
Те о р е м а 1. Пусть управление е Ш является допустимым в задаче (^). Кроме того, пусть в задаче выполнено предположение (Ж):
Зи(• )е Ш: /(и)> /(^). (2.3)
Тогда для того, чтобы управление е Ш было глобально оптимальным в задаче (^), необходимо и достаточно выполнения следующих условий (^):
У(у(•), р): у(•) е АСп(Т), ве К,
(2.4)
hi(У(ti)) + \h(y(t), t)dt = ß - Z, Z := J(w),
T
в-(у )<в<в+, (2.5)
<УЙ! (у(?!)), X(и) - у(?!)> + ¡<УЙ(у(0, 0, *(и) - у(ФЯ <
т (2.6) < & (х(гь и)) + ¡^(х(г, и), г) + /0(и(г), г)]йг- в Vu(•) е Ш.
т
Нетрудно видеть, что это условие глобальной оптимальности в теореме 1, во-первых, связано с принципом максимума Понтрягина (ПМП). Действительно, полагая в (2.4)-(2.6)
у(г) := г(г), в := &(г(Ь)) + ¡^(г(г), ?) + /0(Чг), г)]йг, (2.7)
т
мы получаем, что при любом допустимом управлении «(•) е Ш в силу вариационного неравенства (2.6) справедлива следующая цепочка:
Ци) = 1(и; г) := &(х(гь и)) - <Ук (г()), х(гь и)> + + ¡[g(х(г, и), г) + /0(и(г), г) - <ук(г(г), г), х(г, и)>]йг >
т
> Iг(*) := gl(г(г 1)) - < Vк,(г(г,)), г(г,)> +
+
T
Jfe(г(t), t) + fo(w(t), t) - <Vh(z(t), t), z(t)>] dt,
где z(t) = x(t, w). Это означает, что управление w е Ш будет решением следующей линеаризованной задачи (^^(z)):
Iz(u) I min, u е Ш. (2.8)
u
Отсюда следует, что процесс (z('), w(-)) удовлетворяет условию максимума
0 = шахДНг(?), w(?), Vг(?), ?) V? е Т, (2.9)
V
V е и
где Д^И(х, и, у, 1) = Н(х, V, у, 1) — Н(х, и, у, 1), а отображение (х, и, у, 1) ^ Н(х, и, у, 1) — функция Понтрягина для задачи (^):
Н(х, и, у, ?) = (у,/(х, и, ?)) -g(x, ?) + Л(х, ?) -/о(и, 0.
При этом абсолютно непрерывная функция 1 ^ уг(0 является единственным решением сопряженной системы ОДУ
у (?) = - у( ?)Фг (?) + Vg (г (?), ?) - V Л (г (о, О V ? е Т, 1 (2 10)
у( ?!) = - V г (?!)) + V Лх(г (?!)); ]
где
Фг(?) = /(г(?), *(?), ?), 1 = .
А это и означает, что управление е Ш удовлетворяет ПМП в задаче (^).
Во-вторых, отметим, что в необходимой части условий глобальной оптимальности (2.4)—(2.6) ограничение у(-) е АСп(Т) можно ослабить, рассматривая лишь интегрируемые или кусочно-непрерывные вектор-функции у(-) (у(-) е РСп(Т)), такие, что интегралы, входящие в (2.1), (2.4) и (2.6), имеют смысл.
В-третьих, условие глобальной оптимальности обладает алгоритмическим (конструктивным) свойством. Это означает, что если найдется пара (у(-), р), удовлетворяющая (2.4), (2.5), и управление и (•) е Ш, нарушающие вариационное неравенство (2.6) при и(-) = и (•), то имеем (X (•) = х(-, и)):
0 > ^(Х(?!)) - (VЛ! (у(?!)), Х(?!) - у(?!)) - р + |[g(X(?), ?) + /о( и(?), ?) - (VЛ (у (?), ?), X(?) - у (?))]
+
Т
Отсюда в силу выпуклости функций А1(^) и Н(•, 1), 1 е Т следует неравенство 0 > g!(X(?!)) - Л! (X(?!)) + Л! (у(?!)) - р +
|[ g (X (?), ?) + /о( и (?), ?) - Л (X (?), ?) + Л (у (?), ?)] А.
+
Т
Иначе говоря, /(и) < 1(м>) с учетом (2.4). Таким образом, в случае нарушения условий глобальной оптимальности (2.4)—(2.6) всегда есть возможность улу
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.