# Linear Constrained Optimization
# 1. Đặt vấn đề
Một **bài toán linear programming**, gọi tắt linear programing(LP), có thể được biểu diễn dưới nhiều dạng. Mỗi LP bao gồm một hàm đối tượng (cứ hiểu đây là một hàm tuyến tính) và một tập các ràng buộc tuyến tính.

Ví dụ :
$$
\begin{array}{lc}
\underset{\mathbf{x}}{\operatorname{minimize}} & \mathbf{C}^{T} \mathbf{x} \\
\text { subject to } & \mathbf{w}_{\mathrm{LE}}^{(i) \top} \mathbf{x} \leq b_{i} \text { for } i \in\{1,2, \ldots\} \\
& \mathbf{w}_{\mathrm{GE}}^{(j)^{\top}} \mathbf{x} \geq b_{j} \text { for } j \in\{1,2, \ldots\} \\
& \mathbf{w}_{\mathrm{EQ}}^{(k) \top} \mathbf{x}=b_{k} \text { for } k \in\{1,2, \ldots\}
\end{array}
$$
Với $i,j,k$ là chỉ số của các ràng buộc trong tập các ràng buộc. Đưa một bài toán ngoài thực tế về dạng toán học như này thường không đơn giản. Bài viết chỉ tập trung vào thuật toán để tìm ra lời giải cho bài toán LP trên lý thuyết và chỉ thảo luận sơ qua cách mô hình hóa vấn đề ở thực tế.

Ví dụ về bài toán thực tế :
*Nguồn : slide lớp QHTT - CQ2022 - DHKHTN*:

$$
\begin{array}{lr}
\underset{x_{1}, x_{2}, x_{3}}{\operatorname{minimize}} & 2 x_{1}-3 x_{2}+7 x_{3} \\
\text { subject to } & 2 x_{1}+3 x_{2}-8 x_{3} \leq \quad 5 \\
& 4 x_{1}+x_{2}+3 x_{3} \leq \quad 9 \\
& x_{1}-5 x_{2}-3 x_{3} \geq-4 \\
& x_{1}+x_{2}+2 x_{3}=1
\end{array}
$$
## 1.1 Dạng tổng quát
Nói tóm lại, ta có thể viết LP dưới dạng ma trận và được một dạng tổng quát như sau :
$$
\begin{array}{cc}
\underset{\mathbf{x}}{\operatorname{minimize}} & \mathbf{c}^{\top} \mathbf{x} \\
\text { subject to } & \mathbf{A}_{\mathrm{LE}} \mathbf{x} \leq \mathbf{b}_{\mathrm{LE}} \\
& \mathbf{A}_{\mathrm{GE}} \mathbf{x} \geq \mathbf{b}_{\mathrm{GE}} \\
& \mathbf{A}_{\mathrm{EQ}} \mathbf{x}=\mathbf{b}_{\mathrm{EQ}}
\end{array}
$$
Lưu ý : Mỗi constraint (ràng buộc) được viết dưới dạng element-wise. Tức $a < b$ nghĩa là $a_i < b_i, \forall{i}$ .

## 1.2 Dạng chuẩn
Từ dạng tổng quát có thể chuyển về dạng chuẩn. Ở dạng chuẩn, các ràng buộc phải thoả mãn các điều kiện sau:
* Các bất phương trình có dấu bé hơn
* Các biến cần tìm (biến x) là nonnegative (không âm ở đây là ma trận không âm, chứ không phải số thực không âm).

Dạng chuẩn được viết lại như sau :
$$
\begin{array}{rr}
\underset{\mathbf{x}}{\operatorname{minimize}} & \mathbf{c}^{\top} \mathbf{x} \\
\text { subject to } & \mathbf{A x} \leq \mathbf{b} \\
& \mathbf{x} \geq \mathbf{0}
\end{array}
$$

Dưới đây là cách chuyển bất phương trình chứa dấu lớn hơn và dấu bằng về với bất phương trình chứa dấu bé hơn.

