Bài Toán Tối Ưu Hóa

Giới thiệu bài toán tối ưu

Một bài toán tối ưu có dạng chính tắc như sau: \<\begin{aligned}\mathrm{min.}~ & f_0(x) \label{eq:convexprob_obj} &\qquad \qquad \qquad (1)\\\mathrm{s.t.}~ & f_i(x) \leq 0, i = 1, \ldots, m &\qquad \qquad \qquad (2)\label{eq:convexprob_ineqcon}\\& h_i(x) = 0, i = 1, \ldots, p, &\qquad \qquad \qquad (3)\label{eq:convexprob_eqcon} \end{aligned}\> trong đó, \(x \in \mathbf{R}^n\) là biến của bài toán tối ưu, \(f_0\) là hàm mục tiêu,(2) và (3) là các ràng buộc.

Bạn đang xem: Bài toán tối ưu hóa

\(p^*\) được gọi là nghiệm tối ưu nếu \(p^* = \min \{f_0(x) | f_i(x) \leq 0, i = 1,\ldots,m, h_i(x) = 0, i = 1, \ldots, p\}\).

Miền xác định của bài toán được định nghĩa là giao của các miền xác định của tất cả các hàm trong bài toán \<\begin{aligned}\mathcal{D} = (\cap_{i=0}^m \rm{dom} f_i) \cap (\cap_{i=1}^p \rm{dom} h_i).\end{aligned}\> Miền khả thi của bài toán được định nghĩa là tập hợp các điểm thỏa mãn các ràng buộc \<\begin{aligned}\left\lbrace x | x \in \mathcal{D}; f_i(x) \leq 0, i = 1, \ldots, m; h_i(x) = 0, i = 1, \ldots, p \right\rbrace\end{aligned}\>

Nếu bài toán không có chặn dưới thì \(p^* = -\infty\) và nếu miền nghiệm là rỗng thì bài toán vô nghiệm (\(p^* = \infty\)).

\(x^*\) được gọi là điểm cực trị (hay vector cực trị) nếu \(x^*\) thuộc miền khả thi và \(f_0(x^*) = p^*\). Tập hợp tất các các điểm cực trị của bài toán thì được gọi là tập cực trị \<\begin{aligned}X_{opt} = \{ x | x \in \mathcal{D} ~ \mathrm{and} ~ f_0(x) = p^*\}\end{aligned}\>

Một vector \(x^*\) được gọi là vector cực trị cục bộ nếu tồn tại một số thực \(R\) dương đủ nhỏ sao cho \(f_0(x)\) đạt cực tiểu trong lân cận của \(x^*\) bán kính \(R\) \<\begin{aligned}f_0(x^*) = & \min \{f_0(z) | f_i(z) \leq 0, i = 1, \ldots, m, \\& h_i(z) = 0, i = 1, \ldots, p, \|z – x^* \|_2 \leq R \},\end{aligned}\>

Một số biến đổi bài toán tương đương

Hai bài toán tối ưu được gọi là tương đương nếu ta có thể suy ra dễ dàng nghiệm của một bài toán nếu có nghiệm của bài toán kia.

Ví dụ có một số bài toán tối ưu mà ràng buộc dạng chận trên và chận dưới đơn giản như sau \<\begin{aligned}\mathrm{min.}~ & f_0(x)\\\mathrm{s.t.}~ & l_i \leq x_i \leq u_i, i = 1, \ldots, n.\end{aligned}\> Ta có thể chuyển bài toán trên thành bài toán tối ưu dạng chính tắc như sau: \<\begin{aligned}\mathrm{min.}~ & f_0(x)\\\mathrm{s.t.}~ & l_i- x_i \leq 0, i = 1, \ldots, n\\& x_i – u_i \leq 0, i = 1, \ldots, n.\end{aligned}\>

Bài toán tìm cực đại

Đối với bài toán tìm cực đại \<\begin{aligned}\mathrm{max.} ~ & f_0(x)\\\mathrm{s.t.} ~ & f_i(x) \leq 0, i = 1, \ldots, m \\& h_i(x) = 0, i = 1, \ldots, p.\end{aligned}\> ta có thể chuyển bài toán trên về thành tìm cực tiểu \(- f_0(x)\).

Biến đổi các hàm mục tiêu và ràng buộc

Một bài toán có hàm mục tiêu và các ràng buộc được nhân với các hằng số cũng là bài toán tương đương với bài toán gốc \<\begin{aligned}\mathrm{min.} ~ & \tilde{f}(x) = \alpha_0 f_0(x)\\\mathrm{s.t} ~ & \tilde{f}_i (x) = \alpha_i f_i(x) \leq 0, i = 1, \ldots, m \\& \tilde{h}_i(x) = \beta_i h_i(x) = 0, i = 1, \ldots, p,\end{aligned}\> trong đó \(\alpha_i > 0, i=0, \ldots, m\) và \(\beta_i \neq 0, i=1, \ldots, p\).

