Constrained Optimization – First and Second order conditions

Trong bài trước ta đã nói về tối ưu không ràng buộc. Theo đó cho bài toán tối ưu

{\displaystyle \min_x f\left(x\right)}

và gọi x^* là lời giải của bài toán này. Ta có thể chứng minh rằng x^* thỏa:

  • Điều kiện bậc nhất: đạo hàm tại x^* bằng 0

{\displaystyle \nabla f\left(x^*\right)=0}

  • và điều kiện bậc hai: ma trận Hessian tại  x^*

{\displaystyle \nabla^2 f\left(x^*\right)} là positive definite.

Trong bài này, ta xét bài toán tối ưu ràng buộc có dạng sau:

\begin{array}{rl}{\displaystyle \min_x} & f\left(x\right) \\ \text{subject to} & h\left(x\right)=0 \\ \; & g\left(x\right) \leq 0 \end{array}

với  x \in \mathbb{R}^n,\; f\left(x\right): \mathbb{R}^n \rightarrow \mathbb{R}, \; h\left(x\right): \mathbb{R}^n \rightarrow \mathbb{R}^m, \; g\left(x\right): \mathbb{R}^n \rightarrow \mathbb{R}^p. Nghĩa là ta tối ưu hàm f(x) với m ràng buộc đẳng thức (có dấu =) và p ràng buộc bất đẳng thức (có dấu  \leq). Để bài toán không bị over-constrained (quá ràng buộc?) thì m nên nhỏ hơn n, nhưng p thì có thể lớn hơn n.

1. Các khái niệm

Feasible point: Một điểm x_0 gọi là feasible nếu nó thỏa tất cả các ràng buộc: h\left(x_0\right) = 0,\; g\left(x_0\right) \leq 0.

Tại feasible point, các ràng buộc bất đẳng thức được chia làm 2 phần:

g\left(x_0\right) \leq 0: \quad \left[\begin{array}{c}\hat{g}\left(x_0\right) = 0\\ \tilde{g}\left(x_0\right) < 0\end{array}\right]

Active set: tại feasible point x_0, tập các ràng buộc đẳng thức h\left(x_0\right)\hat{g}\left(x_0\right) được gọi là active set tại x_0. Gọi active set tại x\hat{h}\left(x\right) = \left\{h\left(x\right),\;\hat{g}\left(x\right)\right\}.

Tangent plane: tại một điểm \tilde{x} bất kì, tập các vector y trực giao với \nabla \hat{h}\left(\tilde{x}\right) được gọi là tangent plane. Kí  hiệu Tagent plane là T:

T = \left\{y\vert \nabla \hat{h}\left(\tilde{x}\right)y = 0\right\}

Một cách nôm na, tangent plane là siêu phẳng trực giao với gradient của active set.

2. Điều kiện cho bài toán tối ưu với ràng buộc đẳng thức

Cho bài toán:

\begin{array}{rl}{\displaystyle \min_x} & f\left(x\right) \\ \text{subject to} & \hat{h}\left(x\right)=0 \end{array}

với  \hat{h}\left(x\right): \mathbb{R}^n \rightarrow \mathbb{R}^m chỉ là các ràng buộc đẳng thức.

Hàm Lagrangian (Lagrangian function) của f(x) là:

\mathcal{L}\left(x, \lambda\right) = f\left(x\right) + \lambda^\top\hat{h}\left(x\right)

Trong đó \lambda \in \mathbb{R}^m gọi là toán tử  Lagrange.

Điều kiện bậc nhất là:

\nabla_x \mathcal{L}\left(x^*,\lambda^*\right) = \nabla f\left(x^*\right) + \lambda^{*\top} \nabla \hat{h}\left(x^*\right) = 0^\top

nghĩa là đạo hàm bậc nhất theo x của hàm  Lagrangian bằng 0. Khi đó cả x^*\lambda^* được mang đi kiểm tra điều kiện bậc 2.

Điều kiện bậc 2 là ma trận:

Z^\top\nabla_x^2 \mathcal{L}\left(x^*,\lambda^*\right)Zpositive definite.

trong đó

\nabla_x^2 \mathcal{L}\left(x^*,\lambda^*\right) = \nabla^2 f\left(x^*\right) + \sum_{j=1}^m \lambda^*_j \nabla^2 \hat{h}_j\left(x^*\right)

là đạo hàm bậc 2 của hàm  Lagrangian, và  Z là một cơ sở của tangent plane.

Một cách nôm na, điều kiện bậc 2 là ma trận Hessian của hàm Lagrangian là positive definite trên không gian tangent plane (mặc dù bản thân ma trận Hessian đó có thể là indefinite trong \mathbb{R}^{n\times n}).

Nhắc lại rằng tangent plane là không gian tạo bởi các vector y trực giao với đạo hàm bậc nhất của active set. Trong trường hợp này active set là toàn bộ các ràng buộc trong \hat{h}\left(x\right). Do \nabla \hat{h}\left(x\right) \in \mathbb{R}^{m\times n} nên y \in \mathbb{R}^n, và tangent plane cũng chỉ có n-m vector độc lập tuyến tính (vì m < n). Do đó Z \in \mathbb{R}^{n\times \left(n-m\right)}.