$$
\begin{aligned}
&\mathbf{A}_{\mathrm{GE}} \mathbf{x} \geq \mathbf{b}_{\mathrm{GE}} \quad \rightarrow \quad \begin{array}{r}
-\mathbf{A}_{\mathrm{GE}} \mathbf{x} \leq-\mathbf{b}_{\mathrm{GE}} \\
\mathbf{A}_{\mathrm{EQ}} \mathbf{x}=\mathbf{b}_{\mathrm{EQ}}
\end{array} \quad \rightarrow \quad \begin{array}{r}
\mathbf{A}_{\mathrm{EQ}} \mathbf{x} \leq \mathbf{b}_{\mathrm{EQ}} \\
-\mathbf{A}_{\mathrm{EQ}} \mathbf{x} \leq-\mathbf{b}_{\mathrm{EQ}}
\end{array}
\end{aligned}
$$

Ngoài ra ta cũng phải đảm bảo biến mục tiêu (ma trận x) là nonnegative.

Sau khi biển đổi chỉ còn bất phương trình có dấu bé hơn, ta được LP như sau :

Chúng ta viết lại $x$ thành $x^+ - x^-$ và ràng buộc $x^+ \geq 0$ và $x^- \geq 0$. Lấy ví dụ đơn giản : phần tử $-1$ là một số âm và có thể viết lại dưới dạng $-1 = 2 - 3$ với $2,3$ là số dương (tương tự với ma trận bao gồm nhiều phần tử).Ta được dạng chuẩn như sau :
$$
\begin{array}{rr}
\underset{\mathbf{x}^{+}, \mathbf{x}^{-}}{\operatorname{minimize}} \quad\left[\begin{array}{ll}
\mathbf{c}^{\top} & -\mathbf{c}^{\top}
\end{array}\right]\left[\begin{array}{l}
\mathbf{x}^{+} \\
\mathbf{x}^{-}
\end{array}\right] \\
\text {subject to } \quad\left[\begin{array}{ll}
\mathbf{A} & -\mathbf{A}
\end{array}\right]\left[\begin{array}{l}
\mathbf{x}^{+} \\
\mathbf{x}^{-}
\end{array}\right] \leq \mathbf{b} \\
{\left[\begin{array}{l}
\mathbf{x}^{+} \\
\mathbf{x}^{-}
\end{array}\right] \geq \mathbf{0}}
\end{array}
$$

## 1.3 Dạng đẳng thức

Để giải LP, người ta đưa về dạng đẳng thức. Các ràng buộc chỉ bao gồm các đẳng thức thay vì các bất đẳng thức như hai dạng trên.
$$
\begin{array}{rr}
\underset{\mathbf{x}}{\operatorname{minimize}} & \mathbf{c}^{\top} \mathbf{x} \\
\text { subject to } & \mathbf{A x}=\mathbf{b} \\
\mathbf{x} \geq \mathbf{0}
\end{array}
$$

Bất cứ LP dạng chuẩn nào đều có thể chuyển về dạng đẳng thức bằng cách biến đổi cách bất đẳng thức có dấu bé hơn thành đẳng thức bằng công thức sau :
$$
\mathbf{A x} \leq \mathbf{b} \quad \rightarrow \quad \mathbf{A x}+\mathbf{s}=\mathbf{b}, \quad \mathbf{s} \geq \mathbf{0}
$$

Chúng ta có thể viết gọn lại dưới dạng ma trận.
$$
\begin{array}{rr}
\underset{\mathbf{x}, \mathbf{s}}{\operatorname{minimize}} \quad\left[\begin{array}{ll}
\mathbf{c}^{\top} & \mathbf{0}^{\top}
\end{array}\right]\left[\begin{array}{l}
\mathbf{x} \\
\mathbf{s}
\end{array}\right] \\
\text { subject to }\left[\begin{array}{ll}
\mathbf{A} & \mathbf{I}
\end{array}\right]\left[\begin{array}{l}
\mathbf{x} \\
\mathbf{s}
\end{array}\right]=\mathbf{b} \\
{\left[\begin{array}{l}
\mathbf{x} \\
\mathbf{s}
\end{array}\right] \geq \mathbf{0}}
\end{array}
$$

# 2. Thuận toán Simplex
## 2.1 Vertices
1. Vertices (đỉnh):

- Phương trình tuyến tính trong đẳng thức có các tập khả thi dưới dạng các hình đa giác lồi trên các mặt phẳng. Các đa giác này được hình thành bởi giao điểm của các đa thức ràng buộc bằng.
- Các đỉnh của đa giác là các điểm trong tập khả thi mà không nằm giữa các điểm khác trong tập khả thi đó.

