close

Вход

Забыли?

вход по аккаунту

?

Алгоритм решения задачи минимизации квадратичного функционала с нелинейными ограничениями с использованием метода ортогональной циклической редукции.

код для вставкиСкачать
ЧЕЛЫШОВ М. С., ШАМАНАЕВ П. А.
АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ МИНИМИЗАЦИИ КВАДРАТИЧНОГО
ФУНКЦИОНАЛА С НЕЛИНЕЙНЫМИ ОГРАНИЧЕНИЯМИ С ИСПОЛЬЗОВАНИЕМ
МЕТОДА ОРТОГОНАЛЬНОЙ ЦИКЛИЧЕСКОЙ РЕДУКЦИИ
Аннотация. Описывается алгоритм решения задачи минимизации квадратичного
функционала
с
нелинейными
ограничениями.
Для
решения
системы
линейных
алгебраических уравнений специальной структуры применяется метод ортогональной
циклической редукции.
Ключевые
слова:
задача
минимизации
с
нелинейными
ограничениями,
квадратичный функционал, ортогональная циклическая редукция.
CHELYSHOV M. S., SHAMANAEV P. A.
QUADRATIC FUNCTIONAL NONLINEAR MINIMIZATION PROBLEM SOLVING
ALGORITHM BY ORTHOGONAL CYCLIC REDUCTION METHOD
Abstract. The article describes an algorithm for solving the quadratic functional nonlinear
minimizing problem. The orthogonal cyclic reduction method is applied for the solution of the
system of linear algebraic equations of special structure.
Keywords: nonlinear minimization problem, quadratic functional, orthogonal cyclic
reduction.
При
решении
задач
идентификации
параметров
систем
обыкновенных
дифференциальных уравнений на основе экспериментальных данных [5; 6] возникает задача
минимизации квадратичного функционала с нелинейными ограничениями:
1

mz , mz   H 2 z , z   H 2~
z , z ,
min
2
 z
Tz  h ,
 g z   0,


(1)
z   Nn  p — вектор известных
где z   Nn  p — вектор неизвестных параметров, ~
параметров,
H2 
1 T
H1 H1 ,
N
где H1  [ I Nn  ONn p ] , I Nn — единичная
Nn  Nn  -матрица,
Nn  p  -матрица,
T  [T1 T 2TN T ] ,
1
ONn p — нулевая
где T1 , T N — постоянные q  n  -матрицы, T — постоянная q  p  -матрица , Ti ,
i  2 , N  1 — нулевые q  n  -матрицы, h   q — вектор известных параметров,
g z   column g1 z ,, g N 1 z ,
g i z   column g i ,1 z ,, g i ,n z ,
i  1, N  1 .
Предполагается, что матрица Якоби вектор-функции нелинейных ограничений имеет
специальную структуру следующего вида:
 
g z ( r )
z
 D1


 A



K1
D2
K2


D N 1
K N 1
E1 

E2 
.

E N 1 
(2)
где Dl , Kl  nn , El  n p , l  1, N  1 .
Для задачи (1) введем функцию Лагранжа:
Lz   mz    , g z    ,Tz  h ,
где    N 1n ,   q , и разложим её в ряд Тейлора в точке z (r ) :
 
2
Lz   L z( r )  l2 z   o z  z( r )  ,


где
 
1   2 L z (r )
l2 z   l1 z   
z  z (r ) , z  z (r )
2  z 2
 

,

 
 L z ( r )

l1 z   
, z  z ( r )   L z ( r ) ,
 z

 
 
 
 
2
(r )
N n 1
L z ( r )
g z ( r )
 2 L z (r )
T  gi, j z
 H 2 z (r )  ~
z  T
 TT ,

H


, (3)
  i, j
2
z
z
z 2
z 2
i 1 j 1


Тогда задача безусловной минимизации:
min Lz 
z
аппроксимируется последовательностью квадратичных задач минимизации:

r  0 ,

 z (0) ,
 s ( r )  arg min l s ( r )  z ( r ) ,
2

s
(
r

1
)
(
r
)
(
 z
 z  s r) ,

r  r  1,




где s ( r )  column dx1 , dx2 ,, dxN , d   Nn  p .
При каждом фиксированном r задача (4) сводится к решению системы
2
(4)






 l 2 s ( r )  z ( r )
 0,

s

(r )
(r )
 l1 s  z
 0,




(r )
(r )
 l1 s  z
 0.




(5)
С учетом (3) систему (5) можно записать в виде:


Hs( r )  T T   AT    H 2 z ( r )  ~
z ,
 (r )
(r )
Ts  h  Tz ,
 As( r )   g z ( r ) ,

(6)
 
где
N 1 n
H  H 2    i , j
T
 .
 2 g i, j z (r )
(7)
z 2
i 1 j 1
Приведем общий алгоритм решения задачи минимизации квадратичного функционала
с нелинейными ограничениями.
1. Задание начальных значений следующих параметров:
z(0) Nn p , (0)  0 ( N 1)n , (0)  0 q ,   0 , r  0 — шаг алгоритма.
2. Вычисление матриц Якоби и Гессе. Вычислим матрицы
Dl , Kl  nn , El  n p , l  1, N  1 .
и сформируем матрицу Якоби согласно (2)


