Tài liệu điều kiện tối ưu trong bài toán quy hoạch toàn phương

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI 2 ĐÀM TUẤN ANH ĐIỀU KIỆN TỐI ƢU TRONG BÀI TOÁN QUY HOẠCH TOÀN PHƢƠNG LUẬN VĂN THẠC SĨ TOÁN HỌC HÀ NỘI – 2016 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI 2 ĐÀM TUẤN ANH ĐIỀU KIỆN TỐI ƢU TRONG BÀI TOÁN QUY HOẠCH TOÀN PHƢƠNG Chuyên ngành: Toán giải tích Mã số: 60 46 01 02 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC PGS. TS. NGUYỄN NĂNG TÂM HÀ NỘI – 2016 LỜI CẢM ƠN Luận văn được hoàn thành tại Trường Đại học Sư phạm Hà Nội 2. Tác giả chân thành cảm ơn PGS. TS. Nguyễn Năng Tâm đã tận tình hướng dẫn, tạo điều kiện cho tác giả hoàn thành luận văn Thạc sĩ. Tác giả xin bày tỏ lòng biết ơn các thầy cô giáo và cán bộ công nhân viên của Trường Đại học Sư phạm Hà Nội 2 đã quan tâm giúp đỡ. Tác giả chân thành cảm ơn các thầy cô giáo và các bạn đồng nghiệp đã tạo mọi điều kiện thuận lợi cho tác giả hoàn thành luận văn thạc sĩ. Hà Nội, tháng 12 năm 2016 Tác giả luận văn Đàm Tuấn Anh LỜI CAM ĐOAN Tôi xin cam đoan luận văn này là kết quả nghiên cứu của riêng tôi dưới sự hướng dẫn của PGS TS Nguyễn Năng Tâm. Trong quá trình nghiên cứu và hoàn thành luận văn tôi đã kế thừa những thành quả khoa học của các nhà khoa học và đồng nghiệp với sự trân trọng và biết ơn. Tôi xin cam đoan rằng các thông tin trích dẫn trong luận văn đã được chỉ rõ nguồn gốc. Hà Nội, tháng 12 năm 2016 Tác giả luận văn Đàm Tuấn Anh Mục lục MỞ ĐẦU 5 1 KIẾN THỨC CHUẨN BỊ 7 1.1. Không gian Euclide Rn . . . . . . . . . . . . . . . . . . . 7 1.2. Tập lồi, hàm lồi . . . . . . . . . . . . . . . . . . . . . . . 8 1.3. Bài toán quy hoạch toàn phương . . . . . . . . . . . . . 9 2 ĐIỀU KIỆN TỐI ƯU TRONG BÀI TOÁN QUY HOẠCH TOÀN PHƯƠNG 28 2.1. Điều kiện tối ưu bậc nhất . . . . . . . . . . . . . . . . . . 28 2.2. Điều kiện tối ưu bậc hai . . . . . . . . . . . . . . . . . . 34 KẾT LUẬN 48 TÀI LIỆU THAM KHẢO 49 3 DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT Rn không gian Euclid n chiều. f : X → Rn ánh xạ đi từ X vào Rn int A phần trong của A A bao đóng của A ∇ f (x) gradient của f tại điểm x h., .i tích vô hướng trong Rn k.k chuẩn trong không gian Rn ( x, y) = {λx + (1 − λ) y|λ ∈ (0, 1)} đoạn thẳng mở nối x và y ( x, y) = {λx + (1 − λ) y|λ ∈ [0, 1]} đoạn thẳng đóng nối x và y 4 Mở đầu 1. Lý do chọn đề tài Quy hoạch toàn phương là 1 bộ phận đặc biệt của quy hoạch toán họcvà có nhiều ứng dụng trong lý thuyết cũng như thực tế trong vòng nửa thế kỉ nay, quy hoạch toàn phương được phát triển mạnh mẽ, các nhà toán học nghiên cứu các bài toán quy hoạch ngày một sâu sắc cả về các vấn đề định tính cũng như các thuật toán hữu hiệu để giải các bài toán về máy tính điện tử. Sau khi được học những kiến thức về toán học về toán giải tích với mong muốn tìm hiểu sâu hơn nên tôi đã chọn đề tài "Điều kiện tối ưu trong bài toán qui hoạch toàn phương" để nghiên cứu. 2. Mục đích nghiên cứu Khảo sát điều kiện tối ưu bậc nhất, điều kiện tối ưu bậc hai trong bài toán quy hoạch toàn phương. 5 3. Nhiệm vụ nghiên cứu Nghiên cứu về điều kiện tối ưu trong bài toán quy hoạch toàn phương trong Rn . 4. Đối tượng và phạm vi nghiên nghiên cứu Đề tài chủ yếu tập trung nghiên cứu về bài toán quy hoạch tối ưu và điều kiện tối ưu bậc nhất, bậc hai của bài toán quy hoạch toàn phương. 5. Phương pháp nghiên cứu Tổng hợp, phân tích, hệ thống các kiến thức trong các tài liệu về bài toán quy hoạch phi toàn phương. 6. Giả thuyết khoa học Trình bày bài toán quy hoạch toàn phương từ đó đưa ra điều kiện tối ưu bậc nhất và điều kiện tối ưu bậc hai của bài toán quy hoạch toàn phương. 6 Chương 1 KIẾN THỨC CHUẨN BỊ 1.1. Không gian Euclide Rn Tập hợp R := n n T x = ( x1 , ..., xn ) : x1 , ..., xn ∈ R o với hai phép toán ( x1 , ..., xn )T + (y1 , ..., yn )T = ( x1 + y1 , ..., xn + yn )T T T λ( x1 , ..., xn ) = (λx1 , ..., λxn ) , λ ∈ R lập thành một không gian véc tơ Euclide n− chiều. T Nếu x = ( x1 , ..., xn ) ∈ Rn thì xi gọi là thành phần hoặc tọa độ thứ i của x. Véc tơ không của không gian này gọi là gốc của Rn và được T ký hiệu đơn giản là 0, vậy 0 = (0, ..., 0) . Trong Rn ta định nghĩa tích vô hướng chính tắc h., .i như sau: T T Với ( x1 , ..., xn ) + (y1 , ..., yn ) ∈ Rn ta có n h x, yi = ∑ xi yi . i =1 T Đôi khi ta còn ký hiệu là x T y. Khi đó với mọi x = ( x1 , ..., xn ) ∈ Rn ta 7 định nghĩa k x k := q s h x, x i = n ∑ ( xi ) 2 i =1 và gọi là chuẩn Euclide của véc tơ x. 1.2. Tập lồi, hàm lồi 1.2.1. Tập lồi Định nghĩa 1.2.1. Tập X ⊂ Rn được gọi là tập lồi, nếu x, y ∈ X, ∀λ ∈ [0, 1], ta có λx + (1 − λ) y ∈ X Nếu X là tập lồi và đồng thời là tập đóng (mở) trong Rn thì ta gọi X là tập lồi đóng (tương ứng, mở). Ví dụ 1.2.1. Tập rỗng, hình cầu trong Rn là những tập lồi. Định nghĩa 1.2.2. Tập X ⊂ Rn gọi là tập đa diện lồi nếu X có dạng X = { x : Ax ≤ b}, trong đó A là ma trận cấp m × n và b ∈ Rn . Định nghĩa 1.2.3. Tập K ⊂ Rn gọi là nón nếu với mọi x ∈ K, t ≥ 0 ta có tx ∈ K. Nếu nón K là tập lồi thì K gọi là nón lồi. Định nghĩa 1.2.4. Cho X ⊂ Rn là một tập lồi và f : X → R. Ta nói f là hàm lồi trên X khi và chỉ khi f (λx + (1 − λ) y) ≤ λ f ( x ) + (1 − λ) f (y) , ∀ x, y ∈ X, λ ∈ [0, 1] Ví dụ 1.2.2. a) Hàm hằng f ( x ) = a là một hàm lồi trên R. b) Hàm f ( x ) = x3 là hàm không lồi trên R. 8 1.3. Bài toán quy hoạch toàn phương 1.3.1. Bài toán quy hoạch toàn phương Định nghĩa 1.3.1. Ta nói rằng f : Rn → R là một hàm toàn phương tuyến tính nếu ở đó tồn tại một ma trận D ∈ Rn×n , một véc tơ c ∈ Rn và một số thực α sao cho 1 1 f ( x ) = x T Dx + c T x + α = h x, Dx i + hc, x i + α 2 2 (1.1) với mọi x ∈ Rn .       d11 ...d1n c1 x1   .  .   .  .  Nếu D =   ............. , c =  . , x =  . , thì (1.1) trở dn1 ...dnn cn xn thành ! n 1 n n f (x) = ∑ dij xi x j + ∑ ci xi + α 2 j∑ =1 i =1 i =1
Vì x T Dx = 12 x T D + D T x với mọi x ∈ Rn , nên trong (1.1) chúng ta
1 có thể thay D bởi một ma trận đối xứng D + D T . Vì vậy, chúng 2 ta giả sử rằng ma trận vuông trong biểu diễn của hàm toàn phương tuyến tính là đối xứng. Không gian các ma trận đối xứng n × n được ký hiệu là RnS×n . Định nghĩa 1.3.2. Bài toán ( P) được gọi là một bài toán quy hoạch toán học toàn phương tuyến tính (hoặc quy hoạch toàn phương) nếu f là một hàm toàn phương tuyến tính và ∆ là một tập đa diện lồi. Trong (1.1), nếu D là ma trận không thì f là một hàm afine. Do vậy, lớp các quy hoạch tuyến tính là một lớp con của lớp các quy hoạch toàn phương. Trong trường hợp tổng quát, các quy hoạch toàn phương là các bài toán quy hoạch không lồi. 9 Ví dụ 1.3.1. Bài toán quy hoạch toàn phương sau là không lồi min f ( x ) = x12 − x22 , x ∈ ∆  trong đó ∆ = x = ( x1 , x2 ) ∈ R2 |1 ≤ x1 ≤ 3, 1 ≤ x2 ≤ 3 . Rõ ràng nếu chúng ta bỏ hằng số α trong biểu thức (1.1) của f thì ta không làm thay đổi tập nghiệm của bài toán min { f ( x ) : x ∈ ∆}, trong đó ∆ ⊂ Rn là một tập đa diện lồi. Do đó, thay cho (1.1) chúng ta 1 có dạng đơn giản hơn f ( x ) = x T Dx + c T x của hàm mục tiêu 2 Chúng ta gọi các bài toán quy hoạch toàn phương   1 T x Dx + c T x : x ∈ n , Ax ≥ b , min 2   1 T x Dx + c T x : x ∈ n , Ax ≥ b, x ≥ 0 , min 2   1 T T n min x Dx + c x : x ∈ , Ax ≥ b, Cx = d 2 là dạng chuẩn tắc, dạng chính tắc và dạng tổng quát (tương ứng). Định nghĩa trên của bài toán quy hoạch toàn phương chính tắc là được thừa nhận bởi vì bài toán quy hoạch toàn phương của dạng này có rất nhiều quan hệ với bài toán dạng tuyến tính. Định nghĩa 1.3.3. Một ma trận D ∈ Rn được gọi là xác định dương (xác định âm) nếu v T Dv > 0 (tương ứng v T Dv < 0) với mọi v ∈ Rn \ {0}. Nếu v T Dv ≥ 0 (tương ứng v T Dv ≤ 0) với mọi v ∈ Rn thì D được gọi là nửa xác định dương (tương ứng là nửa xác định âm). 1 Mệnh đề 1.3.1. Cho f ( x ) = x T Dx + c T x + α với D ∈ RnS×n , c ∈ Rn 2 và α ∈ R. Nếu D là ma trận nửa xác định dương thì f là một hàm lồi. Chứng minh. Vì x 7→ c T x + α là một hàm lồi và tổng của hai hàm lồi là một hàm lồi nên để chứng minh f là hàm lồi ta chỉ ra rằng f 1 ( x ) := 10 x T Dx là một hàm lồi. Giả sử D là một ma trận nửa xác định dương. Khi đó, với mọi u ∈ Rn và v ∈ Rn ta có T 0 ≤ (u − v) D (u − v) = u T Du − 2v T Du + v T Dv Từ bất đẳng thức trên suy ra v T Dv ≤ u T Du − 2v T D (u − v) (1.2) Với bất kỳ x ∈ Rn , y ∈ Rn và t ∈ (0, 1) cho trước bất kỳ, chúng ta đặt z = tx + (1 − t) y. Từ (1.2) chúng ta có z T Dz ≤ y T Dy − 2z T D (y − z) z T Dz ≤ x T Dy − 2z T D ( x − z) Vì y − z = t (y − x ) và x − z = (1 − t) ( x − y), từ hai bất đẳng thức cuối chúng ta suy ra rằng (1 − t) zT Dz + tzT Dz ≤ (1 − t) yT Dy + tx T Dx Do đó f 1 (tx + (1 − t) y) = f 1 (z) ≤ t f 1 ( x ) + (1 − t) f (y) Vậy f 1 là một hàm lồi. Nếu D là nửa xác định âm thì hàm f được cho bởi (1.1) là lõm, nghĩa là f (tx + (1 − t) y) = f 1 (z) ≥ t f ( x ) + (1 − t) f (y) với mọi x ∈ Rn , y ∈ Rn và t ∈ (0, 1). Trong trường hợp ma trận D không nửa xác định dương và cũng không nửa xác định âm, chúng ta 1 nói rằng f ( x ) = x T Dx + c T x, ở đây c ∈ Rn là một hàm toàn phương 2 11 tuyến tính không xác định. Bài toán quy hoạch toàn phương với hàm mục tiêu toàn phương tuyến tính không xác định được gọi là quy hoạch toàn phương không xác định. Chú ý. Dễ thấy rằng nếu f được cho bởi công thức (1.1), thì ta có ∇2 f ( x ) = D với mọi x ∈ Rn . Ví dụ 1.3.2. Cho k điểm a1 , a2 , ..., ak trong Rn , chúng ta muốn tìm một điểm x ∈ Rn mà tổng 2 f ( x ) := k x − a1 k + ... + k x − ak k 2 đạt giá trị cực tiểu của nó. Ta thấy rằng k f (x) = ∑ ( x − ai ) T k T ( x − ai ) = kx x − 2 i =1 ∑ ai i =1 !T k x + ∑ aiT ai i =1 là một hàm toàn phương lồi. Ta có x là một nghiệm của bài toán nếu và chỉ nếu ∇ f ( x ) = 0. Vì k ∇ f ( x ) = 2kx − 2 ∑ ai , i =1 chúng ta có thể viết điều kiện 0 = ∇ f ( x ) tương đương với 1 k x = ∑ ai . k i =1 1 k ∑ ai là nghiệm duy nhất của bài toán. Điểm đặc biệt k i =1 x được gọi là barycenter của hệ { a1 , a2 , ..., ak } . 1 1 Đầu tiên, chúng ta định nghĩa z1 = a1 + a2 . Đặt 2 2 Như vậy x = zi = i 1 z i −1 + a i +1 i+1 i+1 với mọi i ≥ 2. 12 Bằng phương pháp quy nạp không khó để chỉ ra rằng x := zk−1 là barycenter của hệ { a1 , a2 , ..., ak }. Thực hiện xây dựng theo thứ tự trọng tâm của một hệ các điểm trong R2 , đó là tiện ích để sử dụng trong dạng véc tơ của công thức xác định zi sau đây: 1 −−−→ z i −1 a i i+1 − → z−− i −1 z i = với mọi i ≥ 2. Ví dụ 1.3.3. Lấy ∆ = { x ∈ Rn : Ax ≥ b, Cx = d}, ở đó A ∈ R m × n, C ∈ Rs×n , b ∈ Rm và d ∈ Rs . (Đẳng thức Cx = d có thể thiếu trong công thức. Tương tự, bất đẳng thức Ax ≥ b cũng có thể thiếu). Lấy αi (i = 1, ..., n) , aei (i = 1, ..., n), β và βe là một họ của 2n + 2 các giá trị thực thỏa mãn các điều kiện n ∑ i =1 a2i n = 1, ∑ aei 2 = 1 (1.3) i =1 Chú ý rằng ( x ∈ Rn : M= n ∑ ai xi + β = 0 ) i =1 và ( e = M x ∈ Rn : n ∑ eai xi + βe = 0 ) i =1 là hai siêu phẳng trong Rn . Tìm x ∈ ∆ sao cho hàm   2 2 e f ( x ) = (dist ( x, M)) − dist x, M , trong đó dist ( x, Ω) = inf {k x − zk : z ∈ Ω} là khoảng cách từ x đến một tập con Ω ⊂ Rn , đạt cực tiểu. Chúng ta có   n    dist ( x, M) =  ∑ αi xi + β  i =1  13 (1.4) Để chứng minh công thức này chúng ta xét quy hoạch toàn phương lồi sau đây n 2 min ϕ (z) = k x − zk : z ∈ M o (1.5) Ta có z = (z1 , ..., zn ) ∈ M là nghiệm của (1.5) nếu và chỉ nếu ở đó tồn tại µ ∈ R sao cho 0 ∈ ∂ϕ (z) + µ (α1 , ..., αn ) . Khi đó ∂ϕ (z) = {∇ ϕ (z)} = {−2 ( x − z)}, kết luận này là đạt được nếu và chỉ nếu 2 ( x − z) = µ (α1 , ..., αn ) . µ Có nghĩa là z = x − α, ở đây α := (α1 , ..., αn ). Khi z ∈ M, chúng ta có 2 µ 0 = hα, zi + β = hα, x i − hα, αi + β. 2 Thế vào (1.3) chúng ta thu được µ = 2 (hα, x i + β). Do đó  µ  2 2 2 (dist ( x, M)) = k x − zk = x − x − α 2  µ 2 = hα, αi = (hα, x i + β)2 . 2 Do đó (1.5) luôn đúng. Tương tự ta có        n   e e dist x, M = ∑ e αi xi + β  .  i =1  Vậy n ∑ αi xi + β f (x) = n = i =1 n ∑∑ j =1 i =1 !2 !2 ∑ eαi xi + βe n − i =1 n αi α j − e αi e α j xi x j + 2 ∑
    2 2 e e βαi − βe αi xi + β − β . i =1 Từ đây chúng ta kết luận rằng f ( x ) là hàm toàn phương tuyến tính; vậy bài toán chúng ta xét ở trên là một bài toán quy hoạch toàn phương ở dạng tổng quát. 14 Dễ dàng chỉ ra như vậy nếu chúng ta chọn    10      01     A= ,b =    −10     0−1 1      −3   −3 1 α = (1, 0) , β = 0, e α = (0, 1) , βe = 0 thì bài toán được thực hiện, ở đây phương trình Cx = d bị khuyết. Trong trường hợp này, chúng ta có M = { x = ( x1 , x2 ) : x1 = 0, x2 ∈ R} , e = { x = ( x1 , x2 ) : x1 ∈ R, x2 = 0} , M   e dist ( x, M) = | x1 | và dist x, M = | x2 | 1.3.2. Định lý về sự tồn tại nghiệm bài toán quy hoạch toàn phương Xét một bài toán quy hoạch toàn phương dạng chuẩn tắc 1 min f ( x ) := x T Dx + C T x với x ∈ Rn , Ax ≥ b 2 (1.6) trong đó D ∈ RnS×n , A ∈ Rm×n , c ∈ Rn và b ∈ Rm Định lý 1.3.1. [10, trang 108] Nếu θ = in f { f ( x ) : x ∈ ∆ ( A, b)} là một số thực hữu hạn thì bài toán (1.6) có một nghiệm. Chứng minh. Chúng ta sẽ chứng minh theo Blum and Oettli (1972). Từ giả thiết θ ∈ Rn , suy ra ∆ ( A, b) 6= ∅. Chọn một điểm x0 ∈ ∆ ( A, b). Lấy ρ > 0 tùy ý cho trước. Đặt