- Tập khả thi bao gồm các loại điểm khác nhau.
- Điểm trong vùng giao (vùng xanh ở hình trên): đây không phải là những điểm tối ưu vì hàm mục tiêu có thể cải thiện bằng cách dịch chuyển các điểm này theo phương $\vec{c}$
- Điểm trên bề mặt: Những điểm này có khả năng tối ưu nếu bề mặt vuông góc với $\vec{c}$.
- Đối với những điểm trên bề mặt không vuông góc với c: Có thể được cải thiện bằng cách trượt dọc mặt phẳng theo phương chiếu của −c lên bề mặt
- Tương tự như vậy, điểm trên cạnh có khả năng tối ưu nếu cạnh đó vuông góc với c. Nếu không thì có thể được cải thiện bằng cách truợt trên phương chiếu của c lên cạnh đó.
- Cuối cùng, các đỉnh cũng có thể là phương án tối ưu.
- Thuật toán simplex tạo ra các đỉnh tối ưu.
- Nếu chương trình tuyến tính có một giải pháp ràng buộc, thì nó sẽ chứa ít nhất một đỉnh
- Hơn nữa, sẽ có ít nhất một giải pháp tại một đỉnh. Trong trường hợp này thì toàn bộ các cạnh hoặc mặt phẳng đều là tối ưu, giải pháp tại mọi đỉnh đều tốt như nhau.
- $Ax = b$ chỉ có một giải pháp tối ưu duy nhất.
- Để giải, $A$ phải chuyển thành ma trận vuông ($m\times m$).
- cho $A$ là ma trận $m \times n$.
- trong đó: chọn $m \quad (m \leq n)$ biến cực biên và cho các biến còn lại bằng $0$, bỏ $n-m$ cột của $A$ tương ứng với các biến còn lại. Ma trận $A$ trở thành ma trận vuông $m \times m$
- Ví dụ:
$$
\left[\begin{array}{lllll}
a_{11} & a_{12} & a_{13} & a_{14} & a_{15} \\
a_{21} & a_{22} & a_{23} & a_{24} & a_{25} \\
a_{31} & a_{32} & a_{33} & a_{34} & a_{35}
\end{array}\right]\left[\begin{array}{c}
x_{1} \\
0 \\
x_{3} \\
x_{4} \\
0
\end{array}\right]=\left[\begin{array}{lll}
a_{11} & a_{13} & a_{14} \\
a_{21} & a_{23} & a_{24} \\
a_{31} & a_{33} & a_{34}
\end{array}\right]\left[\begin{array}{l}
x_{1} \\
x_{3} \\
x_{4}
\end{array}\right]=\left[\begin{array}{l}
b_{1} \\
b_{2} \\
b_{3}
\end{array}\right]
$$

- Chỉ số của các thành phần được chia thành $2$ tập $v, \mathcal{B}$
- $i \in v\rightarrow x_i=0 \text{ hay } x_v=0$
- $v$ có $n-m$ phần tử
- $\mathcal{B}$ có $n$ phần tử
- $v \subset \mathcal{B}$
- Ma trận $A_{\mathcal{B}}$ là ma trận $m \times m$ phần tử được tạo thành từ $m$ cột của $A$ chọn bởi $\mathcal{B}$
- Ta có:
$$
\left[\begin{array}{lllll}
a_{11} & a_{12} & a_{13} & a_{14} & a_{15} \\
a_{21} & a_{22} & a_{23} & a_{24} & a_{25} \\
a_{31} & a_{32} & a_{33} & a_{34} & a_{35}
\end{array}\right]\left[\begin{array}{c}
x_{1} \\
0 \\
x_{3} \\
x_{4} \\
0
\end{array}\right]=\left[\begin{array}{lll}
a_{11} & a_{13} & a_{14} \\
a_{21} & a_{23} & a_{24} \\
a_{31} & a_{33} & a_{34}
\end{array}\right]\left[\begin{array}{l}
x_{1} \\
x_{3} \\
x_{4}
\end{array}\right]=\left[\begin{array}{l}
b_{1} \\
b_{2} \\
b_{3}
\end{array}\right]
$$

$Ax=A_{\mathcal{B}} \times x_{\mathcal{B}}=b \rightarrow x_{\mathcal{B}}=A_{\mathcal{B}} ^{-1} b$

