Luận án Tiến sĩ Toán học: Điều kiện tối ưu và đối ngẫu cho bài toán quy hoạch thương đa mục tiêu không trơn

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:107

Thêm vào BST

Báo xấu

17
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận án "Điều kiện tối ưu và đối ngẫu cho bài toán quy hoạch thương đa mục tiêu không trơn" đã xây dựng và chứng minh các định lý điều kiện cần và điều kiện đủ tối ưu cho bài toán (MFP). Đồng thời Luận án cũng đã xây dựng và chứng minh các định lý đối ngẫu yếu, đối ngẫu mạnh và đối ngẫu ngược kiểu Mond-Weir và kiểu Wolfe cho bài toán này

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án Tiến sĩ Toán học: Điều kiện tối ưu và đối ngẫu cho bài toán quy hoạch thương đa mục tiêu không trơn

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ———————————– Phạm Thị Linh ĐIỀU KIỆN TỐI ƯU VÀ ĐỐI NGẪU CHO BÀI TOÁN QUY HOẠCH THƯƠNG ĐA MỤC TIÊU KHÔNG TRƠN LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội – 2022
BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ———————————– Phạm Thị Linh ĐIỀU KIỆN TỐI ƯU VÀ ĐỐI NGẪU CHO BÀI TOÁN QUY HOẠCH THƯƠNG ĐA MỤC TIÊU KHÔNG TRƠN LUẬN ÁN TIẾN SĨ TOÁN HỌC Chuyên ngành: Toán ứng dụng Mã số chuyên ngành: 9.46.01.12 NGƯỜI HƯỚNG DẪN KHOA HỌC : 1. GS.TS. Đỗ Văn Lưu 2. TS. Nguyễn Công Điều Hà Nội – 2022
Lời cam đoan Tôi xin cam đoan đây là công trình nghiên cứu của tôi. Các kết quả viết chung với các tác giả khác đã được sự nhất trí của các đồng tác giả đưa vào Luận án. Các kết quả được nêu trong Luận án này là trung thực và chưa từng được ai công bố trong bất kỳ một công trình nào khác. Tôi xin chịu trách nhiệm với những lời cam đoan của mình. Tác giả Phạm Thị Linh ii
Lời cảm ơn Luận án được hoàn thành tại Viện Công nghệ Thông tin, Học viện Khoa học và Công nghệ thuộc Viện Hàn lâm Khoa học và Công nghệ Việt Nam dưới sự hướng dẫn tận tình của GS. TS. Đỗ Văn Lưu và TS. Nguyễn Công Điều. Tác giả xin bày tỏ sự kính trọng và lòng biết ơn sâu sắc nhất tới hai Thầy. Tác giả cũng xin bày tỏ lòng biết ơn tới các thầy giáo, cô giáo của Viện Công nghệ Thông tin, Học viện Khoa học và Công nghệ thuộc Viện Hàn lâm Khoa học và Công nghệ Việt Nam đã tạo điều kiện, giúp đỡ tác giả trong quá trình học tập và nghiên cứu. Trong quá trình học tập, nghiên cứu tác giả đã được tham gia Seminar của Viện Toán học và Khoa học ứng dụng Thăng Long, Trường Đại học Thăng Long Hà Nội. Tác giả xin chân thành cảm ơn. Tác giả xin chân thành cảm ơn Ban giám hiệu, Khoa Khoa học Cơ bản và Bộ môn Toán - Tin của Trường Đại học Kinh tế và Quản trị Kinh doanh, nơi tác giả đang công tác đã tạo điều kiện thuận lợi trong suốt quá trình học tập và nghiên cứu. Cuối cùng, tác giả xin bày tỏ lòng biết ơn sâu sắc tới những người thân trong gia đình đã động viên, chia sẻ và khích lệ tác giả để tác giả có thể hoàn thành Luận án tiến sĩ của mình. Tác giả Phạm Thị Linh iii
Mục lục Lời cam đoan ii Lời cảm ơn iii Mục lục iv Danh mục các ký hiệu và chữ viết tắt vi Mở đầu 1 Chương 1. Một số kiến thức chuẩn bị 18 1.1 Một số khái niệm cơ bản . . . . . . . . . . . . . . . . . . 18 1.2 Một số kết quả vô hướng hóa của Gong . . . . . . . . . . 21 1.3 Dưới vi phân suy rộng . . . . . . . . . . . . . . . . . . . 22 1.4 Kết luận Chương 1 . . . . . . . . . . . . . . . . . . . . . 24 Chương 2. Điều kiện cần và điều kiện đủ cho nghiệm hữu hiệu yếu của bài toán quy hoạch thương đa mục tiêu 25 2.1 Điều kiện cần . . . . . . . . . . . . . . . . . . . . . . . . 25 2.1.1 Điều kiện cần Fritz John . . . . . . . . . . . . . . 26 2.1.2 Điều kiện cần Kuhn-Tucker . . . . . . . . . . . . 31 2.2 Điều kiện đủ . . . . . . . . . . . . . . . . . . . . . . . . 35 2.3 Kết luận Chương 2 . . . . . . . . . . . . . . . . . . . . . 39 Chương 3. Điều kiện cần và điều kiện đủ cho tựa nghiệm hữu hiệu yếu của bài toán quy hoạch thương đa mục iv
tiêu 41 3.1 Điều kiện cần . . . . . . . . . . . . . . . . . . . . . . . 41 3.1.1 Điều kiện cần Fritz John . . . . . . . . . . . . . . 42 3.1.2 Điều kiện cần Kuhn-Tucker . . . . . . . . . . . . 47 3.2 Điều kiện đủ . . . . . . . . . . . . . . . . . . . . . . . . 51 3.3 Kết luận Chương 3 . . . . . . . . . . . . . . . . . . . . . 56 Chương 4. Đối ngẫu cho bài toán quy hoạch thương đa mục tiêu với nghiệm hữu hiệu yếu 57 4.1 Bài toán đối ngẫu kiểu Mond-Weir . . . . . . . . . . . . 57 4.2 Bài toán đối ngẫu kiểu Wolfe . . . . . . . . . . . . . . . 64 4.3 Kết luận Chương 4 . . . . . . . . . . . . . . . . . . . . . 72 Chương 5. Đối ngẫu cho bài toán quy hoạch thương đa mục tiêu với tựa nghiệm hữu hiệu yếu 73 5.1 Bài toán đối ngẫu kiểu Mond-Weir . . . . . . . . . . . . 73 5.2 Bài toán đối ngẫu kiểu Wolfe . . . . . . . . . . . . . . . 79 5.3 Kết luận Chương 5 . . . . . . . . . . . . . . . . . . . . . 86 Kết luận và hướng nghiên cứu tiếp theo 88 Danh mục công trình của tác giả 90 Tài liệu tham khảo 91 v
Danh mục các ký hiệu và chữ viết tắt X∗ Không gian tôpô đối ngẫu của X hx∗ , xi Giá trị của phiếm hàm x∗ ∈ X ∗ tại x ∈ X cl Bao đóng ∗ yếu conv Bao lồi intD Phần trong của D d(x, Q) Khoảng cách từ x ∈ X đến Q B(x; δ) Hình cầu mở tâm x bán kính δ f − (x; υ) Đạo hàm theo phương Dini dưới của f tại x theo phương v f + (x; υ) Đạo hàm theo phương Dini trên của f tại x theo phương v ∇f (x) Đạo hàm Fréchet của f tại x ∇G f (x) Đạo hàm Gâteaux của f tại x ∂ C f (x) Dưới vi phân Clarke của f tại x ∂ M P f (x) Dưới vi phân Michel-Penot của f tại x ∂ ∗ f (x) Dưới vi phân suy rộng của f tại x T (D; x) Nón tiếp tuyến Clarke của D tại x ∈ D N (D; x) Nón pháp tuyến Clarke của D tại x (MFP) Bài toán quy hoạch thương đa mục tiêu vi
Mở đầu Các bài toán tối ưu có hàm mục tiêu là các hàm thương được gọi là bài toán quy hoạch thương. Bài toán quy hoạch thương được nảy sinh từ các vấn đề kinh tế hoặc phi kinh tế. Đó chính là Bài toán cực đại lợi nhuận trên chi phí, Bài toán cực đại giá trên thời gian, Bài toán cực đại đầu ra trên đầu vào, Bài toán cực tiểu chi phí trên thời gian, Bài toán cực đại tỷ lệ tín hiệu trên tạp âm của bộ lọc quang phổ trong vật lý, Bài toán lên kế hoạch, Bài toán lập trình quy mô lớn,.... Năm 1962, Charnes và Cooper [1] đã đưa ra bài toán quy hoạch thương. Từ đó, bài toán quy hoạch thương thu hút được sự chú ý và quan tâm của rất nhiều nhà nghiên cứu. Tuy nhiên phần lớn các kết quả mang tính lý thuyết và xét trên tập chấp nhận được là tập lồi tùy ý hay khối đa điện lồi tùy ý [2] – [14]. Giả sử f, g, hk (k = 1, 2, · · · , m) là các hàm trên tập D của không gian Euclide n chiều Rn . Xét hàm f (x) q(x) = (1) g(x) trên tập S = {x ∈ D : hk (x) 6 0, k = 1, · · · , m}, (2) trong đó, g(x) dương trên D. Ta có, Bài toán quy hoạch phi tuyến: (P ) : sup{q(x) : x ∈ S} (3) được gọi là Bài toán quy hoạch thương một mục tiêu. Ta có một số dạng khác của Bài toán quy hoạch thương một mục tiêu như: sup{ min qi (x) : x ∈ S} (4) 16i6p 1
và p nX o sup qi (x) : x ∈ S , (5) i=1 trong đó, qi (x) = fi (x)/gi (x), gi (x) > 0. Bài toán (4) còn được gọi là bài toán quy hoạch thương suy rộng [15]. Các Bài toán (4) và (5) đều có mối liên hệ với bài toán quy hoạch thương đa mục tiêu max{(q1 (x), · · · , qp (x)) : x ∈ S}. (6) Nếu f, g là các hàm affine và S là đa diện lồi thì (P) được gọi là bài toán quy hoạch thương tuyến tính. Bài toán này có dạng n cT x + α o sup T : Ax 6 b, x > 0 , (7) d x+β trong đó, c, d ∈ Rn , α, β ∈ R, T là ký hiệu phép chuyển vị, A là ma trận cấp m × n và b ∈ Rm . Bài toán (P) được gọi là bài toán quy hoạch thương bậc hai nếu f, g là các hàm bậc hai và S là đa diện lồi. Bài toán (P) được gọi là bài toán quy hoạch thương lõm nếu f là hàm lõm trên D và g, hk là các hàm lồi trên D, D là một tập lồi. Nếu giảm bớt các giả thiết về tính lồi hoặc tính lõm thì bài toán quy hoạch thương một mục tiêu được gọi là bài toán không lõm suy rộng và được nhiều tác giả quan tâm trong tối ưu toàn cục. Xét Bài toán (3): Bài toán này nảy sinh từ các vấn đề kinh tế hoặc phi kinh tế. Sau đây, ta sẽ trình bày một số ứng dụng của bài toán này trong các lĩnh vực kinh tế, phi kinh tế và một số lĩnh vực khác. Gilmore và Gomory đã phân tích bài toán chia cổ phần trong ngành công nghiệp giấy [16]. Nhóm nghiên cứu này đã chỉ ra rằng việc giảm tỷ lệ nguyên liệu thô được thực hiện là tối ưu hơn việc giảm thiểu lượng nguyên liệu bị hao hụt. Bài toán chia cổ phần này là bài toán quy hoạch thương tuyến tính. Hoskins và Blom [17] đã sử dụng bài toán quy hoạch thương một mục tiêu để phân tích giảm chi phí lao động. 2
Bài toán quy hoạch thương phi tuyến bậc hai lõm xuất phát từ bài toán lựa chọn danh mục đầu tư được đề xuất bởi Ziemba, Parkan và Brooks-Hill [18]. Ohlson và Ziemba [19] đã xét bài toán n cT x o max :x∈S , (8) (xT Cx)γ trongđó, c ∈ Rn dương, C là ma trận xác định dương cấp n × n và 1 γ ∈ 0, . Ở đây c và C được xác định bởi vectơ lợi nhuận kỳ vọng 2 1 e và ma trận phương sai-hiệp phương sai V . Với γ ∈ 0, thì tử số 2 không phải là hàm lồi và do đó Bài toán (8) không phải là bài toán quy hoạch thương lõm [20]–[22]. Mao [23], Faaland và Jacobs [24] đã sử dụng bài toán quy hoạch thương tuyến tính trong việc lựa chọn các danh mục đầu tư. Những ứng dụng khác của bài toán quy hoạch thương một mục tiêu trong kế hoạch tài chính được đề xuất bởi Uberti [25] với bài toán cho thuê. Konno và Inori [26] đã tối ưu hóa kỳ hạn trung bình hoặc năng suất trung bình trong giao dịch trái phiếu bằng bài toán quy hoạch thương một mục tiêu. Dantzig, Blattner và Rao [27] đã phân tích bài toán thương một mục tiêu để xác định hành trình cho các con tàu hoặc máy bay trong đó một chu trình trong mạng lưới sẽ được xác định trước để giảm thiểu tỷ lệ chi phí theo thời gian. Kydland [28] đã nghiên cứu về bài toán vận chuyển hàng hóa với việc tối ưu hóa lợi nhuận trên mỗi đơn vị thời gian. Cả bài toán chi phí và bài toán thời gian đều phụ thuộc vào lượng hàng hóa. Nếu doanh thu là hàm tuyến tính cũng như chi phí và thời gian là các hàm tuyến tính thì đã có kết quả nghiên cứu đối với bài toán quy hoạch thương tuyến tính. Derman [29], Klein [30] đã nghiên cứu về quy trình ngẫu nhiên để cực tiểu chi phí/thời gian. Charnes, Cooper và Rhodes [31] đã sử dụng bài toán quy hoạch thương tuyến tính để đánh giá hoạt động của các tổ chức phi lợi nhuận 3
trong các bài toán công cộng và đưa ra một loạt các quyết định. Các quyết định này được chọn dựa vào cực đại tỷ số của đầu ra/đầu vào. Một ví dụ khác về cực đại đầu ra/đầu vào được đưa ra bởi Stancu- Minasian [32]. Trong mô hình kinh tế vĩ mô, nhóm nghiên cứu này đã cực đại tăng trưởng của thu nhập quốc dân trên đầu tư và tiêu dùng. Một số kết quả về mặt lý thuyết đã được thực hiện bởi Eichhorn [33, 34]. Bài toán giá trị ban đầu trong giải tích số [35] có thể đưa về bài toán cực đại thương Rayleigh. Điều này dẫn tới bài toán quy hoạch thương bậc hai không lõm. Một bài toán quy hoạch thương một mục tiêu trong vật lý được đưa ra bởi Falk [36] về cực đại tỷ lệ tín hiệu trên tạp âm của bộ lọc quang phổ. Điều này dẫn tới bài toán quy hoạch thương bậc hai lõm. Bài toán quy hoạch thương một mục tiêu bậc hai lõm nảy sinh từ lý thuyết định vị như là đối ngẫu của bài toán cực tiểu định vị [37]. Một nguồn khá phong phú của bài toán quy hoạch thương một mục tiêu là bài toán lập trình quy mô lớn. Bài toán quy hoạch thương một mục tiêu còn được gặp một cách gián tiếp trong bài toán quy hoạch ngẫu nhiên được nghiên cứu bởi Charnes và Cooper [38] và Bereanu [39]. Xét bài toán lập trình ngẫu nhiên max{aT x : x ∈ S}, (9) trong đó, a là vectơ hệ số có phân phối chuẩn tắc đa chiều và S là tập lồi, chấp nhận được. Giả sử rằng thị trường quyết định thay bài toán (9) bằng bài toán max{P (aT x > k) : x ∈ S}. Khi đó, Bài toán (9) trở thành bài toán n eT x − k o max :x∈S , (10) (xT V x)1/2 trong đó, e là vectơ trung bình của a và V , V là ma trận phương sai-hiệp phương sai [38, 39]. Khi đó mô hình cực đại xác suất của Bài toán (9) trở thành bài toán quy hoạch thương lõm. 4
Ngoài Bài toán (9), ta xét bài toán quy hoạch bậc hai ngẫu nhiên lõm max{f0 (x) + θf1 (x) : x ∈ S}, (11) trong đó, f0 , f1 là các hàm lõm trên tập lồi chấp nhận được S, f1 > 0 và θ là biến ngẫu nhiên (liên tục). Khi đó mô hình cực đại xác suất của Bài toán (11) có thể đưa về bài toán quy hoạch thương một mục tiêu: n f (x) − k o 0 max :x∈S . (12) f1 (x) Bài toán (11) tương đương với Bài toán (12) và đó là bài toán quy hoạch thương tuyến tính [39]. Nếu f0 lõm và f1 tuyến tính thì Bài toán (12) trở thành bài toán quy hoạch thương lõm. Tuy nhiên nếu f1 là hàm lõm (phi tuyến) thì Bài toán (12) không còn là bài toán quy hoạch thương lõm. Hiển nhiên Bài toán (11) sẽ trở thành bài toán quy hoạch thương bậc hai [40, 41]. Bài toán (9) và (11) thường gặp trong bài toán lên kế hoạch. Gaudioso và Monaco [42] đã sử dụng bài toán quy hoạch thương bậc hai như một bài toán con trong thuật toán giải bài toán không khả vi lồi. Sideri [43] đã xấp xỉ bài toán giả lõm suy rộng (địa phương) bằng bài toán quy hoạch thương tuyến tính. Bài toán quy hoạch thương lõm có một số tính chất quan trọng của bài toán lõm dựa trên tính lõm suy rộng của hàm mục tiêu [44] – [46] f (x) q(x) = g(x) 1. cực đại địa phương là cực đại toàn cục; 2. cực đại là duy nhất nếu tử số là lõm chặt hoặc mẫu số lồi chặt; 3. nghiệm của điều kiện tối ưu Karush-Kuhn-Tucker là cực đại với giả thiết rằng các hàm f, g, hi khả vi trên tập mở D; 4. cực đại đạt được tại điểm biên của đa diện lồi S của bài toán quy hoạch thương tuyến tính. 5
Từ tính chất 1 và 3 ta thấy có thể giải bài toán quy hoạch thương lõm bằng một số thuật toán giải quy hoạch lõm. Đồng thời từ đó ta cũng thấy rằng một số phương pháp quy hoạch lõm có thể áp dụng đối với bài toán có hàm mục tiêu tựa lõm [46] – [49]. Nếu (P) là bài toán quy hoạch thương tuyến tính thì từ tính chất 4 ta có thể tìm cực đại x bằng cách xác định một dãy các điểm biên xi của S với việc tăng dần giá trị q(xi ). Phương pháp tựa đơn hình đối với dạng này được đề xuất bởi Martos [50] và Swarup [51]. Một số thuật toán quy hoạch lõm không thể áp dụng được với bài toán quy hoạch lõm suy rộng [46]. Do đó, việc chọn các thuật toán quy hoạch lõm để giải bài toán quy hoạch thương lõm trực tiếp bị hạn chế. Tuy nhiên, ta có thể chỉ ra rằng bài toán quy hoạch thương lõm có thể đưa về bài toán quy hoạch lõm bằng cách đổi biến 1 1 y= x, t= . (13) g(x) g(x) Khi đó, bài toán (P) trở thành bài toán n y y y 0 (P ) : sup tf : thk 6 0,k = 1, · · · , m, tg 6 1, t t t (14) y o ∈ D, t > 0 . t Đây là bài toán quy hoạch lõm [52, 53]. Nếu y/t là nghiệm tối ưu của (P 0 ) thì x = y/t là nghiệm tối ưu của (P). Bằng cách đổi biến như trên Charnes và Cooper [1] đã chỉ ra rằng bài toán quy hoạch thương tuyến tính có thể đưa về bài toán quy hoạch tuyến tính. Như vậy, bài toán (P) có thể giải một cách gián tiếp bằng cách giải bài toán tương đương (P 0 ). Việc giải bài toán (P 0 ) thay vì giải bài toán (P) có thể áp dụng khi f và g có cấu trúc đại số nhất định. Trong trường hợp đặc biệt của bài toán quy hoạch thương tuyến tính (7), bằng phép biến đổi (13) ta có thể đưa về bài toán quy hoạch tuyến tính n o T T sup c y + αt : Ay − bt 6 0, d y + βt = 1, y > 0, t > 0 . (15) 6
Khi đó, Bài toán (7) giải được bằng phương pháp đơn hình [1, 49]. Đối ngẫu Wolfe của (P 0 ) có dạng     λ → inf,  T  −∇f (x) + (∇h(x)) u + λ∇g(x) = 0,    (DPw ) : −f (x) + (h(x))T u + λg(x) > 0, (16)   x ∈ D, u ∈ Rm , u > 0, λ > 0,       (λ không bị hạn chế nếu g affine).  Tương tự quy hoạch lõm [45], hệ thức đối ngẫu yếu, đối ngẫu mạnh, đối ngẫu ngược cũng như các kết quả đối ngẫu khác có thể áp dụng với (P) và (DP ) ((P) và (DPw )) [53, 54]. Một số kết quả đối ngẫu tương tự khác đã được đề xuất trong các tài liệu [40, 54] với bài toán quy hoạch thương tuyến tính và trong các tài liệu tham khảo [40, 53, 54] với các bài toán quy hoạch thương phi tuyến. Mặc dù một số vấn đề đối ngẫu đã được đề nghị và chứng minh, nhưng các kết quả về thuật toán còn rất ít và hầu hết các nghiên cứu đều mang tính lý thuyết. Đã có rất nhiều thuật toán dựa trên bài toán quy hoạch tham số (Pq ): (Pq ) : max{f (x) − qg(x) : x ∈ S}, (17) trong đó, q ∈ R là tham số. Trong phần tiếp theo ta giả sử S compact, f và g liên tục trên S. Ký hiệu giá trị tối ưu của hàm mục tiêu của (Pq ) là F (q), x là nghiệm tối ưu của (P) và q = f (x)/g(x). Dễ thấy [55, 56] F (q) > 0 nếu q < q, F (q) = 0 nếu q = q, F (q) < 0 nếu q > q. Hơn nữa nghiệm tối ưu của (Pq ) cũng là nghiệm tối ưu của (P). Để giải bài toán (P) ta tìm nghiệm của phương trình phi tuyến F (q) = 0. 7
Khi nghiên cứu các thuật toán theo hướng này, ta thấy rằng mặc dù việc đánh giá F (q) để tìm q có thể mất thời gian vì nó tương đương với việc giải bài toán (Pq ). Với nghiệm tối ưu x0 của (Pq0 ), đặt y = f (x0 ) − qg(x0 ) (18) là tiếp tuyến của F (q) tại q = q 0 . Isbell và Marlow [57] đã áp dụng phương pháp Newton cho bài toán quy hoạch thương tuyến tính. Sau đó Dinkelbach [55] mở rộng cho bài toán quy hoạch thương phi tuyến và gọi là phương pháp Dinkelbach. Pardolas và Phillip [58] cũng đã đề xuất một phiên bản khác của phương pháp Newton. Ngoài các phương pháp lặp trên, phương pháp quy hoạch tham số Fq cũng có thể được sử dụng. Megiddo [59] đã đưa ra phương pháp để giải bài toán quy hoạch thương kết hợp trong đó bài toán quy hoạch tham số (Pq ) được sử dụng khác phương pháp Dinkelbach [60, 61]. Xét Bài toán (4): Bài toán này được phát sinh khi tỷ lệ tăng trưởng (growthrate) của một nền kinh tế mở được xác định [62, 63]: outputi (x) growthrate = max min , (19) x 16i6p inputi (x) trong đó, x là kế hoạch sản xuất có thể có của nền kinh tế. Trong khoa học quản lý, việc cực đại đồng thời các tỷ lệ có thể dẫn tới Bài toán (4). Một ứng dụng khác của mô hình (4) là toán học số. Cho giá trị Fi của hàm F (t) hữu hạn tại một số điểm ti trên một khoảng với tỷ số xấp xỉ của hai đa thức N (t, x1 ) và D(t, x2 ) với vectơ hệ số x1 , x2 có thể xác định được. Nếu xấp xỉ tốt nhất được định nghĩa theo chuẩn L∞ thì bài toán sau giải được
N (t , x )
i 1 max
− Fi
→ inf (20)