Bài toán bậc hai khác gì so với bài toán quy hoạch tuyến tính?

Bài toán quy hoạch tuyến tính có cả hàm mục tiêu và các ràng buộc đều là bậc một, trong khi bài toán bậc hai có hàm mục tiêu chứa số hạng bậc hai toàn phương, cho phép mô hình hóa độ cong và phương sai.

Khi nào bài toán bậc hai có nghiệm tối ưu toàn cục duy nhất?

Khi ma trận của các số hạng bậc hai là ma trận xác định dương nghiêm ngặt và miền nghiệm khả thi bị giới hạn bởi các ràng buộc lồi (tuyến tính), bài toán là lồi nghiêm ngặt và sở hữu nghiệm cực tiểu toàn cục duy nhất.

Tại sao bài toán bậc hai không lồi lại khó giải?

Khi ma trận bậc hai không xác định (có giá trị riêng âm), hàm mục tiêu có dạng hình yên ngựa xuất hiện nhiều cực tiểu cục bộ. Bài toán này đã được chứng minh là NP-hard, không thể tìm nghiệm toàn cục trong thời gian đa thức.

Bài toán bậc hai được ứng dụng như thế nào trong máy học?

Trong mô hình máy vector hỗ trợ (SVM), việc tìm siêu phẳng phân tách tối ưu với khoảng cách lề lớn nhất giữa các lớp dữ liệu được quy về giải một bài toán quy hoạch bậc hai lồi đối ngẫu.

Bài toán bậc hai là gì? Bản chất, thuật toán và ứng dụng

Bài toán bậc hai, thường được gọi là bài toán quy hoạch bậc hai trong lý thuyết tối ưu hóa toán học, là lớp bài toán tìm cực trị của một hàm mục tiêu đa thức bậc hai dưới các điều kiện ràng buộc tuyến tính (đẳng thức hoặc bất đẳng thức). Đây là một trong những nền tảng quan trọng nhất của toán học ứng dụng, nghiên cứu vận hành và khoa học tính toán, đóng vai trò cầu nối giữa bài toán quy hoạch tuyến tính và các bài toán tối ưu hóa phi tuyến phức tạp.

Dạng toán tổng quát và phân loại toán học

Trong đại số tuyến tính và tối ưu hóa toán học, một bài toán quy hoạch bậc hai tổng quát thường được biểu diễn dưới dạng tường minh với vector biến quyết định trong không gian Euclid nhiều chiều. Mục tiêu là tìm vector tối ưu nhằm cực tiểu hóa hoặc cực đại hóa giá trị hàm bậc hai trong miền chấp nhận được xác định bởi các phương trình và bất phương trình ràng buộc (Nocedal và Wright, 2006).

Mô hình toán học tiêu chuẩn

Dạng toán học tiêu chuẩn của bài toán quy hoạch bậc hai có ràng buộc tuyến tính được thiết lập như sau:

\min_{x} \quad f(x) = \frac{1}{2} x^T Q x + c^T x

Thỏa mãn các điều kiện ràng buộc:

A x \le b

E x = d

Trong đó:

$x$ là vector biến cần tìm gồm các thành phần thực.
$Q$ là ma trận thực đối xứng kích thước vuông đặc trưng cho phần bậc hai của hàm mục tiêu. Nếu ma trận ban đầu không đối xứng, nó luôn có thể được chuyển đổi thành ma trận đối xứng tương đương bằng phép lấy trung bình với ma trận chuyển vị mà không làm thay đổi giá trị của hàm mục tiêu.
$c$ là vector hệ số tuyến tính biểu diễn độ dốc bậc một.
$A$ và $E$ là các ma trận hệ số ràng buộc dạng bất đẳng thức và đẳng thức.
$b$ và $d$ là các vector vế phải giới hạn miền nghiệm khả thi.

Phân loại theo tính chất ma trận và hình học hàm mục tiêu

Hình học của hàm mục tiêu và tính chất tối ưu của bài toán phụ thuộc cốt lõi vào các giá trị riêng của ma trận bậc hai $Q$ (trong khi miền khả thi được định hình bởi hệ thống các ràng buộc tuyến tính):