- Bởi vì $Ax=b$ hay $A_{\mathcal{B}} \times x_{\mathcal{B}}=b$ chỉ có một nghiệm duy nhất:
- Nên ma trận $A_{\mathcal{B}}$ phải độc lập tuyến tính
- Hay $A_{\mathcal{B}}$ là ma trận khả nghịch.
- Kết quả của bài toán là $x_{\mathcal{B}}$
- Ví dụ:
$$
\left[\begin{array}{rrrr}
1 & 1 & 1 & 1 \\
0 & -1 & 2 & 3 \\
2 & 1 & 2 & -1
\end{array}\right] \mathbf{x}=\left[\begin{array}{r}
2 \\
-1 \\
3
\end{array}\right], \quad \mathbf{x} \geq 0
$$
có phương án cực biên $x = [1,1,0,0]$.

- Nhận xét:
- $x$ là một đỉnh trong tập khả thi
- $x$ có hai phần tử bằng $0$
- Ta có thể chọn $\mathcal{B}=\{1,2,3\}$ hoặc $\mathcal{B}=\{1,2,4\}$ đểu được.
- Ta có:
- $$
\begin{aligned}
&\mathbf{A}_{\{1,2,3\}}=\left[\begin{array}{rrr}
1 & 1 & 1 \\
0 & -1 & 2 \\
2 & 1 & 2
\end{array}\right] \\
&\mathbf{A}_{\{1,2,4\}}=\left[\begin{array}{rrr}
1 & 1 & 1 \\
0 & -1 & 3 \\
2 & 1 & -1
\end{array}\right]
\end{aligned}
$$

- với mỗi $\mathcal{B}$, $A_{\mathcal{B}}$ đều là ma trận khả nghịch

Thử chạy chương trình:

## 2.2 First-Order Necessary Conditions
### First-Order Necessary Conditions
The first-order necessary conditions (FONCs) là những điều kiện dùng để kiểm tra xem một đỉnh có tối ưu hay chưa, và cách để chuyển tiếp sang một đỉnh khác tốt hơn.

Giả sử $f$ là một hàm khả vi liên tục (continuously differentiable) và $x^*$ là nghiệm cực tiểu. Chọn một vector $d \in \mathbb{R}$ bất kỳ. Vì chúng ta đang trong trường hợp unconstrained, di chuyển cách xa điểm $x^*$ theo hướng của $d$ hay $-d$ sẽ không đưa chúng ta ra khỏi $D$ ngay lập tức. Nói cách khác, chúng ta có $x^* + \alpha d \in D, \forall \alpha \in \mathbb{R}$ tiến dần về 0.

Với $d$ cố định, chúng ta xem $f(x^*+\alpha d)$ là một hàm với biến thực $\alpha$, với miền là một khoảng nào đó chứa 0. Ta sẽ gọi nó theo một hàm $g$ mới:

$$g(\alpha):=f(x^*+\alpha d)$$

Vì $x^*$ là nghiệm cực tiểu của $f$, nên ta biết rõ 0 là một nghiệm cực tiểu của $g$ (Vì với $\alpha = 0$ thì $x^* + \alpha d = x^*$). Dùng hàm $g$ thay cho $f$ sẽ hiệu quả vì $g$ là một hàm theo một biến vô hướng và do đó, cực tiểu của nó có thể được nghiên cứu bằng cách sử dụng phép giải tích thông thường. Cụ thể, chúng ta có thể viết khai triển Taylor first-order cho $g$ quanh điểm $\alpha = 0$:

$$g(\alpha)=g(0)+g'(0)\alpha + o(\alpha)$$

Trong đó $o(\alpha)$ là "higher-order terms" tiến về 0 nhanh hơn $\alpha$

$$\lim_{\alpha \to 0}\frac{o(\alpha)}{\alpha}=0$$

Chúng ta muốn chắc chắn rằng:

$$g'(0) = 0$$

Ta sẽ dùng phản chứng với giả sử $g'(0) \neq 0$. Sẽ tồn tại một $\epsilon > 0$ đủ nhỏ để $|\alpha|<\epsilon$, làm cho $|\dfrac{o(\alpha)}{\alpha}|$ sẽ bé hơn $|g'(0)|$. Nói cách khác, tồn tại các điểm $\alpha$ và $-\epsilon < \alpha < \epsilon $ sao cho $|\dfrac{o(\alpha)}{\alpha}| < |g'(0)|$. Ta có thể viết lại như sau:

