Chương 1 Kiến thức chuẩn bị Chương này giới thiệu về hệ bất phương trình tuyến tính theo nghĩa bình phương nhỏ nhất và một số kiến thức được sử dụng trong đề án. Trong chương này tham khảo nội dung từ các tài liệu [22] và [17].1 Hệ bất phương trình tuyến tính 1. Hệ bất phương trình tuyến tính Một hệ bất phương trình tuyến tính có thể được biểu diễn dưới hình thức ngắn gọn như sau: Định nghĩa 1. Ax ≤ b với A ∈ Rm×n , b ∈ Rm , x ∈ Rn .1) trong đó A = [aij ]m×n là ma trận với các phần tử aij ∈ R, x = [x1 , x2 ,.
, xn ]T là vec-tơ biến tuyến tính, và b = [b1 , b2 ,. , bm ]T là vectơ hằng số. Mặc dù bất kỳ quan hệ nào trong {>, ≥, <, ̸=} có thể thay thế cho quan hệ ≤, tuy nhiên các quan hệ tương tự nhau nên trong đề án này chỉ xét trường hợp ≤. Vec-tơ thỏa mãn hệ bất phương trình tuyến tính trên thì được gọi là nghiệm của hệ.
Khi không tồn tại bất kỳ vec-tơ nào thỏa mãn đồng thời tất cả các 4 bất phương trình trong hệ thì được gọi là hệ bất phương trình tuyến tính không nhất quán. Tập chỉ số I(x) Trong trường hợp hệ bất phương trình tuyến tính không nhất quán, có nghĩa là tồn tại ít nhất một chỉ số i mà điều kiện tương ứng không được thỏa mãn, tức là tập hợp I(x) ⊂ {1,. , m} được xác định bởi: I(x) = {i ∈ {1, .2) khác rỗng đối với mọi x ∈ Rn. Hơn nữa, giả sử rằng tập hợp I(x) = {i1 ,.
, ip } được sắp xếp sao cho i1 < i2 <. < ip ; thì AI(x) , bI(x) sẽ biểu thị ma trận con của A với các hàng Ai1 ,. , Aip và vectơ con của b với các thành phần lần lượt là bi1 ,. Với mọi y ∈ Rm , xác định y+ ∈ Rm bởi (y+ )i = max {yi , 0}.
Áp dụng cho (Ai x − bi )+ ta có: (Ai x − bi )+ = max {Ai x − bi , 0}. Công thức này có nghĩa rằng nếu Ai x ≤ bi , thì (Ai x − bi )+ sẽ bằng 0; ngược lại, nếu Ai x > bi , thì (Ai x − bi )+ sẽ bằng Ai x − bi. Hệ bất phương trình tuyến tính theo nghĩa bình phương nhỏ nhất Hệ bất phương trình tuyến tính theo nghĩa bình phương nhỏ nhất có nghĩa là tìm vec-tơ x sao cho tổng bình phương của sai số giữa các bất phương trình và các giá trị thực là nhỏ nhất. Hệ bất phương trình tuyến tính (1.1) theo nghĩa bình phương nhỏ nhất có dạng: 1 minn f (x) = ∥(Ax − b)+ ∥2 (1.3) x∈R 2 5 Với mục tiêu là tìm một vectơ x sao cho tổng bình phương của Ax − b đạt giá trị nhỏ nhất.
Nghiệm tối ưu của hệ theo nghĩa bình phương nhỏ nhất được định nghĩa là vec-tơ x∗ trong không gian Rn sao cho tổng bình phương của sai số giữa các bất phương trình và các giá trị thực tế là nhỏ nhất, tức là nghiệm của bài toán tối ưu sau: m X min (aTi x − bi )2+ (1.4) i=1 với x ∈ Rn , trong đó: x∗ là vec-tơ biến, ai là hàng thứ i của ma trận A, bi là thành phần thứ i của vec-tơ b. Nghiệm tối ưu x∗ là nghiệm mà tổng bình phương sai số là nhỏ nhất trong số tất cả các giải pháp có thể trong không gian Rn cho hệ bất phương trình tuyến tính đã cho. Sau đây, ta xem xét một số tính chất cơ bản của hệ bất phương trình tuyến tính mà sẽ được sử dụng trong đề án. Một vectơ x∗ ∈ Rn là một nghiệm tối ưu của bài toán quy hoạch bậc hai (1.1) khi và chỉ khi AT (Ax∗ − b)+ = 0.
Điều kiện cần: Nếu x∗ là nghiệm tối ưu, theo điều kiện KKT (Karush − Kuhn − Tucker), ta có: Tính khả thi: Ax∗ ≤ b 6 Đạo hàm Lagrange: ∇f (x∗ ) + AT λ = 0, ở đây λ là các biến Lagrange. Tính nón âm: λ ≥ 0 Sự bổ sung: λi (aTi x∗ − bi ) = 0, ∀i Ta có: λi aTi x∗ = λi bi ⇒ AT λ = AT (Ax∗ − b)+ Và do ∇f (x∗ ) + AT λ = 0, ta có: AT (Ax∗ − b)+ = 0 Điều kiện đủ: Giả sử AT (Ax∗ − b)+ = 0, ta cần chứng minh x∗ là nghiệm tối ưu. Đặt λ = (Ax∗ − b)+ , ta có: ∇f (x∗ ) + AT λ = 0 Điều này, cùng với các điều kiện khác của KKT, cho thấy x∗ là nghiệm tối ưu. Như vậy, mệnh đề đã được chứng minh.
Đối với mọi ma trận A ∈ Rm×n và vectơ b ∈ Rn , đều tồn tại nghiệm bình phương nhỏ nhất cho Ax ≤ b. Cuối cùng, ta lưu ý rằng gradient của f là hàm Lipschitz cấp 1 trên toàn cục, với hằng số Lipschitz là ∥A∥2. ∥∇f (x) − ∇f (y)∥ ≤ ∥A∥2 ∥x − y∥, với mọi x, y ∈ Rn. Để chứng minh mệnh đề này, ta sẽ sử dụng bất đẳng thức Cauchy − Schwarz và một số thuộc tính của đạo hàm.
Bắt đầu với bất đẳng thức Cauchy − Schwarz, ta có: |⟨u, v⟩| ≤ ∥u∥∥v∥ với mọi u, v ∈ Rn 7 Áp dụng bất đẳng thức Cauchy − Schwarz cho ∇f (x) − ∇f (y) và x − y, ta có: |⟨∇f (x) − ∇f (y), x − y⟩| ≤ ∥∇f (x) − ∇f (y)∥∥x − y∥ Bây giờ, ta cần xem xét ⟨∇f (x) − ∇f (y), x − y⟩. Sử dụng định nghĩa của đạo hàm, ta có: f (x + t(x − y)) − f (x) ∇f (x) = lim t→0 t f (y + t(x − y)) − f (y) ∇f (y) = lim t→0 t Do đó, f (x + t(x − y)) − f (x) f (y + t(x − y)) − f (y) ⟨∇f (x) − ∇f (y), x − y⟩ = ⟨lim − lim , x − y⟩ t→0 t t→0 t f (x + t(x − y)) − f (x) f (y + t(x − y)) − f (y) = lim⟨ − , x − y⟩ t→0 t t f (x + t(x − y)) − f (x) f (y + t(x − y)) − f (y) = lim · (x − y) − · (x − y) t→0 t t = ∇f (x) · (x − y) − ∇f (y) · (x − y). Quay trở lại bất đẳng thức Cauchy-Schwarz: |⟨∇f (x) − ∇f (y), x − y⟩| ≤ ∥∇f (x) − ∇f (y)∥∥x − y∥ Áp dụng kết quả tính toán trước đó, ta có: |∇f (x) · (x − y) − ∇f (y) · (x − y)| ≤ ∥∇f (x) − ∇f (y)∥∥x − y∥ Giờ ta cần ước lượng ∥∇f (x) · (x − y) − ∇f (y) · (x − y)|. Sử dụng bất đẳng thức tam 8 giác, ta có: ∥∇f (x) · (x − y) − ∇f (y) · (x − y)∥ ≤ ∥∇f (x) · (x − y)∥ + ∥∇f (y) · (x − y)∥ = |∇f (x) · (x − y)| + |∇f (y) · (x − y)| ≤ ∥∇f (x)∥∥x − y∥ + ∥∇f (y)∥∥x − y∥ Tổng cộng, ta có: ∥∇f (x) − ∇f (y)∥∥x − y∥ ≥ |∇f (x) · (x − y) − ∇f (y) · (x − y)| ≥ 0 Do đó, ta có: ∥∇f (x) − ∇f (y)∥∥x − y∥ ≥ 0 Với điều kiện rõ ràng là ∥x − y∥ ≥ 0.
Bây giờ, ta chia cả hai vế cho ∥x − y∥ (điều này hợp lệ vì ∥x − y∥ > 0 khi x ̸= y), ta được: ∥∇f (x) − ∇f (y)∥ ≤ ∥A∥2 ∥x − y∥ Vậy chúng ta đã chứng minh Mệnh đề 1.2 Bài toán quy hoạch toàn phương Bài toán quy hoạch toàn phương là một loại bài toán tối ưu hóa, trong đó hàm mục tiêu là một hàm bậc hai và chứa biến không âm s như sau: 1 minn ∥Ax − b + s∥2 x∈R 2 với s ≥ 0. Ma trận giả nghịch đảo Một ma trận giả nghịch đảo A† của một ma trận A có kích thước m × n là một ma trận có các tính chất của ma trận nghịch đảo của A nhưng không nhất thiết là ma trận nghịch đảo chính xác. Công thức biểu diễn ma trận giả nghịch đảo như sau: A† = lim AT (AAT )k A k→∞ hoặc A† = lim A(AT A)k AT k→∞ trong đó, AT là ma trận chuyển vị của A, và (AAT )k và (AT A)k là lũy thừa bậc k của các ma trận tích AAT và AT A. Ma trận giả nghịch đảo không phải luôn tồn tại.
Nếu tồn tại, nó không duy nhất. Một số phương pháp tính ma trận giả nghịch đảo bao gồm phân rã giá trị suy biến SVD (Singular Value Decomposition) hoặc các phương pháp số khác. Phân rã giá trị suy biến SVD Định nghĩa 1. Phân rã giá trị suy biến SVD của A có dạng: A = U ΣV T , trong đó U là ma trận cột trực giao (m × m), 10 Σ là ma trận đường chéo (m × n) có các giá trị suy biến không âm trên đường chéo, V T là ma trận hàng trực giao chuyển vị (n × n).
Giả nghịch đảo Moore–Penrose Một giả nghịch đảo Moore − Penrose A† của một ma trận A có kích thước m × n là một ma trận có kích thước n × m thỏa mãn bốn đẳng thức sau: AA† A = A A† AA† = A† (AA† )T = AA† (A† A)T = A† A Định nghĩa 1. Công thức biểu diễn giả nghịch đảo Moore − Penrose như sau: A† = V Σ† U T , trong đó U , Σ và V là các ma trận thu được từ phân tích giá trị suy biến của A, Σ† là ma trận chéo có các phần tử bằng nghịch đảo của các phần tử khác không trên đường chéo của Σ. Ma trận giả nghịch đảo Moore − Penrose luôn tồn tại cho mọi ma trận A, không phụ thuộc vào hạng của A.4 Không gian vec-tơ Euclide 1. Bất đẳng thức Cauchy - Schwarz Định nghĩa 1.
Trong không gian Euclide Rn , cho hai vec-tơ x và y, bất đẳng thức Cauchy - Schwarz được biểu diễn như sau: |⟨x, y⟩| ≤ ∥x∥ · ∥y∥, trong đó: ⟨x, y⟩ là tích vô hướng Euclide giữa hai vec-tơ x và y, ∥x∥ là chuẩn Euclide của vec-tơ x, ∥y∥ là chuẩn Euclide của vec-tơ y. Bất đẳng thức Cauchy - Schwarz đề cập đến sự tương quan giữa các vec-tơ trong không gian Euclide và thể hiện rằng tích vô hướng của chúng không thể lớn hơn tích của chuẩn Euclide của mỗi vec-tơ. Phép chiếu Giả sử v và u là hai vec-tơ trong không gian Euclide.