∆ρ = ∆ ( A, b) ∩ B x0 , ρ . Chú ý rằng ∆ρ là tập lồi, khác rỗng và compact. Xét bài toán sau  min f ( x ) : x ∈ ∆ρ 15 (1.7) Theo định lý Weierstrass, tồn tại y ∈ ∆ρ sao cho  f (y) = qρ := min f ( x ) : x ∈ ∆ρ . Vì tập nghiệm của (1.7) là khác rỗng và compact, nên tồn tại yρ ∈ ∆ρ sao cho  yρ − x0 = min y = x0 : y ∈ ∆ρ , f (y) = qρ Chúng ta khẳng định rằng ở đó phải tồn tại ρ > 0 sao cho yρ − x0 < ρ với mọi ρ ≥ ρ (1.8) Thật vậy, nếu khẳng định này sai thì chúng ta sẽ tìm một dãy tăng ρk → +∞ sao cho với mọi k tồn tại yρk ∈ ∆ρk sao cho
f yρk = qρk , yρk − x0 = ρk (1.9) Để đơn giản các ký hiệu, chúng ta viết yk thay cho yρk . Khi đó yk ∈ ∆ ( A, b), chúng ta có Ai yk ≥ bi với i = 1, ..., m, trong đó Ai biểu thị dòng thứ i của A và bi biểu thị phần tử thứ i của b. Với i = 1, khi  đó dãy A1 yk là bị chặn dưới, chúng ta có thể chọn dãy con {k0 } ⊂ 0 A1 yk tồn tại. Không mất tính tổng quát, giả sử rằng {k} sao cho lim 0 k →∞  {k0 } ≡ {k}, khi đó dãy A1 yk hội tụ tới chính nó. Tương tự, với i = 2 0 A2 yk . Không mất ở đó tồn tại một dãy con {k0 } ⊂ {k} sao cho lim 0 k →∞ tính tổng quát, giả sử rằng {k0 } ≡ {k }. Tiếp tục quá trình trên với i = m để tìm một không gian con {k0 } ⊂ {k} sao cho tất cả các giới hạn 0 lim Ai yk , (i = 1, ..., m) 0 k →∞ tồn tại. Để đơn giản, chúng ta giả  sử rằng {k0 } ≡ {k} . Lấy I =  k k {1, ..., m} , I0 = i ∈ I : lim Ai y = bi và I1 = I \ I0 = i ∈ I : lim Ai y > bi . k→∞ k→∞ 16 Do vậy tại đó tồn tại ε > 0 và i ∈ I1 sao cho lim Ai yk > bi + ε k→∞
Theo (1.9), yk − x0 /ρk = 1 với mọi k. Vì hình cầu đơn vị trong Rn là một tập compact, không mất tính tổng quát, giả sử rằng dãy   k y − x0 ρk hội tụ đến v ∈ Rn khi k → ∞. Rõ ràng, kvk = 1. Khi ρk → +∞, với mọi i ∈ I0 chúng ta có  k A y − b i i 0 = lim Ai yk − bi = lim k→∞ k→∞ ρk     k 0 y −x A i x 0 − bi = lim Ai + lim = Ai v. k→∞ k→∞ ρk ρk    Tương tự, với mọi i ∈ I1 chúng ta có  0 ≤ lim inf Ai yk − bi k→∞   A i y k − bi = lim inf k→∞ ρk     yk − x0 A i x 0 − bi = lim Ai + lim k→∞ k→∞ ρk ρk  = Ai v Vì vậy Ai v = 0 với mọi i ∈ I0 , Ai v ≥ 0 với mọi i ∈ I1 . (1.10) Từ điều này chúng ta kết luận rằng v là một hướng của nón lùi xa của tập đa diện lồi ∆ ( A, b). Từ (1.10) chúng ta có y + tv ∈ ∆ ( A, b) với mọi t ≥ 0 và y ∈ ∆ ( A, b) (1.11) Khi đó  
 f yk = f yρk = qρk = min f ( x ) : x ∈ ∆ρk  = min f ( x ) : x ∈ ∆ ( A, b) ∩ B ( x0 , ρk ) 17 