$$|\alpha|<\epsilon \Rightarrow |o(\alpha)|<|g'(0)\alpha|$$

Đối với những giá trị $\alpha$ ứng với điệu kiện trên, từ công thức $g(\alpha)=g(0)+g'(0)\alpha + o(\alpha)$ ta có:

$$g(\alpha) - g(0) < g'(0)\alpha + |g'(0)\alpha|$$

Nếu ta tiếp tục giới hạn $\alpha$ để có được một $\alpha = -g'(0)$, thì $g'(0)\alpha + |g'(0)\alpha| = 0$ và $g(\alpha)-g(0)<0 \Leftrightarrow g(\alpha)<g(0)$. Nhưng điều này lại mâu thuẫn với việc $g(0)$ đạt cực tiểu. Vì vậy ta đã chứng minh được $g(0)$ = 0.

Chúng ta có thể diễn tả lại kết quả này theo hàm $f$. Một ứng dụng đơn giản của chain-rule từ phép tính vectơ, ta sẽ được công thức:

$$g'(\alpha) = \nabla f(x^*+\alpha d)\cdot d$$

Trong đó:
$$\nabla f := (f_{x_1}, ... f_{x_n})^T$$

là gradient của $f$ và dấu $\cdot$ là một tích vô hướng. Như vậy với $\alpha = 0$, ta có:

$$g'(0)=\nabla f(x^*) \cdot d = 0 $$

Vì $g'(0) = 0$ và $d$ được chọn ngẫu nhiên, ta có thể kết luận:

$$\nabla f(x^*)=0$$
Đây được xem là first-order necessary condition cho tối ưu.

Một điểm $x^*$ thỏa mãn điều kiện trên được gọi là nghiệm cực trị. Chúng ta nhấn mạnh rằng kết quả là hợp lệ khi $f$ khả vi liên tục và $x^* \in D$
### FONCs với bài toàn optimal của chúng ta
Ta có hàm Lagrange:

$$\mathcal{L}(x, \mu, \lambda)=c^Tx-\mu^Tx-\lambda^T(Ax-b)$$

Với các điều kiện FONCs cụ thể cho bài toán như sau:
- feasibility: $Ax=b, x\geq 0$
- dual feasibility: $\mu \geq 0$
- complementary slackness: $\mu \bigodot x = 0$
- stationarity: $A^T \lambda + \mu = c$
FONCS rất hiệu quả trong việc tối ưu bài toán tuyến tính, vì vậy nếu $\mu$ và $\lambda$ có thể tính được cho một đỉnh nào đó và nó thỏa 4 điều kiện của FONCs, thì đỉnh đó là đỉnh tối ưu.

