CHƯƠNG 2. BÀI TOÁN TỐI ƯU TOÀN PHƯƠNG
2.1 BÀI TOÁN TỐI ƯU TOÀN PHƯƠNG VỚI MỘT HẠN CHẾ
Giả sử H là đa tạp affine trên ¡ và ( ),n f x ( )g x là những hàm toàn phương trên ¡ xác định bởi n
0 0
( ) : 1 , , ,
f x 2 x Q x c x ( ) 1 , 1 1, 1.
g x 2 x Q x c x d (2.1) Ở đó ,Qi i 0,1 là ma trận đối xứng cấp n n và ci ¡ n, d1 ¡ .
Xét bài toán tối ưu toàn phương
min f x( ) |x H g x, ( ) 0 (QPA) min f x( ) |x H g x, ( ) 0 (QPB) Qui ƣớc D ¡ , G x ¡ n | ( )g x 0 cho bài toán (QPA) và D ¡ ,
| ( ) 0
G x ¡ n g x cho bài toán (QPB) và giả sử ( , )L x y f x( ) yg x( ) ở đó x ¡ n, y ¡ Rõ ràng .
( ) nÕu , sup ( , )
trong các trường hợp còn lại.
y D
f x x G
L x y
Do đó giá trị tối ƣu của bài toán (QPA) hoặc (QPB) là:
v(QPA)=inf sup ( , ),
x H y L x y
¡
v(QPB)=inf sup ( , ).
x H y
L x y
¡
Ta nói tính đối ngẫu mạnh của bài toán (QPA) hoặc (QPB) đƣợc thỏa mãn nếu
v(QPA)=supinf ( , )
y x H
L x y
¡
(Trường hợp D ¡ ) (2.2)
v(QPB)=supinf ( , )
y x H
L x y
¡
(Trường hợp D ¡ ). (2.3) Vế phải của (2.2) hoặc (2.3) được gọi là bài toán đối ngẫu tương ứng của bài toán (QPA) hoặc (QPB). Theo Bổ đề 1.2.1, nếu inf ( , )
x H L x y thì hàm (., )
L y là lồi trên H . Vì vậy, để cho tiện, ta quy ƣớc khi inf , supremum trong bài toán đối ngẫu có thể xét trên tập những y D mà hàm
(., )
L y là lồi trên H .
Để nghiên cứu các điều kiện bảo đảm tính đối ngẫu, chúng ta đƣa vào những giả thiết sau đây:
(S) Tồn tại x* H thoả mãn g x( )* 0.
(T) Tồn tại y* D sao cho L x y( , *) f x( ) y g x* ( ) là lồi ngặt trên H .
Định lý 2.1.1 (Định lý về đối ngẫu, Theorem 3, [12])
(i) Nếu giả thiết (S) là thoả mãn thì (2.2) thoả mãn. Ngoài ra,
v(QPA) > -∞ (nghĩa là trường hợp giả thiết (T) cũng thoả mãn với D ¡ ), thì tồn tại y ¡ sao cho L x y lồi trên ( , ) H và
v(QPA) min ( , ) max inf ( , ).
x H L x y y x H L x y
¡ (2.4) Khi ấy điểm x H là nghiệm tối ưu của (QPA) nếu và chỉ nếu thoả mãn
( ) ( ), 0
f x y g x u với mọi u E, yg x( ) 0, g x( ) 0. (2.5) Ở đây E là không gian con của đa tạp affine H .
(ii) Nếu H là không gian con và v(QPB) > -∞ thì ( )
g x là hàm thuần nhất lấy giá trị dương và âm trên H ,
Hoặc g x và ( ) f x là những hàm thuần nhất. Khi ấy (2.3) thoả mãn và ( ) tồn tại y ¡ sao cho L x y là lồi trên ( , ) H và
v(QPB)= min ( , ) max inf ( , ).
x H L x y y x H L x y
¡ (2.6)
Điểm x H là nghiệm tối ưu của (QPB) nếu và chỉ nếu thoả mãn
( ) ( ), 0
f x y g x u với mọi u H, ( )g x 0. (2.7) (iii) Nếu giả thiết (T) là thoả mãn thì (2.3) thoả mãn, khi đó supremum có thể lấy trên y D với L(., )y là lồi trên H . Ngoài ra, nếu bài toán đối ngẫu có nghiệm tối ưu y D thì x H là nghiệm tối ưu của bài toán ban đầu nếu và chỉ nếu
( ) ( ), 0
f x y g x u với mọi u E, (2.8) Ở đây E là không gian con của H .
Chứng minh
(i) Theo sự tồn tại của y từ hệ quả 1.2.1,(i). Điểm x là nghiệm tối ƣu của (QPA) nếu và chỉ nếu max ( , ) ( , ) min ( , ).
x H
y L x y L x y L x y
¡ Do đó, nếu và chỉ
nếu điều kiện (2.5) thoả mãn không cần điều kiện (., )L y lồi trên H.
(ii) Khi ( )g x là hàm thuần nhất nhận cả giá trị dương và giá trị âm trên không gian con H. Sự tồn tại của y suy ra từ hệ quả 1.2.1,(ii). Khi cả hai f x( ),
( )
g x là những hàm thuần nhất, nếu ( )g x 0 với mọi x H thì
inf f x( ) | ( )g x 0,x H v(QPB), do đó theo hệ quả 1.2.1,(iii), v(QPB) > -
∞ suy ra tồn tại ( ,y y1 2) ¡ sao cho y f x1 ( ) y g x2 ( ) 0 với mọi
\ 0 .
x H Nếu y1 0 thì y g x2 ( ) 0 với mọi x H \ 0 , do đó ( )g x 0 với mọi x H, từ đó ( )g x 0 với mọi x H. Mâu thuẫn. Vì vậy, y1 0 và ta có (2.6) thỏa mãn với 2
1
y .
y y ¡
Tương tự, nếu ( ) 0g x với mọi x H thì
inf f x( ) | g x( ) 0,x H v(QPB), do đó (2.6) thoả mãn với y ¡ nào đó. Vì ( , )L x y là lồi trên H, điều kiện (2.7) là điều kiện cần và đủ để x H là nghiệm tối ƣu của bài toán (QPB).
(iii) Nếu giả thiết (T) là thoả mãn thì kết luận suy ra từ Định lý 1.1.1 trong đó C Hvà D ¡ cho bài toán (QPB).
Nếu thêm vào giả thiết (T), bài toán đối ngẫu có nghiệm tối ƣu y D thì x H là nghiệm của bài toán ban đầu nếu và chỉ nếu nó là nghiệm của bài toán tối ƣu lồi min ( , ),
x H L x y do đó nếu và chỉ nếu nó thoả mãn (2.8).
Định lí đƣợc chứng minh.
Chú ý 2.1.1 (Remark 3, [12])
a) Theo Chú ý 1.2.1, nếu ( ),f x ( )g x là những hàm thuần nhất, nghĩa là
( ) 0 , ,
f x Q x x g x( ) Q x x1 , thì Định lý 2.1.1 vẫn đúng nếu H là hình nón chính qui.
b) Trong trường hợp H ¡ ta đã biết, bằng cách đặt n Q y( ) Q0 yQ1,
0 1
( ) ,
c y c yc d y( ) yd1. Bài toán đối ngẫu của (QPA) có thể viết dưới dạng (SDP)
( ) ( )
max | 0, .
( )T 2 ( ) Q y c y
t y D
c y d y t (2.9) Trong trường hợp tổng quát H ¡ n, theo chú ý ở trên về supremum có thể chỉ cần lấy trên tập hợp y ¡ mà ( , )L x y là hàm lồi trên H, nghĩa là
inf ( , )
x H L x y là bài toán lồi. Từ đó bài toán (2.2) chính là làm cực đại hàm lõm ( ) inf ( , )
y x H L x y trên ¡ và giá trị của ( )y tại mỗi y nhận đƣợc bằng cách giải bài toán lồi. Nó dễ dàng giải đƣợc nhờ giải bài toán đối ngẫu theo phương pháp giải bài toán quy hoạch lồi.
Hệ quả 2.1.1 (Corollary 3, [12]) Trong (QPA) hoặc (QPB) nếu f x hoặc ( ) ( )
g x lồi ngặt trên ¡ n thì đối ngẫu mạnh được thỏa mãn.
Chứng minh Nếu ( )f x hoặc ( )g x là lồi ngặt trên ¡ thì tồn tại n y* ¡ sao cho f x( ) y g x* ( ) là lồi ngặt trên ¡ và do đó theo Bồ đề 1.2.2 nó thoả mãn n điều kiện bức trên H . Hàm ( , )L x y f x( ) yg x( ) thoả mãn tất cả các điều kiện của Định lý 1.1.1 với C H, D ¡ (cho (QPA)) hoặc D ¡ cho (QPB)). Theo định lý này, đối ngẫu xảy ra.
Như một hệ quả, bài toán cực tiểu toàn phương trên elipxoit dạng
min f x( ) | Qx x, r x2, ¡ n . (2.10) Với Q 0 (xác định dương) có thể giải hiệu quả bằng cách giải bài toán SDP với đối ngẫu của nó.
Điều này trái với bài toán cực tiểu hàm toàn phương với hạn chế tuyến tính, mà ta đã biết là bài toán NP-khó..
Chú ý 2.1.2 (Remark 4, [12]) Nhƣ là một ví dụ đơn giản minh họa cho điều kiện (T), ta xét bài toán min x14 ax12 bx1 . Thế x12 x2, bài toán trở thành cực tiểu bài toán toàn phương của hai biến x x1, :2
2 2
2 2 1 1 2
min x ax bx x| x 0 . (2.11) Bởi vì x22 ax2 bx1 x12 x2 x x1 1 b x x2 2 a 1 khi
1, 2
x x nên điều kiện (T) đƣợc thỏa mãn. Do đó, theo Định lý 2.1.1, (iii), (2.11) tương đương với bài toán lồi. Chú ý rằng bao lồi của tập hợp không lồi 1, ,x x1 12,...,x1n T |x1 a b, ¡ n 1 đƣợc mô tả chính xác bởi các
hạn chế SDP (trong [10]), do đó với bất kỳ đa thức một biến P xn( )1 bậc ,n bài toán tối ƣu
1 , 1
min n( )
x a b P x hoàn toàn đặc trƣng bởi bài toán SDPs.
Chú ý 2.1.3 (Remark 5, [12]) Mệnh đề sau đây đƣợc thiết lập trong [11, Định lý 3.8]: Trong (QPA) giả thiết điều kiện (S) thoả mãn. Điểm chấp nhận đƣợc x là nghiệm tối ƣu của bài toán (QPA) nếu và chỉ nếu tồn tại y ¡ sao cho
( ) ( ), 0
f x y g x u với mọi u E, yg x( ) 0 (2.12)
0 1
(Q yQ u u) , 0 với mọi u E, (2.13) ở đó E là không gian con song song với H .
Hệ quả 2.1.2 (Corollary 4, [12]) Trong (QPA) khi H ¡ n giả thiết điều kiện (S) thoả mãn. Khi ấy x ¡ n là nghiệm của (QPA) nếu và chỉ nếu tồn tại
y ¡ thoả mãn
0 1
0
Q yQ (2.14)
0 1 0 1
(Q yQ x) c yc 0 (2.15)
1 1
2 , 2 1 0
Q x c x d (2.16) Khi Q không là ma trận xác định dương, thì điều kiện cuối cùng được thay 0 thế bằng điều kiện
1 1
2 , 2 1 0
Q x c x d (2.17) Chứng minh Từ Định lý 2.1.1, (i), x là nghiệm tối ƣu của (QPA) nếu và chỉ nếu tồn tại y ¡ sao cho ( , )L x y f x( ) yg x( ) là lồi và x là điểm cực tiểu của hàm lồi này. Nghĩa là, nếu và chỉ nếu tồn tại y ¡ thoả mãn (2.14) và (2.5), nghĩa là thoả mãn (2.14)-(2.16).
Nếu bất đẳng thức (2.16) đƣợc thỏa mãn ngặt, nghĩa là
1 1
2 , 2 1 0
Q x c x d thì ( )g x 0, do đó ( )g x 0 với mọi x trong một lân cận nào đó của .x Khi ấy x là cực tiểu địa phương, do đó nó là cực tiểu toàn cục của ( )f x trên ¡ mà nó xảy ra chỉ nếu n, Q0 là xác định dương.
Một trường hợp đặc biệt quan trọng của bài toán (QPA) thoả mãn điều kiện (S) là bài toán miền tin cậy (trust region subproblem-TRS), mà nó là bài toán qui hoạch phi tuyến:
1 2
min , , | , .
2 x Qx c x x x r (TRS) Đặc biệt hóa cho bài toán (TRS), từ hệ quả 2.1.2 ta có kết quả sau đây.
Hệ quả 2.1.3 (Corollary 5, [12]) Điều kiện cần và đủ để x là nghiệm tối ưu toàn cục của bài toán (TRS) là tồn tại y ¡ thoả mãn
0
Q yI (2.18) 0
Qx yx c (2.19) x r (2.20) Hệ quả 2.1.4 (Corollary 6, [12]) Với f g H được định nghĩa như trong , , (2.1), giả thiết g x là hàm thuần nhất nhận cả giá trị dương và giá trị âm ( ) trên H . Khi ấy
,
x H ( )g x 0 f x( ) 0 (2.21) nếu và chỉ nếu tồn tại y ¡ sao cho ( )f x yg x( ) 0 với mọi x H.
Hệ quả 2.1.5 (Strict Finsler’sTheorem [5], Corollary 7 [12]) Với f g là , những hàm thuần nhất và H ¡ n ta có
0,
x ( )g x 0 f x( ) 0, (2.22) nếu và chỉ nếu tồn tại y ¡ sao cho f x( ) yg x( ) 0 với mọi x 0.
Chứng minh Điều này suy ra trực tiếp từ Hệ quả 1.2.1,(iii) (S-bổ đề với bất đẳng thức không ngặt). Do f x( ) và g x( ) là thuần nhất, nên tồn tại
2
1 2
( ,y y ) ¡ sao cho y f x1 ( ) y g x2 ( ) 0 với mọi x H \ 0 . Từ (2.22) ta phải có y1 0 do đó 2
1
y y
y nên ta có điều phải chứng minh.
Hệ quả 2.1.6 (Corollary 8, [12]) Giả sử f g H, , được định nghĩa như (2.1) ở trên. Khi ấy có đúng một trong các khả năng sau đây xảy ra
(i) Tồn tại x H thoả mãn ( )f x 0, ( )g x 0;
(ii) Tồn tại y ( ,y y1 2) ¡ 2 \ (0,0) thoả mãn y f x1 ( ) y g x2 ( ) 0với mọi .
x H
Chứng minh Rõ ràng (i) và (ii) không thể đồng thời xảy ra. Thật vậy, nếu (i) không xảy ra thì có thể xảy ra 2 khả năng sau:
1) ( )f x 0 với mọi x H sao cho ( )g x 0.
2) ( )g x 0 với mọi x H sao cho ( )f x 0.
Trong trường hợp 1), nếu 0 là cực tiểu địa phương của ( )g x trên H, thì ( ) 0
g x với mọi x H, do đó y f x1 ( ) y g x2 ( ) 0 với mọi x H với
1 0,
y y2 1. Nếu trong trường hợp ngược lại, 0 không là cực tiểu địa phương của ( )g x trên H thì mọi x H thoả mãn ( )g x 0 là giới hạn của dãy xk H thoả mãn (g xk) 0, k 1,2,... Do đó
inf f x( ) | ( )g x 0,x H inf f x( ) | ( )g x 0,x H 0. Theo Định lý 2.1.1,(i) tồn tại y2 ¡ sao cho f x( ) y g x2 ( ) 0 với mọi x H.
Chứng minh trường hợp 2) tương tự, với hoán vị ( )f x và ( )g x .
Hệ quả 2.1.7 (Corollary 9, [12]) Giả sử f g H được định nghĩa như ở trên, , , giả sử A B là 2 tập hợp con đóng của đa tạp affine , H sao cho A B H .
Giả thiết điều kiện (S) là thoả mãn. Nếu ( ) 0
f x với mọi x A, khi ( )g x 0 với mọi x B. (2.23) Khi ấy tồn tại y ¡ sao cho ( )f x yg x( ) 0 với mọi x H.
Chứng minh Từ điều kiện (S) suy ra H B\ , do đó A . Rõ ràng
| ( ) 0 .
x H g x A Nếu x0 H thoả mãn g x( 0) 0 thì với mọi ,k tồn tại xk H thoả mãn 0 1
k ,
x x
k g x( k) 0, x0 là cực tiểu địa phương của ( )
g x trên H, do đó x0 là cực tiểu toàn cục trên H. Nghĩa là g x( ) g x( )0 0 với mọi x H, mâu thuẫn với điều kiện (S). Vì vậy,
| ( ) 0 | ( ) 0 .
x H g x cl x H g x A
Giả thiết (2.23) kéo theo f x( ) 0 với mọi x H mà g x( ) 0, do đó inf f x( ) | ( )g x 0 0. Vậy sự tồn tại của y suy ra từ Định lý 2.1.1,(i). Ta có điều phải chứng minh.
Hệ quả 2.1.7 chứa Định lý Yuan (Định lý 2.3, [14]) như là trường hợp đặc biệt khi H ¡ và n f x( ) Q x x0 , , g x( ) Q x x1 , , với Q1 không xác định dấu. Thật vậy, khi ấy điều kiện (S) là thoả mãn, trong khi đó ( )f x yg x( ) 0 với mọi x ¡ có nghĩa là n Q0 yQ1 0.
Trong [15] một loạt các mệnh đề tương tự S-Bổ đề của Yakubovich đã được thiết lập mà nó không chứa Định lý của Dines. Để kết thúc phần này, ta phát biểu mở rộng của Định lý Dines và có thể chứng tỏ nó tương đương với Hệ quả 1.2.1.
Hệ quả 2.1.8 (Corollary 10, [12])
(i) Với f x ( ), g x H được định nghĩa như trong (2.1), thì tập hợp ( ),
2
1 2
| , ( ) , ( )
C t R x H f x t g x t là lồi.
(ii) Với f x( ), ( )g x là những hàm thuần nhất và H là không gian con, thì tập hợp G t R2| x H f x, ( ) t g x1, ( ) t2 là lồi.
Chứng minh Để chứng minh tính lồi của C ta xét điểm a ( ,a a1 2) ¡ 2 \C bất kì. Vì C là tập hợp đóng, tồn tại điểm a C sao cho a1 a1, a2 a2. Khi ấy không tồn tại x H sao cho:
( ) 1,
f x a g x( ) a2. (2.24) Theo hệ quả 2.1.6 (suy ra từ hệ quả 1.2.1,(i)), tồn tại ( ,y y1 2) ¡ 2 \ 0,0 thỏa mãn y f x1( ( ) a1) y g x2 ( ) a2 0 với mọi x H.
Đặt La: t ¡ 2| y t1 1 y t2 2 y a1 1 y a2 2 , dễ dàng kiểm tra đƣợc C La, trong khi đó a La. Do đó với mọi a C tồn tại nửa không gian La tách a và .C Suy ra, a,
C a CL điều này chứng minh tính lồi của .C
Trở về tập hợp G với ( ),f x ( )g x là những hàm thuần nhất và H là không gian con, ta quan sát thấy rằng nếu tồn tại x H thoả mãn
1 ( ) 2 ( ) 0,
a g x a f x a f x1 ( ) 0 thì 1 1 ( )2 ( ) ( ) 0, a a f x
f x f x vì vậy đặt 1 2
( )
a r
f x
ta có a1 r f x2 ( ) f rx( ) và 2 1 ( ) 2 ( ) ( ).
( )
a a g x r g x g rx
f x Do đó
a G vì rx H. Vì vậy, nếu a G thì
1 1 2
min a f x a g x( ) | ( ) a f x( ) 0,x H 0. Theo Hệ quả 1.1.1,(ii), tồn tại y ¡ thoả mãn a f x1 ( ) y a g x1 ( ) a f x2 ( ) 0 với mọi x H.
Khi đó G La : t ¡ 2| a t1 2 y a t( 1 2 a t2 1) 0 , a La (vì a12 0), trong khi đó a G. Vì vậy có thể tách a và G bởi nửa không gian, điều này chứng minh tính lồi của tập hợp .G