BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC QUY NHƠN TRẦN NAM HẢI PHƯƠNG TRÌNH SUY RỘNG VÀ MỘT SỐ VẤN ĐỀ LIÊN QUAN LUẬN VĂN THẠC SĨ TOÁN HỌC Bình Định - Năm 2020 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC QUY NHƠN TRẦN NAM HẢI PHƯƠNG TRÌNH SUY RỘNG VÀ MỘT SỐ VẤN ĐỀ LIÊN QUAN Chun ngành : Tốn giải tích Mã số : 46 01 02 Người hướng dẫn: TS NGUYỄN VĂN VŨ Mục lục Mở đầu Chương 1 Kiến thức chuẩn bị 1.1 Khơng gian Rn Rm×n 1.2 Cơ sở giải tích đa trị 1.3 Một số kết khái niệm khác 1.3.1 Cơ sở giải tích lồi 1.3.2 Định lý điểm bất động Kakutani 10 Chương Phương trình suy rộng nghiệm chúng 11 2.1 Các kết 11 2.2 Trường hợp ánh xạ đa diện 17 2.3 Tính ổn định phương trình suy rộng tuyến tính 19 Chương Một số ứng dụng vào toán quy hoạch phi tuyến 23 3.1 Sơ lược toán quy hoạch toán học 23 3.2 Điều kiện đủ cấp hai 24 3.3 Nghiệm nhiễu địa phương toán quy hoạch phi tuyến 33 3.4 Điều kiện Lipschitz trường hợp đa diện 36 Kết luận 45 Tài liệu tham khảo 46 Quyết định giao đề tài luận văn thạc sĩ ii Mở đầu Trong luận văn này, quan tâm đến lớp tốn mà nói chung thiết lập lại dạng bao hàm thức sau ∈ f (x) + T (x), (1) f hàm liên tục, khả vi Fréchet từ tập mở Ω ⊂ Rn đến Rn , T ánh xạ đa trị xác định nhận giá trị Rn Về mặt thuật ngữ, ta nói phương trình suy rộng, dựa theo [1] (Chú ý là, T đồng với ánh xạ x ∈ Rn −→ {0} (1) trở thành phương trình f (x) = 0.) Trong số trường hợp, người ta xét đến lớp mở rộng (1), có dạng ∈ f (p, x) + T (x), (2) f : (p, x) ∈ Rk × Ω −→ Rn , T (1) Mục tiêu chủ yếu nghiên cứu tập nghiệm (giải theo biến thứ hai x) (2) p gần giá trị sở p0 Một trường hợp riêng (2) trường hợp đặc biệt T lấy toán tử vi phân ∂ψC [2, Section 23] tương ứng với hàm tiêu tập lồi đóng C ⊂ Rn Nhắc lại hàm ψC xác định ψC (x) := 0, x ∈ C +∞, x ∈ / C Điều cho ta phương trình suy rộng đặc biệt ∈ f (p, x) + ∂ψC (x) (3) Về mặt trực quan hình học, bao hàm thức dẫn đến −f (p, x) pháp vec tơ tập lồi C x Nhiều toán quy hoạch toán học, toán bù, toán kinh tế dạng khác mà ta biểu diễn thành (3) Chẳng hạn, xét toán bù phi tuyến F (x) ∈ K ∗ , x ∈ K, (4) x, F (x) = 0, đó, F : Rn → Rn , K nón lồi đa diện khác rỗng Rn K ∗ := {y ∈ Rn | y, k ≥ với k ∈ K}, viết lại thành ∈ F (x) + ∂ψK (x) Người đọc quan tâm đến lớp toán bù phi tuyến (với K = Rn+ ), tham khảo thêm [3, 4, 5, 6] Điều kiện cần Kuhn-Tucker cho quy hoạch toán học [5] dạng đặc biệt (4) Thật vậy, xét toán θ(y) (5) với ràng buộc g(y) ≤ 0, h(y) = 0, θ, g h hàm khả vi từ Rm đến R, Rq Rr theo thứ tự Khi đó, điều kiện cần tối ưu Kuhn-Tucker tương ứng m ∇θ(y) + r ∇gi (y)ui + i=1 ∇hj (y)vj = 0, j=1 g(y) ≤ 0, u ≥ 0, h(y) = 0, u, g(y) = 0, kí hiệu ∇ϕ ánh xạ gradient hàm số khả vi ϕ Ta viết lại r dạng (4) cách lấy n = m + q + r, K = Rm × Rm + × R , x = (y, u, v)   ∇θ(y) + g (y)∗ (u) + h (y)∗ (v)  F (x) =   −g(y) −h(y)    với g (y)∗ (tương ứng h (y)∗ ) tốn tử liên hợp ứng với ánh xạ tuyến tính g (y) (tương ứng h (y)) Luận văn nhằm trình bày lại số kết liên quan đến dáng điệu nghiệm toán(2) số ứng dụng quan trọng chúng lĩnh vực liên quan Về mặt nội dung, luận văn chia thành chương sau: Chương Kiến thức chuẩn bị Trong chương này, chúng tơi hệ thống hóa lại kiến thức sở giải tích đại số Rn , khái niệm định nghĩa để triển khai luận văn sau Chương Phương trình suy rộng nghiệm chúng Chương chúng tơi trình bày kết luận văn, phương trình suy rộng dáng điệu nghiệm chúng (tiêu biểu Định lý 2.1) Tiếp theo, xem xét lớp ánh xạ đa trị quan trọng đảm bảo số tính chất cần thiết Định lý 2.1 Phần cuối số ứng dụng trường hợp phương trình suy rộng tuyến tính Chương Một số ứng dụng Trong chương chúng tơi trình bày số ứng dụng từ kết Chương 2, ứng dụng điều kiện đủ cấp hai, tìm nghiệm nhiễu tốn quy hoạch phi tuyến, điều kiện Lipschitz số ứng dụng khác Luận văn hoàn thành hướng dẫn thầy Nguyễn Văn Vũ Tác giả xin bày tỏ lòng biết ơn chân thành đến thầy, người tận tình giúp đỡ để tác giả hoàn thành luận văn cách tốt Tác giả xin chân thành cảm ơn quý thầy cô khoa Tốn Thống kê, Phịng đào tạo sau đại học trường Đại học Quy Nhơn, quý thầy cô tham gia giảng dạy cho lớp Cao học Tốn khóa 21 tạo điều kiện giúp đỡ cho tác giả trình học tập nghiên cứu Nhân tác giả xin cảm ơn gia đình, bạn bè quan tâm, động viên giúp đỡ tác giả q trình học tập hồn thành luận văn Cuối tác giả hy vọng luận văn đóng góp tài liệu tham khảo hữu ích cho bạn sinh viên, học viên cao học tìm tịi nghiên cứu chủ đề có liên quan Tác giả Chương Kiến thức chuẩn bị 1.1 Khơng gian Rn Rm×n Mục hệ thống hóa số khái niệm ký hiệu liên quan đến không gian Ơclit thực Như thường lệ, ta viết Rn để không gian gồm véc tơ thực n chiều (quy ước viết dạng cột) Rm×n khơng gian ma trận thực cỡ m × n Với ma trận M ký hiệu M T ma trận chuyển vị M Nếu M T = M ta nói ma trận đối xứng M nửa xác định dương xT M x ≥ với véc tơ x Cuối cùng, M xác định dương xT M x > x = Cho trước hai véc tơ xT = (x1 , x2 , , xn ) y T = (y1 , y2 , , yn ) Rn , tích vơ hướng chúng xác định theo biểu thức x, y := xT y = x1 y1 + x2 y2 + + xn yn Khi đó, chuẩn Ơclit tương ứng hàm số · : Rn −→ R cho x = x, x Với ma trận A cỡ m × n đại lượng A := λmax (AT A) gọi chuẩn phổ A, λmax (AT A) ký hiệu cho giá trị riêng lớn ma trận đối xứng AT A Phép tốn lấy tích vơ hướng lấy chuẩn có số tính chất sau [7] i) Ax, y = x, AT y (hay viết tương đương theo phép toán ma trận xT Ay = y T AT x); ii) AB ≤ A B ; Ax ≤ A x ; Ax, y ≤ Ax + y Trong phần sau đây, cần đến số khái niệm tôpô [8] Cho trước x ∈ Rn số thực r > Hình cầu mở tâm x bán kính r tập hợp B(x, r) = {y ∈ Rn : y − x < r} Tương tự, hình cầu đóng tâm x bán kính r định nghĩa sau ¯ r) = {y ∈ Rn : y − x ≤ r} B(x, Tập hợp S ⊂ Rn gọi mở điểm thuộc S điểm trong, nghĩa ¯ r) x bao hàm S Tập với điểm x ∈ S tồn lân cận B(x, ¯ r) hợp S gọi tập đóng ứng với x ∈ / S tồn lân cận B(x, x không chứa điểm thuộc tập S Cho ánh xạ f : Ω ⊂ Rn −→ Rm f gọi liên tục x ∈ Ω với dãy (xk ) ⊂ Ω hội tụ x ta có limk→∞ f (xk ) = f (x) Ánh xạ f gọi Lipschitz tập hợp Ω ⊂ Ω tương ứng với số L > f (x) − f (y) ≤ L x − y , ∀x, y ∈ Ω Ta nói hàm f khả vi Fréchet điểm x Ω tồn ánh xạ tuyến tính f (x) : Rn −→ Rm , thỏa mãn [9] lim h →0 f (x + h) − f (x) − f (x)(h) = h Ánh xạ f (x) gọi đạo hàm Fréchet f x Khi Jacobian f x ma trận ánh xạ tuyến tính f (x) Các phần tử ma trận đạo hàm riêng thành phần f lấy theo biến tương ứng Cho S ⊂ Rn khác rỗng, x ∈ Rn điểm Hàm khoảng cách từ x đến S định nghĩa d(x, S) := inf{ x − y | y ∈ S}, với quy ước d(x, ∅) = +∞ Với S = ∅ hàm d(·, S) Lipschitz với số L = 1.[10] Hình 1.1: Tính chất Lipschitz khoảng X 1.2 Cơ sở giải tích đa trị Một ánh xạ đa trị F : Rn ⇒ Rm hiểu ánh xạ từ Rn vào tập hợp gồm tập Rm Đồ thị gph F , miền hữu hiệu dom F miền ảnh rge F ánh xạ đa trị F : X ⇒ Y tương ứng xác định biểu thức [11] gphF = {(x, y) ∈ Rn × Rm | y ∈ F (x)}, domF = {x ∈ Rn | F (x) = ∅}, rgeF = {y ∈ Rm | ∃x ∈ Rn cho y ∈ F (x)} Ánh xạ ngược F −1 : Rm ⇒ Rn ánh xạ đa trị F : Rn ⇒ Rm xác định quy tắc F −1 (y) = {x ∈ Rn | y ∈ F (x)}, ∀y ∈ Rm Định nghĩa 1.1 (Tính liên tục ánh xạ đa trị [11]) Xét ánh xạ đa trị F : Rn ⇒ Rm • Ta nói F nửa liên tục x¯ ∈ dom F với tập mở V ⊂ Rm thỏa mãn F (¯ x) ⊂ V tồn lân cận mở U ⊂ Rn x¯ cho F (x) ⊂ V, ∀x ∈ U Nếu F nửa liên tục điểm thuộc dom F , F gọi nửa liên tục • Ta nói F nửa liên tục x¯ ∈ dom F với tập mở V ⊂ Rm thỏa mãn F (¯ x) ∩ V = ∅ tồn lân cận mở U x¯ cho F (x) ∩ U = ∅, ∀x ∈ U ∩ domF Nếu F nửa liên tục điểm thuộc dom F , F gọi nửa liên tục • Ta nói F liên tục x¯ ∈ dom F F đồng thời nửa liên tục nửa liên tục x¯ Nếu F liên tục điểm thuộc dom F , F gọi liên tục Ví dụ 1.2 Xét ánh xạ đa trị:     {0} F (x) = [-1, 1]    {1} x0 từ R vào R nửa liên tục R không nửa liên tục x¯ = Như vậy, F liên tục R ( Hình 1.2) Hình 1.2: Đồ thị F (x) Định nghĩa 1.3 [11] Ta nói ánh xạ đa trị F : Rn ⇒ Rm Lipschitz (địa phương) (hoặc gần) x¯ với mô-đun l (U.L l), tồn l > δ > cho ¯ F (x) ⊂ F (¯ x) + l x − x¯ B 36 thấy LM khơng có giá trị đơn gần p0 bao hàm LM P chặt chẽ Xét tốn quy hoạch tồn phương 2 (x1 − x2 ) − ηx1 , Với ràng buộc −x1 + 2x2 ≤ 0, −x1 − 2x2 ≤ 0, Trong η tham số Cho η = tốn có cực tiểu gốc tọa độ; với η > có cực tiểu địa phương 23 η(2, ±1) điểm yên ngựa (η, 0).Vì trường hợp LM ánh xạ đa trị ngặt SP η > 3.4 Điều kiện Lipschitz trường hợp đa diện Định lý 3.11 [21] Cho F hàm liên tục, khả vi Fréchet từ tập lồi mở Ψ ⊂ Rn đến Rn Cho R ánh xạ đa trị đa diện từ Rn đến Rn , định nghĩa H := F + R Cho x0 ∈ Ψ x ∈ Rn , định nghĩa LFx0 (x) := F (x0 ) + F (x0 )(x − x0 ) Giả sử có tập compact X0 ⊂ Ψ cho i) Với x0 x1 thuộc X0 , hạn chế LFx0 LFx1 đến X0 giống ii) Với γ > x0 ∈ X0 , Xγ ∩ (LFx0 + R)−1 (0) = X0 ; Xγ := X0 + γB ⊂ Ψ Khi có số δ > cho ánh xạ đa trị H −1 ∩ Xδ Lipschitz địa phương 0, với (H −1 ∩ Xδ )(0) = X0 Chứng minh Cho x0 ∈ X0 , định nghĩa Tx0 để (LFx0 + R)−1 Đặt := 21 γ Đầu tiên chứng minh tồn số λ số dương 37 η cho với x0 ∈ X0 , Tx0 ∩ X Lipschitz ηB với mô-đun λ Chọn x0 ∈ X0 ; tổng LFX0 + R đa diện, [35, Proposition 1], với số λ(x0 ) η(x0 ) > cho Tx0 Lipschitz η(x0 )B với mô-đun λ(x0 ) Nếu ta lấy η(x0 ) đủ nhỏ, theo đó, (Tx0 ∩ X )(0) = X0 hàm đa trị Tx0 ∩ X Lipschitz η(x0 )B với mô-đun λ(x0 ) Bây giờ, sử dụng giả thiết liên tục, chọn lân cận N0 x0 đủ nhỏ cho với x ∈ X0 ∩ N0 , (a) λ(x0 ) F (x) − F (x0 ) < 12 , (b) Với x ∈ X , LFx0 (x ) − LFx (x ) ≤ 21 η(x0 ) Chọn x ∈ X0 ∩ N0 q ∈ 12 η(x0 )B Nếu w ∈ (Tx ∩ X )(q), w ∈ X tương tự q ∈ LFx (w) + R(w), q + LFx0 (w) − LFx (w) ∈ LFx0 (w) + R(w) w ∈ (Tx0 ∩ X )[q + LFx0 (w) − LFx (w)] Tuy nhiên, q + LFx0 (w) − LFx (w) ≤ q + LFx0 (w) − LFx (w) 1 ≤ η(x0 ) + η(x0 ) = η(x0 ), 2 Vì tính liên tục Lipschitz ta có w ∈ X0 + λ(x0 ) q + LFx0 (w) − LFx (w) B Bây đặt x1 điểm X0 với d(w, X0 ) = w − x1 Bởi giả thuyết x0 , x, x1 ∈ X0 , ta có LFx0 (x1 ) = LFx (x1 ) Do LFx0 (w) − LFx (w) = LFx0 (x1 ) − LFx (x1 ) + [F (x0 ) − F (x)](w − x1 ) ≤ F (x0 ) − F (x) w − x1 38 d(w, X0 ) ≤ λ(x0 ) q + λ(x0 ) F (x0 ) − F (x) ≤ λ(x0 ) q + d[w, X0 ] w − x1 d(w, X0 ) ≤ 2λ(x0 ) p , (Tx ∩ X )(q) ⊂ (Tx ∩ X )(0) + 2λ(x0 ) q , Điều cho thấy Tx ∩ X Lipschitz 12 η(x0 )B với mô-đun 2λ(x0 ) Bây giờ, với λ η > 0, với x ∈ X0 , Tx ∩ X Lipschitz ηB với mô-đun λ Từ giả thiết liên tục compact, ta chọn đối số < δ ≤ min{ , η} cho β ≤ δ , với y ∈ Xγ z ∈ X0 với y − z ≤ δ , max{1, λ F (y) − F (z) − F (z)(y − z) ≤ y−z Bây chọn q ∈ 21 ηB đặt x ∈ (H −1 ∩ Xδ )(q) Khi q ∈ F (x) + R(x), x1 ∈ X0 với x − x1 = d[x − x0 ] ta có q + LFx1 (x) − F (x) ∈ LFx1 (x) + R(x) x ∈ (Tx1 ∩ X )[q + LFx1 (x) − F (x)] Tuy nhiên x − x1 1 ≤ η+ η≤η 2 q + LFx1 (x) − F (x) ≤ q + Vì tính Lipschitz liên tục Tx1 ∩ X , d[x, X0 ] ≤ λ q + d[x, X0 ] nghĩa d(x, X0 ) ≤ 2λ q Do (H −1 ∩ Xδ )(q) ⊂ X0 + 2λ q B (3.21) 39 với q ∈ 12 ηB Bây đặt x0 ∈ X0 Bởi giả thuyết ∈ (Fx0 + R)(x0 ) = F (x0 ) + R(x0 ) = H(x0 ), Vì X0 ⊂ (B −1 ∩ Xδ )(0) Mặt khác, áp dụng (3.21) với q = ta thấy (H −1 ∩ Xδ )(0) ⊂ X0 , (H −1 ∩ Xδ (0) = X0 H −1 ∩ Xδ Lipschitz ηB với mô-đun 2λ Chứng minh hoàn thành Nhận xét 3.12 Kết cho phép đo chuyển vị điểm dừng x nhân tử u hàm đạo hàm toán nhiễu Chúng ta cho thấy điều tiến hành đo lường dịch chuyển đơn giản trường hợp hàm liên quan Lipschitz p Theo đó, ta viết U0 thay U (x0 , p0 ) làm phần 3.2 Định lý 3.13 [21] Giả sử giả thuyết Định lý 3.9 , giả sử C Q đa diện Khi lấy lân cận N7 p0 số µ cho với p ∈ N7 , x ∈ SP (p) u ∈ U (x, p), d[(x, u), x0 ì U0 ] àd[0, F (x, u, p0 ) + CìQ (x, p)] F (x, u, p0 ) − F (x, u, p) (3.22) F (x, u, p) := f (x, p) + g (x, p) ∗ u −g(x, p) Chứng minh Chúng ta áp dụng Định lý (3.11) đến hàm F (x, u) cho F (x, u, p0 ) Ta lấy R = ∂ψC×Q lựa chọn cho X0 , ta lấy tập {X0 } × U0 , để ψ = Ω × Rm Để kiểm chứng giả thuyết (i), chứng minh u0 , u1 , u2 ∈ U0 , LF(x0 ,u0 ) (x0 , u2 ) = LF(x0 ,u1 ) (x0 , u2 ) Tuy nhiên, tính toán đại số cho thấy đại lượng f (x0 , p0 ) + g (x0 , p0 ) ∗ u2 −g(x0 , p0 ) 40 Vì (i) thỏa mãn Đối với giả thuyết (ii), ta giả sử u0 ∈ U0 số x u, ∈ (LF(x0 ,u0 ) + ∂ψC×Q (x, u) Khi x điểm dừng u nhân tử liên hợp x, tốn quy hoạch tồn phương (cf (3.6)): f (x0 , p0 )(x − x0 ) + x − x0 , L”(x0 , u0 , p0 )(x − x0 ) g(x0 , p0 ) + g (x0 , p0 )(x − x0 ) ∈ Qo , Với ràng buộc (3.23) x∈C Tuy nhiên (3.23) thỏa mãn điều kện đủ cấp hai (tại x0 bội số nó, mơ-đun phụ thuộc vào bội số), ràng buộc quy; hai tính chất tương tự với tính chất toán phi tuyến (3.11) Bởi vậy, ý với u ∈ Rm ta thay (3.23) hàm mục tiêu: f (x0 , p0 )(x − x0 ) + = f (x0 , p0 )(x − x0 ) + + 21 x − x0 , [ m x − x0 , L”(x0 , u , p0 )(x − x0 ) x − x0 , L”(x0 , u0 , p0 )(x − x0 ) (u − u0 )i g”i (x0 , p0 )](x − x0 ) i=1 Khi số ngoặc vng ma trận đối xứng n × n nhỏ u đóng với u0 Áp dụng Định lý 3.5, ta kết luận lân cận M4 (x0 ) , phụ thuộc vào u0 , cho với u dần đến u0 , cặp (x, u) với ∈ [LFx0 ,u ) + ∂ψC×Q ](x, u), x ∈ / M4 x = x0 Một đối số sơ cấp từ tập compact U0 (Định lý 3.4) M4 độc lập với u0 Nếu ta lấy λ đủ nhỏ cho x0 + λB ⊂ M4 , với U0 ∈ U0 , (x, u) ∈ Xγ ∩ [LF(x0 ,u0 ) + ∂C×Q ]−1 (0), x ∈ M4 , x = x0 , u ∈ U0 cách kiểm tra Mặt khác u1 ∈ U0 , rõ ràng (x0 , u1 ) ∈ Xγ , ta kiểm tra lại ∈ LF(x0 ,u0 ) (x0 , u1 ) + ∂ψC×Q (x0 , u1 ) Theo ta có, với u0 ∈ U0 , Xγ ∩ [LF(x0 ,u0 ) + ∂ψC×Q ]−1 (0) = x0 × U0 = X0 Vì giả thiết (ii) Định lý 3.11 thỏa mãn Và ta kết luận với δ > hình cầu W Rn+m , ánh xạ đa trị [(F (·, ·, p0 ) + ∂ψC×Q ]−1 ∩ Xγ 41 Lipschitz W với [(F (·, ·, p0 ) + ∂ψC×Q ]−1 ∩ Xγ ](0) = x0 × U0 Lấy mơ-đun Lipschitz µ Vì SP U nửa liên tục Định lý 3.4, ta tìm lân cận N7 (p0 ) M5 (x0 ) cho M5 ⊂ x0 + δB (a) Với x ∈ M5 p ∈ N7 , U (x, p) ⊂ U0 + δB ; (b) Với p ∈ N7 , SP (p) ⊂ M5 ; (c) Với x ∈ M5 p ∈ N7 u ∈ U (x, p), F (x, u, p0 ) − F (x, u, p) ∈ W Chọn p ∈ N7 , x ∈ SP (p) u ∈ U (x, p) Khi (x, u) ∈ Xδ (a) (b), ta lấy v hình chiếu gốc tọa độ F (x, u, p0 ) + ∂ψC×Q , từ (3.12) ta có ∈ F (x, u, p) + ∂ψC×Q (x, u), F (x, u, p0 ) − F (x, u, p) ∈ F (x, u, p0 ) + ∂ψC×Q (x, u); Do v ≤ F (x, u, p0 ) − F (x, u, p) v ∈ W Khi −1 (x, u) ∈ [F (·, ·, p0 ) + ∂ψC×Q ∩ Xδ ](v), tính liên tục Lipschitz ta có d[(x, u), {x0 } ì U0 ] v = àd[0, F (x, u, p0 ) + CìQ (x, u)] F (x, u, p0 ) − F (x, p, u) , chứng minh hoàn thành Nhận xét 3.14 Ràng buộc (3.22) đơn giản ta xây dựng giả thuyết nhiễu tốt 42 Hệ 3.15 [21] Giả sử giả thuyết Định lý 3.13 Giả sử P tập không gian tuyến tính, f , g, g Lipschitz Ω × P Khi với số λ giới hạn (3.22) thay d((x, u), {x0 } × U0 ) ≤ λ p − p0 (3.24) Chứng minh Với số liệu (3.22) ta có, F (x, u, p0 ) − F (x, u, p) = [f (x, p0 ) − f (x, p)] + [g (x, p0 ) − g (x, p)]∗ u −[g(x, p0 ) − g(x, p)] Do x ∈ SP (p) nên gần x0 , u giới hạn đồng (x, p) gần (x0 , p0 ), ta thấy với L, F (x, u, p0 ) − F (x, u, p) ≤ L p − p0 , Và từ (3.22) ta có (3.24) Nhận xét 3.16 Ràng buộc (3.24) áp dụng để tính khoảng cách từ x đến điểm x0 , từ u đến tập U0 Sẽ tốt ta thêm giả thiết SP hàm đơn trị lân cận p0 , ta thiết lập tính chất mạnh liên tục Lipschitz địa phương Suy đoán vây khuyến khích tồn số kết biết dường theo hướng Ví dụ, Kojima cho thấy [36] rằng, toán đặc biệt (3.2) điều kiện đủ cấp hai mạnh Định nghĩa 3.1, kết hợp với tính quy ràng buộc, nghĩa SP đơn trị liên tục gần p0 Ta thấy [26] ràng buộc định tính củng cố từ giả thiết quy sử dụng (và Kojima) hướng ràng buộc liên kết độc lập tuyến tính, SP Lipschitz địa phương thực p0 Sự thật thúc đẩy câu hỏi tự nhiên sau đây: Ta kết hợp ràng buộc định tính điều kiện đủ cấp hai cách hợp lý ,khi SP LM hàm đơn trị, Lipschitz địa phương p0 hay khơng? Ta cho ví dụ cho thấy ràng buộc định tính mạnh ràng buộc quy, có khả kết hợp với điều kiện đủ cấp hai mạnh nhất, câu trả lời cho câu hỏi không Đặc biệt, nghiên cứu tốn hình chiếu gốc tọa độ lên đa giác lồi biểu diễn cực tiểu tập ràng buộc tuyến tính, ta thấy nghiệm 43 tốn khơng Lipschitz với nhiễu nhỏ ràng buộc Để làm rõ chất ví dụ này, ta giải thích thuật ngữ cực tiểu đại diện Một tập ràng buộc tuyến tính m( đẳng thức bất đẳng thức), với n biến gọi cực tiểu đại diện đa giác lồi S ⊂ Rn :(i) S tập nghiệm ràng buộc, (ii) khơng có tập nghiệm ràng buộc tuyến tính m Rn nhỏ S Một số tác giả nghiên cứu ý tưởng này; Bài viết Telgen [37] giải thích đưa đại diện Kết [37] nói tập nghiệm hệ ràng buộc tuyến tính cực tiểu đại diện quy khơng chứa bất đẳng thức dư thừa( Có bất đẳng thức riêng lẻ xóa mà khơng làm thay đổi tập nghiệm) Vì yêu cầu cực tiểu đại diện mạnh ràng buộc định tính ràng buộc quy Ví dụ, xét họ đa giác lồi S(b, c) định nghĩa với cặp (b, c) số thực hệ tuyến tính A(b)x ≥ a(c) , đó:       , a(c) :=   1        −1 0  0 A(b) :=   −1  1    b 1+c kiểm tra S(0, 0) tập {x × R4 | x3 ≥ + max(|x1 |, |x2 |)}, cực tiểu đại diện hệ A(0) ≥ a(0) Bây giờ, hình chiếu gốc tọa độ S(b, c) nghiệm tốn quy hoạch tồn phương lồi x (QP (b, c)) Với ràng buộc A(b)x ≥ a(c) Tất nhiên, hàm mục tiêu QP (b, c) dạng bậc hai xác định dương Tuy nhiên, ta xét véc tơ: x(b, c) := (0, 0, 1, 0)T + cb−1 (0, 0, 0, 1)T u(b, c) := (0.5, 0.5, 0, 0)T + cb−2 (−1, −1, 1, 1)T Ta thấy với b > ≤ c ≤ 12 b2 , 44 A(b)x(b, c) = a(c), x(b, c) = u(b, c)A(b), (3.25) u(b, c) ≥ Điều kiện (3.25) cho thấy x(b, c) nghiệm QP (b, c), mặt khác , rõ ràng với b > c1 , c2 ∈ [0, 21 b2 ], x(b, c1 ) − x(b, c2 ) = b−1 |c1 − c2 | = b−1 [A(b), a(c1 )] − [A(b), a(c2 )] , chuẩn [A, a] tính cách lấy bậc hai tổng bình phương thành phần Điều nghĩa nghiệm QP (b, c) xem hàm [A, a], khơng Lipschitz lân cận [A(0), a(0)] Điều giải phủ định dự đoán Daniel [18] mâu thuẫn với kết phát biểu Levitin [33, Theorem 4] Một trước ví dụ truyền đạt đến Levitin với yêu cầu làm rõ tác giả vào năm 1977, đến năm 1980 không nhận hồi âm 45 Kết luận Trong luận văn này, chúng tơi trình bày số nội dung sau dựa theo tài liệu [1] [21]: • Khảo sát phương trình suy rộng dáng điệu nghiệm chúng, kết chủ chốt liên quan đến chủ đề bao gồm Định lý 2.1 Mệnh đề 2.3 • Xem xét kết từ Định lý 2.1 Mệnh đề 2.3 trường hợp ánh xạ đa diện ứng dụng vào việc nghiên cứu tính ổn định phương trình suy rộng tuyến tính • Ứng dụng phương trình suy rộng tuyến tính quy hoạch phi tuyến 46 Tài liệu tham khảo [1] S M Robinson, "Generalized equations and their solutions, Part I: Basic Theory", Mathematical Programming study 10 (1979), 128-141 [2] R T Rockafellar , convex analysis (Priceton University Press, Princeton, NJ, 1970) [3] R W Cottle, "Nonlinear programs with postively bounded Jacobians , SIAM Journal on Applied Mathematics 14 (1966) 147 - 158 [4] G B Dantzig and R W Cottle ,"Positive (semi-) definite programming", in: J Abadie, ed., Nonlinear programming ( North- Holland, Asterdam, 1968) 55-73 [5] O L Mangasarian, Nonlinear programming (McGraw-Hill, New York, 1969) [6] J.J Moré ,"Classes of functions and feasibility conditions in non linear complementarity problems", Mathematical Programming (1974) 327-338 [7] Phan Thanh Nam, "BÀI TẬP THỰC HÀNH VÀ PHƯƠNG PHÁP TÍNH",BÀI GIẢNG CHUN ĐỀ (Bình Định- 2015) [8] C Berge, Topological spaces ( Macmilan, New York, 1963) [9] Jonathan M Borwein, Qiji J Zhu, "Techniques of Variational Analysis", (Springer-Verlag New York) [10] R T Rockafellar and Roger J-B Wets, "Variational Analysis",With figure drawn by Maria Wets (1997, 2nd printing 2004, 3rd printing 2009) 47 [11] Nguyễn Đông Yên, Giáo trình giải tích đa trị (NXB Khoa học tự nhiên Công nghệ, 2007) [12] Dattorro, Convex Optimization and Euclidean Distance Geometry (Meβ oo, 2005, v2009.10.28) [13] S Kakutani, " A generalization of Brouwer’s fixed point theorem", Duke Mathematical Journal (1941) 457-459 [14] H Nikaido, Convex structures and economic theory (Academic Press, New York and London,1968) [15] H Brézis , Opérateurs maximaux monotones ( North- Holland, Asterdam, 1973) [16] R T Rockafellar "Local boundedness of nonlinear, monotone operators", Michigan Mathematical Journal 16 (1969) 397-407 [17] S M Robinson, "An implicit-function theorem for generalized variational inequalities", Technical Summary (Report No 1672, Mathematics Research Center, University of Wisconsin-Madison, 1976; available from Nationnal Technical Information Service under Accession No ADA031952) [18] J.W Daniel, " Stability of the solution of definite quadratic programs", Mathematical Programming (1973) 41-53 [19] S M Robinson, "A characterization of stability in linear programming", Operation Research 25 (1977), 435-447 [20] S M Robinson, "Stability theory for systems of inequalities Part II: Differentiable nonlinear systems", SIAM Journal on Numerical Analysis 13 (1976), 497-513 [21] S M Robinson, "Generalized equations and their solutions, Part II: Applications to nonlinear programming", Mathematical Programming study 19 (1982), 200-221 48 [22] A.V Fiacco and G.P McCormick, Nonlinear programming: Sequential unconstrained minimization techniques (Wiley, New York, 1968) [23] M Guignard, "Generalized Kuhn-Tucker conditions for mathematical programming problems in a Banach space’, SIAM Journal on control (1969) 232-241 [24] H Maurer and J Zowe, "First and second-order necessary and sufficient optimality conditions for infinite-dimensional programming problems",Mathematical Programming, 16 (1975) 1354-1358 [25] H Maurer, "First and second-order necessary and sufficient optimality conditions in mathematical programming and optimal control",Schriftenreihe des Rechenzentrums Der Universitaăt Muă nster Ne 38, (August 1979) [26] S M Robinson, "Strongly regular generalized equations", Mathematics of Operation Research (1980), 754-76943-62 [27] N H Josephy, "Newton’s method for generalized equations" Technical Summary Report No., 1965, Mathematics Research Center, University of Wisconsin, Madison, WI (June 1979) [28] R B Wilson , "A simplicial algorithm for concave programming", Dissertation, Graduate School of Business Administration, Havard University, Boston, MA (1963) [29] S P Han and O L Mangasarian, "Exact penalty functions in nonlinear programming", Mathematical Programming 17 (1979) 251-269 [30] S M Robinson, "First order conditions for general nonlinear optimization", SIAM Journal on Applied Mathematics 30 (1976), 597-607 [31] O.L Mangasarian and S Fromovitz, "The Fritz John necessary optimality conditions in the presence of equality and inequality constraints", Journal of Mathematical Analysis and Applications 17 (1967) 37-47 i [32] S M Robinson, "Stability theory for systems of inequalities Part I: Linear Systems", SIAM Journal on Numerical Analysis 12 (1975), 754-769 [33] E S Levitin, "On the local perturbation theory of the problem of mathematical programming in a Banach space, Soviet Mathematics Doklady 16 (1975) 1354-1358 [34] J Gauvin, "A necessary and suffiient regulatity condition to have bounded multipliers in non convex programming", Mathematical Programming 12 (1977) 136-138 [35] S M Robinson, "Some cotinuity properties of polyhedral multifunctions", Mathematical programming Study 14 (1981), 206-214 [36] M Kojima, "Strongly stable stationary solutions in nonnlinear programs",in S.M Robinson,ed., Analysis and computation of fixed points.(Academic Press, New York, 1980) pp 93-138 [37] J Telgen , "Minimal representation of convex polyhedral sets", Working paper No 88, College of Business Administration, Havard University of Tenessee, Knoxville,TN (February 1980) Quyết định giao đề tài luận văn thạc sĩ ...BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC QUY NHƠN TRẦN NAM HẢI PHƯƠNG TRÌNH SUY RỘNG VÀ MỘT SỐ VẤN ĐỀ LIÊN QUAN Chuyên ngành : Toán giải tích Mã số : 46 01 02 Người hướng dẫn:... đa trị quan trọng đảm bảo số tính chất cần thiết Định lý 2.1 Phần cuối số ứng dụng trường hợp phương trình suy rộng tuyến tính Chương Một số ứng dụng Trong chương chúng tơi trình bày số ứng dụng... sở giải tích đại số Rn , khái niệm định nghĩa để triển khai luận văn sau Chương Phương trình suy rộng nghiệm chúng Chương chúng tơi trình bày kết luận văn, phương trình suy rộng dáng điệu nghiệm