Dạng hàm số
Một bài toán tối ưu hóa là một bài toán có dạng
$$ p^* := \displaystyle\min_x : f_0(x) \mbox{ với điều kiện } f_i(x) \le 0, \;\; i=1,\ldots, m , $$
trong đó
- $x \in {\mathbb{R}}^n$ là biến quyết định;
- $f_0 : {\mathbb{R}}^n \rightarrow {\mathbb{R}}$ là hàm mục tiêu, hay hàm chi phí;
- $f_i : {\mathbb{R}}^n \rightarrow {\mathbb{R}}, i=1,\ldots,m$ biểu diễn các ràng buộc;
- $p^*$ là giá trị tối ưu.
Trong biểu thức trên, cụm từ “với điều kiện” đôi khi được thay thế bằng ký hiệu dấu hai chấm.
Thường thì bài toán trên được gọi là một “lập trình toán học”. Thuật ngữ “lập trình” (hay “chương trình”) không ám chỉ một mã máy tính. Nó được sử dụng chủ yếu vì lý do lịch sử. Chúng ta sẽ sử dụng thuật ngữ chặt chẽ hơn (nhưng ít phổ biến hơn) là “bài toán tối ưu hóa”.
Ví dụ: Một bài toán tối ưu hóa hai biến.
Dạng epigraph
Trong tối ưu hóa, ta luôn có thể giả định rằng hàm mục tiêu là một hàm tuyến tính của các biến. Điều này có thể được thực hiện thông qua biểu diễn epigraph của bài toán, vốn dựa trên việc thêm một biến vô hướng mới [latex]t[/latex]:
$$ p^* = \displaystyle\min_{x,t} : t \mbox{ subject to } f_0(x)-t\le 0, \;\; f_i(x) \le 0, \;\; i=1,\ldots, m . $$
Tại điểm tối ưu, [latex]t=p^*[/latex]. Trong biểu thức trên, hàm mục tiêu là [latex]\tilde{f}_0 : \mathbb{R}^{n+1} \rightarrow \mathbb{R}[/latex], với các giá trị [latex]\tilde{f}_0 (x,t) = t[/latex].
Ta có thể hình dung điều này như sau. Xét các tập mức dưới của hàm mục tiêu, có dạng [latex]\{ x : t \ge f_0(x) \}[/latex] với một giá trị [latex]t \in \mathbb{R}[/latex] nào đó. Bài toán tương đương với việc tìm giá trị [latex]t[/latex] nhỏ nhất sao cho tập mức dưới tương ứng giao với tập các điểm thỏa mãn các ràng buộc.
Ví dụ: Góc nhìn hình học về bài toán tối ưu hóa hai biến..
Các dạng chuẩn khác
Đôi khi ta tách riêng các ràng buộc đẳng thức, nếu có:
$$\min_x : f_0(x) \mbox{ subject to } h_i(x) = 0, \;\; i=1,\ldots,p, \;\; f_i(x) \le 0, \;\; i=1,\ldots, m,$$
trong đó các hàm [latex]h_i[/latex] là cho trước. Dĩ nhiên, ta có thể quy bài toán trên về dạng chuẩn ở trên, bằng cách biểu diễn mỗi ràng buộc đẳng thức bằng một cặp bất đẳng thức.
Đôi khi, các ràng buộc được mô tả một cách trừu tượng thông qua một điều kiện tập hợp, có dạng [latex]x \in \mathbf{X}[/latex] với một tập con [latex]\mathbf{X}[/latex] nào đó của [latex]\mathbb{R}^n[/latex]. Ký hiệu tương ứng là
$$\displaystyle\min_{x \in \mathbf{X}} : f_0(x)$$
Một số bài toán có dạng bài toán tối đa hóa. Các bài toán như vậy có thể dễ dàng được đưa về dạng chuẩn thông qua biểu thức
[latex]\displaystyle\max_{x \in \mathbf{X}} f_0(x) = -\displaystyle\min_{x \in \mathbf{X}} g_0(x),[/latex]
trong đó $g_0 := -f_0$.