Bài toán bậc hai lồi: Xảy ra khi ma trận $Q$ là ma trận nửa xác định dương, nghĩa là mọi giá trị riêng của ma trận đều không âm. Khi đó, hàm mục tiêu là hàm lồi trên toàn bộ không gian. Nếu miền khả thi là tập lồi (được giới hạn bởi các ràng buộc tuyến tính), bài toán trở thành bài toán tối ưu lồi. Bất kỳ điểm cực tiểu cục bộ nào cũng đồng thời là điểm cực tiểu toàn cục duy nhất hoặc thuộc tập nghiệm tối ưu toàn cục. Trường hợp ma trận $Q$ xác định dương nghiêm ngặt, hàm mục tiêu lồi nghiêm ngặt và nghiệm tối ưu là duy nhất.
Bài toán bậc hai không lồi: Xảy ra khi ma trận $Q$ là ma trận không xác định, có cả giá trị riêng dương và giá trị riêng âm, hoặc nửa xác định âm. Trong trường hợp này, đồ thị của hàm mục tiêu có hình yên ngựa hoặc lõm, dẫn tới sự xuất hiện của nhiều cực tiểu cục bộ rời rạc trong không gian nghiệm. Việc tìm kiếm cực tiểu toàn cục trở nên phức tạp hơn rất nhiều so với trường hợp lồi.
Bài toán bậc hai không ràng buộc: Khi không có bất kỳ ràng buộc đẳng thức hay bất đẳng thức nào, nếu ma trận xác định dương, điểm tối ưu được xác định trực tiếp bằng nghiệm của hệ phương trình đạo hàm triệt tiêu dạng đại số tuyến tính.

Điều kiện tối ưu Karush-Kuhn-Tucker

Lý thuyết tối ưu hóa cung cấp hệ thống điều kiện giải tích chặt chẽ để xác định điểm tối ưu của bài toán bậc hai có ràng buộc, được biết đến là hệ điều kiện Karush-Kuhn-Tucker (KKT). Theo phân tích chuẩn mực của Nocedal và Wright (2006), đối với lớp bài toán quy hoạch bậc hai lồi, hệ điều kiện KKT không chỉ là điều kiện cần mà còn là điều kiện đủ để một điểm khả thi đạt cực tiểu toàn cục.

Hàm Lagrange tương ứng với bài toán bậc hai có ràng buộc được xây dựng bằng cách nhân các hàm ràng buộc với vector nhân tử Lagrange:

\mathcal{L}(x, \lambda, \mu) = \frac{1}{2} x^T Q x + c^T x + \lambda^T (A x - b) + \mu^T (E x - d)

Hệ điều kiện tối ưu KKT bao gồm bốn nhóm quan hệ đại số:

Tính dừng: Gradient của hàm Lagrange theo biến quyết định phải triệt tiêu tại điểm cực trị:
$\nabla_x \mathcal{L} = Q x + c + A^T \lambda + E^T \mu = 0$
Tính khả thi nguyên thủy: Điểm nghiệm phải thỏa mãn đầy đủ các ràng buộc ban đầu của bài toán:
$A x \le b, \quad E x = d$
Tính khả thi đối ngẫu: Nhân tử Lagrange ứng với các ràng buộc bất đẳng thức phải không âm:
$\lambda \ge 0$
Độ bù bổ sung: Tích của từng nhân tử Lagrange với ràng buộc bất đẳng thức tương ứng phải bằng không:
$\lambda_i (A_i x - b_i) = 0$
với mọi chỉ số ràng buộc. Điều này có nghĩa là nếu một ràng buộc không tích cực (nghiệm nằm hoàn toàn bên trong miền cho phép), nhân tử Lagrange tương ứng bắt buộc phải bằng không.

Chiến lược và phương pháp giải thuật

Các phương pháp số học giải bài toán bậc hai đã phát triển mạnh mẽ và chia thành hai nhánh chiến lược chính được ghi nhận trong giáo trình chuẩn mực của Nocedal và Wright (2006): phương pháp tập hoạt động (active-set methods) và phương pháp điểm trong (interior-point methods).

Phương pháp tập hoạt động

