Ý tưởng cốt lõi của thuật toán quy hoạch toàn phương tuần tự (SQP) là gì?

SQP giải bài toán tối ưu hóa phi tuyến có ràng buộc bằng cách giải lặp một chuỗi các bài toán con quy hoạch toàn phương (QP), trong đó hàm mục tiêu của bài toán con là xấp xỉ bậc hai của hàm Lagrange và các ràng buộc phi tuyến được tuyến tính hóa tại điểm lặp hiện tại.

Hiệu ứng Maratos là gì và vì sao cần bước hiệu chỉnh bậc hai (SOC)?

Hiệu ứng Maratos xảy ra khi một bước lặp đơn vị đầy đủ có xu hướng tiến gần nghiệm nhưng bị hàm đánh giá từ chối do vi phạm ràng buộc phi tuyến tăng nhẹ tỷ lệ với độ cong. Bước hiệu chỉnh bậc hai (SOC) tính thêm một vector phụ để uốn cong quỹ đạo về mặt khả thi, giúp bước lặp được chấp nhận và bảo toàn tốc độ hội tụ nhanh.

Khi nào nên ưu tiên dùng SQP thay vì phương pháp điểm trong (Interior-Point)?

SQP đặc biệt phù hợp cho các bài toán yêu cầu khởi động ấm thường xuyên như trong điều khiển dự báo mô hình (NMPC), hoặc khi chi phí đánh giá hàm mục tiêu và gradient rất tốn kém, vì SQP thường chỉ đòi hỏi tương đối ít số lần gọi hàm để đạt nghiệm chính xác.

Làm thế nào để ma trận xấp xỉ Hessian luôn xác định dương trong SQP?

Thuật toán thường áp dụng công thức cập nhật damped BFGS của Powell (1978). Khi điều kiện cong bị vi phạm do độ cong của ràng buộc, hệ số suy giảm sẽ biến đổi vector gradient sai phân thành tổ hợp lồi với ma trận hiện tại, bảo đảm tích vô hướng luôn dương và duy trì tính xác định dương của ma trận xấp xỉ.

Thuật toán SQP là gì? Quy hoạch toàn phương tuần tự

Thuật toán SQP (quy hoạch toàn phương tuần tự, tiếng Anh: Sequential Quadratic Programming) là một phương pháp tối ưu hóa số phi tuyến lặp, giải các bài toán tối ưu hóa có ràng buộc phi tuyến bằng cách giải liên tiếp một chuỗi các bài toán quy hoạch toàn phương xấp xỉ, sử dụng xấp xỉ bậc hai của hàm Lagrange và tuyến tính hóa các ràng buộc tại mỗi bước lặp. Trong lý thuyết tối ưu hóa toán học, SQP được đánh giá là một trong những phương pháp tiêu biểu đối với các bài toán phi tuyến trơn có kích thước từ nhỏ đến lớn, nhờ khả năng đạt được tốc độ hội tụ tiệm cận siêu tuyến tính.

Cơ sở lý thuyết và dẫn xuất bài toán con quy hoạch toàn phương

Xem xét bài toán quy hoạch phi tuyến tổng quát trong không gian hữu hạn chiều:

\min_{x \in \mathbb{R}^n} f(x) \quad \text{s.t.} \quad c_i(x) = 0 \quad (i \in \mathcal{E}), \quad c_j(x) \ge 0 \quad (j \in \mathcal{I})

Trong đó $f: \mathbb{R}^n \rightarrow \mathbb{R}$ là hàm mục tiêu, $c_i(x)$ là các hàm ràng buộc đẳng thức biểu diễn tập chỉ số $\mathcal{E}$ , và $c_j(x)$ là các hàm ràng buộc bất đẳng thức biểu diễn tập chỉ số $\mathcal{I}$ . Hàm Lagrange liên kết với bài toán được định nghĩa:

\mathcal{L}(x, \lambda) = f(x) - \sum_{i \in \mathcal{E} \cup \mathcal{I}} \lambda_i c_i(x)