Ta cũng có thể đổi biến \(x = \phi(z)\) để chuyển đổi bài toán tương đương miễn phép đổi biến \(\phi\) là ánh xạ một – một: \<\begin{aligned}\tilde{f}_i(z) = f_i(\phi(z)), i = 0, \ldots, m, \quad \tilde{h}_i(z) = h_i(\phi(z)), i = 0, \ldots, p.\end{aligned}\> Do đó bài toán tương đương có được là: \<\begin{aligned}\mathrm{min.}~ & \tilde{f}_0 (z) \\\mathrm{st.}~ & \tilde{f}_i (z) \leq 0, i = 1, \ldots, m \\& \tilde{h}_i(z) = 0, i = 1, \ldots, p\end{aligned}\>

Ta cũng có thể biến đổi tương đương các hàm mục tiêu và ràng buộc bằng các hàm riêng rẽ. Cho \(\psi_0: \mathbb{R}^n \rightarrow \mathbb{R}^n\) là hàm đơn điệu tăng, \(\psi_1, \ldots, \psi_m: \mathbb{R} \rightarrow \mathbb{R}\) thỏa mãn \(\psi_i(u) \leq 0\) nếu và chỉ nếu \(u \leq 0\), và \(\xi_1, \ldots, \xi_{p}: \mathbb{R} \rightarrow \mathbb{R}\) thoả mãn \(\xi_i(u) = 0\) nếu và chỉ nếu \(u = 0\). Định nghĩa các hàm số sau: \<\begin{aligned}\tilde{f}_i(x) &= \psi_i(f_i(x)), i = 0, \ldots, m, \\\tilde{h}_i(x) &= \xi_{i}(h_i(x)), i = 0, \ldots, p.\end{aligned}\> Ta có bài toán sau tương được với bài toán gốc (1)-(3) \<\begin{aligned}\mathrm{min.}~ & \tilde{f}_0 (x) \\\mathrm{s.t.}~ & \tilde{f}_i (x) \leq 0, i = 1, \ldots, m \\& \tilde{h}_i(x) = 0, i = 1, \ldots, p.\end{aligned}\>

Ví dụ các bài toán cực tiểu norm và cực tiểu norm bình phương là tương đương. Thay vì giải bài toán gốc \<\begin{aligned}\min ~ \| Ax – b \|_2.\end{aligned}\> không khả vi tại một số điểm, ta có thể giải bài toán tương đương khả vi tại mọi điểm \<\begin{aligned}\min ~ \| Ax – b \|_2^2 = (Ax – b)^T(Ax – b).\end{aligned}\>

Biến phụ

Biến đổi bài toán tương đương có thể thực hiện bằng cách thêm vào biến phụ. Ví dụ bài toán sau tương được với bài toán gốc (1)-(3) bằng cách thêm biến \(s_i, i = 1, \ldots, m\) \<\begin{aligned}\mathrm{min.}~ & f_0(x)\\\mathrm{s.t.}~ & s_i \geq 0, i = 1, \ldots, m \\& f_i(x) + s_i = 0, i = 1, \ldots, m \\& h_i(x) = 0, i = 1, \ldots, p.\end{aligned}\>

Lược bớt và thêm ràng buộc đẳng thức

Ta cũng có thể lược bớt ràng buộc đẳng thức nếu có hàm số \(\phi\) sao cho \(h_i(x) = 0, i = 1, \ldots, p\) nếu và chỉ nếu \(x = \phi(z)\), thì ta có bài toán sau tương đương với bài toán gốc (1)-(3). \<\begin{aligned}\mathrm{minimization}~ & \tilde{f}(z) = f_0(\phi(z)) \\\mathrm{subject ~ to}~ & \tilde{f}_i (z) = f_i(\phi(z)) \leq 0, i = 1, \ldots, m.\end{aligned}\>

Thêm ràng buộc đẳng thức Hai bài toán sau là tương đương: \<\begin{aligned}\mathrm{min.}~ & f_0(A_0 x + b_0)\\\mathrm{s.t.}~ & f_i(A_i x + b_i) \leq 0, i = 1, \ldots, m \\& h_i(x) = 0, i = 1, \ldots, p.\end{aligned}\> và \<\begin{aligned}\mathrm{min.}~ & f_0(y_0)\\\mathrm{s.t.}~ & f_i(y_i) \leq 0, i = 1, \ldots, m \\& y_i = A_i x + b_i, i = 0, \ldots, m \\& h_i(x) = 0, i = 1, \ldots, p.\end{aligned}\>