Phương pháp tập hoạt động bắt nguồn từ ý tưởng coi các ràng buộc bất đẳng thức tích cực như các ràng buộc đẳng thức tạm thời. Tại mỗi bước lặp, thuật toán duy trì một tập hợp các ràng buộc đang hoạt động (active set). Bài toán lúc này được quy về việc giải một chuỗi các bài toán bậc hai chỉ có ràng buộc đẳng thức, vốn tương đương với việc giải một hệ phương trình đại số tuyến tính KKT.

Dựa trên nghiệm tạm thời và dấu của nhân tử Lagrange, thuật toán sẽ quyết định thêm một ràng buộc mới vào tập hoạt động hoặc loại bỏ một ràng buộc đang có. Phương pháp này đặc biệt hiệu quả đối với các bài toán có quy mô vừa và nhỏ, hoặc khi thuật toán cần khởi động ấm (warm-start) từ một nghiệm xấp xỉ đã biết trước, một đặc tính rất quan trọng trong điều khiển thời gian thực.

Phương pháp điểm trong

Phương pháp điểm trong tiếp cận bài toán bằng cách đi qua phần trong của miền khả thi thay vì men theo biên như các phương pháp tập hoạt động. Bằng cách kết hợp hàm phạt rào cản logarithmic cho các ràng buộc bất đẳng thức, thuật toán chuyển bài toán ràng buộc thành một chuỗi các bài toán tối ưu hóa trơn.

Họ thuật toán điểm trong nguyên thủy - đối ngẫu (primal-dual interior-point) áp dụng phương pháp lặp Newton để giải hệ phương trình phi tuyến KKT bị nhiễu bởi tham số rào cản. Nhờ tốc độ hội tụ nhanh và số bước lặp gần như không phụ thuộc vào kích thước của bài toán, phương pháp điểm trong là lựa chọn vượt trội cho các bài toán quy hoạch bậc hai lồi có quy mô lớn với hàng nghìn biến số.

Bảng dưới đây so sánh các đặc tính kỹ thuật cơ bản giữa hai họ thuật toán chủ đạo:

Đặc tính kỹ thuật	Phương pháp tập hoạt động	Phương pháp điểm trong
Quy mô bài toán phù hợp	Quy mô nhỏ đến vừa, ma trận dày hoặc thưa	Quy mô lớn đến rất lớn, ma trận thưa
Đặc điểm quỹ đạo lặp	Di chuyển trên biên của miền khả thi	Di chuyển qua phần trong của miền khả thi
Khả năng khởi động ấm	Rất tốt, tận dụng hiệu quả nghiệm từ bước trước	Kém thuận lợi hơn, đòi hỏi kỹ thuật khởi tạo phức tạp
Chi phí tính toán mỗi bước	Thấp, giải hệ phương trình tuyến tính kích thước nhỏ	Cao hơn, giải hệ phương trình KKT toàn phần
Độ tin cậy hội tụ	Hội tụ hữu hạn bước đối với bài toán lồi (với giả định không suy biến hoặc có cơ chế chống vòng lặp)	Hội tụ đa thức theo lý thuyết phức tạp tính toán

Độ phức tạp tính toán và tính chất NP-hard

Độ phức tạp tính toán của bài toán bậc hai có sự phân hóa sâu sắc dựa trên tính chất phổ giá trị riêng của ma trận hệ số:

Quy hoạch bậc hai lồi: Có thể giải được trong thời gian đa thức nhờ phương pháp elip (ellipsoid method) hoặc các thuật toán điểm trong nguyên thủy - đối ngẫu (primal-dual interior-point methods). Điều này đặt bài toán bậc hai lồi vào lớp bài toán tính toán hiệu quả tương tự như quy hoạch tuyến tính.
Quy hoạch bậc hai không lồi: Khi ma trận có giá trị riêng âm, bài toán trở thành bài toán tối ưu toàn cục không lồi. Nghiên cứu kinh điển của Pardalos và Vavasis (1991) đã chứng minh một kết quả nền tảng: bài toán quy hoạch bậc hai là bài toán NP-hard ngay cả khi ma trận bậc hai chỉ có duy nhất 1 giá trị riêng âm. Kết quả lý thuyết này chỉ ra rằng việc tìm nghiệm tối ưu toàn cục cho bài toán bậc hai tổng quát là thách thức tính toán rất lớn, không tồn tại thuật toán thời gian đa thức trừ khi lớp P bằng NP.