Ý tưởng nền tảng của SQP khởi nguồn từ việc áp dụng phương pháp Newton giải hệ điều kiện dừng Karush-Kuhn-Tucker (KKT) đối với bài toán có ràng buộc đẳng thức, sau đó mở rộng sang bài toán có ràng buộc bất đẳng thức. Tại mỗi bước lặp $x_k$ , thuật toán thiết lập một bài toán con quy hoạch toàn phương (QP subproblem) để tìm hướng dịch chuyển $d \in \mathbb{R}^n$ :

\min_{d \in \mathbb{R}^n} \nabla f(x_k)^T d + \frac{1}{2} d^T B_k d

thỏa mãn các ràng buộc tuyến tính hóa:

c_i(x_k) + \nabla c_i(x_k)^T d = 0 \quad (i \in \mathcal{E})

c_j(x_k) + \nabla c_j(x_k)^T d \ge 0 \quad (j \in \mathcal{I})

Ở đây, $B_k$ là ma trận đối xứng xác định dương đóng vai trò xấp xỉ ma trận Hessian của hàm Lagrange theo biến $x$ , ký hiệu là $\nabla_{xx}^2 \mathcal{L}(x_k, \lambda_k)$ . Nghiệm của bài toán con QP cung cấp hướng tìm kiếm $d_k$ , đồng thời các nhân tử Lagrange liên kết với các ràng buộc của bài toán con QP đóng vai trò là ước lượng trực tiếp cho vector nhân tử tối ưu $\lambda_{k+1}$ của bài toán gốc.

Xấp xỉ Quasi-Newton và công thức cập nhật BFGS sửa đổi của Powell

Trong thực tế tính toán, việc tính toán chính xác ma trận đạo hàm riêng bậc hai $\nabla_{xx}^2 \mathcal{L}(x_k, \lambda_k)$ đòi hỏi chi phí giải tích và thời gian xử lý lớn. Do đó, các thuật toán SQP thực hành thường áp dụng kỹ thuật Quasi-Newton để cập nhật ma trận xấp xỉ $B_k$ qua từng bước lặp mà chỉ cần dùng thông tin gradient bậc nhất.

Tuy nhiên, do sự hiện diện của các ràng buộc phi tuyến, ma trận Hessian thực sự của hàm Lagrange có thể không xác định dương trên toàn bộ không gian ngay cả ở lân cận nghiệm tối ưu. Nếu áp dụng công thức BFGS tiêu chuẩn, điều kiện cong $s_k^T y_k > 0$ (với $s_k = x_{k+1} - x_k$ và $y_k = \nabla_x \mathcal{L}(x_{k+1}, \lambda_{k+1}) - \nabla_x \mathcal{L}(x_k, \lambda_{k+1})$ ) có thể bị vi phạm, làm mất tính xác định dương của ma trận $B_{k+1}$ .

Vào năm 1978, M. J. D. Powell đã đề xuất công thức cập nhật BFGS sửa đổi (damped BFGS update) nhằm khắc phục hiện tượng này. Powell (1978) định nghĩa một vector biến đổi $r_k$ là tổ hợp tuyến tính lồi giữa vector sai phân gradient $y_k$ và tích $B_k s_k$ :

r_k = \theta_k y_k + (1 - \theta_k) B_k s_k

Trong đó hệ số suy giảm $\theta_k \in (0, 1]$ được xác định theo quy tắc ngưỡng:

\theta_k = \begin{cases} 1 & \text{nếu } s_k^T y_k \ge 0.2 \, s_k^T B_k s_k \\ \frac{0.8 \, s_k^T B_k s_k}{s_k^T B_k s_k - s_k^T y_k} & \text{nếu } s_k^T y_k < 0.2 \, s_k^T B_k s_k \end{cases}