Do tất cả các ràng buộc đẳng thức trong \hat{h}\left(x\right) đều là active set và là không đổi nên tangent plane là cố định, do đó cơ sở Z cũng không đổi. Nghĩa là ta chỉ cần tính Z một lần cho toàn bộ thuật toán tối ưu. Đây là điểm khác biệt của bài toán tối ưu với ràng buộc đẳng thức.

3. Điều kiện cho bài toán tối ưu với ràng buộc đẳng thức và bất đẳng thức

Cho bài toán:

\begin{array}{rl}{\displaystyle \min_x} & f\left(x\right) \\ \text{subject to} & h\left(x\right)=0 \\ \; & g\left(x\right)\leq 0 \end{array}

Nhắc lại rằng các ràng buộc có dấu  \geq có thể dễ dàng chuyển thành dạng \leq.

Hàm Lagrangian (Lagrangian function) của f(x) là:

\mathcal{L}\left(x, \lambda, \mu \right) = f\left(x\right) + \lambda^\top h\left(x\right) + \mu^\top g\left(x\right)

Trong đó \lambda \in \mathbb{R}^m,\;\mu\in\mathbb{R}^p.

Điều kiện bậc nhất là:

\begin{array}{r}\nabla_x \mathcal{L}\left(x^*,\lambda^*, \mu^*\right) = \nabla f\left(x^*\right) + \lambda^{*\top} \nabla h\left(x^*\right) + \mu^{*\top} \nabla g\left(x^*\right)= 0^\top \\ \mu^{*\top}g\left(x^*\right) = 0\\ \mu^* \geq 0 \end{array}

nghĩa là đạo hàm bậc nhất theo x của hàm  Lagrangian bằng 0, cùng với 2 điều kiện khác cho \mug(x). Khi đó cả x^*, \; \lambda^*,\; \mu^* được mang đi kiểm tra điều kiện bậc 2.

Điều kiện bậc 2 là ma trận:

Z^\top\nabla_x^2 \mathcal{L}\left(x^*,\lambda^*, \mu^* \right)Zpositive definite.

trong đó

\nabla_x^2 \mathcal{L}\left(x^*,\lambda^*,\mu^*\right) = \nabla^2 f\left(x^*\right) + \sum_{j=1}^m \lambda^*_j \nabla^2 h_j\left(x^*\right) + \sum_{k=1}^p \mu^{*}_k \nabla^2 g_k\left(x^*\right)

là đạo hàm bậc 2 của hàm  Lagrangian, và  Z là một cơ sở của tangent plane. Tuy nhiên lưu ý rằng tangent plane trong trường hợp này là

T = \left\{y\vert \nabla h\left(x^*\right)y = 0,\; \nabla \hat{g}\left(x^*\right)y = 0\right\}

tức là tập các vector y trực giao với đạo hàm bậc nhất của active set. Vấn đề là active set thay đổi theo x (tại các vị trí khác nhau thì các ràng buộc trong active set là khác nhau), do đó cơ sở Z cũng thay đổi tùy theo x.

4. Ví dụ MATLAB

<T.B.D>

Advertisements

7 comments

  1. Cụ thể làm sao giải bài toán tối ưu này nhỉ? Tác giả có thể cho ví dụ lời giải cụ thể hoặc một phương pháp giải nào đó.
    Xin cảm ơn!

  2. hi bạn,
    Bài này chỉ là tổng quan các điều kiện dừng của bài toán tối ưu. Mình sẽ lần lượt trình bày các thuật toán trong những bài sau.

  3. Vâng cảm ơn tác giả rất nhiều.
    Mình đang tìm hiểu về Machine learning (AdaBoost, SVM) ứng dụng trong Computer vision, nhưng đụng tới bài toán tối ưu hóa đau đầu quá. Đang tìm tài liệu.
    Rất mong tác giả có thể chia sẽ một số kinh nghiệm và tài liệu tham khảo cho vấn đề này.
    Xin trân trọng cảm ơn!

  4. Hi,
    Tài liệu tiếng Việt thì mình không rõ, bạn tìm những người học chuyên ngành Toán hỏi thử xem có không. Còn dân IT ở VN mà học optimization thì hình như toàn là tự học từ tài liệu tiếng Anh thôi 😀
    Sách tiếng Anh thì có vài quyển sau:

    J. Nocedal and S.J. Wright, Numerical Optimization, 2nd edition, Springer Series in Operations Research
    D.G. Luenberger and Y. Ye, 2008, Linear and Nonlinear Programming, 3rd ed., Springer.

    Bạn có thể google, hoặc nếu ko thì gửi email cho mình (phvu @ fit.hcmus.edu.vn), mình sẽ gửi ebook cho.

  5. cảm ơn tác giả rất nhiều, đọc cái này thật vỡ ra nhiều điều, đỡ phải ôm mấy quyển sách tiếng anh to đùng 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s