Tài liệu Khoá luận tốt nghiệp Bài toán con miền tin cậy với ràng buộc bất đẳng thức tuyến tính

TRƯ Ờ N G ĐẠI H Ọ C s ư PH Ạ M HÀ N Ộ I 2 KHOA TOÁN NGUYỄN THỊ TOÁN BÀI TOÁN CON MIỀN TIN CẬY VỚI RÀNG BUỘC BẤT ĐẲNG THỨC TUYẾN TÍNH K HÓA LUẬN T Ố T N G H IỆ P Đ ẠI H Ọ C C huyên n g àn h : G iải tích Người hướng dẫn khoa học: ThS. HOÀNG NGỌC TUẤN LỜI CẢM ƠN Trước khi trình bày nội dung chính của bài khóa luận, em xin bày tỏ lòng biết ơn sâu sắc tới Thạc sỹ Hoàng Ngọc Tuấn người đã tận tình hướng dẫn để em có thể hoàn thành khóa luận này. Em cũng xin bày tỏ lòng biết ơn chân thành tới toàn thể các thầy cô giáo trong khoa Toán, Trường Đại học Sư phạm Hà Nội 2 đã dạy bảo em tận tình trong suốt quá trình học tập tại khoa. Nhân dịp này em cũng xin được gửi lời cảm ơn chân thành tới gia đình, bạn bè đã luôn bên em, động viên, giúp đỡ em trong suốt quá trình học tập và thực hiện khóa luận này. Xuân Hòa, tháng 05 năm 2015 Sinh viên Nguyễn T hị Toán LỜI CAM ĐOAN Em xin cam đoan khóa luận này là công trình nghiên cứu của riêng em. Trong khi nghiên cứu em đã kế thừa những thành quả nghiên cứu của các nhà khoa học và nghiên cứu với sự trân trọng và biết ơn. Những kết quả nêu trong khóa luận chưa được công bố trên bất kì công trình nào khác. Xuân Hòa, tháng 05 năm 2015 Sinh viên N guyễn T hi Toán Mục lục Lồi M ở Đ ầu .. 2 C hương 1. Cơ sở lí thuyết 4 1.1. Giói thiệu chung 4 1.2. Tính lồi ẩn của m iền tin cậy m ỗ rộng 5 1.3. Sự nới lỏng SD P chính xác 10 1.4. Tối ư u to àn cục và đối ngẫu m ạnh 16 C hương 2. ứ n g dụng 24 2.1. ứ n g d ụ n g vào tối ư u vững 24 2 . 1 . 1 . Bình phương tối thiểu vững 2 . 1 .2 . Bài toán quy hoạch nón bậc hai vững 2.2. M ở rộ n g và nghiên cứ u thêm 27 29 32 K ết lu ận 36 Tài liệu th a m khảo 37 1 L Ờ I M Ở ĐẦU 1.Lí do chọn đề tài Ngày nay, bài toán con miền tin cậy với ràng buộc bất đẳng thức tuyến tính đã được quan tâm nghiên cứu rất nhiều cả về lý thuyết lẫn ứng dụng trong thực tiễn. Mô hình bài toán này được phát triển mở rộng từ bài toán miền tin cậy cổ điển. Bài toán miền tin cậy, tìm cực tiểu của hàm toàn phương không lồi trên một hình cầu, là bài toán con quan trọng trong phương pháp miền tin cậy để giải bài toán tối ưu phi tuyến. Nó có được nhiều tính chất quan trọng ví dụ như sự nới lỏng quy hoạch tuyến tính nửa xác định (sự nới lỏng SDP) chính xác và đối ngẫu mạnh. Với việc chọn đề tài này em mong muốn sẽ góp phần làm rõ tính chất và ứng dụng của bài toán con miền tin cậy với ràng buộc bất đẳng thức tuyến tính. 2. M ục đích nghiên cứu Mục đích của bài khóa luận nhằm trình bày hai mặt mạnh và hữu ích của bài toán miền tin cậy cổ điển tiếp tục được thỏa mãn cho bài toán miền tin cậy mở rộng với ràng buộc bất đẳng thức tuyến tính dưới một điều kiện số chiều mới. Đầu tiên, chúng ta thiết lập rằng lớp của bài toán miền tin cậy mở rộng có sự nới lỏng SDP chính xác là thỏa mãn mà không cần ràng buộc tiêu chuẩn Slater. Thứ hai, chúng ta chỉ ra rằng điều kiện số chiều cùng với điều kiện Slater đảm bảo rằng một tập hợp của các nhân tử Lagrange bậc một và bậc hai kết hợp là cần và đủ cho tối ưu toàn cục của bài toán miền tin cậy mở rộng và cho đối ngẫu mạnh. Cuối cùng, chúng ta chỉ ra rằng điều kiện số chiều là dễ dàng thỏa mãn cho mô hình miền tin cậy mở rộng sinh ra từ sự sửa đổi của bài toán bình phương tối thiểu vững LSP cũng như bài toán mô hình quy hoạch nón bậc hai vững. 3. P hư ơng p h áp nghiên cứu Nghiên cứu nhằm đưa ra nội dung và tìm hiểu rõ hơn về bài toán con miền tin cậy với ràng buộc bất đẳng thức tuyến tính. 4. P h ạm vi nghiên cứu Do thời gian không nhiều nên bài khóa luận chỉ tìm hiểu được một số điều về bài toán con miền tin cậy với ràng buộc bất đẳng thức tuyến tính. 5. Bố cục đề tài Bố cục của bài khóa luận bao gồm hai chương • Chương 1 của khóa luận trình bày tóm tắt về cd sở lí thuyết bao gồm: tính lồi ẩn, sự nới lỏng SDP chính xác, tính tối ưu toàn cục và đối ngẫu mạnh của bài toán con miền tin cậy với ràng buộc bất đẳng thức tuyến tính và minh họa chúng bằng một số ví dụ. 2 • Chương hai của khóa luận tập trung trình bày ứng dụng của bài toán con miền tin cậy với ràng buộc bất đẳng thức tuyến tính. Đăc biệt chú trọng đến ứng dụng vào tối ưu vững của bài toán bình phương tối thiểu cũng như bài toán mô hình quy hoạch nón bậc hai. Do thời gian thực hiện đề tài không nhiều, kiến thức còn hạn chế nên khóa luận không tránh khỏi những sai sót. Tác giả mong nhận được sự góp ý và những ý kiến phản biện của quý thầy cô và bạn đọc. Xin chân thành cảm ơn! 3 Chương 1 Cơ sỏ lí thuyết 1.1. Giới thiệu chung Xét bài toán mô hình miền tin cậy mỏ rộng với ràng buộc bất đẳng thức tuyến tính (p) min xTAx + aTX xeM " thỏa mãn \\x —JCo112 < Oí, bỊX < /3/, ỉ — 1 , . . . ,m, trong đó A là một ma trận đối xứng cấp ( n x n ) , a , bị, JC() G M" và a , Pi e R , a > 0, ỉ' = 1 ,..., m. Bài toán mô hình của dạng này xuất phát từ việc áp dụng phương pháp miền tin cậy đối với nghiệm bài toán tối ưu ràng buộc, ví dụ như bài toán quy hoạch phi tuyến với ràng buộc bất đẳng thức tuyến tính, bài toán tối ưu phi tuyến với các biến rời rạc [ 1 ], và bài toán tối ưu vững dưới chuẩn ma trận hoặc tính bất định đa diện [4]. Trong trường hợp đặc biệt của (P) trong đó (bị, Pi) — (0, 0), nó là mô hình miền tin cậy nổi tiếng, và được nghiên cứu rộng rãi từ lý thuyết đến thuật toán. Bài toán miền tin cậy cổ điển có được sự nới lỏng quy hoạch nửa xác định (sự nới lỏng SDP) chính xác và thừa nhận đối ngẫu mạnh. Hơn nữa, nghiệm của nó có thể tìm bằng cách giải một hệ Lagrangian đối ngẫu. Thật không may, những kết quả này, nói chung, không còn đúng với mô hình miền tin cậy mở rộng (P) của chúng ta. Thật vậy, ngay trong trường hợp đơn giản nhất của (P) với ràng buộc bất đẳng thức 4 tuyến tính duy nhất, đã được chỉ ra rằng sự nới lỏng SDP là không chính xác [2]. Tuy nhiên, trong trường hợp cho ràng buộc bất đẳng thức duy nhất, đối ngẫu mạnh và sự nới lỏng SDP chính xác thỏa mãn dưới một điều kiện số chiều. 1.2. Tính lồi ẩn của miền tin cậy mỏ rộng Trong phần này, chúng ta nhận được tính chất về tính lồi ẩn quan trọng của hệ toàn phương miền tin cậy mở rộng cái mà giữ vai trò quan trọng trong nghiên cứu của chúng ta về sau về sự nới lỏng chính xác và đối ngẫu mạnh. Chúng ta bắt đầu bằng cách đặt các kí hiệu và định nghĩa sẽ được sử dụng về sau trong bài khóa luận. Đường thẳng thực được kí hiệu bởi M và không gian Euclicle thực n chiều được kí hiệu là M'2. Tập tất cả các vec-tơ không âm của R n được kí hiệu bởi R n + . Không gian tất cả ma trận thực đối xứng cấp (n X n) được kí hiệu là s nxn. M a trận đơn vị cấp (n X rì) được kí hiệu bởi In. Kí hiệu A y B có nghĩa là ma trận A —B là nửa xác định dương. Tuy nhiên, kí hiệu A y B là xác định dương. Tập bao gồm tất cả các ma trận nửa xác định dương cấp n X n được kí hiệu là S" . Cho A, B e s nxn. Tích trong của A và B được kí hiệu bỏi A •B = ị ị aịjbịj, trong đó dịj là phần tử nằm ỏ dòng i cột j của A và bịj là phần tử nằm ở dòng i cột j của B. Một sự kiện hữu ích về tích trong là A • (xx;7 ) = XTAX với mọi x G K " và A £ S'ỈX'\ Cho một ma trận A G s nxn, đặt Ker(A) := { d G R" : Ad = 0}. Với một không gian con L, người ta sử dụng dim L để kí hiệu số chiều của L. M ệnh đề 1.2.1. Cho f(x) = xTAx + aTx + 7 , go(x) — II* —*o ||2 —OL và gi(x) = b j x — /3/, i = 1 , . . . , ra, A G S'ỈX", a , Xo, bi G R ” VÀ 7 , a , Pi £ R, i = 1 , . . . , m. Khi đó, u ( / , go, g \ , . . . , g m) l à đóng. Chứng minh. C h o ( /, sk0 , s \ ĩ .. . , s kJ e ư ( / , go, g i , . . . ,gm) với ( r \ số, skì : . . . , s i ) ->• 0 , So, Si Bởi định nghĩa, với mọi k, tồn tại X* G M sao cho /(/) < | | / - * o ||2 < a + 4 , b ] x k < /3] + s \ , . . . , b m Txk < Pm +s^ . ( 1 .2 . 1 ) Điều này chứng tỏ rằng ^ bị chặn, và như vậy, bằng cách cho tiến đến dãy con, chúng ta có thê giả thiết rằng xk - ì X. Khi đó, chuyển qua giới hạn q1.2. lị), chúng ta có f ( x ) < r , \\x- x0\\2 < a + So, b]X < Pị + s \ , . . . , b m Tx < p„ + sm. 5 Nghĩa là, (г, 50, S |,...,S W) e ơ ( / , go, g \ , • • • ,8m)-D o vậy, ơ ( / , go, g l , . . . , gm) là đóng. □ Ví dụ một chiều đơn giản sau chứng tỏ rằng tập ơ ( / , go, g \ , . . . , g m), nhìn chung, không là tập lồi. Ví dụ 1.2.1. (Tính không lồi của ơ ( / , go, g i , . . . ,gm)) Đối với (P), cho n = 1, m — 1, f( x ) = x —x2, go(jt) = x 2 — \ v àg i (;t) = —X. Khi đó, f ( x ) = x TAx + атX + r với A = -1, a = 1 và r = 0, g o M = \ \x —*o ||2 —Oí với Xo = 0, a = 1 v àg i (jc) = b \ x —ß\ với b\ — 1 và ßi — 0 . Khi đó, tập ơ ( / , go, g i) không là tập lồi. Đ ể thấy điều này, ta chú ý rằng / ( 0) = 0, go (0) = - 1 vàgi(O ) = O v à / ( l ) = 0, g o (l) = 0 v à g i (1) = - 1 Do vậy, (0, —1,0) G u ( f , go, 8\) và (0, 0, - 1 ) G U ( f , go, g i). Tuy nhiên, trung điểm của chúng (0, —ị , —ị ) ị u ( / , go 5 g I )• Trái lại, tồn tại X G M sao cho 9 ^ 9 1 V 1 X —X < о, X — 1 < ——v à —X < —- . 2 2 Dễ dàng kiểm tra rằng hệ bất phương trình trên vô nghiệm. Đây là một mâu thuẫn, và do đó ( 0 , - ị , - ị ) ệ u ( f , go, gi). Do vậy, ơ ( / , go, g\) là không lồi. Các điều kiện về số chiều sau đóng một vai trò quan trọng trong phần còn lại của bài khóa luận. Nhắc lại rằng với mọi ma trận A £ s n, Ằmin(A) kí hiệu giá trị riêng nhỏ nhất của A. Đ ịnh nghĩa 1.2.1. (Điều kện số chiều) Xét hệ của hàm số f( x ) —XTAx + aTx + 7 , go(;t) = ||jt —xo ||2 —Of5 8i(x) —b ] X —ßi, i = 1 ... ,w, trong đó A G s nxn, a , Xo, bi € M" rà 7 , a , ßi £ R, i = 1 ,... ,ra. Cho s là số chiều của không gian con sinh bởi Khi đỏ, chúng ta nói rằng điều kiện số chiều thỏa mãn hệ khi dỉmKer(A —Xmịn(A)In) > s + 1. (1.2.2) Nói cách khác, điều kiện số chiều khẳng định rằng bội của giá trị riêng của A nhỏ nhất là s+1. Nhắc lại rằng hàm giá trị tối ưu h: R w+I -> M u {+°°} của (P) được cho bởi h(r,s]ĩ, . . . , s m) min { /(* ) : ||x - * o ||2 < « + r, b j x < ß + Sj, i = 1 ,... ,ra}, (r,s 15, .. . , s m) e D} + 00, nếu trái lại, trong đ ó D = { (r , S \ f, . . . , s m) : I|jc — Xo112 < ОС+ г, b j x < ßi + Si , đ ố i với J c G l " } . 6 Đ ịnh lý 1.2.1. [Đều kiện số chiều dẫn tới tính lồi ẩn]. Cho f( x) — X T Ax + атX + 7 , go w = ||x —*o ||2 —a và giịx) = b f x —ßi, i — 1 ... ,ra, A G s nxn, a, X(), bị € шп và Ỵ, Д- € м , i = 1 ,..., т. Giả sử rằng điều kiện số chiều ị 1.2.2 ) là thỏa mãn. ОС, Khi đó, u ( / , go, g i , . . . , g m) := { (/(* ), g o W , gi (■*)>• ■■>£«(*)) : XG Mn} + M++2 là một tập lồi. Chứng minh. Đầu tiên chúng ta chú ý rằng, nếu A là nửa xác định dương, thì / , gi, i = 0 , 1 ,. .. , m là các hàm lồi. Do vậy, trong trường hợp này Ư ( / , go, g 1 , . . . , gm) luôn là lồi. Vì vậy, chúng ta có thể giả sử rằng A không là nửa xác định dương và do đó Ằmin(A) < 0. [U (/, go, g i , . . . , g w)] = epỉh. Cho D = {(r, : | | x - * o ||2 < « + r, b j X < ßi + 5/} với X e Mn}. Rõ ràng, D là một tập lồi. Khi đó, theo định nghĩa, chúng ta có u ( / , go, g i , . . . ,gm) = epih. [Tính lồi của h àm giá tri h]. Đ ể thấy điều này, ta khẳng định rằng, với mỗi (r, S\, . . . , sm) G D , bài toán sự cực tiểu hóa min {/(*) - xmịn(A) 11* - Xo112 : I\x - *0112 < « + r, bỊX < ßi + Si} vCĨữn đạt cực tiểu tại một số I G M" với I|jt —X()| |2 = a + r và b j X < ßi + Sị. Thừa nhận điều này, chúng ta có m in { f ( x ) л-еК" = > Ằnũn { A ) I \ x - Xo 112 : I \ x - Xo 112 < a + r , b j X < ß i + S i } f( x ) - Ằnĩin( A ) { a ^ r ) mị n{ f(x ) : | | x - x 0||2 < a + r, bỊX < ß + s i} - X min(A)(a + r) xeRn — m in {f ( x ) —Ằmin(Л) ( a + r) : I\x —X()112 < а + r, bỊx < ß + Si} xeRn > m ì n{ f(x ) - Ảmin(A)ịịx - Xị)\\2 : Цх-X o ll 2 < a + r, b J x < ß i + Si}, xeRn trong đó bất đẳng thức cuối suy ra bởi Ằ min (A) < 0 . Điều này dẫn tới min ị f ( x ) : I\x —Xo 112 < oc + r, b j X < ß + Si, i = 1....... m} xeM " = m in{ f ( x ) ~ Xmỉn(A)I|x —* 0112 : l k - ^ o ||2 < « + /■, b f x < Д- + 5,-} JCGM" “I“ Л min ) ( Oí -|- r ) . 7 Chú ý rằng F(x) := f( x ) - hùn (A) I\x - Xo 112 — X (A Ằmỉ/7 -I- (ứ - ị - 2 ằot/jị ( A ) x o ) Ằmỉ/7( A ) I Ị.XOỊỊ ) là một hàm lồi, và do vậy, (r, 5i ,.. . , s m) I—y minxelK« { F (x ): \\x —X()||2 < a + r, b j x < pi + .V,-} cũng là lồi. Suy ra rằng (r, S\, . . . , sm) I-» min { f ( x ) : I\x —Xo 112 < a + r, bỊX < p + 51/, ỉ' = 1 ,..., m} xeRn là lồi. Do đó, h là lồi, và như vậy, u ( / , go, g b • • • ì8m) = epi h là lồi. [Cực tiểu đ ạ t được trê n hìn h cầu]. Chúng ta tiến hành chứng minh theo p h ư ơ n g p h á p p h ả n c h ứ n g v à g i ả s ử r ằ n g m ọ i đ i ể m c ự c t i ể u X* c ủ a m in {F(x) : I\x —X()112 < a + r, b j X < pị + Sj} thỏa mãn Iịx* —XQ112 < a + r và b j X* < /3; + Sị. Ta chú ý rằng tồn tại V € R n\{0} sao cho (1.2.3) [Trái lại, ( n - l , b-}-) n Ker(A —7imin(Ạ)In) — {0}. Nhắc lại rằng điều kiện số chiều của chúng ta là dimKer(A —Xmin(Á)In) > 5 + 1, trong đó s là số chiều của không gian con sinh bởi {^1 ,.. n+ 1= (5 + 1) + (72 Khi đó, từ định lý số chiều suy ra - s) < dimKer [A —Xmin [A)Ịn) + dir = dim b ị n Ker(A - Xmịn(A)In) Ker(A - Ằmin(A)In) + f i- điều này là không thể và do đó (|l.2.3|) là đúng], c ố định bất kì điểm cực tiểu X* của min^ỊK» {F(x) : I\x —JC0I|2 < Oí + r, b Ị x < Pi + 5/}. Bây giờ, ta xét hai trường hợp: Trường hơp 1, (a + 2Xmin(A)xq)t v — 0; Trường hơp 2, (a + 2Xmin(A)xo)r V Ỷ 0Giả sử trường hợp 1 đúng, tức là, (a + 2Ằmin(A)xo)TV = 0. Xét x(ỉ) = X* + ỉv. Vì I\x* —Xo 112 < Cí + r nên tồn tại to > 0 sao cho I\x(to) —JCo112 = Oí + r. Chú ý rằng 8 bỊx(to) = b Ị (x* + tov) = bỊX* < Pi + Si và F(x(to)) = (x* + t 0v)T( A - Ả min(A)ỉn)(x* + t 0v) + (a 2 Ảmj „(A)xo)T (x* + ?o v) + ( y — Xmịn (A)|ỊxoỊỊ2) = (x*)T (A Ằmjn(A)ỉn)x* + (a + 2Ằmịn(A)xo)TX* + ( 7 —Amj„(A)ỊỊA:o||2) = F(x')Điều này mâu thuẫn với giả sử của chúng ta rằng X* là điểm cực tiểu bất kì của minxGK» (F(jc) : \\x —xo||2 < a + r, bjX < Pi + Sị} thỏa mãn \\x* —X()||2 < a + r. Giả sử trường hợp 2 đúng, tức là, (a + 2Ằnìin(A)xo)TV Ỷ 0- Bởi phép thế V với -V n ế u c ầ n t h i ế t , c h ú n g t a c ó t h ể g i ả s ử m à k h ô n g l à m m ấ t t í n h t ổ n g q u á t r ằ n g (ạ + 2Xmin(A)TX())TV < 0. VI I|jc* —JC()112 < a + r tồn tại to > 0 sao cho \\x(t) — * 0 112 < a + r với mọi t G (0, í()]. Chú ý rằng bjx(to) — b j (x* + íov) = b Ị X* < /3/ + Si và F(x(t0)) = (x* + t0v)T(A - Ảmin(A)ĩn)(x* + t0v) + (fl + 2Ảmin(A)xo)T (x* + tov) + ( 7 —Ảmị„ (ẩ )| \xo\|2) < (x*)r (Ấ + Xmị„(A)In)x* + (a + 2 Ằmin ( A ) x o ) TX* + ( 7 — Ằmịn { Á ) \ 1* 0 1|2) = F ự ). □ Như một hệ quá, chúng ta suy ra tính lồi ẩn của hệ miền tin cậy nổi tiếng. Hệ q u ả 1.2.1. Cho f(jt) = XTAx + aTX + 7 và go(x) = I —JCo112 — OIÍ trong đỏ A e S'ỈX", ứ, *0 E K” và 7 , ơ, G M. Khi đó, u ( / , go) là lồi. Chứng minh. Cho bị = 0, ỉ — 1 ,... ,ra (do vậy, số chiều của không gian con sinh bởi bm} bằng 0). Khi đó, điều kiện số chiều (Ị1.2.2Ị) rút gọn đến dimKer(A — Kún{A)In) > 1 là luôn được thỏa mãn. Do vậy, Định líjl.2.ljchứng tỏ u ( / , go) luôn là lồi. □ 9 1.3. Sự nối lỏng SDP chính xác Trong phần này, chúng ta thiết lập rằng sự nới lỏng nửa xác định của bài toán mô hình (P) min (p) xTAx + aTX xeM " thỏa mãn \\x —JCo112 < ct, bT ị X < Pi, i = 1 là chính xác dưới điều kiện số chiều. Quan trọng là, nó thỏa mãn mà không cần điều kiện Slater. Đ ể thiết lập sự nới lỏng SDP của (P), chúng ta xét các ma trận cấp A a/2 (n + 1) X (n + 1) sau đây M = x aT/ 2 0 u _ ( 0 ln [ - 4 \ -Xo , ||xo||2 - a J 0 ‘ \- b ĩ/2 b i/2 \ -p, )' (1.3.4) Chú ý rằn g XTA x + aTX = Tr(M X), \\x—xo ||2 —ơ, = Tr(HoX) v ầ b Ị x —Pi = Tr(HịX), trong đó X = XXT với X = (xT, 1)T. Do vậy, bài toán mô hình có thể được viết tương đương như sau min Tr(MX) Xes'|+I thỏa mãn Tr{H()X) < 0, Tr(HịX) < 0, i = 1 , . . . ,m ^ + 1,/Ỉ + 1 = 1, rank(x) = 1, trong đó rank(X) kí hiệu hạng của ma trận X và Xn+\_n+\ là phần tử của X nằm ở dòng thứ n+1 và cột thứ n +1. Bỏ đi ràng buộc hạng là một, chúng ta thu được sự nới lỏng nửa xác định của (P) như sau (SDRP) m in Tr(MX) Xes'ị+I t h ỏ a m ã n T r ( H QX ) < 0 , Tr(HịX) < 0, i = 11+1,n+ 1 -- 1 • 10 Bài toán sự nới lỏng nửa xác định (SDRP) là một quy hoạch lồi trên một không gian ma trận. Bài toán đối ngẫu lồi có thể được phát biểu như sau (D) max { Ị1 : M + V XịHị y ( ^ ^ ^ Ị ;UeR, Ằ,>0,7=0,...,m \ \ 0 Ị1 ) ) = max min < X T Ax + aTX + Ằ{)(|U —xo ||2 —Oí) + Ỵ X i ( b Ị x - P i ) >, Ằj>0 iGi" [ — J nó trùng với bài toán đối ngẫu Lagrangian của (P). Rõ ràng, (SDRP) và (D) là bài toán quy hoạch tuyến tính nửa xác định và do vậy có thể giải được một cách hữu hiệu, trong khi bài toán (P) ban đầu là một quy hoạch toàn phương không lồi với nhiều ràng buộc, nói chung, là một bài toán tính toán khó. Vì vậy, ta nghiên cứu vấn đề này khi sự nới lỏng nửa xác định là chính xác theo nghĩa rằng min(P)= min(SDRP). Nếu A là nửa xác định dương, thì bài toán (P) là bài toán tối ưu toàn phương lồi đã được biết đến với những tính chất tốt ví dụ như đối ngẫu mạnh và và sự nới lỏng chính xác. Vì thế, từ bây giờ , chúng ta giả thiết rằng A không là nửa xác định dương và do vậy, có ít nhất một giá trị âm. Đ ịnh lý 1.3.1. (Sự nới lỏng SDP chính xấc) Giả sử rằng điều kiện số chiều ị 1.2.2) được thỏa mãn. Khi đó, sự nới lỏng nửa xấc định là chính xấc, tức là, min (P) = min(SDRP). Chứng minh, [min(p) —max(D) < + 00]. Đầu tiên chúng ta chứng minh rằng không có quãng cách đối ngẫu giữa (P) và (D) dưới điều kiện số chiều. Ý nghĩa rằng ta chứng tỏ rằng hàm giá trị tối ưu của (P) v (sq, s \ ,...,s m) in f ị x TA x + JCGR" a T X : \ \ x — Jt()||2 < a + So, b j x < Pi + Si, ỉ = là nửa liên tục dưới và là hàm lồi trên Mm+ 1. Đ ể thấy điều này, chúng ta lưu ý rằng e p i v = u ( f , go, g i , . . . , g m) trong đó f ( x ) = xTAx + aTX, goW = ||* - * o || - « và gi (x) = b j X — /3/, ỉ = 1 ,..., m. Vì vậy, từ Mệnh đề 1.2.1 epi do vậy V là một hàm lồi. Tính liên tục dưới của V V là một tập lồi, và sẽ được suy ra từ Mệnh đề 1.2.1 vì £ /(/, go, g i , . . . , g w) là một tập đóng. Ịmin(P) = min(SDRP)] Bằng cách xây dựng của bài toán sự nới lỏng (SDP) bài toán (SDRP) và đối ngẫu (D), chúng ta dễ dàng thấy rằng min(p) > mỉn(SDRP) > max(D). 11 Như vậy không có quãng cách đối ngẫu giữa (P) và (D), chúng ta rút ra được min(P) = min (SDRP). [C ực tiểu đ ạ t được của (SDRP)]. Bây giờ chúng ta chứng tỏ rằng trong (SDRP) đạt được cực tiểu. Đ ể thấy điều này chúng ta chỉ cần thiết lập tập chấp nhận được của (SDRP) bị chặn. Nếu không, thì tồn tại x k G * = V( Y l / với 1 sao cho ||X*||f := ^ T r ( x kx k) -> + 00, Tr(HiXk) < 0, i = 0,1 trong đó Hj, ỉ — 1 ,... ,m được định nghĩa như trong ( 1.3.4>. Điều này dẫn tới 0 < Tr(Yk) < - | M | 2 + a + 2 ( f ) Tx0 và b Ị y k < ft. Vì x k >: 0, chúng ta có Yk —yk(ỵk)T >: 0. Do vậy, l l / l l 2 = Tr(yk(yk)T) < Tr(Yk) < - | M |2 + a + 2 ( / ) 7*0. Do vậy, ỵk là bị chặn, và do đó Tr(Yk) cũng là một dãy bị chặn. Theo đó, cả Yk và yk đều bị chặn. Điều này kéo theo x k là bị chặn, mâu thuẫn với thực tế rằng xk + 00. □ Cần lưu ý rằng tính lồi của tập u ( / , go ->gI J • • • J gm) giữ một vai trò quan trọng trong việc xây dựng sự nới lỏng SDP chính xác của (P). Tuy nhiên, như chúng ta thấy trong các ví dụ sau đây, tính lồi không suy ra rằng bài toán (P) tương đương với bài toán tối ưu lồi theo nghĩa chúng có cùng tập nghiệm tối ưu. Ví d ụ 1.3.1. Xét f( x ) — X2 , go(x) — X2 — 1 và gi (jt) = —X2 + 1. Ta kiểm tra rằng u ự , go, gì) = { 0 2, X2 - 1 , - x 2 + 1 ) : x e M} = {(z, z - 1 , - z + 1 ) :z > 0}, là đóng và là tập lồi. Nói cách khác, bài toán tối ưu tương ứng min^eK{(x 2 :x2 - ì < 0, —X2 + 1 < 0)} không thể tương đương với bài toán tối ưu lồi vì tập nghiệm của nó là { —1 , 1 } không là tập lồi. Một mặt mạnh hấp dẫn của kết quả sự nới lỏng SDP của chúng ta là sự chính xác của nó độc lập với điều kiện Slater. Ví dụ sau minh họa rằng sự nới lỏng SDP của chúng ta có thể chính xác mà không cần điều kiện Slater. 12 v í d ụ 1.3.2. (Sự nới lỏng SDP chính xác mà không cần điều kiện Slater). Xét bài toán tối ưu toàn phương ba chiều với hai bất đẳng thức tuyến tính (EP) min —xị —x ị —xị + 3x\ + 2x2 + 2x 3 (X| ,X2,X3)gR3 thỏa mãn (xi — 1 )2 + xị + xị < 1 , Xị < 0 , *1 + *2 +*3 < 0. Điều này có thể được viết như bài toán mô hình của chúng ta trong đó A = ( V -\ 0 0 0 -1 0 0 \ , a — (3 ,2 ,2)r , Xo = (1 ,0 ,o )7 , a = 1, b\ — (1 ,0 ,0 )7 , b2 — 0 -I ) (1,1 ,1 ) và = p2 — 0. Rõ ràng, điểm chấp nhận được duy nhất là (0,0,0) và do vậy, min(EP) = 0. Chúng ta cũng chú ý rằng không cần điều kiện Slater. Cho không gian con sinh bởi { b ] , b 2 } có số chiều s = 2. Chúng ta thấy rằng dimKer(A —Ằmin(A)In) = 3 = s + 1. Do vậy, điều kiện số chiều được thỏa mãn. Nói cách khác, sự nới lỏng (SDP) của (EP) được cho bởi (.SDRPg) min Z\ + 3Z4 - Z5 + 2Z7 - Z8 + 2Z9 xeS4 thỏa mãn Z\ - 2^4 + Z5 + Z8 < 0 24 < 0 Z4 + Zl + Z9 < 0 ( Z\ Z2 Z3 Z4 \ Z2 Zỹ Z(y z~ì h0. z 3 z 6 z 8 z9 \Z4 Zi z9 1 / Từ đó Zi = Z2 = = Z9 = 0 là chấp nhận được của (SDRPe),min(SDRPE) < 0. ( Hơn nữa, với mỗi X chấp nhận được, X — Zị z1 ZZ22 Zt, Z2 Z4 Z2 Z5 Z(y Z7 z3 z6 z8 Zg z4 z7 z9 I Z ^4 >- 0, chúng ta có / Zl > 0,Z5 > 0, zs> zl> 0 và 13 Z5 > Z j > 0. (1.3.5) Điều này cho biết rằng -2 z4 < Z\ - 2 z4 + Z5 + Z8 < 0 và do vậy Z4 > 0. Vì Z4 < 0, chúng ta có Z4 — 0 và do vậy z 1 + Zs + Z8 < 0. Do đó, Zị = Z5 — Z8 = 0 và Zi — Z9 — 0. VI vậy, m in (SDRP e ) = 0 = min(EP). Trong phần sau, chúng ta sử dụng bài toán tối ưu toàn phương một chiều đơn giản để chứng tỏ rằng sự nới lỏng SDP có thể không chính xác nếu điều kiện số chiều đầy đủ ( 1 .2 .2 ) của chúng ta không được thỏa mãn. Ví d ụ 1.3.3. (Tầm quan trọng của điều kiện số chiều đầy đủ). Xét bài toán sự cực tiểu hóa { E P ^ m ỉ n ị / i x ) :go(x) < 0, gị(x) < 0}, trong đó f ( x ) = x —x2, go(x) = X2 — g\ (x) — —X, n = 1 v à m = 1. Khi đó, f ( x ) — XTA x - \ - a Tx + r vớ i A = — 1, a = 1 v à r = 0 , g o M và — II* — * o | | 2 - oc v ớ i Xo = 0 , oc = 1 (x) = b \ x —ị3i với b\ = 1 và P\ = 0. Rõ ràng, dimKer{A —Ằmịn(A)In) = 1 < 2 = dim s p a n ị b ị } + 1 . Sự nới lỏng SDP của (EP\ ) được cho bởi (.S D R P e ỉ ) min -Zỉ+Z2 Xes2 thỏa mãn Zi — 1 < 0 —Z2 <0 Rất dễ dàng thấy rằng m in(£'P i) = 0 và min(SDRPE\ ) = —1. Do vậy, sự nới lỏng SDP của (EPị) là không chính xác. Xét bài toán tối ưu toàn phương với một ràng buộc chuẩn và một ràng buộc bất đẳng thức toàn phương hạng một (Po) x TAx + aTX min xeRn thỏam ãn ||x —xo||2 < cc, (bTx ) 2 < r, trong đóẨ G s nxn, a, Xo, b G Oi G M và r > 0. 14 Bài toán mô hình của dạng này xuất phát từ ứng dụng của phương pháp miền tin cậy đối với sự cực tiểu hóa cuả một hàm phi tuyến với ràng buộc gián đoạn. Ví dụ, xét bài toán xấp xỉ miền tin cậy min хежп X Ax + a X thỏa mãn ||jt —JCo112 < а , bTX 6 { 1 , - 1 }. Sự nới lỏng liên tục của bài toán trở thành min xTAx + aTx thỏa mãn I|jc —JCo112 < а , 1 < bTX < 1 , trong đó, lần lượt, tương ứng đến (Pq) với r — 1 . Sự nới lỏng SDP của (ffo) được cho bỏi (SDRPq) min Xes'l+i thỏa mãn Tr(MX) Tr ( HoX) < 0 Tr ( Hj X) < 0, i — 1,2 Xn+l,/2+l trong đó M-LVĨ)' W- V - . ,/!rU w . ", ", \ —b / 2 bT/ 2 - y / r l yfr Bây giờ chúng ta có được kết quả sự nới lỏng SDP chính xác như sau đối với bài toán (Po) dưới điều kiện số chiều. Hệ q u ả 1.3.1. (Mô hình miền tin cậy với ràng buộc hạng một) Giả sử rằng dimKer(A Knin{A)In) > 2. Khi đó, sự nới lỏng nửa xác định là chính xác đối với (Pq), nghĩa là, mỉn(Po) = min(SDRPo). 15 Chứng minh. Chú ý rằng (bTx )2 < r là tương đương với —y / r < bTX < y/r. Trong trường hợp này, điều kiện số chiều của Định lí 1.3.1 quy về giả thiết rằng dimKer(A —Ằmin(A)In) > dim spanịb, —b} + Hệ quả được suy ra từ Định lý 1.3.1 và thực tế rằng không gian con sinh bởi {/?, —b} có số chiều nhỏ hơn hoặc bằng 1 . 1.4. □ Tối ưu toàn cục và đối ngẫu mạnh Trong phần này, chúng tôi trình bày điều kiện cần và đủ để tối ưu toàn cục cho (P) và nhờ đó, đạt được đối ngẫu mạnh giữa (P) và (D) khi điều kiện số chiều được thỏa mãn và điều kiện Slater đúng đối với (P). Đ ỉnh lý 1.4.1. (Điều kiện cần và đủ của bài toán tối ưu toàn cục). Đối với (P), giả sử rằng tồn tại X với I —X()||2 < a và bjX < /3n i — 1 , . . . , m, và giả £ sử rằng điều kiện số chiều trong ị 1.2.2) là thỏa mãn. Cho X* là điểm chấp nhận được của (P). Khi đỏ, X* là điểm cực tiểu toàn cục của (P) khi và chỉ khi tồn tại (A<), X\ , . . . , Xm) G M++ 1 sao cho điều kiện sau thỏa mãn: 2 ((A + ẰqI„)x*) = - ( a + 2 Ả{)(x* - X o ) + HỈL1 W i ) , (Điều kiện KKT) A<)( Il-XT* —-XTo112 —oc) = 0 và Ằị(bjx* — Ị5ị) = 0, ỉ — 1 ,..., ra, (Điều kiện B ổ Sung) 0, A+ (Điều kiện Bậc Hai). Chứng minh. [Điều kiện cần đ ể tối ưu] Cho X* là điểm cực tiểu toàn cục của (P). Khi đó, hệ bất phương trình sau vô nghiệm: I I * - -XoH2 < 0^5 b Ị X < f t , i = Đặc biệt, cho 7 = — 1 , . . . , m , XTA x - \ - a TX < (x * )TA x* + a Tx * . + a TX*), hệ bất phương trình sau cũng vô nghiệm: II*- *o ||2 < OÉ, bjX < Pi, i — 1 ,... ,m, XTAx + aTx + 7 < 0. Khi đó, 0 ị i n t u trong đó Ư ( f , go, g i, •••,£»,) := { ( / 0 ), goO ), gi 16 gmO)) : x e R n} + R n Ị +2 là một tập lồi bởi M ệnh đề 1.2.1 Hơn nữa, vì f , g i là các hàm liên tục , chúng ta thấy rằng { ( /M , goM , ^ i W v ^ m W ) : х е Г } + ш Л 7 = int и ( / , go, cũng là lồi. Bây giờ, bởi định lý tách các tập lồi, tồn tại (jU, Я(), X], . . . Д т ) G М++ 2\{ 0 } sao cho, với mọi i g I " , ịầ (x t A x + атX + 7 ) + Я ()(||х -х о | | 2 - а ) + £ X ị ( b Ị x - ßi) > i= 1 0 . Bởi điều kiện tính chấp nhận được chặt, ta thấy rằng ỊẤ Ỷ 0. Do vậy, với mọi i G l " XTАх + атX + 7 + А()(||л: —-Го112 —Oí) + Xị{bT ị X — ßi) > 0, Í=1 trong đó Ằị — Ỵ , i — 0 , 1 ,. .. , m. Cho X = X*, chúng ta thấy rằng m A<) (I \x* - Xo 112 - a ) + £ Xi (bf X* - ßi) > 0. i—1 Bởi vì X* là điểm chấp nhận được của (P), nên A{)( I\x* —X()112 —a ) = 0 và Aj(bỊX* — ßj) = 0 , i = 1 , . . . , ra. Cho h(x) XTAx + aTx + 7 + я<)( 11л: —*o ||2 — cc) + ỵ^-ị Ằj(bỊx —ßi). Khi đó, ta thấy rằng X* là điểm cực tiểu toàn cục của h, và do vậy Vh(x*) — 0 và v 2h(x*) >: 0. Ta nói rằng, 2(A + Ằị)In)x + ị^ũ 2Ằị)(x —Xo) + ^ Xịb^j — 0 và А + Ằ()In ^ 0. [Điều kiện đ ủ của tối ưu] Ngược lại, nếu điều kiện tối ưu được thỏa mãn, thì ta thấy rằng h(x) := xTAx + атX + Ảị)( I\x —Xo112 — ot) + 1 Я/(bỊX —ßi) với v/z(x*) = 0 và v 2h(x * ) b 0. Do vậy, X* là điểm cực tiểu toàn cục của h, và do đó, với mọi điểm chấp nhận được x G K " của (P), m xTAx + aTx > XTАх + атX + Ả{)(\\x —x 0||2 —Oí) + Xị(bJX —ßi) /= 1 > (x*)TA x * + а тX* +Я()(||х* —л:о112 —Oi) + ^ Ảj(bỊX* — ßi) i= 1 = (x*)r Ax:* + a Tx *, 17