Quy tắc này bảo đảm bất đẳng thức $s_k^T r_k \ge 0.2 \, s_k^T B_k s_k > 0$ luôn được duy trì một cách nghiêm ngặt. Ma trận xấp xỉ tại bước tiếp theo được cập nhật theo công thức:

B_{k+1} = B_k - \frac{B_k s_k s_k^T B_k}{s_k^T B_k s_k} + \frac{r_k r_k^T}{s_k^T r_k}

Nhờ cấu trúc này, ma trận $B_{k+1}$ luôn duy trì tính đối xứng xác định dương, bảo đảm bài toán con quy hoạch toàn phương luôn lồi và có nghiệm duy nhất.

Chiến lược hội tụ toàn cục và hàm đánh giá

Để đảm bảo thuật toán có thể hội tụ về nghiệm tối ưu cục bộ từ một điểm xuất phát bất kỳ ở xa nghiệm, SQP cần kết hợp một cơ chế toàn cục hóa (globalization strategy), thường là tìm kiếm theo đường (line search) hoặc vùng tin cậy (trust region), dựa trên một hàm đánh giá (merit function).

Nghiên cứu của S. P. Han vào năm 1977 đã thiết lập nền tảng lý thuyết cho việc toàn cục hóa thuật toán SQP bằng cách sử dụng hàm phạt chuẩn tắc L1 chính xác (exact L1 penalty function):

\phi_1(x; \mu) = f(x) + \mu \left( \sum_{i \in \mathcal{E}} |c_i(x)| + \sum_{j \in \mathcal{I}} \max(0, -c_j(x)) \right)

Han (1977) đã chứng minh rằng nếu tham số phạt $\mu$ tại bước lặp $k$ được chọn đủ lớn, cụ thể là lớn hơn chuẩn cực đại của vector nhân tử Lagrange thu được từ nghiệm của bài toán con QP tại bước hiện tại ( $\mu_k > \|\lambda_{k+1}\|_\infty$ ), thì nghiệm $d_k$ của bài toán con QP luôn là một hướng giảm ngặt của hàm đánh giá $\phi_1(x; \mu)$ . Thuật toán sau đó tìm độ dài bước lặp $\alpha_k \in (0, 1]$ thỏa mãn điều kiện giảm đủ Armijo để cập nhật điểm mới $x_{k+1} = x_k + \alpha_k d_k$ .

Hiệu ứng Maratos và bước hiệu chỉnh bậc hai

Một thách thức lý thuyết quan trọng phát sinh khi kết hợp SQP với hàm đánh giá là hiệu ứng Maratos. Hiện tượng này xảy ra khi một bước lặp đầy đủ $d_k$ (với $\alpha_k = 1$ ) mang lại bước tiến tốt về phía nghiệm tối ưu nhưng lại làm tăng nhẹ mức độ vi phạm ràng buộc phi tuyến tỷ lệ với bình phương độ dài bước lặp do độ cong của mặt ràng buộc. Kết quả là hàm đánh giá từ chối bước lặp đơn vị, buộc thuật toán phải thu nhỏ độ dài bước lặp và làm suy giảm tốc độ hội tụ tiệm cận siêu tuyến tính.

Trong khảo sát hệ thống vào năm 1995, Boggs và Tolle đã phân tích sâu sắc bản chất giải tích của hiệu ứng Maratos và các phương pháp xử lý chuẩn mực. Giải pháp tiêu biểu nhất là kỹ thuật hiệu chỉnh bậc hai (Second-Order Correction - SOC). Sau khi tính được hướng chính $d_k$ , thuật toán giải thêm một bài toán con bổ sung để tìm vector hiệu chỉnh $\hat{d}_k$ :

c_i(x_k + d_k) + \nabla c_i(x_k)^T \hat{d} = 0 \quad (i \in \mathcal{E})