A z( r ) , ( r ) 


g z( r ) , ( r )
.
z
Вычислим матрицу Гессе согласно (7)

H z ,
(r )
(r )
,
(r )


 

2
(r )
N 1 n
 2 L z ( r ) , ( r ) , ( r )
T  g i, j z
.

 H 2    i , j
z 2
z 2
i 1 j 1
3. Уменьшение размерности системы (6) с использованием метода ортогональной
циклической редукции [1].
3.1. Прямой ход метода ортогональной циклической редукции.
Вычислим A k  и g k  :


A( k )  Pk Q( k ) A( k 1) Rk ,
(k )
k  1, kmax ,
где A  A , Q
— матрица ортогональных преобразований, Pk , Rk — матрицы
преобразований, действие которых эквивалентно вычеркиванию четных строк и нечетных
столбцов соответственно.
g( k ) z( r )  Pk Q( k ) g( k 1) z( r ) ,
k  1, kmax ,
0
   
  
 
где g(0) z( r )  g z( r ) .
3
Тогда третье уравнение системы (10) редуцируется к системе:
 
A( kmax )s( kmax )   g ( kmax ) z( k ) ,
где
s  Rs( kmax ) , R  R1R2  Rkmax ,
 dx1 


~
( kmax )
( kmax )
( kmax )
( kmax )
( kmax )
  dxN  .
AA
 [D1
 K1
 E1
], s
 d 


3.2. Вычисление матриц
~
~ T 
~
~
H  RT HR , T  T1  TN T  , B   ~  ,
 A
и вектор-функции
~  h  Tz k 
.
h  
k rmax 

g
z


 
3.3. LQ -факторизация [3]. Методом LQ -факторизации находим матрицу Z , такую
~
что B Z  0 .
3.4. Нахождение решения системы линейных алгебраических уравнений:
~
BBT ~
sB  h
3.5. Вычисление матрицы
~
~
H z  Z T HZ ,
и вектор-функций
~
w( r )  B T ~
sB ,


~(r )
~
hz  Z T [RT H 2 z(r )  ~
z  Hw( r ) ] .
3.6. Нахождение решений системы линейных алгебраических уравнений:
~
~
H z~
sz  hzk .
3.7. Вычисление вектор-функции
~
s  w(r )  Z~
sz .
3.8. Обратный ход метода ортогональной циклической редукции. Восстанавливаем
компоненты dxi , i  2, N  2 вектора s (r ) по формуле:
dxi  Vl( k ) dxm p  U l( k ) x m p  Wl( k ) d  ql( k ) , k  k max , ... , 1, l  2, ... ,
где
N 1
2 k 1
,
p  2k 1 , m  p (l 1) 1, Vl(k ) , Ul(k ) , Wl(k ) , ql(k ) — матрицы и векторы,
получающиеся в результате применения ортогонального преобразования.
4. Вычисление множителей Лагранжа для следующего шага алгоритма.
4
Множители Лагранжа находим как решение следующей системы линейных
алгебраических уравнений:

T  T
 A T
 




  ( r 1)  T 
AT  ( r 1)      Hs( r )  H 2 z ( r )  ~
z .

  A
5. Вычисление нового приближенного решения:
z ( r 1)  z ( r )  s ( r ) .
6. Увеличение номера шага алгоритма: r  r  1.
7. Проверка условия выхода из алгоритма:
Если выполняется условие:

L z ( r ) , ( r ) , ( r ) ,  ( r )
z
то найденное приближение

 ,
z ( r 1) на данном шаге алгоритма будем считать
приближенным решением задачи (1) с заданной точностью  , иначе переходим к пункту 2
данного алгоритма.
ЛИТЕРАТУРА
1.
Атряхин В. А., Челышов М. С., Шаманаев П. А. Применение метода ортогональной
циклической редукции для решения систем линейных алгебраических уравнений с
матрицами
Раздел
специального
вида
"Физико-математические
[Электронный
науки".
–
ресурс]
2014.
//
–
Огарев-online.
№
19. –
Режим доступа: http://journal.mrsu.ru/arts/primenenie-metoda-ortogonalnojj-ciklicheskojjredukcii-dlya-resheniya-sistem-linejjnykh-algebraicheskikh-uravnenijj-s-matricamispecialnogo-vida.
2.
Базара М. Нелинейное программирование. Теория и алгоритмы / пер. с англ.
М. Базара. – М.: Мир, 1982. – 583 с.
3. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация / пер. с. англ. – М.: Мир,
1985. – 509 с.
4. Самарский А. А., Гулин А. В. Численные методы. – М.: Наука, 1989. – 432 c.
5. Челышов М. С., Шаманаев П. А. Идентификация параметров динамических систем
на основе экспериментальных данных // Актуальные вопросы прикладной математики
и информатики: сб. научных трудов. – Саранск: СВМО, 2015. – С. 39–42.
6. Li Zh., Osborne M. R., Prvan T. Parameter estimation of ordinary differential equations //
IMA Journal of Numerical Analysis. – 2005. – No. 25. – Р. 264–285.
5
1/--страниц
Пожаловаться на содержимое документа