Luận văn Quy hoạch Toàn Phương

( , ) : : : inf ( ) : ( , ) . nA b x Ax b f x x A bθ ∆ = ∈ ≥ = ∈∆  Nếu ( , )A b∆ =∅ thì θ = +∞ (quy ước). Nếu ( , )A b∆ ≠ ∅ thì có hai trường hợp xảy ra: hoặc là θ ∈ hoặc là θ = −∞ (khi đó, bài toán không có nghiệm). Một vấn đề được đặt ra là khi trường hợp θ ∈ xảy ra thì bài toán có nghiệm tối ưu hay không? Ta có nhận xét, bài toán tối ưu với hàm mục tiêu không phải là hàm toàn phương có thể không có nghiệm ngay cả khi giá trị tối ưu của nó là hữu hạn. Chẳng hạn, xét ví dụ: cho bài toán 1min : , 1x x x  ∈ ≥     . Khi đó, bài toán không có nghiệm, trong khi giá trị tối ưu của nó 1inf : , 1 0x x x θ  = ∈ ≥ =     là hữu hạn. Định lý Frank-Wolfe được phát biểu sau đây sẽ cho ta biết điều kiện tồn tại nghiệm của bài toán (2.1). 2.1.1. Định lý Frank-Wolfe Định lý 2.1 (định lý Frank-Wolfe) Nếu { }inf ( ) : ( , )f x x A bθ = ∈∆ là một số thực hữu hạn thì bài toán (2.1) có nghiệm. Chứng minh 15 Giả sử θ ∈ . Ta cần chứng minh bài toán (2.1) có nghiệm. Do θ ∈ nên ( , )A b∆ ≠ ∅ . Lấy 0 ( , )x A b∈∆ , với 0ρ > tùy ý. Đặt 0( , ) ( , )A b B xρ ρ∆ = ∆ ∩ . Suy ra, ρ∆ là tập lồi, khác rỗng và compact. Xét bài toán: { }min ( ) :f x x ρ∈∆ . (2.1’) Theo định lý Weierstrass tồn tại y ρ∈∆ sao cho: { }( ) : min ( ) :f y q f x xρ ρ= = ∈∆ Vì tập nghiệm của bài toán (2.1’) là khác rỗng và compact nên tồn tại yρ ρ∈∆ sao cho: { }0 0min : , ( ) .y x y x y f y qρ ρ ρ− = − ∈∆ = Khi đó, luôn tồn tại ˆ 0ρ > sao cho 0 ˆ, .y xρ ρ ρ ρ− < ∀ ≥ (2.2) Thật vậy, giải sử trái lại chúng ta tìm được dãy tăng { } :k kρ ρ → +∞ sao cho với mỗi k tồn tại k k yρ ρ∈∆ sao cho 0( ) , k k k k f y q y xρ ρ ρ ρ= − = . Để đơn giản cho ký hiệu ta viết ky thay cho k yρ . Vì ( , ) ky A b∈∆ nên , 1,..., .ki iA y b i m≥ ∀ = Với 1i = ta có dãy { }1 kA y bị chặn dưới nên tồn tại dãy { } { }'k k⊂ sao cho ' 1' lim k k A y →∞ tồn tại (có thể xảy ra trường hợp '1'lim k k A y →∞ = +∞ ). Không mất tính tổng quát ta giả sử { } { }'k k≡ , khi đó 1lim kk A y→∞ tồn tại. Tương tự, với 2i = ta cũng có 2lim k k A y →∞ tồn tại. Tiếp tục quá trình trên với i m= ta có lim kmk A y→∞ tồn tại. Khi đó, với mỗi { }1,...,i m∈ ta có lim kik A y→∞ tồn tại. Đặt {1,...,m}I = , { }0 0 : lim ki ikI i I A y b→∞= ∈ = , { }1 \ : lim ko i ikI I I i I A y b→∞= = ∈ > . Khi đó, tồn tại 0ε > sao cho 1lim , k i ik A y b i Iε →∞ ≥ + ∀ ∈ . 16 Mặt khác, 0 0 1 k k k k y xy x kρ ρ ρ − − = ⇒ = ∀ . Vì quả cầu đơn vị trong n là compact nên không mất tính tổng quát ta có thể giả sử dãy 0k k y x ρ  −     hội tụ về nv ∈ khi k →∞ và 1v = . Vì kρ → +∞ nên với mỗi 0i I∈ , ta có: ( ) 00 0 lim lim lim lim k i ik k i i k k k i i ik k k k i A y b A y b A x by xA Av ρ ρ ρ →∞ →∞ →∞ →∞ = −  − =        −− = +        = Tương tự, với mỗi 1i I∈ ta có: 0 0 00 0 liminf liminf lim lim k i i k k k i i i i k k k k i i ik k k k i A y b A y A x A x b A x by xA Av ρ ρ ρ ρ ρ →∞ →∞ →∞ →∞  − ≤      − − = +       −− = +        = Khi đó, 00,iAv i I= ∀ ∈ và 10,iAv i I≥ ∀ ∈ . Suy ra, v là phương lùi xa của tập lồi đa diện ( , )A b∆ . Do đó, ( , )y tv A b+ ∈∆ với mọi 0t ≥ và ( , )y A b∈∆ . (2.3) Vì { } { }0 ( ) ( ) min ( ) : min ( ) : ( , ) ( , ) k k k k k f y f y q f x x f x x A b B x ρ ρ ρ ρ = = = ∈∆ = ∈∆ ∩ 17 và dãy { }kρ là dãy tăng kρ → +∞ nên ta có { }( )kf y là dãy giảm và ( )kf y θ→ . Với k đủ lớn, ta có: 1 ( ) 1kf yθ θ− ≤ ≤ + . Sử dụng công thức của hàm f ta có thể viết bất đẳng thức trên dưới dạng: ( ) ( ) ( ) ( ) 0 0 0 0 0 0 0 0 11 2 1( ) ( ) 1 2 Tk k T k T k T T y x D y x c y x x D y x x Dx c x θ θ − ≤ − − + − + + − + + ≤ + Chia các vế của bất đẳng thức trên cho 2kρ và cho k →+∞ ta được 10 0 2 Tv Dv≤ ≤ . Suy ra, 0Tv Dv = . Từ (2.3) suy ra, ( , )ky tv A b+ ∈∆ với mọi 0t ≥ và k∈ . Kết hợp với điều kiện 0Tv Dv = , ta có: ( ) ( ) ( ) ( ) ( ) ( )( ) 1 2 1 2 Tk k k T k T Tk k T k k T f y tv y tv D y tv c y tv y Dy c y t y Dv c v + = + + + + = + + + Suy ra: ( ) 0,Tk Ty Dv c v k+ ≥ ∀ ∈ . (2.4) Giả sử trái lại ( ) 0Tk Ty Dv c v+ < với k∈ nào đó, thì ( )kf y tv+ → −∞ khi t →+∞ , điều này mâu thuẫn với giả thiết θ ∈ . Do đó, ta có công thức (2.4). Mặt khác, , 1v v = và 0k k y x v ρ − → nên tồn tại 1k ∈ sao cho: 0 1, 0 k k y x v k k ρ − > ∀ ≥ Cố định 1k k≥ ta có, 0 , 0ky x v− > . Suy ra: 2 2 220 0 0 2 02 ,k k k ky x tv y x t y x v t v y x− − = − − − + < − (2.5) 18 với 0t > đủ nhỏ. Ta lại có: ( ) 0,k ki i iA y tv A y b i I− = ≥ ∀ ∈ (do với 0i I∈ ta có 0iAv = ). Mặt khác, 1lim , k i ik A y b i Iε →∞ ≥ + ∀ ∈ nên tồn tại 2 2 1,k k k∈ ≥ sao cho: 2 1, ,2 k i iA y b k k i I ε ≥ + ∀ ≥ ∈ . Cố định chỉ số 2k k≥ và chọn 0kδ > sao cho ( )1, 0,2i ktAv i I t ε δ≤ ∀ ∈ ∈ . Khi đó: ( ) ( )1, , 0,2 k i i i i kA y tv b tAv b i I t ε δ− ≥ + − ≥ ∀ ∈ ∈ . Suy ra: ( ),ky tv A b− ∈∆ với mọi ( )0, kt δ∈ . Kết hợp với (2.5) ta có, ( ),ky tv A b− ∈∆ và: ( ) 0 0 0k k k ky tv x y x tv y x ρ− − = − − < − = với mọi ( )0, kt δ∈ đủ nhỏ. Từ (2.4) ta có: ( ) ( ) ( )( ) ( ) ( )( ) ( ) 1 2 . T Tk k k T k k T Tk k T k f y tv y Dy c y t y Dv c v f y t y Dv c v f y − = + − + = − + ≤ Do đó, ky tv− là nghiệm của bài toán { }min ( ) : kf x x ρ∈∆ . Từ bất đẳng thức ( ) 0 0k ky tv x y x− − < − suy ra ky không phải là nghiệm của bài toán trên với khoảng cách tới 0x là nhỏ nhất. Điều này mâu thuẫn với: { }0 0min : , ( ) .k kky x y x y f y qρ ρ− = − ∈∆ = Vậy, ta đã chứng minh được tồn tại ˆ 0ρ > sao cho (2.2) được thỏa mãn. Tiếp tục quá trình chứng minh ta cần chỉ ra tồn tại ˆρ ρ≥ sao cho qρ θ= . (2.6) Vì { }min ( ) :q f x xρ ρ= ∈∆ nên từ (2.6) suy ra định lý đã chứng minh. Chứng minh khẳng định (2.6). Giả sử trái lại ˆ,qρ θ ρ ρ> ∀ ≥ . (2.7) 19 Chú ý rằng, 'q qρ ρ≥ với mọi 'ρ ρ≥ và qρ θ→ khi ρ → +∞ . Từ (2.7) suy ra tồn tại ( )ˆ , ( 1,2)i iρ ρ∈ +∞ = sao cho 1 2ρ ρ . Vì 2ρ ρ> nên từ kết quả (2.2) ta có: 2 0 2y xρ ρ− < . Ta có: 1 2 q qρ ρ> nên 2 0 1 y xρρ < − (Thật vây, nếu 2 0 1 y xρρ ≥ − thì 2 1 yρ ρ∈∆ và ( ) ( )2 2 1 1f y q q f yρ ρ ρ ρ= < = , điều này mâu thuẫn với cách chọn 1yρ ). Đặt 2 0 3 y xρρ = − ta có, 1 3 2ρ ρ ρ nên từ khẳng định (2.2) ta có: 3 2 0 0 3 2y x y xρ ρρ ρ− < = − < . (2.8) Vì 2 3ρ ρ> nên ( ) ( )3 3 2 2q f y f y qρ ρ ρ ρ= ≥ = . Nếu ( ) ( )3 2f y f yρ ρ= thì từ (2.8) suy ra 3yρ là vectơ chấp nhận được của bài toán: { }2min ( ) :f x x ρ∈∆ . (2.9) với hàm mục tiêu có giá trị tối ưu ( )2 2q f yρ ρ= , mà ( ) ( )3 2f y f yρ ρ= nên 3yρ cũng là nghiệm của bài toán (2.9). Mặt khác, 3 2 0 0y x y xρ ρ− < − . Suy ra, 2yρ không phải là nghiệm của bài toán (2.9) với khoảng cách tới 0x là nhỏ nhất, điều này mâu thuẫn với sự tồn tại của 2 yρ . Do đó, ( ) ( )3 2f y f yρ ρ> . Ta lại có, 2 0 3y xρ ρ− = nên 2yρ là vectơ chấp nhận được của bài toán { }3min ( ) :f x x ρ∈∆ . Từ bất đẳng thức ( ) ( )3 2f y f yρ ρ> dẫn đến mâu thuẫn với sự kiện 3 yρ là nghiệm tối ưu của bài toán. Suy ra: khẳng định (2.6) đã được chứng minh. Vậy, bài toán (2.1) có nghiệm.  Trong định lý Frank-Wolfe, nếu thiếu một trong hai điều kiện f là hàm toàn phương hoặc ∆ là tập lồi đa diện thì kết luận của định lý sẽ không còn đúng nữa. 20 Ví dụ 1: Xét bài toán { }1min ( ) :f x x x= ∈∆ trong đó 1( )f x x= là hàm toàn phương nhưng ( ){ }21 2 1 2 1 2, : 1, 0, 0Tx x x x x x x∆ = = ∈ ≥ ≥ ≥ không phải là tập lồi đa diện. Ta có: { }inf ( ) : 0f x xθ = ∈∆ = nhưng bài toán { }1min ( ) :f x x x= ∈∆ không có nghiệm. Ví dụ 2: Xét bài toán 1min : , 1x x x  ∈ ≥     trong đó, { }: 1x x∆ = ∈ ≥ là tập lồi đa diện nhưng hàm 1( )f x x = không phải là hàm toàn phương. Ta có, 1inf : , 1 0x x x θ  = ∈ ≥ =     nhưng bài toán 1min : , 1x x x  ∈ ≥     không có nghiệm. Mặt khác, do ∆ là tập lồi đa diện nên ta có thể phát biểu định lý dưới dạng: Nếu một hàm toàn phương bị chặn dưới trên một tập lồi đa diện thì bài toán min của hàm toàn phương trên tập lồi đa diện đó sẽ có nghiệm. 2.1.2. Định lý Eaves Định lý 2.2 (Định lý Eaves) Bài toán (2.1) có nghiệm nếu và chỉ nếu các điều kiện sau được thỏa mãn: i) ( , )A b∆ khác rỗng. 21 ii) Nếu nv∈ và 0Av ≥ thì 0Tv Dv ≥ . iii) Nếu nv∈ và nx∈ sao cho 0Av ≥ , 0Tv Dv = và Ax b≥ thì ( ) 0TDx c v+ ≥ . Chứng minh ⇒ / Giả sử bài toán (2.1) có nghiệm là x . Ta cần chứng minh các điều kiện i), ii), iii) được thỏa mãn. Thật vậy: Vì x là nghiệm của bài toán (2.1) nên ( , )A b∆ khác rỗng. Suy ra điều kiện i) được thỏa mãn. Giả sử nv∈ và 0Av ≥ . Ta có, ( ) , 0A x tv Ax tAv b t+ = + ≥ ∀ ≥ nên ( , )x tv A b+ ∈∆ với mọi 0t ≥ . Suy ra, ( ) ( ) , 0f x tv f x t+ ≥ ∀ ≥ . Sử dụng công thức của hàm f ta được: ( )21 0, 0 2 TTt v Dv t Dx c v t+ + ≥ ∀ ≥ . Từ đó suy ra, 0Tv Dv ≥ (thật vậy, nếu 0Tv Dv < thì ta cho t →+∞ ở bất đẳng thức trên sẽ dẫn đến điều vô lý). Do đó, điều kiện ii) được thỏa mãn. Giả sử nv∈ và nx∈ sao cho 0Av ≥ , 0Tv Dv = và Ax b≥ . Vì ( , )x tv A b+ ∈∆ với mọi 0t ≥ và x là nghiệm của bài toán (2.1) nên ( ) ( ) , 0f x tv f x t+ ≥ ∀ ≥ . Từ điều kiện 0Tv Dv = suy ra: ( ) 1 ( ), 0. 2 T T Tt Dx c v x Dx c x f x t+ + + ≥ ∀ ≥ Nếu ( ) 0TDx c v+ < thì ta cho t →+∞ ở bất đẳng thức trên sẽ dẫn đến điều vô lý. Suy ra, điều kiện iii) được thỏa mãn. ⇐ / Giả sử các điều kiện i), ii) iii) được thỏa mãn. Ta chứng minh bài toán (2.1) có nghiệm. Đặt { }inf ( ) : ,nf x x Ax bθ = ∈ ≥ . Vì ( , )A b∆ khác rỗng nên θ ≠ +∞ . Nếu θ ∈ thì theo định lý Frank-Wolfe bài toán (2.1) có nghiệm. Ta cần chứng minh θ = −∞ không xảy ra. Thật vậy, giả sử có θ = −∞ . Cố định 0 ( , )x A b∈∆ , với mỗi 0ρ > ta định nghĩa 0( , ) ( , )A b B xρ ρ∆ = ∆ ∩ . Ta xét bài toán 22 { }min ( ) :f x x ρ∈∆ . Gọi qρ là giá trị tối ưu của bài toán này. Lấy yρ ρ∈∆ sao cho ( )f y qρ ρ= và { }0 0min : , ( )y x y x y f y qρ ρ ρ− = − ∈∆ = . Khi đó, luôn tồn tại ˆ 0ρ > sao cho 0 ˆ, .y xρ ρ ρ ρ− < ∀ ≥ Thật vậy, giải sử trái lại chúng ta tìm được dãy tăng { } :k kρ ρ → +∞ sao cho với mỗi k tồn tại k k yρ ρ∈∆ sao cho 0( ) , k k k k f y q y xρ ρ ρ ρ= − = . Để đơn giản cho ký hiệu ta viết ky thay cho k yρ . Vì ( , ) ky A b∈∆ nên , 1,..., .ki iA y b i m≥ ∀ = Với 1i = ta có dãy { }1 kA y bị chặn dưới nên tồn tại dãy { } { }'k k⊂ sao cho ' 1' lim k k A y →∞ tồn tại (có thể xảy ra trường hợp '1'lim k k A y →∞ = +∞ ). Không mất tính tổng quát ta giả sử { } { }'k k≡ , khi đó 1lim kk A y→∞ tồn tại. Tương tự, với 2i = ta cũng có 2lim k k A y →∞ tồn tại. Tiếp tục quá trình trên với i m= ta có lim kmk A y→∞ tồn tại. Khi đó, với mỗi { }1,...,i m∈ ta có lim kik A y→∞ tồn tại. Đặt {1,...,m}I = , { }0 0 : lim ki ikI i I A y b→∞= ∈ = , { }1 \ : lim ko i ikI I I i I A y b→∞= = ∈ > . Khi đó, tồn tại 0ε > sao cho 1lim , k i ik A y b i Iε →∞ ≥ + ∀ ∈ . Mặt khác, 0 0 1 k k k k y xy x kρ ρ ρ − − = ⇒ = ∀ . Vì quả cầu đơn vị trong n là compact nên không mất tính tổng quát ta có thể giả sử dãy 0k k y x ρ  −     hội tụ về nv ∈ khi k →∞ và 1v = . Vì kρ → +∞ nên với mỗi 0i I∈ , ta có: 23 ( ) 00 0 lim lim lim lim k i ik k i i k k k i i ik k k k i A y b A y b A x by xA Av ρ ρ ρ →∞ →∞ →∞ →∞ = −  − =        −− = +        = Tương tự, với mỗi 1i I∈ ta có: 0 0 00 0 liminf liminf lim lim k i i k k k i i i i k k k k i i ik k k k i A y b A y A x A x b A x by xA Av ρ ρ ρ ρ ρ →∞ →∞ →∞ →∞  − ≤      − − = +       −− = +        = Khi đó, 00,iAv i I= ∀ ∈ và 10,iAv i I≥ ∀ ∈ . Suy ra, v là phương lùi xa của tập lồi đa diện ( , )A b∆ . Do đó, ( , )y tv A b+ ∈∆ với mọi 0t ≥ và ( , )y A b∈∆ . (2.10) Vì { } { }0 ( ) ( ) min ( ) : min ( ) : ( , ) ( , ) k k k k k f y f y q f x x f x x A b B x ρ ρ ρ ρ = = = ∈∆ = ∈∆ ∩ và dãy { }kρ là dãy tăng kρ → +∞ nên ta có { }( )kf y là dãy giảm và ( )kf y →−∞ . Suy ra, ( ) 0kf y < với k đủ lớn. Sử dụng công thức của hàm f ta được: ( ) ( ) ( ) ( ) 0 0 0 0 0 0 0 0 1 2 1( ) ( ) 0 2 Tk k T k T k T T y x D y x c y x x D y x x Dx c x − − + − + + − + + < 24 Chia các vế của bất đẳng thức trên cho 2kρ và cho k →+∞ ta được 0Tv Dv ≤ . Vì 0Av ≥ nên từ điều kiện ii) suy ra 0Tv Dv ≥ . Do đó, 0Tv Dv = . Từ (2.10) suy ra, ( , )ky tv A b+ ∈∆ với mọi 0t ≥ và k∈ . Kết hợp với điều kiện 0Tv Dv = , ta có: ( ) ( ) ( ) ( ) ( ) ( )( ) 1 2 1 2 Tk k k T k T Tk k T k k T f y tv y tv D y tv c y tv y Dy c y t y Dv c v + = + + + + = + + + Vì ( , ), 0, 0k Ty A b Av v Dv∈∆ ≥ = nên từ điều kiện iii) suy ra: ( ) ( ) 0,Tk T k Ty Dv c v Dy c v k+ = + ≥ ∀ ∈ . (2.11) Mặt khác, , 1v v = và 0k k y x v ρ − → nên tồn tại 1k ∈ sao cho: 0 1, 0 k k y x v k k ρ − > ∀ ≥ Cố định 1k k≥ ta có, 0 , 0ky x v− > . Suy ra: 2 2 220 0 0 2 02 ,k k k ky x tv y x t y x v t v y x− − = − − − + < − (2.12) với 0t > đủ nhỏ. Ta lại có: ( ) 0,k ki i iA y tv A y b i I− = ≥ ∀ ∈ (do với 0i I∈ ta có 0iAv = ). Mặt khác, 1lim , k i ik A y b i Iε →∞ ≥ + ∀ ∈ nên tồn tại 2 2 1,k k k∈ ≥ sao cho: 2 1, ,2 k i iA y b k k i I ε ≥ + ∀ ≥ ∈ . Cố định chỉ số 2k k≥ và chọn 0kδ > sao cho ( )1, 0,2i ktAv i I t ε δ≤ ∀ ∈ ∈ . Khi đó: ( ) ( )1, , 0,2 k i i i i kA y tv b tAv b i I t ε δ− ≥ + − ≥ ∀ ∈ ∈ . Suy ra: ( ),ky tv A b− ∈∆ với mọi ( )0, kt δ∈ . Kết hợp với (2.12) ta có, ( ),ky tv A b− ∈∆ và: ( ) 0 0 0k k k ky tv x y x tv y x ρ− − = − − < − = 25 với mọi ( )0, kt δ∈ đủ nhỏ. Từ (2.11) ta có: ( ) ( ) ( )( ) ( ) ( )( ) ( ) 1 2 . T Tk k k T k k T Tk k T k f y tv y Dy c y t y Dv c v f y t y Dv c v f y − = + − + = − + ≤ Do đó, ky tv− là nghiệm của bài toán { }min ( ) : kf x x ρ∈∆ . Từ bất đẳng thức ( ) 0 0k ky tv x y x− − < − suy ra ky không phải là nghiệm của bài toán trên với khoảng cách tới 0x là nhỏ nhất. Điều này mâu thuẫn với: { }0 0min : , ( ) .k kky x y x y f y qρ ρ− = − ∈∆ = Vậy, ta đã chứng minh được tồn tại ˆ 0ρ > sao cho: 0 ˆ, (2.13)y xρ ρ ρ ρ− < ∀ ≥ Chú ý rằng, 'q qρ ρ≥ với mọi 'ρ ρ≥ và qρ θ→ = −∞ khi ρ → +∞ . Suy ra: tồn tại ( )ˆ , ( 1,2)i iρ ρ∈ +∞ = sao cho 1 2ρ ρ . Vì 2ρ ρ> nên từ kết quả (2.13) ta có: 2 0 2y xρ ρ− < . Ta có: 1 2 q qρ ρ> nên 2 0 1 y xρρ < − (Thật vây, nếu 2 0 1 y xρρ ≥ − thì 2 1 yρ ρ∈∆ và ( ) ( )2 2 1 1f y q q f yρ ρ ρ ρ= < = , điều này mâu thuẫn với cách chọn 1yρ ). Đặt 2 0 3 y xρρ = − ta có, 1 3 2ρ ρ ρ nên từ khẳng định (2.13) ta có: 3 2 0 0 3 2y x y xρ ρρ ρ− < = − < . (2.14) Vì 2 3ρ ρ> nên ( ) ( )3 3 2 2q f y f y qρ ρ ρ ρ= ≥ = . Nếu ( ) ( )3 2f y f yρ ρ= thì từ (2.14) suy ra 3yρ là vectơ chấp nhận được của bài toán: { }2min ( ) :f x x ρ∈∆ . (2.15) 26 với hàm mục tiêu có giá trị tối ưu ( )2 2q f yρ ρ= , mà ( ) ( )3 2f y f yρ ρ= nên 3yρ cũng là nghiệm của bài toán (2.15). Mặt khác, 3 2 0 0y x y xρ ρ− < − . Suy ra, 2yρ không phải là nghiệm của bài toán (2.15) với khoảng cách tới 0x là nhỏ nhất, điều này mâu thuẫn với sự tồn tại của 2 yρ . Do đó, ( ) ( )3 2f y f yρ ρ> . Ta lại có, 2 0 3y xρ ρ− = nên 2yρ là vectơ chấp nhận được của bài toán { }3min ( ) :f x x ρ∈∆ . Từ bất đẳng thức ( ) ( )3 2f y f yρ ρ> dẫn đến mâu thuẫn với sự kiện 3 yρ là nghiệm tối ưu của bài toán. Do đó, trường hợp θ = −∞ không xảy ra. Vậy, bài toán (2.1) có nghiệm.  Hệ quả 2.1 Giả sử D là ma trận nửa xác định dương thì bài toán (2.1) có nghiệm khi và chỉ khi ( , )A b∆ ≠ ∅ và thỏa điều kiện: ( ) ( ), , 0, 0, 0 0Tn n Tv x Av v Dv Ax Dx c v∈ ∈ ≥ = ≥ ⇒ + ≥  Chứng minh Ta có: D là ma trận nửa xác định dương, tức là 0,T nv Dv v≥ ∀ ∈ . Suy ra, điều kiện ii) của định lý Eaves được thỏa mãn. Do đó, áp dụng định lý Eaves ta có điều phải chứng minh.  Hệ quả 2.2 Nếu D là ma trận xác định dương thì bài toán (2.1) có nghiệm khi và chỉ khi ( , )A b∆ ≠ ∅ . Chứng minh Ta có: D là ma trận xác định dương suy ra điều kiện ii) của định lý Eaves được thỏa mãn. Hơn nữa, nếu 0Tv Dv = thì 0v = . Suy ra, điều kiện iii) cũng được thỏa mãn. Áp dụng định lý Eaves ta có điều phải chứng minh.  Hệ quả 2.3 Cho , , ,n n n n n mSD A c b × ×∈ ∈ ∈ ∈    . Khi đó, bài toán quy hoạch toàn phương: 1min : , , 0 2 T T nx Dx c x x Ax b x + ∈ ≥ ≥     (2.16) có nghiệm nếu và chỉ nếu ba điều kiện sau được thỏa mãn: 27 i) Tập ràng buộc { }, , 0nx Ax b x∈ ≥ ≥ khác rỗng. ii) Nếu , 0, 0nv Av v∈ ≥ ≥ thì 0Tv Dv ≥ . iii) Nếu nv∈ và nx∈ sao cho 0, 0, 0, , 0TAv v v Dv Ax b x≥ ≥ = ≥ ≥ thì ( ) 0TDx c v+ ≥ . Chứng minh Đặt ' , ' 0 A b A b E     = =        trong đó, E là ma trận đơn vị cấp n n× và 0 là vectơ không trong n . Khi đó, ( ) ( )' , 'm n n m nA b+ × +∈ ∈  và bài toán (2.16) được viết lại dưới dạng: 1min : , ' ' 2 T T nx Dx c x x A x b + ∈ ≥     Áp dụng định lý Eaves ta có điều phải chứng minh.  Hệ quả 2.4 Cho , , , , ,n n m n s n n m sSD A C c b d × × ×∈ ∈ ∈ ∈ ∈ ∈      . Khi đó, bài toán quy hoạch toàn phương: 1min : , , 2 T T nx Dx c x x Ax b Cx d + ∈ ≥ =     (2.17) có nghiệm nếu và chỉ nếu ba điều kiện sau được thỏa mãn: i) Tập ràng buộc { }, ,nx Ax b Cx d∈ ≥ = khác rỗng. ii) Nếu , 0, 0nv Av Cv∈ ≥ = thì 0Tv Dv ≥ . iii) Nếu nv∈ và nx∈ sao cho 0, 0, 0, ,TAv Cv v Dv Ax b Cx d≥ = = ≥ = thì ( ) 0TDx c v+ ≥ . Chứng minh Đặt : ' , ' A b A bC d C d        = =       − −    . Khi đó, ( 2 ) ( 2 )' , 'm s n m sA b+ × +∈ ∈  và bài toán (2.17) được viết lại dưới dạng: 28 1min : , ' ' 2 T T nx Dx c x x A x b + ∈ ≥     Áp dụng định lý Eaves ta có điều phải chứng minh.  2.2. Tính chất tập nghiệm của bài toán quy hoạch toàn phương Xét bài toán quy hoạch toàn phương: 1( ) min ( ) : , , 2 T T nP f x x Dx c x x Ax b Cx d = + ∈ ≥ =     trong đó , , , ,n n m n s n m sSD A C b d × × ×∈ ∈ ∈ ∈ ∈     . Đặt: { } { } { }: Ax , , 1,..., , 1,...,nx b Cx d I m J s∆ = ∈ ≥ = = = Ký hiệu: ( )Sol P là tập các nghiệm của bài toán quy hoạch toàn phương (P). 2.2.1. Tính bị chặn của tập nghiệm Gọi 0( )Sol P là tập nghiệm của bài toán quy hoạch toàn phương thuần nhất liên kết với bài toán (P): 0 1( ) min : , 0, 0 2 T nP v Dv v Av Cv ∈ ≥ =     Định nghĩa: Nửa đường thẳng { }: 0w x tv t= + ≥ trong đó: nx ∈ , { }\ 0nv ∈ được gọi là nghiệm tia của bài toán (P) nếu nó là tập con của ( )Sol P . Định lý 2.3. Tập nghiệm ( )Sol P không bị chặn nếu và chỉ nếu (P) có nghiệm tia. Hơn nữa, điều kiện cần và đủ để ( )Sol P không bị chặn là tồn tại ( )x Sol P∈ và { }0( ) \ 0v Sol P∈ sao cho: ( ) 0 TDx c v+ = . (2.18) Chứng minh Giả sử ( )Sol P không bị chặn. Suy ra, tồn tại dãy { }kx trong ( )Sol P sao cho kx →+∞ khi k →+∞ . Không mất tính tổng quát ta giả sử 0kx ≠ với mọi k và k k x v x → với 1v = . Ta sẽ chứng minh 0( )v Sol P∈ . 29 Vì ( )kx Sol P∈ nên ,k kAx b Cx d≥ = . Suy ra: , k k k k k k x b x dA C x x x x ≥ = . Cho k →+∞ ta được 0, 0Av Cv≥ = . Do đó, v là vectơ chấp nhận được của (P0). Mặt khác, ( )Sol P ≠ ∅ theo định lý Eaves ta có, 0Tv Dv ≥ với mọi nv∈ thỏa mãn 0, 0Av Cv≥ = . Do đó, 0Tv Dv ≥ . Cố định xˆ∈∆ . Vì ( )kx Sol P∈ nên ( ) ( )1 ˆ ,2 Tk k T kx Dx c x f x k+ ≤ ∀ ∈ . Chia hai vế của bất đẳng thức cho 2kx và cho k →+∞ ta được, 0Tv Dv ≤ . Suy ra, 0Tv Dv = . Lấy bất kỳ nv∈ là vectơ chấp nhận được của (P0), ta có 0, 0Av Cv≥ = . Từ đó suy ra, 0Tv Dv ≥ . Do đó, ,T T nv Dv v Dv v≤ ∀ ∈ , v thuộc miền ràng buộc của (P0). Vậy, { }0( ) \ 0v Sol P∈ . Bây giờ ta cần chứng minh tồn tại ( )x Sol P∈ thỏa mãn (2.18). Vì ,kAx b k≥ ∀ ∈ lý luận tương tự như trong chứng minh định lý (2.1) ta có dãy con { } { }'k k⊂ sao cho với mỗi i I∈ thì giới hạn ' ' lim kik A x→∞ tồn tại (giới hạn này có thể bằng +∞ ). Ta có: ' ' ' ' lim ( ) lim ( ) k i ik k jk A x b i I C x d j J →∞ →∞ ≥ ∀ ∈ = ∀ ∈ Không mất tính tổng quát ta có thể giả sử { } { }'k k≡ . Đặt: { }0 : lim ki ikI i I A x b→∞= ∈ = và { }1 : lim ki ikI i I A x b→∞= ∈ > . Khi đó, tồn tại 00,kε > ∈ sao cho: ' 0( , ) k i iA x b i I k kε≥ + ∀ ∈ ∀ ≥ . Ta có: 0lim lim 0 ( ) k i i k kk k x biAv A i M x x→+∞ →+∞ = = = ∀ ∈ và 0lim lim 0 ( ) k i i k kk k x biAv A i M x x ε →+∞ →+∞ + = ≥ = ∀ ∈ . 30 Đặt ( )k kx t x tv= − trong đó, 00,t k k> ≥ . Ta có: 0( ) ( ) k k k i i i i iA x t A x tAv A x b i I= − = ≥ ∀ ∈ 1( ) ( ) k k i i i i iA x t A x tAv b tAv i Iε= − ≥ + − ∀ ∈ Cố định 0k k≥ . Từ các bất đẳng thức trên suy ra tồn tại 0δ > sao cho, với mỗi ( )0,t δ∈ ta có: ( )0 1( )ki iA x t b i I I≥ ∀ ∈ ∪ . Hiển nhiên, ( ) ,kj jC x t d j J= ∀ ∈ . Suy ra, ( )kx t ∈∆ với mọi ( )0,t δ∈ . Ta có: ( ) ( ) ( ) ( ) ( ) ( ) 0 ( ) 1 ( ) ( ) ( ) 2 k k T Tk k k k k k k f x t f x x t x D x t x Dx c x t x ≤ − = − − + + − ( )1 02 TT kv Dv Dx c v⇒ − + + ≤ Kết hợp với 0Tv Dv = ta được: ( ) 0TkDx c v+ ≤ . Mặt khác, áp dụng kết quả iii) của hệ quả (2.4) ta được ( ) 0TkDx c v+ ≥ . Suy ra, ( ) 0TkDx c v+ = . Chọn kx x= ta có được phương trình (2.18). Ngược lại, giả sử tồn tại ( )x Sol P∈ và { }0( ) \ 0v Sol P∈ sao cho (2.18) được thỏa mãn. Ta cần chứng minh, bài toán có nghiệm tia. Thật vậy: Đặt { }: : 0w x tv t= + ≥ . Với mỗi 0t > , vì ( )x Sol P∈ và 0( )v Sol P∈ nên: ( ) ( ) A x tv Ax tAv b C x tv Cx tCv d + = + ≥ + = + = Do đó, x tv+ ∈∆ . Vì 0( )v Sol P∈ và 0 là vectơ chấp nhận được của bài toán (P0) ta có 0Tv Dv ≤ . Nếu 0Tv Dv < thì dẫn đến mâu thuẫn với kết quả của hệ quả (2.4). Suy ra, 0Tv Dv = . Kết hợp với điều kiện (2.18) ta được: ( ) ( ) ( ) ( ) ( ) 2 1 2 1 1 ( ). 2 2 T T TT T T f x tv x tv D x tv c x tv x Dx c x t Dx c v t v Dv f x + = + + + +  = + + + + =    31 Vì ( )x Sol P∈ nên ( )x tv Sol P+ ∈ với mọi 0t ≥ . Như vậy, ta đã chứng minh được nếu ( )Sol P không bị chặn thì tồn tại ( )x Sol P∈ và { }0( ) \ 0v Sol P∈ thỏa (2.18) và { }: 0w x tv t= + ≥ là nghiệm tia của (P). Hiển nhiên, nếu bài toán (P) có nghiệm tia thì ( )Sol P không bị chặn.  Từ định lý trên, ta trực tiếp có các kết quả sau: Hệ quả 2.5 Nếu tập nghiệm 0( )Sol P là rỗng hoặc chỉ có một nghiệm là 0 với bất kỳ ( , , ) n m sc b d ∈ × ×   thì tập nghiệm ( )Sol P bị chặn. Trường hợp, 0( )Sol P có chứa phần tử khác 0 và nếu: ( ) { }00, ( ), ( ) \ 0 TDx c v x Sol P v Sol P+ > ∀ ∈ ∀ ∈ thì tập nghiệm ( )Sol P bị chặn. 2.2.2. Tính đóng của tập nghiệm Định lý 2.4 Tập nghiệm ( )Sol P của bài toán quy hoạch toàn phương là tập đóng. Chứng minh Ta có: { }( ) : ( ) ( )Sol P x f x v P= ∈∆ = trong đó, { }( ) inf ( ) :v P f x x= ∈∆ . • Nếu ( )v P là giá trị hữu hạn, mà ∆ là tập đóng, f là hàm liên tục nên ( )Sol P là tập đóng. • Nếu ( )v P = +∞ thì ∆ =∅ . Suy ra, ( )Sol P = ∅ nên ( )Sol P đóng. • Nếu ( )v P = −∞ thì hiển nhiên ( )Sol P = ∅ nên là tập đóng.  Nhận xét: Tập nghiệm cực tiểu địa phương ( ( )loc P ) của bài toán quy hoạch toàn phương có thể không đóng. Ví dụ: Xét bài toán: { }2 22 1 2 1 2 1 2min ( ) : ( , ) , 0, 0 .f x x x x x x x x x= − + = ∈ ≥ ≥ (P1) Ta có: { }1 1 1 2 1 2( ) ; ( ) ( , ) : 0, 0Sol P loc P x x x x x= ∅ = = > = . Rõ ràng, 1( )Sol P là tập đóng nhưng 1( )loc P là tập không đóng. 32 2.2.3. Tính hữu hạn của tập nghiệm Định lý 2.5 i) Nếu D là ma trận xác định dương và ∆ khác rỗng thì (P) có nghiệm duy nhất. Khi đó, tập ( ) ( )Sol P loc P= . ii) Nếu D là ma trận xác định âm thì mỗi nghiệm cực tiểu địa phương của (P) (nếu có) là một điểm cực biên của ∆ . Trong trường hợp này, ( ) ( )Sol P loc P extr⊂ ⊂ ∆ . Khi đó, số nghiệm của bài toán (P) luôn nhỏ hơn số điểm cực biên của ∆ . iii) Nếu D là ma trận nửa xác định dương thì ( )Sol P là tập lồi đóng. Hơn nữa, nếu D là ma trận nửa xác định dương và ( )Sol P là hữu hạn thì ( )Sol P là tập rỗng hoặc ( )Sol P chỉ có một phần tử. Chứng minh i) Giả sử D là ma trận đối xứng xác định dương và { }: : ,nx Ax b Cx d∆ = ∈ ≥ = khác rỗng. Đặt { }: inf : , 1 0T nv Dv v vξ = ∈ = > . Suy ra: 2 ,T nx Dx x xξ≥ ∀ ∈ . Cố định 0x ∈∆ , ta có: ( ) ( ) ( ) ( )0 0 0 0 0 20 0 0 1( ) ( ) 2 1 . . 2 T T f x f x x x D x x Dx c x x x x Dx c x xξ − = − − + + − ≥ − − + − Rõ ràng, vế trái của bất đẳng thức trên dần đến +∞ khi 0x x− → +∞ . Do đó, tồn tại 0γ > sao cho ( )0 0( ) ( ) 1, \ ,f x f x x B x γ− ≥ ∀ ∈∆ . Suy ra, bài toán (P) không thể có nghiệm trong ( )0\ ,B x γ∆ . Mặt khác, ( )0 ,B x γ∆∩ ≠ ∅ nên bài toán ( ){ }0min ( ) : ,f x x B x γ∈∆∩ có nghiệm x . Vì (P) không thể có nghiệm trong ( )0\ ,B x γ∆ nên x cũng là nghiệm của bài toán (P). Ta chứng minh tính duy nhất của nghiệm