Tối ưu trên một vài biến

Ta cũng có thể thực hiện tối ưu trên một vài biến đối với một số bài toán dạng đăc biệt. Ví dụ như bài toán có hai nhóm ràng buộc độc lập giữa \(x_1\) và \(x_2\) sau \<\begin{aligned}\mathrm{min.}~ & f_0(x_1, x_2)\\\mathrm{s.t.}~ & f_i(x_1) \leq 0, i = 1, \ldots, m_1\\& g_i(x_2) \leq 0, i = 1, \ldots, m_2\end{aligned}\> sẽ tương đương với bài toán \<\begin{aligned}\mathrm{min.}~ & \tilde{f}_0(x_1)\\\mathrm{s.t.}~ & f_i(x_1) \leq 0, i = 1, \ldots, m_1,\end{aligned}\> trong đó \<\begin{aligned}\tilde{f}_0(x_1) = \min_{x_2 | g_i(x_2) \leq 0, i = 1,…,m_2} f_0(x_1, x_2).\end{aligned}\>

Biến đổi dạng epigraph

Bài toán dạng epigraph sau là tương đương với bài toán gốc \<\begin{aligned}\mathrm{min.}~ & t\\\mathrm{s.t.}~ & f_0(x) – t \leq 0 \\& f_i(y_i) \leq 0, \quad i = 1, \ldots, m \\& h_i(x) = 0, \quad i = 1, \ldots, p.\end{aligned}\> \((x^*, t^*)\) là cực tiểu của bài toán dạng epigraph nếu và chỉ nếu \(x^*\) là điểm cực tiểu của bài toán gốc và đồng thời \(t^* = f_0(x^*)\).

Bài toán tối ưu lồi

Bài toán tối ưu lồi có dạng như sau \<\begin{aligned}\mathrm{min.}~ & f_0(x)\\\mathrm{s.t.}~ & f_i(x) \leq 0, \quad i = 1, \ldots, m \\& a_i^T x = b_i, \quad i = 1, \ldots, p.\end{aligned}\> Trong đó, các hàm mục tiêu và ràng buộc bất đăng thức \(f_i, i=1, \ldots, m\) đều là hàm lồi. Ràng buộc dạng đẳng thức phải ở dạng tuyến tính.

Từ tính chất giao các tập lồi là tập lồi và epigraph của một hàm lồi là một tập lồi, ta có miền khả thi của một bài toán tối ưu lồi là một tập lồi.

Bài toán tìm cực đại hàm lõm

Bài toán tìm cực đại \<\begin{aligned}\mathrm{max.}~ & f_0(x) \label{eq:convprob_obj}\\\mathrm{s.t.}~ & f_i(x) \leq 0, \quad i = 1, \ldots, m \label{eq:convprob_incon}\\& a_i^T x = b_i, \quad i = 1, \ldots, p, \label{eq:convprob_affcon}\end{aligned}\> trong đó trong đó \(f_0\) là hàm lõm và các hàm \(f_i, i=1,…,m\) lồi cũng được xem là bài toán tối ưu lồi.

Xem thêm: Bản Kế Hoạch Học Tập Mẫu Bản Kế Hoạch Học Tập Du Học Trung Quốc

Điểm cực trị

Trong bài toán tối ưu lồi, điểm cực trị cục bộ cũng là điểm cực trị toàn cục.

Giả sử miền khả thi của bài toán là là \(X = \{ x | f_i(x) \leq 0, i=1, \ldots, m, h_i(x) = 0, i = 1, \ldots, p \}\). Trong trường hợp hàm \(f_0\) khả vi, \(x^*\) là điểm cực trị nếu và chỉ nếu \(x^* \in X\) và \<\begin{aligned}\nabla f_0(x^*)^T (y – x^*) \geq 0, \quad \forall y \in X.\end{aligned}\>

Đặc biệt nếu bài toán tối ưu không có ràng buộc thì điều kiện cần và đủ để \(x^*\) cực trị là \<\begin{aligned}\nabla f_0(x) = 0\end{aligned}\>

Một số ví dụ về bài toán tối ưu lồi

Bài toán quy hoạch tuyến tính mà ta đã làm quen ở Chương 1 là một bài toán tối ưu lồi. \<\begin{aligned}\mathrm{min.}~ & c^T x + d \\\mathrm{s.t.}~ & Gx \preceq h \\& A x = b,\end{aligned}\> trong đó \(G \in \mathbb{R}^{m \times n}\) và \(A \in \mathbb{R}^{p \times n}\).

