Thuật toán tối ưu là gì? Các nghiên cứu khoa học liên quan

Thuật toán tối ưu (tiếng Anh: optimization algorithm) là quy trình tính toán có hệ thống nhằm tìm kiếm giá trị đầu vào tối ưu từ một tập hợp các phương án khả thi, sao cho một hoặc nhiều hàm mục tiêu đạt giá trị cực trị (cực tiểu hoặc cực đại) dưới những điều kiện ràng buộc xác định.

Đây là nền tảng cốt lõi trong toán học ứng dụng, khoa học máy tính, nghiên cứu vận hành, tài chính định lượng và học máy. Việc lựa chọn thuật toán phù hợp với từng lớp bài toán cụ thể có ý nghĩa quyết định đến tốc độ hội tụ, hiệu quả sử dụng tài nguyên tính toán và độ chính xác của nghiệm.

Trong dạng tổng quát nhất, bài toán tối ưu hóa không ràng buộc được biểu diễn như sau:

$\min_{x \in \mathbb{R}^n} f(x)$

Trong đó:

• $x \in \mathbb{R}^n$: vector biến quyết định trong không gian thực $n$ chiều
• $f(x)$: hàm mục tiêu cần tối ưu hóa

Tùy vào mục tiêu cụ thể, bài toán tìm cực đại có thể chuyển đổi tương đương sang bài toán tìm cực tiểu bằng cách tối thiểu hóa hàm $-f(x)$. Trong thực tế, nhiều bài toán kỹ thuật và kinh tế đi kèm các điều kiện ràng buộc dạng đẳng thức hoặc bất đẳng thức, đòi hỏi các không gian tìm kiếm nghiệm phức tạp hơn.

Phân loại thuật toán tối ưu

Các thuật toán tối ưu được phân loại dựa trên bản chất toán học của bài toán, cấu trúc không gian nghiệm và chiến lược tìm kiếm:

• Theo tính chất biến số: Tối ưu liên tục (biến số thực) và tối ưu rời rạc hoặc tổ hợp (biến số nguyên, đồ thị, hoán vị).
• Theo khả năng khả vi: Thuật toán dựa trên đạo hàm (gradient-based) và thuật toán không dùng đạo hàm (derivative-free hoặc black-box).
• Theo tính tất định: Thuật toán tất định (deterministic) luôn cho cùng kết quả với cùng điểm khởi đầu và thuật toán ngẫu nhiên (stochastic) tích hợp yếu tố xác suất.
• Theo phạm vi nghiệm: Tối ưu cục bộ (tìm cực trị địa phương gần điểm bắt đầu) và tối ưu toàn cục (tìm giá trị tối ưu trên toàn miền xác định).

Nhóm bài toán	Thuật toán tiêu biểu	Đặc điểm chính
Tối ưu liên tục khả vi	Gradient Descent, Newton's Method, Quasi-Newton (BFGS)	Khai thác đạo hàm bậc một và bậc hai, hội tụ nhanh trên các hàm lồi
Tối ưu rời rạc và tổ hợp	Branch and Bound, Genetic Algorithm, Simulated Annealing	Không đòi hỏi tính khả vi, áp dụng cho không gian trạng thái tổ hợp quy mô lớn
Tối ưu toàn cục hộp đen	Bayesian Optimization, Particle Swarm Optimization	Thích hợp cho hàm mục tiêu đắt đỏ về chi phí tính toán, phi lồi và nhiều cực tiểu địa phương

Tối ưu không ràng buộc và có ràng buộc

Tùy thuộc vào điều kiện xác định của tập nghiệm khả thi, bài toán tối ưu được phân chia thành dạng không ràng buộc và có ràng buộc. Đối với tối ưu không ràng buộc, miền tìm kiếm bao phủ toàn bộ không gian biến thực. Đối với tối ưu có ràng buộc, nghiệm phải thỏa mãn đồng thời các điều kiện biên:

$\begin{aligned} \min_{x \in \mathbb{R}^n} \quad & f(x) \\ \text{subject to} \quad & g_i(x) \leq 0,\quad i=1,\dots,m \\ & h_j(x) = 0,\quad j=1,\dots,p \end{aligned}$

Trong đó:

• $g_i(x)$: các hàm ràng buộc bất đẳng thức
• $h_j(x)$: các hàm ràng buộc đẳng thức

Để giải lớp bài toán này, các phương pháp kinh điển bao gồm điều kiện tối ưu Karush-Kuhn-Tucker (KKT), phương pháp nhân tử Lagrange, hàm phạt (penalty methods), phương pháp rào cản (barrier methods), phương pháp điểm nội (interior-point methods) và quy hoạch toàn phương tuần tự (Sequential Quadratic Programming - SQP).

Thuật toán tối ưu lồi

Tối ưu hóa lồi là phân ngành đặc biệt quan trọng, trong đó hàm mục tiêu là hàm lồi và tập ràng buộc khả thi là tập lồi. Tính chất này mang lại ưu thế lý thuyết vượt trội: mọi cực tiểu cục bộ đều đồng thời là cực tiểu toàn cục, giúp loại bỏ hoàn toàn rủi ro bị bẫy trong các điểm cực trị không tối ưu.

Nhiều thuật toán hiệu quả được thiết kế riêng cho bài toán lồi, đạt được tốc độ hội tụ đa thức, bao gồm phương pháp gradient chiếu, phương pháp dưới gradient (subgradient method) và phương pháp điểm nội. Một ví dụ tiêu biểu trong học máy là bài toán hồi quy Ridge:

$\min_{w} \left\| Xw - y \right\|_2^2 + \lambda \left\| w \right\|_2^2$

Hàm mục tiêu trên là lồi chặt khi tham số điều hòa dương, đảm bảo tồn tại nghiệm duy nhất và có thể giải chính xác bằng hệ phương trình chuẩn tắc hoặc các thuật toán lặp hội tụ nhanh.

Thuật toán tối ưu phi lồi

Tối ưu phi lồi bao gồm các bài toán mà hàm mục tiêu hoặc miền khả thi không thỏa mãn tính chất lồi. Không gian tìm kiếm của bài toán phi lồi thường phức tạp với nhiều cực tiểu địa phương, cực đại địa phương và điểm yên ngựa (saddle points), khiến việc bảo đảm tìm được nghiệm tối ưu toàn cục trở thành thách thức lớn về mặt tính toán.

Trong các mô hình mạng nơ-ron học sâu, hàm mất mát là hàm phi lồi nhiều chiều. Để vượt qua các điểm yên ngựa và thoát khỏi các cực tiểu địa phương chất lượng kém, các kỹ thuật tối ưu hóa phi lồi thường áp dụng khởi tạo ngẫu nhiên nhiều lần (multi-start), thêm nhiễu ngẫu nhiên vào gradient hoặc sử dụng các giải thuật heuristic và metaheuristic.

Thuật toán tối ưu trong học sâu

Trong học máy và học sâu, quá trình huấn luyện mô hình thực chất là việc giải bài toán tối ưu hóa quy mô lớn trên tập dữ liệu mẫu. Thuật toán gradient descent cơ bản cập nhật vector trọng số theo chiều ngược với hướng của vector gradient:

$\theta_{t+1} = \theta_t - \eta \nabla_\theta \mathcal{L}(\theta_t)$

Trong đó:

• $\theta_t$: vector trọng số tham số tại bước lặp $t$
• $\eta$: tốc độ học (learning rate)
• $\mathcal{L}$: hàm mất mát (loss function)

Trên tập dữ liệu lớn, phương pháp Gradient Descent ngẫu nhiên (Stochastic Gradient Descent - SGD) theo từng lô nhỏ (mini-batch) giúp giảm mạnh chi phí tính toán cho mỗi bước lặp. Các biến thể hiện đại như Momentum, RMSprop và Adam kết hợp động lượng cùng cơ chế tự điều chỉnh tốc độ học thích ứng theo từng chiều tham số, hỗ trợ quá trình huấn luyện mạng nơ-ron sâu đạt hiệu năng vượt trội.

Thuật toán tối ưu rời rạc và tổ hợp

Tối ưu tổ hợp tập trung vào việc tìm kiếm phương án tối ưu trong một tập hợp hữu hạn nhưng có số lượng phần tử bùng nổ tổ hợp. Do không thể áp dụng phép tính vi tích phân, các bài toán nổi tiếng như người du lịch (TSP), xếp ba lô (Knapsack Problem) hay lập lịch công việc (Job Scheduling) thường được tiếp cận qua hai hướng:

• Thuật toán chính xác: Duyệt nhánh và cận (Branch and Bound), quy hoạch động (Dynamic Programming), cho nghiệm tối ưu tuyệt đối nhưng độ phức tạp tăng theo hàm mũ trong trường hợp xấu nhất đối với bài toán NP-khó.
• Thuật toán xấp xỉ và Heuristic: Thuật toán tham lam (Greedy), tìm kiếm cục bộ (Local Search), cùng các metaheuristic phỏng sinh học như giải thuật di truyền (Genetic Algorithm), tối ưu bầy đàn (Particle Swarm Optimization) và mô phỏng tôi luyện (Simulated Annealing) nhằm tìm lời giải cận tối ưu trong thời gian thực thi chấp nhận được.

Tiêu chí đánh giá hiệu năng thuật toán

Hiệu quả của một thuật toán tối ưu được đánh giá toàn diện dựa trên các chỉ số kỹ thuật:

• Tốc độ hội tụ: Số lượng bước lặp hoặc số lần đánh giá hàm mục tiêu cần thiết để đạt ngưỡng sai số cho phép (hội tụ tuyến tính, siêu tuyến tính hoặc bậc hai).
• Chi phí tính toán: Khối lượng phép tính dấu phẩy động và dung lượng bộ nhớ yêu cầu tại mỗi bước lặp.
• Độ bền vững: Khả năng duy trì hiệu quả khi hàm mục tiêu bị nhiễu, điểm khởi tạo ở xa nghiệm hoặc dữ liệu đầu vào chứa sai số đo lường.
• Độ chính xác nghiệm: Khoảng cách từ nghiệm tìm được tới điểm cực trị lý thuyết hoặc giá trị chênh lệch của hàm mục tiêu.

Ứng dụng thực tiễn

Thuật toán tối ưu là công cụ tính toán nền tảng xuất hiện trong hầu hết các ngành khoa học và công nghệ hiện đại. Trong giao thông vận tải và logistics, các thuật toán định tuyến giúp tối ưu hóa mạng lưới cung ứng và giảm chi phí nhiên liệu. Trong kinh tế và tài chính định lượng, các mô hình quy hoạch bậc hai tối ưu hóa danh mục đầu tư theo lý thuyết Markowitz. Trong kỹ thuật cơ khí và xây dựng, tối ưu hóa hình học kết cấu giúp giảm trọng lượng vật liệu mà vẫn bảo đảm khả năng chịu lực an toàn.