Ứng dụng tiêu biểu trong khoa học và kỹ thuật

Bài toán bậc hai không chỉ là một cấu trúc lý thuyết thuần túy mà là công cụ mô hình hóa cốt lõi trong nhiều ngành khoa học và công nghệ:

Tối ưu hóa danh mục đầu tư tài chính

Trong kinh tế học lượng hóa, Harry Markowitz đã công bố mô hình lựa chọn danh mục đầu tư vào năm 1952, đặt nền tảng cho lý thuyết danh mục hiện đại và mang lại cho ông giải thưởng Nobel Kinh tế. Mô hình Markowitz biểu diễn sự đánh đổi giữa lợi nhuận kỳ vọng và rủi ro danh mục:

Nhà đầu tư tìm cách cực tiểu hóa phương sai của lợi nhuận danh mục (được mô hình hóa bằng dạng toàn phương bậc hai của ma trận hiệp phương sai giữa các tài sản) dưới ràng buộc lợi nhuận kỳ vọng đạt mức tối thiểu và tổng tỷ trọng vốn bằng một. Đây chính xác là một bài toán quy hoạch bậc hai lồi với các ràng buộc tuyến tính, cho phép các định chế tài chính xác định đường biên hiệu quả để phân bổ vốn tối ưu.

Máy học và trí tuệ nhân tạo

Trong lĩnh vực máy học và nhận dạng mẫu, thuật toán máy vector hỗ trợ (Support Vector Machine - SVM) do Corinna Cortes và Vladimir Vapnik giới thiệu vào năm 1995 là một trong những thành tựu nổi bật dựa trên bài toán bậc hai. Việc tìm siêu phẳng phân tách tối ưu giữa hai lớp dữ liệu sao cho lề phân cách đạt cực đại dẫn thẳng tới bài toán quy hoạch bậc hai lồi đối ngẫu:

Hàm mục tiêu đối ngẫu là một dạng bậc hai phụ thuộc vào tích vô hướng giữa các vector mẫu trong không gian đặc trưng, được điều chỉnh bởi các ràng buộc hộp và ràng buộc đẳng thức tuyến tính. Nhờ tính chất lồi của bài toán bậc hai, việc huấn luyện máy vector hỗ trợ đảm bảo tìm được nghiệm phân loại tối ưu toàn cục mà không bị mắc kẹt tại các cực tiểu cục bộ.

Điều khiển dự báo mô hình trong kỹ nghệ tự động hóa

Trong kỹ thuật điều khiển tự động, điều khiển dự báo mô hình (Model Predictive Control - MPC) là phương pháp tiên tiến điều khiển các hệ thống công nghiệp phức tạp như nhà máy lọc hóa dầu, hệ thống hàng không và xe tự hành. Tại mỗi chu kỳ lấy mẫu, bộ điều khiển MPC giải một bài toán quy hoạch bậc hai theo thời gian thực để tìm chuỗi tín hiệu điều khiển tối ưu nhằm cực tiểu hóa sai số bám quỹ đạo bậc hai và năng lượng tiêu hao, đồng thời thỏa mãn các giới hạn vật lý nghiêm ngặt về điện áp, vận tốc và áp suất.

Quy hoạch bậc hai tuần tự trong tối ưu phi tuyến

Phương pháp quy hoạch bậc hai tuần tự (Sequential Quadratic Programming - SQP), được phát triển chuẩn mực trong giáo trình của Nocedal và Wright (2006), là một trong những phương pháp nền tảng và hiệu quả để giải các bài toán tối ưu phi tuyến tổng quát có ràng buộc. Tại mỗi bước lặp, thuật toán xấp xỉ hàm Lagrange bằng một dạng bậc hai và xấp xỉ tuyến tính các hàm ràng buộc, quy bài toán phi tuyến phức tạp về một chuỗi các bài toán quy hoạch bậc hai cục bộ dễ giải quyết hơn, kế thừa tốc độ hội tụ nhanh và tính ổn định số học cao.