Деменков Н.П. Вычислительные аспекты решения задач оптимального управления (2007) (1253737), страница 5
Текст из файла (страница 5)
Функциональная зависимость между величинами Xi и αi задана опосредствованно. Для того чтобы по заданным значениямα1, α2,…, αn найти X1,..., Хn, надо построить численное решениезадачи Коши системы (2.3) порядка 2n, причем на каждом шагечисленного интегрирования определять управления u1(t),...,um(t) изусловия максимума функции Гамильтона, т. е. из решения некоторой вспомогательной задачи нелинейного программирования.2. Система невязок (2.5) в случае, когда на концах заданы невсе координаты, дополняется соотношениями, которые получаютиз условия трансверсальности после исключения произвольныхпостоянных.
Достоинством метода является универсальность.2.1.1. Метод НьютонаДля численного решения задачи отыскания корней функциинаиболее широко используется метод Ньютона, один из самыхстарых способов отыскания нулей трансцендентных функций [4].Пусть мы имеем некоторое нулевое приближение – системучисел {α0j}.
Этой системе чисел соответствуют величины X 0i == X i (α 01 , α 02 ,..., α 0 n ). Положимα1j = α0j + δ1j.Считаем величины δ1j малыми, примем, используя разложениев ряд Тейлора,n∂X ij =1 ∂α jX 1i ≡ X i (α 01 + δ11 ,…, α 0 n + δ1n ) = X 0i + ∑δ ,α=α 0 1 ji = 1, 2, …, n.Выберем величины δ1j так, чтобы правые части этих равенствобратились в нуль. Это дает нам n линейных уравнений относительно n величин δ11,…, δ1n.Введем матрицу⎪⎧ ∂X ⎪⎫A(α) = ⎨ i ⎬ , i, j = 1, 2,…,n.⎪⎩ ∂α j ⎭⎪27Тогда уравнение относительно вектора δ1 = (δ11 ,..., δ1n ) запишется таким образом:A(α 0 ) δ1 = − X 0 , или δ1 = − A−1 (α 0 ) X 0 .(2.6)Затем в качестве нового приближения принимаем векторδ1 + α 0 = α1и повторяем процесс.
Общая схема итерации будет такой:δk = − A−1 (α k −1 ) X k −1 ,α k = α k −1 + δk .(2.7)На каждом шаге итерации нужно вычислять матрицу A, причем производные мы должны находить численно. С этой цельюкаждому значению α(k – 1)j нужно дать вариацию Δα(k – 1)j, а затемРис. 2.1. Геометрическая интерпретация методаНьютонадля α(k – 1)j и Δα(k – 1)j вычислить Xkj, т. е. проинтегрировать Псистему. Это потребует на каждом шaгe итерации решения n + 1задач Коши для системы (2.3), порядок которой равен 2n.Метод Ньютона иногда называют методом касательных, основываясь на cледующей его геометрической интерпретации.
ПустьХ и α – скаляры и речь идет об отыскании корня X(α).В точке (α0, Х0) проведем к кривой Х(α) касательную (рис. 2.1).Уравнение касательной имеет видZ (α) = X (α 0 ) + X ′(α)(α − α 0 ).28Точку пересечения Z(α) с осью абсцисс примем в качестве нового приближения α1. Значение α1 будет определяться формулой(2.7), гдеA−1 (α 0 ) =1.X ′(α 0 )Таким образом, геометрически процесс вычислений по методуНьютона можно представить себе следующим образом. Задаем α0и вычисляем X(α0), проводим в этой точке касательную и точку еепересечения с осью абсцисс принимаем в качестве нового значения α = α1. Далее процесс вычислений повторяем.Если начальное приближение α0 выбрано достаточно близко кзначению корня α*, то метод Ньютона сходится очень быстро иудобен для практического использования.Однако если точка α0 не находится в области «приближения»корня, то метод Ньютона расходится.
Например, при отыскании кор-Рис. 2.2. Поведение корней уравнения невязокня функции X = arctg α и при выборе |α0| > λ, где λ – корень уравнения 2α = (1 + α2)аrсtg α, каждое следующее значение переменной αотстоит все дальше и дальше от значения корня (рис. 2.2).Предложено много модификаций метода Ньютона, которыеспособны преодолеть указанную трудность. Широко используетсяследующая модификация [5,6]:α k = α k −1 − ε k −1 A−1 (α k −1 ) X k (α k −1 ),(2.8)29где εk – 1 – некоторый скалярный множитель, не превосходящий 1.Существуют различные способы выбора этого множителя. Всеони, так или иначе основаны на требовании, чтобы соблюдалосьусловиеX (α k ) < X (α k −1 ) .В качестве нормы ||X|| принимают либо max ||Xi||, либоi∑ ( X i )2 .iОбозначим через α1 значение α, полученное по формуле (2.7),т. е.
для ε0 = 1. Как видно из рис. 2.2, |X(α1)| > |X(α0)|, поэтому в1качестве нового приближения α выберем значение α 1 = α 0 + δ1 ,2т. е. положим ε0 = 1/2.Видно, что α 1 находится уже в окрестности корня, где сходится простой метод Ньютона (εk = 1, k = 1, 2,...). Таким образом, выбор множителя ε0 = 1/2, εk = 1, k = 1, 2,… сделал расходящийсяпроцесс сходящимся.Изложенные выше соображения приводят к процедуре использования метода Ньютона (рис.
2.3), которая получила широкоераспространение в настоящее время.Применение подобной процедуры значительно расширяет возможность использования метода Ньютона, однако и она не дает вобщем случае гарантии сходимости метода Ньютона для произвольно выбранного начального приближения α0.При неудачном выборе первого приближения метод Ньютонаможет стать расходящимся. Поэтому, еслиX i (α k ) > X i (α k +1 ) , или X i (α k ) < X i (α k +1 ) ∀i,то1122⎡n⎡n2⎤2⎤⎢ ∑{ X i (k )} ⎥ < ⎢ ∑{ X i (k − 1)} ⎥ .⎣ i =1⎦⎣ i =1⎦3031Рис.
2.3. Модификация метода НьютонаПри реализации метода Ньютона могут появиться некорректные решения, когда малым значениям δk соответствуют большиезначения Xk. Это связано с тем, что приходится обращать матрицучастных производных.Положительная сторона метода Ньютона заключается в егоширокой общности (широкий круг задач), отрицательная – в том,что метод требует возрастающих вычислительных затрат.2.1.2. Метод сопряженных градиентовДля применения метода Ньютона требуется на каждом шагерешать систему линейных уравнений (2.6), которую можно записать в видеAδ + X = 0.Если порядок системы достаточно высокий, то вопрос о выборе способа решения уравнения (2.6) для задачи большой размерности становится уже существенным с позиций построения экономной схемы расчета.Однако при реализации метода Ньютона нет необходимости накаждом шаге решать уравнение (2.6) точно.
Поэтому для его решения имеет смысл применять итерационные методы. Среди этихметодов выделяется своей простотой и удобством метод сопряженных градиентов [7].Порядок расчетов при использовании этого метода следующий.1. Задаем начальное приближение δ0, вычисляем невязку− r0 = Aδ0 + Xи выбираем вектор s1 = r0 .2. Определяем a1 =(r0 , s1 ), δ1 = δ0 + a1s1 и вычисляем невязку( s1 , As1 )− r2 = Aδ1 + X или r1 = r0 − Aa1s1.3. Определяем b1 = −32(r1 , As1 )и выбираем вектор s2 = r1 + b1s1.( s1 , As1 )(r1 , s2 )и т.
д.( s2 , As2 )Если матрица А – симметрическая и положительно-определенная, то описанная процедура заканчивается не более чем черезn шагов. Это значит, что обязательно найдется такое значениеi ≤ n, где n – размерность вектора δ , что ri = 0.В процессе проведения расчетов задаются некоторым числом ρ, ивычисления прекращаются при достижении неравенства4. Полагаем δ2 = δ1 + a2 s2 , где a2 =ri ≤ ρ.Несмотря ни на какие модификации, применение метода Ньютона (или другого метода отыскания корней) невозможно безудовлетворительного первого приближения.
Это первый недостаток подхода, основанного на редукции вариационной задачи ккраевой и ее последующем сведении к задаче отыскания нулейтрансцендентной функции.Вторая трудность, с которой сталкиваются при реализации изложенной техники, связана с неустойчивостью «решения». Мыимеем дело с уравнениями, правые части которых гарантируютнепрерывную зависимость решения от начальных данных. Этозначит, что для достаточно малых значений α с большой степеньюточности выполняется условиеδX = k δα.Коэффициент пропорциональности k зависит, в частности, отвеличины интервала интегрирования Т = tk – t0.
Если движение неустойчиво, то при увеличении Т величина k неограниченно возрастает. На практике часто имеет место такая ситуация: очень маломузначению δα соответствует машинная бесконечность (т. е. значение k очень велико). В этом случае никакие модификации методаНьютона реализованы быть не могут.В силу этих причин метод Ньютона не смог сделаться универсальным методом расчета оптимальных программ на основе принципа максимума Л.С.
Понтрягина.2.2. Перенос граничных условийВ методе Ньютона оптимальная траектория отыскивалась путем выбора из множества оптимальных траекторий, начинающих33ся в точке с координатами хj(t0),той единственной траектории,которая проходит через точку скоординатами хj(tk), как показано на рис. 2.4.Возможен и другой подходк решению. Можно определитьРис.
2.4. Поиск оптимальноймножество всех траекторий,траектории методом Ньютонасвязывающих точки хj(t0) ихj(tk), и далее уже среди этих траекторий искать оптимальную(рис. 2.5).Построение такого множестватраекторий должно заключаться всведении исходной двухточечнойкраевой задачи к задаче Коши.Для систем линейных дифференциальных уравнений такиерешения можно находить методами, основанными на переносеРис.
2.5. Поиск оптимальнойграничных условий с одноготраектории путем переносаконца траектории на другой (меграничных условийтодами прогонки).Рассмотрим управляемую систему, движение которой описывается системой дифференциальных уравненийx = Ax + Bu ,(2.9)илиnmj =1j =1xi = ∑ aij x j + ∑ bij u j .Найти управление, переводящее систему (2.9) за время T = tk – t0из состоянияx (0) = x0(2.10)x (tk ) = xk(2.11)в состояние34так, чтобы функционалtk⎧⎪⎫⎪J ( x , u ) = ∫ ⎨∑ qij xi x j + ∑ dij xi u j + ∑ rij ui u j ⎬ dt1, ji, j⎪⎭t0 ⎪⎩ i, j(2.12)достигал на оптимальной траектории своего наименьшего значения.Составим функцию Гамильтона (c учетом того, что p0 = –1):H = ( Ax , p ) + ( Bu , p ) − ( x , Qx ) − ( x , Du ) − (u , Ru ).(2.13)Уравнение для импульсов будет иметь следующий вид:∂Hp = −= − Aт p + (Q + Q т ) x + Du .∂X(2.14)Управление определим из условия∂H= B т p − D т x − ( R + R т )u = 0,∂U(2.15)u = ( R + R т ) −1 ( B т p − D т x ).(2.16)откудаПодставляя (2.16) в (2.9) и (2.14), мы получим следующую систему порядка 2n:x = Ax + B (( R + R т ) −1 ( B т p − D т x )) == ⎡⎣ A − B ( R + R т ) −1 D т ⎤⎦ x + B ( R + R т ) −1 B т p;p = − Aт p + (Q + Q т ) x + D( R + R т ) −1 ( B т p − D т x ) =(2.17)= ⎡⎣(Q + Q т ) − D( R + R т ) −1 D т ⎤⎦ x + ⎡⎣ − Aт + D( R + R т ) −1 B т ⎤⎦ p.Таким образом, в случае квадратичного функционала задачарасчета оптимальной траектории системы (2.9) сводится к краевойзадаче для линейной системы (2.17).352.2.1.
Перенос линейных краевых условийПредположим, что траектория x (t ) должна удовлетворять линейному краевому условиюn( l0 , x (t0 )) = ∑ l0 j x j (t0 ) = α 0 .(2.18)j =1Поставим задачу переноса краевого условия (2.18) с левогоконца траектории на правый.Будем говорить, что условие (2.18) перенесено из точки t0 вточку t, если удастся так определить независимую от x векторфункцию l (t ) и скалярную функцию α(t), удовлетворяющие условиям:l (t0 ) = l0 ;α(t0 ) = α 0 ,(2.19)что для любого момента t ≠ t0( l (t ), x (t )) = α(t ).Легко убедиться, что для этой цели можно использовать сопряженное уравнениеl = − Aт l .(2.20)Умножим скалярно обе части уравнения (2.9) на l , а уравнения (2.20) на x и сложим:+ = Axl + Bulxll x = − Aт l x_______________________________________ + l x = d ( l , x ) = ( l , Bu ),xldtтак как ( Ax , l ) = ( x , Aт l ).36Откуда(l , x )t = tk= (l , x )tkt = t0+ ∫ ( l , Bu )dt .t0Итак, мы получили следующую теорему.Теорема.
Если l (t ) – решение задачи Коши (2.20), (2.19) ифункция α(t) удовлетворяет уравнениюα = ( l , Bu )(2.21)и условию α(t0 ) = α 0 , то вектор-функция x (t ) для любого значения времени t удовлетворяет условию( l (t ), x (t )) = α(t ).(2.22)Доказанная выше теорема позволяет любое линейное краевое условие типа (2.18) перенести из точки x0 в любую точку.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