Chúng ta có thể phân rã điều kiện stationary thành 2 thành phần $\mathcal{B}$ và $\mathcal{V}$:
$$ A^T\lambda+\mu=c \rightarrow \left\{
\begin{array}{cc}
A^T_{\mathcal{B}}\lambda+\mu_{\mathcal{B}} = c_{\mathcal{B}} \\
A^T_{\mathcal{V}}\lambda+\mu_{\mathcal{V}} = c_{\mathcal{V}}
\end{array}
\right.$$

Chúng ta có thể chọn $\mu_{\mathcal{B}}=0$ để thỏa complementary slackness. Từ đó ta có thể tính giá trị $\lambda$ từ $\mathcal{B}$:

$$\lambda = A_{\mathcal{B}}^{-T}c_{\mathcal{B}}$$

Có $\lambda$ ta tiếp tục tính được:

$$\mu_{\mathcal{V}}=c_{\mathcal{V}}-A^T_{\mathcal{V}}\lambda$$
$$\mu_{\mathcal{V}}=c_{\mathcal{V}}-\big(A^{-1}_{\mathcal{B}}A_{\mathcal{V}}\big)^Tc_{\mathcal{B}}$$

Có được $\mu_{\mathcal{V}}$ cho phép ta đạt được tối ưu của các đỉnh. Nếu $\mu_{\mathcal{V}}$ có phần tử âm, tính chất feasibility ($\mu \geq 0$) không được thỏa và ta tìm đỉnh khác.

## 2.3 Bước tối ưu hóa (Optimization Phase)
Thuật toán đơn hình (simplex algorithm) vận dụng tính chất rằng sẽ luôn có một nghiệm tối ưu là đỉnh của hình đa giác tạo bởi miền khả thi của bài toán. Thuật toán bắt đầu với một partition ($\beta,V$) tương ứng với một đỉnh trong tập khả thi. Partition sẽ được cập nhật mới bằng cách hoán đổi vị trí, nghĩa là đổi chỗ các chỉ số giữa hai tập $\beta$ và $V$. Mỗi lần đổi hoán đổi tương tự với việc ta di chuyển từ một đỉnh trong tập khả thi sang các đỉnh khác cũng cùng tập khả thi đó. Đặc biệt, nếu partition được lựa chọn ban đầu tương ứng với một đỉnh và các biểu thức điều kiện đều có giới hạn (có cận) thì thuật toán đơn hình sẽ đảm bảo hội tụ đến điểm tối ưu.

Việc chuyển đổi $x \rightarrow x'$ giữa các đỉnh phải thỏa mãn biểu thức $Ax'=b$. Bắt đầu thuật toán với một partition được xác định bởi $\beta$, ta chọn biến vào cơ sở (entering variable) bằng cách chọn chỉ số của biến đó (entering index) q thuộc tập $V$ để đưa vào tập $\beta$.
Đỉnh mới $x'$ thỏa:
$$Ax'=A_{\beta}x'_{\beta}+A_{q}x'_{q}=A_{\beta}x_{\beta}=b$$

Ta chọn biến rời cơ sở (leaving variable) với chỉ số của biến đó (leaving index) là p sao cho p thuộc tập $\beta$ trong $x'_{\beta}$ sẽ giảm về 0 trong quá trình biến đổi và được thay thế bằng cột của A tương ứng với chỉ số q. Hay nói cách khác, ta hoán đổi biến vào cơ sở và biến rời cơ sở với nhau bằng phép xoay (pivoting).
Điểm mới sẽ thỏa công thức:
$$x'_{\beta}=x_{\beta}-A^{-1}_{\beta}A_{\{q\}}x'_{q}$$

Và một chỉ số rời cơ sở $p\in\beta$ hoạt động khi:
$$(x'_{\beta})_{p}= 0 = (x_{\beta})_{p}-(A^{-1}_{\beta}A_{\{q\}})x'_{q}$$

và thu được p bằng cách tăng $x_{q}=0$ đến $x'_{q}$ với:
$$x'_{q}=\frac{(x_{\beta})_{p}}{(A^{-1}_{\beta}A_{\{q\}})_{p}}$$

Chỉ số rời cơ sở thu được bằng cách kiểm tra tỉ lệ tối thiểu, nghĩa là ta thực hiện tính toán cho mỗi chỉ số rời cơ sở tiềm năng và chọn ra một chỉ số sao cho $x'_{q}$ tối tiểu. Sau đó ta hoán đổi p và q giữa hai tập $\beta$ và $V$.

Khi này hàm mục tiêu sẽ được tính toán dựa trên $x'_{q}$. Giá trị hàm mục tiêu tại đỉnh mới sẽ bằng:
$$c^{T}x' = c^{T}_{\beta}x'_{\beta}+c_{q}x'_{q}$$

$$
\begin{aligned}
\mathbf{c}^{\top} \mathbf{x}^{\prime} &=\mathbf{c}_{\mathcal{B}}^{\top} \mathbf{x}_{\mathcal{B}}^{\prime}+c_{q} x_{q}^{\prime} \\
&=\mathbf{c}_{\mathcal{B}}^{\top}\left(\mathbf{x}_{\mathcal{B}}-\mathbf{A}_{\mathcal{B}}^{-1} \mathbf{A}_{\{q\}} x_{q}^{\prime}\right)+c_{q} x_{q}^{\prime} \\
&=\mathbf{c}_{\mathcal{B}}^{\top} \mathbf{x}_{\mathcal{B}}-\mathbf{c}_{\mathcal{B}}^{\top} \mathbf{A}_{\mathcal{B}}^{-1} \mathbf{A}_{\{q\}} x_{q}^{\prime}+c_{q} x_{q}^{\prime} \\
&=\mathbf{c}_{\mathcal{B}}^{\top} \mathbf{x}_{\mathcal{B}}-\left(c_{q}-\mu_{q}\right) x_{q}^{\prime}+c_{q} x_{q}^{\prime} \\
&=\mathbf{c}^{\top} \mathbf{x}+\mu_{q} x_{q}^{\prime}
\end{aligned}
$$

Khi này, việc lựa chọn chỉ số vào cơ sở q làm giảm giá trị hàm mục tiêu được thực hiện bằng cách:
$$c^{T}x'-c^{T}x=\mu_{q}x'_{q}$$

Hàm mục tiêu giảm dần khi và chỉ khi $\mu_{q}$ âm. Chính vì vậy, để tối ưu hàm mục tiêu, ta cần phải chọn chỉ số q trong tập $V$ sao cho $\mu_{q}$ âm. Ta sẽ tìm được cực tiểu toàn cục khi tất cả các phần tử trong $\mu_{v}$ đều không âm.

Mở rộng:
Việc có rất nhiều giá trị âm trong $\mu_{v}$, dẫn đến việc ta cần dùng nhiều heuristic khác nhau để chọn được chỉ số vào cơ sở (entering index) thích hợp. Ta có thể sử dụng một trong các phương pháp bên dưới:
- Sử dụng heuristic tham lam (Greedy heuristic) để chọn q sao cho giảm tối đa $c^{T}x$
- Sử dụng quy tắc Dantzig bằng cách chọn q là số âm lớn nhất (số âm nhất) trong $\mu$. Việc áp dụng quy tắc Dantzig giúp cho việc tính toán trở nên dễ dàng hơn nhưng lại không đảm bảo được việc giảm tối đa $c^{T}x$ đồng thời nó lại khá nhạy cảm với việc thay đổi càng ràng buộc bằng cách nhân thêm với hệ số mới (phép scalling).
- Sử dụng quy tắc Bland để tìm q đầu tiên với giá trị âm trong $\mu$. Phương pháp này cho hiệu quả khá kém trong thực tế, tuy nhiên nó giúp chúng ta tránh được các chu kỳ, trong đó các chu kỳ xuất hiện khi ta trả về một đỉnh đã duyệt qua từ trước mà không làm giảm hàm mục tiêu. Quy tắc này thường được dùng chỉ khi sử dụng các quy tắc khác mà không có cải thiện tối ưu nào giữa các lần lặp để thoát khỏi các chu kỳ và đảm bảo được sự hội tụ.

## 2.4 Bước khởi tạo (Initialization Phase)

Bước tối ưu hóa ở trên đòi hỏi phải có một không gian partition (phân vùng $B$ và $\mathcal{V}$) tương ứng với một điểm biên không gian lồi (vertex).
Để tìm một partition tương ứng với vertex, ta phải giải phương trình bổ trợ (auxiliary linear program) để tìm ra partition đầu tiên. Sau đó áp dụng thuật toán tối ưu bên trên để tìm ra partition tương ứng với vertex tối ưu.
Hàm bổ trợ này cũng là một LP, chúng ta chỉ thay đổi hàm mục tiêu bằng cách thêm vào biến $z \in \mathcal{R}^m$ sao cho giải ra $z$ bằng 0. Nếu hàm bổ trợ không tìm được $z$ bằng 0 nghĩa là LP ban đầu không giải được.

Phương trình bổ trợ có dạng :

$$
\underset{\mathbf{x}, \mathbf{z}}{\operatorname{minimize}} \quad\left[\begin{array}{ll}
\mathbf{0}^{\top} & \mathbf{1}^{\top}
\end{array}\right]\left[\begin{array}{l}
\mathbf{x} \\
\mathbf{z}
\end{array}\right]
$$
subject to ${\left[\begin{array}{ll}\mathbf{A} & \mathbf{Z}\end{array}\right]\left[\begin{array}{l}\mathbf{x} \\ \mathbf{z}\end{array}\right]=\mathbf{b} }$ ${\left[\begin{array}{l}\mathbf{x} \\ \mathbf{z}\end{array}\right] \geq \mathbf{0} }$

Ta luôn tìm được vertex khởi tạo của phương trình bổ trợ với không gian $B$ chọn các cột chứa biến $z$ được thêm vào như đã đề cập ở trên. Với $Z$ là ma trận chéo được định nghĩa như sau :
$$
Z_{i i}= \begin{cases}+1 & \text { if } b_{i} \geq 0 \\ -1 & \text { otherwise }\end{cases}
$$

Vertex khởi tạo của LP bổ trợ này có các phần tử $x$ bằng 0 và các phần tử $z_i = |b_i|$.

Partition cuối cùng ta có được từ việc giải phương trình bổ trợ trên cũng chính là partition tạo ra một vertex thuộc tập ứng viên vì $z_i = 0$ như đã nói ở trên. Nếu $z$ không bằng $0$ thì LP ban đầu không giải được.
LP được điều chỉnh một chút để có chứa biến $z$.

$$\underset{\mathbf{x}, \mathbf{z}}{\operatorname{minimize}} \quad\left[\begin{array}{ll}\mathbf{c}^{\top} & \mathbf{0}^{\top}\end{array}\right]\left[\begin{array}{l}\mathbf{x} \\ \mathbf{z}\end{array}\right]\\
\text{subject to} \left[\begin{array}{cc}\mathbf{A} & \mathbf{I} \\ \mathbf{0} & \mathbf{I}\end{array}\right]\left[\begin{array}{l}\mathbf{x} \\ \mathbf{z}\end{array}\right]=\left[\begin{array}{l}\mathbf{b} \\ \mathbf{0}\end{array}\right]\\
\left[\begin{array}{l}
x \\
z
\end{array}\right] \geq 0
$$
LP bắt buộc phải bao gồm biến $z$.
Sau khi giải LP thứ 2 (sau LP đầu tiên dùng để tìm partition khởi tạo), ta thu được $x$ và $z$ với $x$ chính là đáp án cho LP ban đầu đề ra.

## Dual Certificates

FONCs dẫn tới một kết quả là *giá trị tối ưu của bài toán đối ngẫu cũng là giá trị tối ưu của bài toán nguyên bản* tức là $d^* = p^*$

Bài toán nguyên bản có thể chuyển về dạng đối ngẫu của chính bản thân nó:

$$
\begin{aligned}
\max _{\mu \geq 0, \lambda} \min _{\mathbf{x}} \mathcal{L}(\mathbf{x}, \mu, \boldsymbol{\lambda}) &=\max _{\mu \geq 0, \lambda} \min _{\mathbf{x}} \mathbf{c}^{\top} \mathbf{x}-\boldsymbol{\mu}^{\top} \mathbf{x}-\boldsymbol{\lambda}^{\top}(\mathbf{A} \mathbf{x}-\mathbf{b}) \\
&=\max _{\mu \geq 0, \lambda} \min _{\mathbf{x}}\left(\mathbf{c}-\mu-\mathbf{A}^{\top} \boldsymbol{\lambda}\right)^{\top} \mathbf{x}+\boldsymbol{\lambda}^{\top} \mathbf{b}
\end{aligned}
$$

Từ kết quả của phần FONCs ta có được $\mathbf{c} - \mathbf{\mu} - \mathbf{A}^{T} \lambda = 0$. Tương đương $\mu = \mathbf{c} - \mathbf{A}^{T} \lambda \geq 0$

Tóm lại ta có thể chuyển đổi giữa 2 dạng
$$
\begin{array}{lrrr}
\text { Primal Form (equality) } & & \text { Dual Form } & \\
\underset{x}{\operatorname{minimize}} & \mathbf{c}^{\top} \mathbf{x} & \underset{\lambda}{\operatorname{maximize}} & \mathbf{b}^{\top} \boldsymbol{\lambda} \\
\text { subject to } & \mathbf{A x}=\mathbf{b} & \text { subject to } & \mathbf{A}^{\top} \boldsymbol{\lambda} \leq \mathbf{c} \\
& \mathbf{x} \geq \mathbf{0} & &
\end{array}
$$

Và nếu như có ai đó phát biểu rằng $(x^{*}, \lambda^{*})$ là tối ưu, ta có thể kiểm chứng đối ngẫu như thế này

* $x^*$ nằm trong tập có lý (feasible set) của bài toán nguyên bản
* $\lambda ^ {*}$ nằm trong tập có lý của bài toán đối ngẫu.
* $p^* = c^{T} x^{*} = b^{T} \lambda^{*} = d^{*}$

Mã giả của bài toán đối ngẫu như sau

function dual_certificate(LP, x, λ, ε=1e-6)
    A, b, c = LP.A, LP.b, LP.c
    primal_feasible = all(x .≥ 0) && A*x ≈ b
    dual_feasible = all(A'*λ .≤ c)
    return primal_feasible && dual_feasible &&
                        isapprox(c⋅x, b⋅λ, atol=ε)
end