và dãy tăng {ρk } hội tụ đến +∞, chúng ta chỉ ra rằng dãy f yk là
không tăng và f yk → θ. Kết quả là với k đủ lớn chúng ta có   θ − 1 ≤ f yk ≤ θ + 1. Sử dụng công thức của f chúng ta viết lại bất đẳng thức dưới dạng T     1 k 0 k 0 T k 0 θ−1 ≤ y −x D y −x +c y −x 2   1
0 T k 0 + x D y − x + ( x0 )T Dx0 + cT x0 ≤ θ + 1. 2 Chia biểu thức này cho ρ2k và lấy giới hạn khi k → ∞ chúng ta có 1 0 ≤ v T Dv ≤ 0. 2 Do đó v T Dv = 0 (1.12) Theo (1.11) yk + tv ∈ ∆ ( A, b) với mọi t ≥ 0 và k ∈ N trong đó N là tập số nguyên dương. Theo (2.12) chúng ta có  1 T      k k T k k y + tv D y + tv + c y + tv f y + tv = 2    T 1  k T k k T k T Dv + c v . y y Dy + c y + t = 2 Chú ý rằng  T yk Dv + c T v ≥ 0 với mọi k ∈ N (1.13)
Thật vậy, nếu (1.13) là sai thì chúng ta có f yk + tv → −∞ khi t → +∞, điều này mâu thuẫn với giả thiết θ ∈ R. Do đó ta có 2 2 2 E D k k k 2 0 0 k 0 2 0 y − x , v = y − x − 2t y − x , v + t kvk < y − x (1.14) với t > đủ nhỏ. Theo (1.10) 18