Bước hiệu chỉnh $\hat{d}_k$ uốn cong quỹ đạo tìm kiếm quay trở lại bề mặt khả thi phi tuyến, giúp hàm đánh giá chấp nhận bước lặp kép $d_k + \hat{d}_k$ với độ dài bước lặp bằng đơn vị, bảo toàn tốc độ hội tụ nhanh của thuật toán.

Đặc tính hội tụ và phân tích tiệm cận

Tốc độ hội tụ của thuật toán SQP phụ thuộc vào độ chính xác của xấp xỉ ma trận Hessian:

Thuật toán Newton SQP: Khi ma trận Hessian thực sự của hàm Lagrange $\nabla_{xx}^2 \mathcal{L}(x_k, \lambda_k)$ được tính toán chính xác tại mỗi bước lặp, thuật toán đạt tốc độ hội tụ bậc hai cục bộ ở lân cận nghiệm KKT thỏa mãn điều kiện đủ bậc hai (Boggs và Tolle, 1995).
Thuật toán Quasi-Newton SQP: Khi sử dụng ma trận xấp xỉ $B_k$ cập nhật bằng công thức damped BFGS của Powell (1978), thuật toán đạt tốc độ hội tụ siêu tuyến tính cục bộ nếu thỏa mãn điều kiện Dennis-Moré mở rộng trên không gian con không gian rỗng của ma trận Jacobian các ràng buộc tích cực. Đáng chú ý, lý thuyết giải tích số chỉ ra rằng ma trận $B_k$ không cần hội tụ về ma trận Hessian thực sự trên toàn không gian để đảm bảo tốc độ hội tụ siêu tuyến tính này.

Tối ưu hóa quy mô lớn và phần mềm SNOPT

Khi áp dụng SQP cho các bài toán công nghiệp quy mô lớn, việc lưu trữ và phân rã các ma trận dày đặc trở nên không khả thi. Vào năm 2002, Philip E. Gill, Walter Murray và Michael A. Saunders đã công bố gói phần mềm SNOPT trên tạp chí SIAM Journal on Optimization, đánh dấu một bước tiến quan trọng trong việc triển khai SQP cho các bài toán tối ưu hóa ràng buộc phi tuyến quy mô lớn.

SNOPT kết hợp cấu trúc ma trận thưa, phương pháp không gian rỗng (null-space method), và kỹ thuật xấp xỉ Quasi-Newton bộ nhớ hữu hạn đối với ma trận Hessian rút gọn của hàm Lagrange. Bên cạnh đó, SNOPT sử dụng hàm đánh giá Lagrange mở rộng trơn (smooth augmented Lagrangian merit function), giúp nâng cao tính ổn định số học khi xử lý các ràng buộc bất khả thi cục bộ thông qua cơ chế quy hoạch đàn hồi (elastic programming).

So sánh SQP với các phương pháp quy hoạch phi tuyến khác

Bảng dưới đây tổng hợp các đặc tính so sánh giữa thuật toán SQP, phương pháp điểm trong (Interior-Point), và phương pháp Lagrange mở rộng (Augmented Lagrangian):

Tiêu chí so sánh	Thuật toán SQP	Phương pháp điểm trong (Interior-Point)	Phương pháp Lagrange mở rộng
Cơ chế xử lý ràng buộc	Tuyến tính hóa ràng buộc tại mỗi bước, giải bài toán con QP	Chuyển ràng buộc bất đẳng thức thành hàm phạt rào cản logarit	Đưa ràng buộc vào hàm mục tiêu kèm số hạng phạt bậc hai
Khả năng khởi động ấm (Warm-start)	Rất thuận lợi do duy trì tập tích cực giữa các lần giải kế tiếp	Khó khởi động ấm vì điểm bắt đầu phải nằm sâu trong miền khả thi	Trung bình, phụ thuộc vào ước lượng nhân tử Lagrange ban đầu
Số lần gọi hàm mục tiêu và gradient	Ít, phù hợp khi việc đánh giá hàm tốn kém chi phí tính toán	Trung bình, cần nhiều bước lặp rào cản khi tiến gần biên	Nhiều, do cần giải tối ưu hóa không ràng buộc ở vòng lặp trong
Khả năng mở rộng quy mô biến số	Phù hợp từ quy mô vừa đến lớn (với triển khai ma trận thưa SNOPT)	Rất mạnh cho các bài toán cực lớn nhờ cấu trúc hệ phương trình đối xứng	Tốt cho các bài toán có cấu trúc tách biến đặc thù
Tốc độ hội tụ tiệm cận	Siêu tuyến tính (Quasi-Newton) hoặc bậc hai (Newton SQP)	Siêu tuyến tính hoặc bậc hai cục bộ	Tuyến tính hoặc siêu tuyến tính bậc thấp

