Xét bài toán tối ưu hóa
\[ (P) \quad \min_x f_0(x): f_i(x) \leq 0, \quad i=1, \ldots, m. \]
Tập khả thi
Tập khả thi của bài toán \(P\) được định nghĩa là
\[ \mathbf{X}:=\left\{x \in \mathbb{R}^n: f_i(x) \leq 0, \quad i=1, \ldots, m\right\} . \]
Một điểm [latex]x[/latex] được gọi là khả thi cho bài toán \(P\) nếu nó thuộc tập khả thi [latex]\mathbf{X}[/latex], tức là nó thỏa mãn các ràng buộc.
Example: Trong bài toán tối ưu đồ chơi, tập khả thi là “hình hộp” trong [latex]\mathbb{R}^2[/latex], được mô tả bởi [latex]-1 \leq x_1 \leq 2, 0 \leq x_2 \leq 3[/latex].
Tập khả thi có thể rỗng nếu các ràng buộc không thể được thỏa mãn đồng thời. Trong trường hợp này, bài toán được gọi là không khả thi.
Nghiệm là gì?
Trong một bài toán tối ưu hóa, ta thường quan tâm đến việc tính toán giá trị tối ưu của hàm mục tiêu, và cũng thường là một phần tử tối thiểu hóa, là một véctơ đạt được giá trị đó, nếu có.
Bài toán tìm điểm khả thi
Đôi khi một hàm mục tiêu không được cung cấp. Điều này có nghĩa là ta chỉ quan tâm đến việc tìm một điểm khả thi, hoặc xác định rằng bài toán là không khả thi. Theo quy ước, ta đặt [latex]f_0[/latex] là một hằng số trong trường hợp đó, để phản ánh thực tế rằng ta không quan tâm đến việc lựa chọn một điểm [latex]x[/latex] miễn là nó khả thi.
Giá trị tối ưu
Giá trị tối ưu của bài toán là giá trị của hàm mục tiêu tại điểm tối ưu, và ta ký hiệu nó là [latex]p^*[/latex]:
\[ p^*:=\min_x f_0(x): f_i(x) \leq 0, \quad i=1, \ldots, m . \]
Ví dụ: Trong bài toán tối ưu đồ chơi, giá trị tối ưu là [latex]p^*=-10.2667[/latex].
Tập tối ưu
Tập tối ưu (hay, tập nghiệm) của bài toán (P) được định nghĩa là tập hợp các điểm khả thi mà tại đó hàm mục tiêu đạt được giá trị tối ưu:
[latex]\mathbf{X}^{\text{opt}}:=\left\{x \in \mathbf{X}: f_0(x)=p^*\right\}.[/latex]
Ta quy ước rằng tập tối ưu là rỗng nếu bài toán không khả thi.
Một ký hiệu chuẩn cho tập tối ưu là thông qua ký hiệu argmin:
\[ \mathbf{X}^{\text{opt}}=\arg\min_{x \in \mathbf{X}} f_0(x) . \]
Một điểm [latex]x[/latex] được gọi là tối ưu nếu nó thuộc tập tối ưu. Các điểm tối ưu có thể không tồn tại, và tập tối ưu có thể rỗng. Điều này có thể là do bài toán không khả thi. Hoặc, nó có thể là do giá trị tối ưu chỉ đạt được ở giới hạn.
Ví dụ: Bài toán
\[ \min_x e^{-x} \]
không có điểm tối ưu, vì giá trị tối ưu [latex]p^*=0[/latex] chỉ đạt được ở giới hạn khi [latex]x \rightarrow +\infty[/latex].
Nếu tập tối ưu không rỗng, ta nói rằng bài toán là khả thi.
Tính dưới tối ưu
Tập [latex]\epsilon[/latex]-dưới tối ưu được định nghĩa là
[latex]\mathbf{X}_\epsilon:=\left\{x \in \mathbf{X}: f_0(x) \leq p^*+\epsilon\right\} .[/latex]
(Với ký hiệu của chúng ta, [latex]\mathbf{X}_0=\mathbf{X}_{\text{opt}}[/latex].) Bất kỳ điểm nào trong tập [latex]\epsilon[/latex]-dưới tối ưu đều được gọi là [latex]\epsilon[/latex]-dưới tối ưu.
Tập hợp này cho phép đặc trưng hóa các điểm gần với điểm tối ưu (khi [latex]\epsilon[/latex] nhỏ). Thông thường, các thuật toán thực tế chỉ có thể tính toán các nghiệm dưới tối ưu, và không bao giờ đạt đến điểm tối ưu thực sự.
Ví dụ: Thuật ngữ của bài toán đồ chơi hai chiều.
Cực tiểu địa phương và cực tiểu toàn cục
Một điểm [latex]z[/latex] là cực tiểu địa phương nếu có một giá trị [latex]R>0[/latex] sao cho [latex]z[/latex] là tối ưu cho bài toán
\[ \min_x f_0(x): f_i(x) \leq 0, \quad i=1, \ldots, m, \quad \| z-x\|_2 \leq R \]
Nói cách khác, một phần tử tối thiểu hóa địa phương [latex]x[/latex] tối thiểu hóa [latex]f_0[/latex], nhưng chỉ đối với các điểm lân cận trên tập khả thi. Vì vậy, giá trị của hàm mục tiêu không nhất thiết là giá trị tối ưu của bài toán.
Thuật ngữ cực tiểu toàn cục (hay, cực tiểu cho ngắn gọn) được sử dụng để phân biệt các điểm trong tập tối ưu với các cực tiểu địa phương.
Ví dụ: một hàm có các cực tiểu địa phương.
Nhiều thuật toán tối ưu có thể bị kẹt tại các cực tiểu địa phương, một tình huống thường được mô tả là một thách thức lớn trong các bài toán tối ưu hóa.
