NHĨM 8Bộ mơn: Kinh Tế Quản Lí Các phương pháp biểu diễn mối quan hệ kinh tếQuan hệ tổng cộng, trung bình, cậnbiênPhân tích tối ưu hóaKỸ THUẬT TỐIƯU HÓAPhép vi phân. Khái niệm đạo hàmQui tắc vi phânTối ưu hóa bằng phép tốnTối ưu hóa nhiều biếnTối ưu hóa ràng buộc I. Các phương pháp biểu diễn cácmối quan hệ kinh tế Mối quan hệ đơn giản Sử dụng bảng hoặcđồ thịMối quan hệ phức tạp Sử dung phương trình- Là phương pháp hữu ích- Sử dụng các kĩ thuật của phép toán vi phântrong việc xác định giải pháp tối ưu của một vấnđề VD: giả sử rằng mối quan hệ giữa tổng doanh thu [TR] của một doanhnghiệp và khối lượng [Q] hàng hố,dịch vụ mà doanh nghiệp đó bán ratrong một thời gian nhất định[ví dụ 1 năm] là:TR = 100Q – 10 Mối quan hệ giữa tổng doanh thu của doanh nghiệp và lượng bán của nó cóthể được biểu diễn dưới dạng phương trình, bảng hay đồ thị. II. Quan hệ trung bình, tổng cộng, cận biên2.1/ Tổng chi phí, chi phí trung bình và chi phí cận biên:• Tổng chi phí [TC]: Là tổng các khoản chi phí cố định và biến đổi ngắn hạnphát sinh khi doanh nghiệp sản xuất một lượng sản lượng nhất định. • Chi phí trung bình[AC]: là chi phí cho mỗi đơn vị sản xuất trong qtrình sản xuất. Chi phí trung bình [AC] bằng tổng chi phí chia cho sảnlượngTC: Tổng chi phíAC=TC/QQ: Sản lượng• Ví dụ, bộ phận sản xuất của ABC International đã hoàn thành sản xuất10.000 widget. Chi phí cố định của đợt sản xuất là 30.000 đơ la, cộngthêm 2 đơ la cho chi phí biến đổi cho mỗi đơn vị sản xuất. Tính tốn kếtquả là:[$ 30,000 chi phí cố định + $ 20,000 Chi phí biến đổi] / 10,000 Đơn vị= chi phí trung bình 5 Đơ la • Chi phí bình qn [ATC]: là chi phí tính trên mỗi đơn vị sản lượng,bao gồm tất cả các chi phí đầu vào của sản xuất.ATC = TC/QQ : Sản lượngTC : Tổng chi phí của tất cả cácloại đầu vài được sử dung để sảnxuất ra sản lượngATC = AFC + AVCAFC: Chi phí cố định bìnhqnAVC: Chi phí biến đổi bình * Chi phí cận biên [MC]: là mức tăng chi phí [∆C] khi sản lượng tăngthêm một đơn vị [∆Y]. MC cùng với doanh thu cận biên [MR] quyết địnhmức sản lượng cho phép doanh nghiệp đạt lợi nhuận tối đaChi phí cận biên [MC] bằng thay đổi trong tổng chi phí trên mỗi đơnvị thay đổi của sản lượng 2.2/Sự hình thành về mặt hình học của các đường chi phí trung bìnhvà chi phí cận biên:- Đường AC và MC trong hình 2.2 có thểđược xây dựng một cách hình học từđường TC.- Hình 2.2 chỉ ra một mối quan hệ quantrọng giữa đường AC và MC. Đó là: khiMC nằm dưới AC thì AC giảm và khi MCnằm trên AC thì AC tăng. Khi AC khơngtăng cũng khơng giảm thì MC cắt AC từphía dưới- Doanh thu cận biên và lợi nhuận cậnbiên là thay đổi trong tổng doanh thu vàtổng lợi nhuận trên mỗi đơn vị thay đổitrong doanh số hay sản lượng. III. PHÂN TÍCH TỐI ƯU HĨA Xem xét q trình một doanh nghiệp xác định mức sản lượng màtại đó tối đa hóa tổng lợi nhuận. Sử dụng các đường tổng doanh thu và tổng chi phí để đặt ra cơ sởcho việc phân tích cận biên.Tối đa hóa lợi nhuận bằngphương pháp tổng doanh thuvà tổng chi phíPhân tích tốiưu hóaTối ưu hóa bằng phân tíchcận biên Tối đa hóa lợi nhuận bằng phương pháp tổng doanh thu và tổng chi phíTCĐEFC240TRDBMCJ180TR [ Total Revenue]: Tổng doanh thuTC [ Total Cost] :Tổng chi phíMC [ Marginal Cost]: Chi phí cận biênMR [ Marginal Revenue]: Doanh thucận biênH120D*AH*60C*B*12E”345MRQ Tổng lợi nhuận tại từng mốc sản lượng [Q]C”301G”-5023B”H”4D”5Q Tối ưu hóa bằng phân tích cận biênPhân tích cận biên ? Là q trình tính tốn ước lượng các lợi ích tăngthêm hay khơng khi cơng ty đầu tư thêm một khoảntiền vào trong quá trình sản xuất. Chi phí cận biên[MC]: là thay đổi trong tổng chiphí trên đơn vị sản lượng thay đổi được chỉ ra bởi độdốc của đường TC. Doanh thu cận biên[ MR]: là thay đổi trong tổngdoanh thu trên đơn vị sản lượng hay doanh số thayđổi và được chỉ ra bơi độ dốc của đường TR. Độ dốc của đường TR hay MRvượt quá độ dốc của đường TChay MC Doanh nghiệp nênmở rộng sản lượng hay doanhsố Lợi nhuận tăng.TCĐEFC240TRDB1MCJ180H120Để doanh nghiệp tối đa hóa lợinhuận MR=MC và MC cắtMR từ phía dưới.D*AH*602C*B*12E”345MRQHàm lợi nhuận quay bềlõm lên trên khoản lỗ làtối đa.Hàm lợi nhuận quay bề lõmxuống dưới tối đa hóa lợinhuận. Phép vi phân khái niệm đạo hàmPhân tích tối ưu có thể được áp dụng một cách thiết thực hơn, hiệu quảhơn khi được gắn với phép vi phân. Dựa trên khái niệm đạo hàm màđược liên hệ chặt chẽ với khái niệm cận biên Doanh thu cận biên là thay đổi trong tổng doanh thutrên mỗi đơn vị sản lượng thay đổiVD: khi sản lượng tăng từ 2 lên 3 đơn vị tổng doanh thu tăng từ 160Đ lên 210Đ.Như vậyMRĐây là độ dốc của dây BC trên đường tổng doanh thu. Tuy nhiên, khi lượng có thể phân chia vơcùng nhỏ[ có nghĩa là nhỏ hơn 1 và càng nhỏ đến mức ta muốn, thậm chí tiền đến 0 trong giớihạn]. MR là tốc độ của các dây càng nhỏ và tiến đến độ dốc của TR tại 1 điểm trong giới hạn.Điểm giữa B và C trên đường tổng doanh thu ở hình 2.4, doanh thu cận biên là độ dốc của dây BC.Đây là doanh thu cận biên bình quân giữa 2 và 3 đơn vị sản lượng. Mặt khác doanh thu cận biên tại Blà độ dốc của đoạn BK, đây là tiếp tuyến với đường tổng doanh thu tại điểm B Doanhthu cậnbiên tại1 điểmtrênđườngtổngdoanhthuLà độ dốc của doanh thu tại điểm đóDoanh thu cận biên tại 1 điểm nhất định trênđường tổng doanh thu bằng độ dốc của tổngdoanh thu đó tại điểm đóĐộ dốc này thay đổi ở mọi điểm trên tổngdoanh thuChú ý: nếu thay đổi X càng nhỏ thì giá trị của đạo hàm càng gầnvới độ dốc của đường đó tại 1 điểmVD: Trong hình 2.4, với giữa 2 và 4, bình quân [ độ dốc của dây BD].Đối với càng nhỏ giữa 2 và 3, bình quân = 50[ độ dốc của dây BC] sátvới độ dốc của đường đó tại điểm B [ = 60] TR[Y]240K210B16090... .CD.A.E.TR[X]12345Khái niệm đạo hàm hình 2.4Q V. CÁC QUY TẮC VI PHÂN 1. KHÁI NIỆMVi phân là quá trình xác định đạo hàm của một hàm số .Tức là tìm thayđổi của Y ứng với thay đổi của X khi thay đổi của X tiếp đến 0. 2. CÁC QUY TẮC VI PHÂNQuy tắc hằng sốQuy tắc hàm số mũ ở biếnQuy tắc đạo hàm của tổng các hàm sốQuy tắc đạo hàm của 1 tíchQuy tắc đạo hàm của 1 thươngQuy tắc đạo hàm của hàm a. Quy tắc hằng số :•• Đạohàm của 1 hàm hằng số Y=f[x]=a với mọigiá trị của a [ là hằng số].•Y=f[x]=a•
Header Page 1 of 54.BỘ GIÁO DỤC VÀ ĐÀO TẠOTRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2======NGUYỄN THÀNH LUÂNĐIỀU KIỆN TỐI ƯU BẬC HAICHO BÀI TOÁN TỐI ƯU VÉCTƠLUẬN VĂN THẠC SĨ TOÁN HỌCHÀ NỘI, 2018Footer Page 1 of 54.Header Page 2 of 54.BỘ GIÁO DỤC VÀ ĐÀO TẠOTRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2======NGUYỄN THÀNH LUÂNĐIỀU KIỆN TỐI ƯU BẬC HAICHO BÀI TOÁN TỐI ƯU VÉCTƠChuyên ngành: Toán Giải tíchMã số: 8 46 01 02LUẬN VĂN THẠC SĨ TOÁN HỌCNgười hướng dẫn khoa học: TS. Nguyễn Văn TuyênHÀ NỘI, 2018Footer Page 2 of 54.Header Page 3 of 54.Lời cảm ơnLuận văn thạc sĩ chuyên ngành Toán giải tích với đề tài “Điều kiệntối ưu bậc hai cho bài toán tối ưu véctơ” là kết quả của quá trình cố gắngkhông ngừng của bản thân và được sự giúp đỡ, động viên khích lệ củacác thầy cô, bạn bè đồng nghiệp và người thân. Qua trang viết này tácgiả xin gửi lời cảm ơn tới những người đã giúp đỡ tôi trong thời gian họctập - nghiên cứu khoa học vừa qua.Tôi xin tỏ lòng kính trọng và biết ơn sâu sắc đối với T.S. NguyễnVăn Tuyên đã trực tiếp tận tình hướng dẫn, cũng như cung cấp tài liệu,thông tin khoa học cần thiết cho tôi hoàn thành luận văn này.Tôi xin chân thành cảm ơn toàn thể các thầy cô giáo giảng viênKhoa Toán, các thầy cô phòng Sau Đại học và các thầy cô của TrườngĐại Học Sư Phạm Hà Nội 2 đã giảng dạy cũng như đã tạo điều kiện chotôi hoàn thành tốt công việc nghiên cứu khoa học của mình.Cuối cùng tôi xin chân thành cảm ơn đồng nghiệp, đơn vị công tác,gia đình và bạn bè đã động viên, tạo điều kiện giúp đỡ tôi trong quá trìnhhọc tập và thực hiện luận văn.Tác giả luận vănNguyễn Thành LuânFooter Page 3 of 54.Header Page 4 of 54.Lời cam đoanLuận văn Thạc sĩ chuyên ngành Toán Giải tích với đề tài “Điều kiệntối ưu bậc hai cho bài toán tối ưu véctơ” được hoàn thành tại Trường Đạihọc Sư phạm Hà Nội 2, dưới sự hướng dẫn của TS. Nguyễn Văn Tuyên,là kết quả nghiên cứu của bản thân, không trùng với bất cứ luận văn nàokhác.Trong quá trình nghiên cứu và viết luận văn, tôi đã kế thừa nhữngthành tựu của các nhà khoa học với sự trân trọng và biết ơn.Tôi cũng cam đoan các thông tin trích dẫn trong luận văn đã đượcchỉ rõ nguồn gốc.Tác giả luận vănNguyễn Thành LuânFooter Page 4 of 54.Header Page 5 of 54.Mục lục1 Một số kiến thức chuẩn bị81.1. Dưới vi phân bậc nhất đối xứng . . . . . . . . . . . . . . .1.2. Dưới vi phân bậc hai đối xứng8. . . . . . . . . . . . . . . 131.3. Các định lý luân phiên . . . . . . . . . . . . . . . . . . . . 182 Điều kiện tối ưu bậc hai cho bài toán tối ưu véctơ242.1. Khái niệm nghiệm . . . . . . . . . . . . . . . . . . . . . . 242.2. Điều kiện chính quy. . . . . . . . . . . . . . . . . . . . . 252.3. Điều kiện cần tối ưu . . . . . . . . . . . . . . . . . . . . . 352.4. Điều kiện đủ tối ưu . . . . . . . . . . . . . . . . . . . . . . 54Kết luận60Tài liệu tham khảo60Footer Page 5 of 54.1Header Page 6 of 54.Mở đầu1. Lý do chọn đề tàiMột trong các vấn đề quan trọng nhất trong lý thuyết tối ưu đó lànghiên cứu các điều kiện cần và điều kiện đủ tối ưu. Các điều kiện tối ưukhông những hữu ích trong việc xác định nghiệm của một bài toán tối ưumà còn đóng vai trò cốt yếu trong việc xây dựng các thuật toán để tìmnghiệm xấp xỉ của bài toán này.Trong các bài toán tối ưu, điều kiện bậc nhất [quy tắc Fermat]thường đóng vai trò là các điều kiện cần cực trị. Quy tắc Fermat cho tamột tiêu chuẩn xác định những điểm có khả năng đạt cực trị của mộthàm số. Một điểm thỏa mãn quy tắc Fermat còn gọi là một điểm dừng.Đối với một bài toán tổng quát [không lồi] thì quy tắc Fermat không đủđể ta nhận biết một điểm dừng có là điểm cực trị của bài toán hay không.Điều kiện cực trị bậc hai không những làm mịn hơn điều kiện cầncực trị bậc nhất mà còn bổ sung cho các điều kiện này trong việc đưa racác điều kiện đủ cho một điểm dừng là điểm cực trị của hàm số. Hơn thếnữa, nó còn giúp ta xây dựng các thuật toán tìm nghiệm tối ưu cũng nhưđánh giá tốc độ hội tụ của các thuật toán này; xem [1, 11, 17].Trong luận văn này, chúng tôi sẽ tập trung nghiên cứu các điều kiệnFooter Page 6 of 54.2Header Page 7 of 54.tối ưu bậc hai cho các bài toán tối ưu có dạng sauminRl+f [x][VP]với ràng buộc x ∈ Q0 := {x ∈ Rn : g[x]0},ở đó f := [fi ], i ∈ I := {1, . . . , l}, và g := [gj ], j ∈ J := {1, . . . , m} làcác hàm véctơ xác định trên không gian Euclide Rn .Như chúng ta biết rằng nếu fi , gj là các hàm khả vi Fréchet tạix¯ ∈ Q0 và x¯ là một nghiệm hữu hiệu yếu của [VP], thì tồn tại các nhântử Lagrange [λ, µ] ∈ Rl × Rm thỏa mãnlmλi ∇fi [¯x] +i=1µj ∇gj [¯x] = 0,[0.1]0, µj gj [¯x] = 0,[0.2]j=1µ = [µ1 , . . . , µm ]λ = [λ1 , . . . , λl ]0, [λ, µ] = 0;[0.3]xem [12, Theorem 7.4]. Các điều kiện [0.1]–[0.3] được gọi là điều kiệncần bậc nhất kiểu F.-John. Tính dương của một nhân tử ứng với mộthàm mục tiêu nào đó cho ta thấy vai trò của mục tiêu này trong việc xácđịnh nghiệm tối ưu của bài toán. Nếu λ = 0, thì các điều kiện [0.1]–[0.3]được gọi là điều kiện cần bậc nhất kiểu Karush–Kuhn–Tucker [KKT ].Đối với các bài toán tối ưu véctơ có hai kiểu điều kiện KKT . Khi mà tấtcả các nhân tử Lagrange của các hàm mục tiêu đều dương, thì ta nói bàitoán thỏa mãn điều kiện KKT mạnh [SKKT ]. Trường hợp còn lại đượcgọi là điều kiện KKT yếu [W KKT ].Để đạt được các điều kiện tối ưu kiểu KKT thì bài toán phải thỏamãn một điều kiện chính quy nào đó. Trong lý thuyết tối ưu, có haikiểu giả thiết chính quy đặt lên các ràng buộc và mục tiêu của bài toán.Các giả thiết được gọi là các điều kiện chuẩn hóa ràng buộc [constraintqualifications [CQ]] nếu nó chỉ đặt lên các ràng buộc của bài toán này.Nếu các điều kiện này đặt lên cả hàm mục tiêu và ràng buộc, thì chúng sẽFooter Page 7 of 54.3Header Page 8 of 54.được gọi là các điều kiện chính quy [regularity conditions [RC]]; xem [5].Một trong những nghiên cứu đầu tiên về điều kiện tối ưu bậc haicho các bài toán tối ưu véctơ trơn C 2 được thực hiện bởi Wang [20]. Trongbài báo này, các tác giả đã đề xuất một số kiểu điều kiện chuẩn hóa ràngbuộc và đạt được các điều kiện cần bậc hai kiểu F.-John và kiểu W KKTcho các bài toán tối ưu véctơ có cả ràng buộc đẳng thức và bất đẳngthức. Một điều kiện đủ cho các nghiệm hữu hiệu cũng được nghiên cứutrong bài báo này. Sau đó, Bigi và Castellani [2, 3] đã nhận được một sốđiều kiện cần bậc hai kiểu W KKT bằng cách sử dụng một số kiểu điềukiện chính quy bậc hai.Maeda [13] là người đầu tiên đề xuất một kiểu điều kiện chính quybậc hai theo nghĩa của Abadie [ASRC] và nhận được các điều kiện cầnvà điều kiện đủ bậc hai kiểu SKKT qua các đạo hàm bậc hai suy rộngtheo nghĩa Clarke cho các bài toán tối ưu véctơ với các mục tiêu và ràngbuộc thuộc lớp hàm C 1,1 .Gần đây, Huy và các đồng nghiệp [8,9] đã đề xuất một số điều kiệnchính quy kiểu Abadie mới qua các dưới vi phân đối xứng bậc hai đểnghiên cứu các điều kiện tối ưu bậc hai kiểu KKT cho bài toán [VP] vớidữ liệu thuộc lớp C 1,1 .Trên cơ sở các tài liệu tham khảo được trích dẫn ở trên, trong luậnvăn này chúng tôi sẽ khảo sát các điều kiện tối ưu bậc hai cho các bàitoán tối ưu véctơ C 1,1 .2. Mục đích nghiên cứuNghiên cứu các điều kiện tối ưu bậc hai cho các bài toán tối véctơ.Footer Page 8 of 54.4Header Page 9 of 54.3. Nhiệm vụ nghiên cứuNghiên cứu các tính chất của dưới vi phân bậc hai đối xứng, cácđiều kiện chính quy và các điều kiện cần tối ưu bậc hai cho các bài toántối ưu véctơ với dữ liệu C 1,1 .4. Đối tượng và phạm vi nghiên cứu• Đối tượng nghiên cứu: Điều kiện tối ưu bậc hai• Phạm vi nghiên cứu: Lý thuyết tối ưu véctơ5. Phương pháp nghiên cứuTham khảo và cập nhật những nghiên cứu của các tác giả trongnước cũng như ngoài nước liên quan đến đề tài.6. Dự kiến đóng góp mớiLuận văn sẽ trình bày một cách hệ thống về các điều kiện tối ưubậc hai cho các bài toán tối ưu véctơ với dữ liệu C 1,1 .Footer Page 9 of 54.5Header Page 10 of 54.Một số ký hiệuNtập các số tự nhiênRtập các số thựcR := R ∪ {±∞}tập các số thực mở rộngRnkhông gian Euclide n-chiềuRn+tập các véctơ không âm của RnRn−tập các véctơ không dương của Rnx∗ , xtích vô hướng trong Rnxchuẩn của véctơ x0Xvéctơ 0 trong không gian X0số 0, hoặc véctơ 0 trong không gian cho trướcF :X⇒Yánh xạ đa trị từ X vào YdomFmiền xác định của FgphFđồ thị của F{xn }, [xn ]dãy số thực, hoặc dãy véctơBXhình cầu đơn vị đóng trong XBhình cầu đơn vị đóng trong không gian định chuẩn chotrướcBρ [x], B[x, ρ]hình cầu đóng tâm x, bán kính ρBρ [x], B[x, ρ]hình cầu mở tâm x, bán kính ρN [x]tập tất cả các lân cận của điểm xNB [x]tập tất cả các lân cận cân của điểm xLim supgiới hạn trên theo nghĩa Painlevé - KuratowskiFooter Page 10 of 54.6Header Page 11 of 54.N [¯x; Ω]nón pháp tuyến Mordukhovich của Ω tại x¯N [¯x; Ω]nón pháp tuyến Fréchet của Ω tại x¯∇f [x]đạo hàm Fréchet của f tại x∂f [x]dưới vi phân Mordukhovich của f tại x∂ ∞ f [x]ˆ [x]∂fdưới vi phân suy biến của f tại xD∗ F [¯x, y¯][·]đối đạo hàm Fréchet của F tại [¯x, y¯]∗F [¯x, y¯][·]DNđối đạo hàm Mordukhovich của F tại [¯x, y¯]dưới vi phân Fréchet của f tại xΩx → x¯ và x ∈ Ωx −→ x¯fx → x¯ và f [x] → f [¯x]α↓α¯α→α¯ và αA⊂BA là tập con của BA∩Bgiao của hai tập hợp A và BA∪Bhợp của hai tập A và BA×Btích Descartes của hai tập A và BA\Bhiệu của hai tập A và BA+Btổng véctơ của hai tập A và Bint Aphần trong của tập hợp Ari Aphần trong tương đối của tập hợp AA, cl Abao đóng của tập hợp Abd [A]biên của tập hợp AAcphần bù của tập hợp Aaff [A]bao aphin của tập hợp Aconv [A]bao lồi của tập hợp Acone [A]bao nón của tập hợp A✷kết thúc chứng minhx −→ x¯α¯Footer Page 11 of 54.7Header Page 12 of 54.Chương 1Một số kiến thức chuẩn bị1.1.Dưới vi phân bậc nhất đối xứngCho mỗi tập Ω ⊂ Rn , ta kí hiệu bao đóng, phần trong, bao lồi vànón lồi sinh của Ω tương ứng bởi cl Ω, int Ω, conv Ω và cone Ω. Ta nóiΩ ⊂ X là đóng địa phương tại x¯ ∈ Ω nếu có một lân cận U của x¯ sao choΩ ∩ cl U là tập đóng.Kí hiệuΠ[x, Ω] : = {ω ∈ cl Ω | x − ω = dist[x, Ω]}là tập các chân hình chiếu của x lên Ω tương ứng với khoảng cách Euclide.Cho F : Rn ⇒ Rn là một ánh xạ đa trị. Giới hạn trên theo dãy theonghĩa Painlevé-Kuratowski tại x¯ của F được xác định bởiLim sup F [x] := {x∗ ∈ Rn | ∃xk → x¯, x∗k → x∗ , x∗k ∈ F [xk ], ∀k ∈ N}.x→¯xĐịnh nghĩa 1.1. Cho x¯ ∈ cl Ω, nón đóng sau đâyN [¯x, Ω] := Lim sup[cone[x − Π[x, Ω]]][1.1]x→¯xđược gọi là nón pháp tuyến cơ bản/nón pháp tuyến Mordukhovich của tậpΩ tại x¯. Nếu x¯ ∈/ cl Ω, thì ta đặt N [¯x, Ω] = ∅.Footer Page 12 of 54.Header Page 13 of 54.Từ định nghĩa, ta có thể suy ra nón pháp tuyến cơ bản [1.1] có tínhvững với nhiễu của x¯, tức là ánh xạ đa trị N [., Ω] luôn có đồ thị đóng.Nếu Ω là một tập lồi, thì nón pháp tuyến cơ bản trùng với nónpháp tuyến cổ điển theo nghĩa giải tích lồi. Tuy nhiên, trong trường hợptổng quát nón pháp tuyến cơ bản có thể không lồi.Chúng ta biết rằng, nón pháp tuyến Clarke của Ω tại x¯ là bao lồiđóng của nón pháp tuyến cơ bản, tức làNC [¯x, Ω] = cl conv N [¯x, Ω].[1.2]Như vậy, thông qua việc lấy bao lồi đóng trong [1.2] ta thấy nón pháptuyến Clarke có thể lớn hơn thực sự nón pháp tuyến cơ bản. Để minhhọa chúng ta xét ví dụ sau.Ví dụ 1.1. Cho tập Ω = {[x1 , x2 ] ∈ R2 | x2 ≥ −|x1 |} và x¯ = [0, 0] ∈ Ω.Khi đó, dễ dàng tính đượcN [¯x, Ω] = {[x1 , x2 ] ∈ R2 | x2 = −|x1 |}.Mặt khác, theo định nghĩa, ta cóNC [¯x, Ω] = cl conv N [¯x, Ω] = {[x1 , x2 ] ∈ R2 | x2 ≤ −|x1 |}.Định nghĩa 1.2. Cho Ω ⊂ X, x¯ ∈ Ω. Nón pháp tuyến Fréchet của Ω tạix¯ được định nghĩa bởiˆ [¯Nx; Ω] :=x∗ , x − x¯x ∈ X | lim supx − x¯Ωx→¯x∗∗0 ,Ωở đó kí hiệu x −→ x¯ có nghĩa là x → x¯ và x ∈ Ω.ˆ [¯Theo định nghĩa, dễ thấy Nx; Ω] là một nón lồi đóng.Mệnh đề 1.1 [Xem [15, Proposition 2.2]]. Với bất kì Ω ⊂ Rn và bất kìđiểm x¯ ∈ cl Ω, ta cóˆ [x; Ω].N [¯x, Ω] = Lim sup Nx→¯xFooter Page 13 of 54.9Header Page 14 of 54.Định nghĩa 1.3. Cho F : Rn ⇒ Rm là ánh xạ đa trị bất kì và cho[¯x, y¯] ∈ cl gphF . Ánh xạ đa trị D∗ F [¯x, y¯] : Rm ⇒ Rn được định nghĩabởiD∗ F [¯x, y¯][y ∗ ] := {x∗ ∈ Rn | [x∗ , −y ∗ ] ∈ N [[¯x, y¯], gph F ]}[1.3]được gọi là đối đạo hàm của F tại điểm [¯x, y¯]. Ta đặt D∗ F [¯x, y¯] = ∅ nếu[¯x, y¯] ∈/ cl gphF . Ta sử dụng kí hiệu D∗ F [¯x] khi F là ánh xạ đơn trị tạix¯ và y¯ = F [¯x].Theo định nghĩa này, ánh xạ đa trị [1.3] là thuần nhất dương tươngứng với y ∗ và tập hợp D∗ F [¯x, y¯][0] là một nón đóng.Nếu trong [1.3], nón pháp tuyến cơ bản được thay bằng nón pháptuyến Clarke hoặc nón pháp tuyến Fréchet thì các ánh xạDC∗ F [¯x, y¯][y ∗ ] := {x∗ ∈ Rn | [x∗ , −y ∗ ] ∈ NC [[¯x, y¯], gph F ]},ˆ ∗ F [¯ˆ [[¯Dx, y¯][y ∗ ] := {x∗ ∈ Rn | [x∗ , −y ∗ ] ∈ Nx, y¯], gph F ]}tương ứng được gọi là đối đạo hàm Clarke và đối đạo hàm Fréchet của Ftại [¯x, y¯].Phần còn lại của mục này, chúng ta xét một hàm số thực mở rộngϕ : Rn → R và một số khái niệm dưới vi phân cho hàm này. Tập trên đồthị và tập dưới đồ thị của ϕ tương ứng được kí hiệu bởiepi ϕ := {[x, α] ∈ Rn × R | ϕ[x] ≤ α},hypo ϕ := {[x, α] ∈ Rn × R | ϕ[x] ≥ α}.Định nghĩa 1.4 [xem [8, Definition 1.3]]. Cho x¯ ∈ dom ϕ := {x ∈Rn | |ϕ[x]| < +∞}. Tập hợp∂ϕ[¯x] := {x∗ ∈ Rn | [x∗ , −1] ∈ N [[¯x, ϕ[¯x]], epi ϕ]}[1.4]được gọi là dưới vi phân hoặc dưới vi phân qua giới hạn của ϕ tại x¯. Nếux¯ ∈/ dom ϕ thì ta đặt ∂ϕ[¯x] = ∅.Footer Page 14 of 54.10Header Page 15 of 54.Trong [1.4], nếu ta thay nón pháp tuyến cơ bản bằng nón pháptuyến Clarke hoặc nón pháp tuyến Fréchet thì các tập hợp∂C ϕ[¯x] := {x∗ ∈ Rn | [x∗ , −1] ∈ NC [[¯x, ϕ[¯x]], epi ϕ]}vàˆ x] := {x∗ ∈ Rn | [x∗ , −1] ∈ Nˆ [[¯∂ϕ[¯x, ϕ[¯x]], epi ϕ]}tương ứng được gọi là dưới vi phân Clarke và dưới vi phân Fréchet của ϕtại x¯.Định nghĩa 1.5 [xem [8, Definition 1.4]]. Cho x¯ ∈ dom ϕ. Các tập hợp∂ + ϕ[¯x] := {x∗ ∈ Rn | [−x∗ , 1] ∈ N [[¯x, ϕ[¯x]], hypo ϕ]}và∂S ϕ[¯x] := ∂ϕ[¯x] ∪ ∂ + ϕ[¯x]tương ứng được gọi là dưới vi phân trên và dưới vi phân đối xứng của ϕtại x¯.Từ định nghĩa, dễ dàng suy ra∂ + ϕ[¯x] = −∂[−ϕ][¯x] và ∂S [λϕ][¯x] = λ∂S ϕ[¯x], ∀λ ∈ R.Tiếp theo, chúng ta sẽ đưa ra một số quy tắc tính toán cho dưới vi phânđối xứng của các hàm Lipschitz.Mệnh đề 1.2. Giả sử f là hàm khả vi chặt tại x¯ và g là hàm Lipschitzquanh x¯. Khi đó, ta có:[i] ∂S [f + g][¯x] = ∇f [¯x] + ∂S g[¯x].[ii] ∂S [f.g][¯x] = ∇f [¯x].g[¯x] + ∂S [f [¯x].g][¯x].Chứng minh. [i] Theo [16, Proposition 1.107] và với các giả thiết củamệnh đề, ta có∂[f + g][¯x] = ∇f [¯x] + ∂g[¯x].Footer Page 15 of 54.11Header Page 16 of 54.Mặt khác, ta có∂ + [f + g][¯x] = −∂[−[f + g]][¯x] = −∂[[−f ] + [−g]][¯x] == −∇[−f ][¯x] − ∂[−g][¯x] = ∇f [¯x] + ∂ + g[¯x].Do đó, ta có∂S [f + g][¯x] = ∂[f + g][¯x] ∪ ∂ + [f + g][¯x] = ∇f [¯x] + ∂S g[¯x].[ii] Theo [16, Proposition 1.111], ta có:∂[f.g][¯x] = ∇f [¯x].g[¯x] + ∂[f [¯x].g][¯x].Mặt khác, ta có:∂ + [f.g][¯x] = −∂[−f.g][¯x] = −∂[[−f ].g][¯x]= −[∇[−f ][¯x].g[¯x] + ∂[[−f ][¯x].g][¯x]]= ∇f [¯x].g[¯x] − ∂[−[f [¯x].g]][¯x]= ∇f [¯x].g[¯x] + ∂ + [f [¯x].g][¯x].Do đó, ta có∂S [f.g][¯x] = ∂[f.g][¯x] ∪ ∂ + [f.g][¯x] = ∇f [¯x].g[¯x] + ∂S [f [¯x].g][¯x].Bây giờ, chúng ta sẽ đưa ra quy tắc đổi biến cho dưới vi phân đốixứng. Trước hết, chúng ta nhắc lại về quy tắc đổi biến cho dưới vi phân.Mệnh đề 1.3 [xem [16, Proposition 1.112]]. Giả sử g : Rn → Rm khảvi chặt tại x¯ với đạo hàm ∇g[¯x] là tràn ánh và ϕ : Rn × Rm → R vớiϕ[x, y] = ϕ1 [x] + ϕ2 [y] và ϕ2 : Rm → R hữu hạn tại y¯ = g[¯x]. Khi đó,ta có quy tắc đổi biến∂[ϕ ◦ g][¯x] = ∇ϕ1 [¯x] + ∇g[¯x]∗ ∂ϕ2 [¯y ].Footer Page 16 of 54.12Header Page 17 of 54.Từ mệnh đề trên, ta sẽ có quy tắc đổi biến cho dưới vi phân đốixứng.Mệnh đề 1.4. Giả sử g : Rn → Rm khả vi chặt tại x¯ với đạo hàm ∇g[¯x]là tràn ánh và ϕ : Rm → R hữu hạn tại y¯ = g[¯x]. Khi đó, ta có quy tắcsau∂S [ϕ ◦ g][¯x] = ∇g[¯x]∗ ∂S ϕ[¯y ].Chứng minh. Áp dụng Mệnh đề 1.3 với các hàm ϕ1 [x] = 0 với mọi x vàϕ2 [y] = ϕ[y], ta có∂[ϕ ◦ g][¯x] = ∇g[¯x]∗ ∂ϕ[¯y ].Mặt khác ta có:∂ + [ϕ ◦ g][¯x] = −∂[−ϕ ◦ g][¯x] = −∂[[−ϕ] ◦ g]= −[∇[g][¯x]∗ ∂[−ϕ][¯y ]] = ∇g[¯x]∗ [−∂[−ϕ][¯y ]]= ∇g[¯x]∗ ∂ + ϕ[¯y ].Do đó, ta có∂S [ϕ ◦ g][¯x] = ∂[ϕ ◦ g][¯x] ∪ ∂ + [ϕ ◦ g][¯x] = ∇g[¯x]∗ ∂S ϕ[¯y ].1.2.Dưới vi phân bậc hai đối xứngPhần tiếp theo, chúng ta sẽ trình bày một số tính chất của dưới viphân bậc 2 đối xứng. Giả sử ϕ : Rn → R là một hàm số cho trước.Định nghĩa 1.6 [xem [8, Definition 1.5]]. Lấy [¯x, y¯] là một điểm thùyý thuộc gph ∂ϕ. Ánh xạ đa trị ∂ 2 ϕ[¯x, y¯] : Rn ⇒ Rn được định nghĩa bởi∂ 2 ϕ[¯x, y¯][u] := [D∗ ∂ϕ][¯x, y¯][u] = {v | [v, −u] ∈ N [[[¯x, y¯]], gph∂ϕ]}được gọi là dưới vi phân bậc 2 của ϕ tại x¯ tương ứng với y¯.Footer Page 17 of 54.Header Page 18 of 54.Trong Định nghĩa 1.6, nếu ta thay nón pháp tuyến cơ bản bằng cácnón pháp tuyến Clarke hoặc nón pháp tuyến Fréchet thì tương ứng ta sẽcó các dưới vi phân Clarke và dưới vi phân Fréchet bậc 2.Chúng ta sẽ trình bày một số tính chất của dưới vi phân bậc 2.Trước hết ta trình bày công thức vô hướng hóa cho một hàm Lipschitz.Mệnh đề 1.5 [Xem [15, Proposition 2.11]]. Cho Φ : Rn → Rm là mộtánh xạ đơn trị và liên tục Lipschitz quanh x¯. Khi đóD∗ Φ[¯x][y ∗ ] = ∂ y ∗ , Φ [¯x], ∀y ∗ ∈ Rm .Từ mệnh đề này ta thấy rằng với một hàm f ∈ C 1,1 [D], với D làmột tập con mở của Rn và x¯ ∈ D. Khi đó∂ 2 f [¯x][v] := ∂ 2 f [¯x, ∇f [¯x]][v] = ∂ v, ∇f [¯x], ∀v ∈ Rn .Tương tự, ta cũng có dưới vi phân Clarke và dưới vi phân Fréchet bậc 2được xác định như sau:∂C2 f [¯x][v] = ∂C v, ∇f [¯x],và∂ˆ2 f [¯x][v] = ∂ˆ v, ∇f [¯x] ∀v ∈ Rn .Dựa vào các công thức vô hướng hóa trên, dưới vi phân bậc 2 đốixứng cho lớp hàm C 1,1 được định nghĩa như sau.Định nghĩa 1.7 [Xem [7, Definition 2.6]]. Cho x¯ ∈ D. Ánh xạ đa trị∂S2 ϕ[¯x] : Rn ⇒ Rn được định nghĩa bởi∂S2 f [¯x][v] := ∂S v, ∇f [¯x] = ∂ v, ∇f [¯x] ∪ ∂ + v, ∇f [¯x] ∀v ∈ Rnvà gọi là dưới vi phân bậc 2 đối xứng của f tại x¯.Tiếp theo, ta trình bày một số tính chất của dưới vi phân đối xứngbậc 2 của một hàm thuộc lớp C 1,1 .Footer Page 18 of 54.14Header Page 19 of 54.Mệnh đề 1.6. Giả sử f, g ∈ C 1,1 [D], D là một tập mở trong Rn vàx¯ ∈ D. Khi đó, ta có các khẳng định sau:[i] Với mọi λ ∈ R ta có∂S2 f [¯x][λv] = λ.∂S2 f [¯x][v] ∀v ∈ Rn .[ii] Với mọi λ ∈ R ta có∂S2 [λf ][¯x][v] = λ.∂S2 f [¯x][v] ∀v ∈ Rn .[iii] Với mỗi v ∈ Rn ánh xạ x → ∂S2 f [x][v] từ Rn vào Rn là bị chặnđịa phương. Hơn nữa, nếu xk → x¯, x∗k → x∗ và x∗k ∈ ∂S2 f [xk ][v] thìx∗ ∈ ∂S2 f [¯x][v].Chứng minh. Các khẳng định [i] và [ii] được suy ra trực tiếp từ địnhnghĩa của dưới vi phân bậc 2 đối xứng .[iii] Giả sử v ∈ Rn , x¯ ∈ D và ∇f Lipschitz địa phương quanh x¯ hệsố L. Khi đó, tồn tại hình cầu mở B[¯x, δ] ⊂ D sao cho| ∇f [x], v − ∇f [u], v | = | ∇f [x] − ∇f [u], v | ≤ L. v . x − u ,với mọi x, u ∈ B[¯x, δ]. Vì vậy ánh xạ x → ∇f [x], v là Lipschitz địaphương quanh x¯ với hệ số L. v . Từ Hệ quả 1.81 [16] suy ra tính bị chặnđịa phương của ∂S2 f [.][v] quanh x¯.Giả sử, ta có xk → x¯, x∗k → x∗ vàx∗k ∈ ∂S2 f [xk ][v] = ∂ v, ∇f [xk ] ∪ ∂ + v, ∇f [xk ] ∀k ∈ N.Bằng cách thay bằng dãy con [nếu cần], nên không làm mất tính tổngquát, ta có thể giả sử dãy [x∗k ] thuộc vào một trong các trường hợp sau:Trường hợp 1: Dãy [x∗k ] ⊂ ∂ v, ∇f [xk ]. Do tính nửa liên tục trên củaFooter Page 19 of 54.15Header Page 20 of 54.x][v].x] ⊂ ∂S2 f [¯∂ v, ∇f [·] tại x¯ và xk → x¯, x∗k → x∗ , nên x∗ ∈ ∂ v, ∇f [¯Trường hợp 2: Dãy [x∗k ] ⊂ ∂ + v, ∇f [xk ] = −∂[− v, ∇f ][xk ]. Suy ra[−x∗k ] ⊂ ∂[− v, ∇f ][xk ].Do tính nửa liên tục trên của ∂[− v, ∇f ][·] tại x¯ và −x∗k → −x∗ nên tacó −x∗ ∈ ∂[− v, ∇f ][¯x], hay làx∗ ∈ −∂[− v, ∇f ][¯x] = ∂ + v, ∇f [¯x] ⊂ ∂S2 f [¯x][v]·Ta nhắc lại quy tắc Fermat cho một điểm là cực trị địa phương củamột hàm số thực.Bổ đề 1.1 [xem [16, Proposition 1.114]]. Nếu hàm số φ : Rn → R đạtcực trị địa phương tại x¯, thì ta cóˆ x] ∪ ∂ˆ+ φ[¯0 ∈ ∂φ[¯x] ⊂ ∂S φ[¯x].Tiếp theo, chúng ta trình bày công thức dạng khai triển Taylor đốivới dưới vi phân bậc 2 đối xứng cho hàm thuộc lớp C 1,1 .Định lý 1.1. Cho I là một khoảng mở chứa [0, 1] và φ ∈ C 1,1 [I]. Khiđó, tồn tại t0 ∈ [0, 1] sao cho1φ[1] − φ[0] − ∇φ[0] ∈ ∂S2 φ[t0 ][1].2Chứng minh. Đặt ϕ[t] = φ[1] − φ[t] − ∇φ[t][1 − t] − [1 − t]2 .λ, vớit ∈ [0, 1] và λ = φ[1] − φ[0] − ∇φ[0]. Dễ thấy rằng ϕ là một hàm liêntục trên [0, 1] và thỏa mãn ϕ[0] = ϕ[1] = 0. Do đó, tồn tại t0 ∈ [0, 1] saocho hàm ϕ đạt cực trị địa phương tại điểm này. Theo quy tắc Fermat tasuy ra0 ∈ ∂S ϕ[t0 ].Footer Page 20 of 54.16Header Page 21 of 54.Do các hàm φ[·] và [1 − ·]2 khả vi chặt nên theo Mệnh đề 1.2, ta có∂S ϕ[t0 ] = −∇φ[t0 ] + ∂S [−∇φ[t][1 − t]]|t0 + 2[1 − t0 ]λ,hay là∂S ϕ[t0 ] = −∇φ[t0 ] + ∇φ[t0 ] − [1 − t0 ]∂S [∇φ[t]]|t0 + 2[1 − t0 ]λ= −[1 − t0 ]∂S [∇φ[t]]|t0 + 2[1 − t0 ]λ.Do ∂S [∇φ[t]]|t0 = ∂S 1, ∇φ[·] [t0 ] = ∂S2 φ[t0 ][1], nên ta có0 ∈ −[1 − t0 ]∂S2 φ[t0 ][1] + 2[1 − t0 ]λ.Điều này tương đương với1λ ∈ ∂S2 φ[t0 ][1],21hay là φ[1] − φ[0] − ∇φ[0] ∈ ∂S2 φ[t0 ][1].2Hệ quả 1.1 [Công thức khai triển Taylor]. Cho f ∈ C 1,1 [Rn ]. Khi đó,với mỗi a, b ∈ Rn đều tồn tại z ∗ ∈ ∂fS2 [ξ][b − a], với ξ ∈ [a, b], sao chof [b] − f [a] − ∇f [a], b − a =1 ∗z ,b − a .2Chứng minh. Xét hàm φ[t] = f [a + th], với t ∈ R và h := b − a. Hàmφ thỏa mãn các điều kiện trong Định lý 1.1 và ∇φ[t] = ∇f [a + th], h .Do đó, tồn tại t0 ∈ [0, 1] sao cho1φ[1] − φ[0] − ∇φ[0] ∈ ∂S2 φ[t0 ][1],2hay là1f [b] − f [a] − ∇f [a], b − a ∈ ∂S2 φ[t0 ][1].2Ta có∂S2 φ[t0 ][1] = ∂S 1, ∇φ[·] [t0 ] = ∂S [∇φ[·]][t0 ]= ∂S [ ∇f [a + [·]h], h ][t0 ].Footer Page 21 of 54.17[1.5]Header Page 22 of 54.Áp dụng quy tắc đổi biến trong Mệnh đề 1.3, ta có∂S2 φ[t0 ][1] = ∂S [ ∇f [a + [·]h], h ][t0 ]= h, ∂S ∇f [a + t0 h], h= h, ∂S2 f [a + t0 h][h] .Thay vào công thức [1.5] ta đượcf [b] − f [a] − ∇f [a], b − a ∈1h, ∂S2 f [ξ][h] ,2với ξ := a + t0 h và h = b − a. Điều này kéo theo rằng tồn tại z ∗ ∈∂fS2 [ξ][b − a] sao chof [b] − f [a] − ∇f [a], b − a =1 ∗z ,b − a .2Công thức trên được gọi là công thức khai triển Taylor của f tạiđiểm a.1.3.Các định lý luân phiênCho x là một véctơ n-chiều được xác định bởi x = [x1 , x2 , ..., xn ],trong đó xi ∈ R. Gọi A là ma trận cấp m × nA11 ... A1n.A=............Am1 ... AmnMa trận chuyển vị của A làA11 . . . Am1.AT = .........A1n . . . AmnFooter Page 22 of 54.18Header Page 23 of 54.Với A là ma trận cấp m × n , x là vectơ n-chiều, b là vectơ m-chiều, hệAx = b được hiểu làA x + · · · + A1n xn = b1 11 1........................A x + · · · + A x = b .m1 1mn nmTa đưa vào các quan hệ thứ tự sẽ sử dụng cho các phần sau.Cho x, y ∈ Rn . Ta viếtx = y ⇔ xi = yi , i = 1, . . . , nxy ⇔ xix ≥ y ⇔ xiyi , i = 1, . . . , nyi , và x = yx > y ⇔ xi > yi , i = 1, . . . , n.Định lý sau được dùng trong chứng minh của một số định lý luân phiên.Định lý 1.2 [xem [14, Corollary 18, p. 26]]. Cho các ma trận A, B, C, Dlần lượt cấp p1 × n, p2 × n, p3 × n, p4 × n, với A, B hoặc C là ma trậnkhác không. Khi đó hệIAx0 Bx0 Cx0Dx = 0có nghiệm xvàIIAT y1 + B T y2 + C T y3 + DT y4 = 0, y1120, y230, y304có nghiệm x ∈ Rn , y1 ∈ Rp , y2 ∈ Rp , y3 ∈ Rp , y4 ∈ Rp , thỏa mãnAx + y1 > 0Bx + y2 > 0vàCx + y3 > 0.Tiếp theo ta sẽ trình bày các định lý liên quan đến sự xuất hiệnmột trong hai sự kiện loại trừ lẫn nhau. Hai sự kiện, kí hiệu là I và II, sẽlà nghiệm của hai hệ đẳng thức tuyến tính và/hoặc bất đẳng thức tuyếnFooter Page 23 of 54.19Header Page 24 of 54.tính. Định lý luân phiên có thể được phát biểu như sau: Hoặc I, hoặc II,nhưng không bao giờ xảy ra đồng thời. Nếu ta kí hiệu ¯I là phủ định củaI, II là phủ định của II, thì chúng ta có thể phát biểu định lý luân phiênnhư sau.Dạng chính tắc của định lý luân phiên:I ⇔ IIhoặc tương đương vớiI ⇔ II.Lược đồ chứng minh cơ bản của định lý luân phiên là:I ⇔ II [hoặc tương đương I¯ ⇐ II]và ¯I ⇒ II [hoặc tương đương I ⇐ II].Chứng minh I ⇒ II thường khá là sơ cấp, nhưng chứng minh ¯I ⇒ II phảisử dụng một số định lí tồn tại nghiệm. Trong các định lý tiếp theo, để chongắn gọn, một số các điều kiện nhất quán sẽ không được nêu ra. Chẳnghạn, ta luôn giả sử rằng các ma trận có cùng số hàng, số cột và các véctơlà có cùng số chiều.Định lý 1.3 [Định lý luân phiên Slater]. Cho các ma trận A, B, C, D,trong đó A và B là ma trận khác không. Khi đó hoặc hệIAx > 0 Bx > 0 Cx0Dx = 0có nghiệm xhoặc hệIIA T y 1 + B T y2 + C T y3 + D T y4 = 0 vớiy1 ≥ 0, y2 0, y3 0 hoặc y1 0, y2 > 0, y3 0có nghiệm y1 , y2 , y3 , y4nhưng không bao giờ đồng thời.Chứng minh. [I ⇒ II]. Theo giả thiết, I đúng. Ta sẽ chứng minh rằngnếu II cũng đúng, thì sẽ xảy ra mâu thuẫn. Nếu cả I và II cùng đúng, thìFooter Page 24 of 54.20Header Page 25 of 54.tồn tại x, y1 , y2 , y3 , y4 thỏa mãnxAT y1 + xB T y2 + xC T y3 + xDT y4 > 0bởi vì xDT y4 = 0, xC T y3xB T y2 > 0 và xAT y10, và hoặc xB T y20 và xAT y1 > 0, hoặc0. Điều này mâu thuẫn với đẳng thức đầu tiêncủa II. Vậy I và II không đồng thời đúng. Do đó ta có [I ⇒ II].[¯I ⇒ II]. Ax ≯ 0 ¯I ⇒ {Ax 0, Bx 0, Cx 0, Dx = 0} ⇒hoặc Bx = 0 y1 ≥ 0 Ax 0, Bx 0, Cx 0, Dx = 0 TTTT⇒⇒hoặcA y1 + B y2 + C y3 + D y 4 = 0 yy >0 0, y0, y01232[theo Định lý 1.2]⇒ II.Định lý được chứng minh.Định lý 1.4 [Định lý luân phiên Motzkin]. Cho các ma trận A, C, và D,trong đó A là ma trận khác không. Khi đó hoặc hệIAx > 0 Cx0 Dx = 0có nghiệm xhoặc hệIIA T y1 + C T y3 + D T y 4 = 0y1 ≥ 0, y30có nghiệm y1 , y3 , y4nhưng không bao giờ đồng thời.Chứng minh. [I ⇒ II] Nếu cả I và II cùng đúng, thì tồn tại x, y1 , y3 , y4thỏa mãnxAT y1 + xC T y3 + xDT y4 > 0Footer Page 25 of 54.21