Các biến đổi tương đương sau vẫn bảo toàn tính lồi bến bài toán gốc là lồi.

Dạng epigraph của một bài toán lồi cũng là một bài toán lồi.Thêm biến phụ \(s_i\) tương ứng với ràng buộc \(f_i(x) \leq 0\) để biến ràng buộc này thành ràng buộc dạng đẳng thức.Bài toán tối ưu trên một số biến trong trường hợp bài toán gốc có các ràng buộc độc lập theo các biến vẫn là bài toán lồi (xem phần 3.2).

Bài toán tối ưu hàm toàn phương

Bài toán tối ưu hàm toàn phương có dạng sau \<\begin{aligned}\mathrm{min.}~ & (1/2) x^T P x + q^T x + r \\\mathrm{s.t.}~ & Gx \leq h \\& A x = b,\end{aligned}\> trong đó \(P \in \mathbb{R}^{n \times n}, P \succeq 0\), \(G \in \mathbb{R}^{m \times n}\) và \(A \in \mathbb{R}^{p \times n}\). Bài toán trên là một bài toán tối ưu lồi.

Bài toán tối ưu trong hồi quy tuyến tính (linear regression hay còn gọi là least square) chính là một bài toán tối ưu hàm toàn phương \<\begin{aligned}\| Ax – b\|^2_2 = x^T A^T A x – 2b^T A x + b^T b.\end{aligned}\> Nghiệm của bài toán tối ưu trên là \(x^* = A^\dagger b\), trong đó \(A^\dagger = (A^T A)^{-1} A^T\) là ma trận nghịch đảo giả (Moore-Penrose pseudo-inverse) của ma trận A, được xem là dạng tổng quát của phép nghịch đảo ma trận trong trường hợp ma trận không vuông hay không khả nghịch.

Geometric programming

Bài toán tối ưu geometric programming xuất hiện trong một số lĩnh vực trong kỹ thuật, kinh tế, khoa học quản lý,… Các bài toán maximum likelihood trong học máy thường thuộc nhóm này. Ta có thể đưa bài toán geometric programming thành bài toán lồi tương đương.

Ta có một số định nghĩa trước khi định nghĩa bài toán geometric programming như sau: Hàm đơn thức (monomial) được định nghĩa là \(f(x) = c x_1^{a_1} x_2^{a_2} \ldots x_n^{a_n}\), trong đó \(c > 0, a_i \in \mathbb{R}\). Hàm đa thức (posynomial) là hàm có dạng như sau \(f(x) = \sum_{k = 1}^K c x_1^{a_{1k}} x_2^{a_{2k}} \ldots x_n^{a_{nk}}\) trong đó \(c_k > 0\).

Bài toán tối ưu có dạng \<\begin{aligned}\mathrm{min.}~ & f_0(x)\\\mathrm{s.t.}~ & f_i(x) \leq 1, \quad i = 1, \ldots, m \\& h_i(x) = 1, \quad i = 1, \ldots, p,\end{aligned}\> trong đó \(f_0, \ldots, f_m\) đều là posynomial, \(h_i\) là monomial được gọi là bài toán tối ưu dạng geometric programming.

Bằng cách thay biến \(y_i = \log x_i\) và lấy logarit các hàm, ta có

đơn thức \(f(x) = c x_1^{a_1} x_2^{a_2} \ldots x_n^{a_n}\) trở thành \<\begin{aligned}\log f(e^{y_1}, \ldots, e^{y_n})= a^T y + b\end{aligned}\> trong đó \(b = \log c\),posynomial \(f(x) = \sum_{k = 1}^K c x_1^{a_{1k}} x_2^{a_{2k}} \ldots x_n^{a_{nk}}\) trở thành \<\begin{aligned}\log f(e^{y_1}, \ldots, e^{y_n})= \log\Big(\sum_{i=1}^K e^{a_{ik}^T + b_{ik}}\Big),\end{aligned}\> trong đó \(b_k = \log c_k\),

Do đó, geometric programming tương đương với bài toán tối ưu lồi sau \<\begin{aligned}\mathrm{max.}~ & \log\Big(\sum_{i=1}^K e^{a_{0k}^T + b_{0k}}\Big)\\\mathrm{s.t.}~ & \log\Big(\sum_{i=1}^K e^{a_{ik}^T + b_{ik}}\Big) \leq 1, \quad i = 1, \ldots, m \\& Gy + d = 0, \quad i = 1, \ldots, p.\end{aligned}\>

Tài liệu tham khảo:

Stephen P. Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.