http://www.me.titech.ac.jp/ nakata/nakata.html p.1/20
1-(a). Faybusovich(1997) Linear systems in Jordan algebras and primal-dual interior-point algorithms,, Euclid Jordan p.2/20
Euclid Jordan V Euclid Jordan : V 2 V x, y V, α, β R x y = y x (αx 1 + βx 2 ) y = αx 1 y + βx 2 y x ((x x) y) = (x x) (x y) x x + y y = 0 = x = y = 0 p.3/20
Euclid Jordan V Euclid Jordan : V 2 V x, y V, α, β R x y = y x (αx 1 + βx 2 ) y = αx 1 y + βx 2 y x ((x x) y) = (x x) (x y) x x + y y = 0 = x = y = 0 (LP) V = R n, 0 B @ x 1 x 2. x n 1 0 y 1 y n 1 y 2 C B A @. C A 0 1 x 1 y 1 x 2 y 2 B @. C A x n y n p.3/20
Euclid Jordan V Euclid Jordan : V 2 V x, y V, α, β R x y = y x (αx 1 + βx 2 ) y = αx 1 y + βx 2 y x ((x x) y) = (x x) (x y) x x + y y = 0 = x = y = 0 (SOCP) ( 0 1 V = R n @ x ) 0 A x 1 x0 R, x 1 R n 1 0 1 0 1 0 1 @ x 0 A @ y 0 A x 1 y 1 @ x 0y 0 + x T 1 y 1 x 0 y 1 + y 0 x 1 A p.3/20
Euclid Jordan V Euclid Jordan : V 2 V x, y V, α, β R x y = y x (αx 1 + βx 2 ) y = αx 1 y + βx 2 y x ((x x) y) = (x x) (x y) x x + y y = 0 = x = y = 0 (SDP) V = S n {X R n n X = X T }, X Y (XY + Y X)/2 p.3/20
e x e = x, e y = y x 1 x x 1 = x 1 x = e x α x β = x α+β x = r λ k c k k=1 c 2 k = c k, c i c j = 0, x, y r λ k (x y) k=1 r k=1 c k = e p.4/20
K {x 2 V x V } K {x V y K, x, y 0} = K x K λ(x) 0 x, y K, x, y = 0 x y = 0 x y K x K y x, y int(k), g GL(V ), gk = K, gx = y p.5/20
maximize c, x minimize b, y subject to Ax = b, subject to z = A y c, x K 0. z K 0. x V, y R m, z V c V, b R m A : V R m A : R m V K: A Ax, y = x, A y p.6/20
maximize c, x minimize b, y subject to Ax = b, subject to z = A y c, x K 0. z K 0. x V, y R m, z V V K LP R n {(x 1, x 2,, x n ) T R n x i 0} SOCP R n {(x 0, x 1 ) T R n x 0 x 1 } SDP S n {X S n X } p.6/20
Ax = b z = A y c x z = 0 x, z K 0 p.7/20
Ax = b z = A y c x z = 0 x, z K 0 (x, y, z) z = A y c Ax = b V R m V x z = µe, µ > 0 x, z K 0 µ 0 p.7/20
1-(b). p.8/20
1-(b). p.8/20
1-(b). p.8/20
1-(b). p.8/20
1-(b). p.8/20
1-(b). p.8/20
1-(b). p.8/20
1-(b). p.8/20
1-(b). p.8/20
Euclid Jordan L x L y x y = L x y = L y x d dx x y = d dx L yx = L y P x 2L 2 x L x 2 Q x,y L x L y + L y L x L x y P 1 x = P x 1 P Px y = P x P y P x (P x y) 1 = P 1 x y 1 Q x 2,y = P x L P 1 x y P x p.9/20
Ax b 0 F (x, y, z) = A y c z = 0 x z µe 0 p.10/20
Ax b 0 F (x, y, z) = A y c z = 0 x z µe 0 Newton (x, y, z), (dx, dy, dz) F (x, y, z)(dx, dy, dz) = F (x, y, z) p.10/20
Ax b 0 F (x, y, z) = A y c z = 0 x z µe 0 Newton (x, y, z), Adx = r p A dy dz = r d L z dx + L x dz = r c (dx, dy, dz) b Ax c A y + z µe x z p.10/20
Newton Adx = r p A dy dz = r d L z dx + L x dz = r c b Ax c A y + z µe x z p.11/20
Newton Adx = r p A dy dz = r d L z dx + L x dz = r c b Ax c A y + z µe x z 1. B := AL 1 z L x A 2. s := r p + AL 1 z (r c + L x r d ) 3. Bdy = s 4. dz := A dy r d 5. dx := L 1 z (r c L x dz) p.11/20
Newton Adx = r p A dy dz = r d L z dx + L x dz = r c b Ax c A y + z µe x z 1. B := AL 1 z L x A 2. s := r p + AL 1 z (r c + L x r d ) 3. Bdy = s 4. dz := A dy r d 5. dx := L 1 z (r c L x dz) L 1 z p.11/20
Ax b 0 F (x, y, z) = A y c z = 0 x z µe 0 p.12/20
Ax b 0 F (x, y, z) = A y c z = 0 x z µe 0 F g (x, y, z) = Ax b A y c z P g x P 1 g z µe = 0 0 0 P g x = 2g (g x) (g g) x p.12/20
Ax b 0 F (x, y, z) = A y c z = 0 x z µe 0 F g (x, y, z) = Ax b A y c z P g x P 1 g z µe = 0 0 0 F g Newton p.12/20
F Newton Adx = r p A dy dz = r d L z dx + L x dz = r c b Ax c A y + z µe x z p.13/20
F Newton Adx = r p A dy dz = r d L z dx + L x dz = r c b Ax c A y + z µe x z F g Newton Adx = r p b Ax A dy dz = r d c A y + z L P 1 g z P gdx + L Pg xp 1 g dz = r c µe P g x P 1 g z p.13/20
1. B := AP 1 g L 1 Pg 1 2. s := r p + AP 1 g L z P g xp 1 g A L 1 3. Bdy = s 4. dz := A dy r d 5. dx := P 1 g L 1 Pg 1 Pg 1 z (r c + L Pg xp 1 g r d ) (r z c L Pg xp 1 g dz) p.14/20
1. B := AP 1 g L 1 Pg 1 2. s := r p + AP 1 g L z P g xp 1 g A L 1 3. Bdy = s 4. dz := A dy r d 5. dx := P 1 g L 1 Pg 1 Pg 1 z (r c + L Pg xp 1 g r d ) (r z c L Pg xp 1 g dz) L 1 Pg 1 z g K p.14/20
1. B := AP 1 g L 1 Pg 1 2. s := r p + AP 1 g L z P g xp 1 g A L 1 3. Bdy = s 4. dz := A dy r d 5. dx := P 1 g L 1 L 1 Pg 1 z Pg 1 Pg 1 z (r c + L Pg xp 1 g r d ) (r z c L Pg xp 1 g dz) g K HKM g := z 1/2 P 1 g L 1 Pg 1 L z P g xp 1 g NT P 1 g z = P g x P 1 g L 1 Pg 1 L z P g xp 1 g = Q x,z 1 = P 2 g p.14/20
HKM Newton Adx = r p b Ax A dy dz = r d c A y + z P z 1/2dx + P z 1/2Q x,z 1dz = r c µe P z 1/2x 1. B := AQ x,z 1A 2. s := r p + A(P 1 r z 1/2 c + Q x,z 1r d ) 3. Bdy = s 4. dz := A dy r d 5. dx := P 1 r z 1/2 c Q x,z 1dz p.15/20
x + αdx K α x + αdx K P x 1/2(e + αp 1 dx) K x 1/2 e + αp 1 dx K x 1/2 λ k (e + αp 1 dx) 0 x 1/2 1 + αλ k (P 1 dx) 0 x 1/2 λ := λ min (P 1 x 1/2 dx) α = 1 (λ < 0) λ (λ 0) p.16/20
LP R n = {(x i ) x i R (i = 1, 2,, n)} Euclid Jordan (x i ) (y i ) = (x i y i ) e e = (1) x (x i ) 1 = (1/x i ) K = {(x i ) R n x i 0} L x L (xi ) = diag(x i ) P x P (xi ) = diag(x 2 i ) Q x,y Q (xi ),(y i ) = diag(x i y i ) n (x i ) = x k e k x, y k=1 (x i ), (y i ) = x T y p.17/20
SOCP R n = Euclid Jordan e x ( ( x 0 x 1 1 0 ) ) Jx x T Jx { x 0 x 1 ( ) y 0 y 1 x 0 R, x 1 R n 1 = ( x 0 y 0 + x T 1 y 1 x 0 y 1 + y 0 x 1 ) } K = {x x 0 x T 1 x 1 } J = 0 1 @ 1 0T A 0 I p.18/20
SOCP ( ) x 0 x L T 1 x x 1 x 0 I P x 2xx T (x T Jx)J Q x,y xy T + yx T (x T Jy)J x 0 = (x 0 + x T 1 x 1) x 1 1 2 x 1 2 x T 1 x 1 + (x 0 x T 1 x 1) 1 2 x 1 2 x T 1 x 1 x, y 2x T y J = 0 1 @ 1 0T A 0 I p.19/20
SDP S n = {X R n n X = X T } Euclid Jordan X Y = (XY + Y X)/2 e I x X = X 1 K = {X S n X } L x (I X + X I)/2 P x X X Q x,y (X Y + Y X)/2 n X = λ k v k v T k x, y n i,j=1 k=1 X ij Y ij p.20/20