Ứng dụng nghiên cứu và triển khai thực tiễn

Thuật toán SQP được ứng dụng rộng rãi trong nhiều nhánh kỹ thuật tính toán và khoa học ứng dụng hiện đại:

Điều khiển dự báo mô hình phi tuyến (Nonlinear Model Predictive Control - NMPC): Nhờ khả năng khởi động ấm hiệu quả giữa các chu kỳ lấy mẫu liên tiếp, SQP là thuật toán trung tâm trong các bộ điều khiển tự động hóa cho hệ thống robot chuyển động, xe tự hành, và các quá trình công nghệ hóa chất.
Tối ưu hóa quỹ đạo hàng không vũ trụ: SQP được sử dụng để tính toán quỹ đạo phóng tên lửa, hạ cánh tàu vũ trụ, và đường bay tối ưu tiêu hao nhiên liệu tối thiểu của máy bay dân dụng.
Bài toán trào lưu công suất tối ưu (Optimal Power Flow - OPF): Trong kỹ thuật hệ thống điện, SQP được nghiên cứu để giải quyết bài toán vận hành kinh tế và phân bố trào lưu công suất trong lưới điện truyền tải có xét đến các giới hạn điện áp và công suất máy phát.
Nghiên cứu ứng dụng tại Việt Nam: Các nhà khoa học và kỹ sư tại các trường đại học kỹ thuật và viện nghiên cứu chuyên ngành ở Việt Nam đã ứng dụng thuật toán SQP vào việc mô phỏng quá trình truyền nhiệt, tối ưu hóa kết cấu công trình xây dựng, và phát triển các thuật toán điều khiển phi tuyến cho các hệ thống năng lượng tái tạo.

Đánh giá ưu điểm và hạn chế kỹ thuật

Việc lựa chọn thuật toán SQP cho các bài toán kỹ thuật cần cân nhắc các đặc điểm kỹ thuật sau:

Ưu điểm

Hiệu quả tính toán số lần gọi hàm: SQP đòi hỏi tương đối ít số lần đánh giá hàm mục tiêu và gradient để đạt được độ chính xác cao, đặc biệt có lợi thế khi hàm mục tiêu liên quan đến việc chạy các mô hình mô phỏng vật lý kéo dài.
Độ chính xác nghiệm: Nghiệm thu được thỏa mãn điều kiện KKT với dung sai số học nhỏ nhờ việc kết hợp thông tin độ cong bậc hai.
Xử lý linh hoạt cả ràng buộc đẳng thức và bất đẳng thức thông qua cơ chế nhận diện tập ràng buộc tích cực của bài toán con QP.

Hạn chế

Chi phí giải bài toán con QP: Ở các bài toán có ma trận dày đặc kích thước rất lớn, việc giải bài toán con QP tại mỗi bước lặp đòi hỏi khối lượng tính toán đại số tuyến tính đáng kể.
Khả năng không khả thi của bài toán con: Do việc tuyến tính hóa các ràng buộc phi tuyến, bài toán con QP tại một số bước lặp có thể rơi vào tình trạng vô nghiệm, đòi hỏi thuật toán phải tích hợp các cơ chế đàn hồi hoặc kỹ thuật biến phụ linh hoạt để khôi phục tính khả thi.