Trong các bài học trước về phương pháp hàm chắn logarit (Barrier Method), ta đã thấy quy trình tối ưu hóa giải bài toán lồi có ràng buộc bất đẳng thức thông qua một chuỗi các bài toán không ràng buộc xấp xỉ. Tuy nhiên, Barrier Method bộc lộ hai hạn chế lớn trong thực tế: Thứ nhất, thuật toán đòi hỏi nghiệm xuất phát phải khả thi nghiêm ngặt, hoặc phải giải một bài toán Pha I riêng biệt rất tốn kém. Thứ hai, mỗi bước lặp ngoài đòi hỏi giải gần như chính xác bài toán định tâm bên trong bằng phương pháp Newton, khiến tổng chi phí tính toán tăng cao.

Phương pháp điểm trong nguyên thủy - đối ngẫu (Primal-Dual Interior-Point Method) khắc phục triệt để các nhược điểm này. Đây là thuật toán tiêu chuẩn công nghiệp được triển khai trong hầu hết các bộ giải tối ưu hóa hiện đại như MOSEK, SDPT3, SeDuMi, OSQP hay Ipopt. Thuật toán cập nhật đồng thời biến nguyên thủy $x$ và các nhân tử đối ngẫu $\lambda ,\nu$ tại mỗi bước lặp, không yêu cầu điểm lặp phải khả thi nghiêm ngặt (Infeasible Start), và đạt tốc độ hội tụ siêu tuyến tính ở lân cận nghiệm tối ưu.

---

1. Hệ Điều Kiện KKT Bị Xáo Trộn và Độ Lệch Đối Ngẫu Đại Diện

Xét bài toán tối ưu lồi tổng quát:

$$\begin{array}{rl}& \underset{x}{min}{f}_0(x)\\ & \text{s.t.}{f}_i(x)\le 0,i=1,\dots ,m,\\ & Ax=b,\end{array}$$

trong đó $f_0,f_1,\dots ,f_m:{\mathbb{R}}^n\to \mathbb{R}$ là các hàm lồi khả vi liên tục hai lần, và ma trận $A\in {\mathbb{R}}^{p\times n}$ có hạng đủ $\mathrm{rank}(A)=p$.

Hệ điều kiện tối ưu của bài toán gồm bốn nhóm:

1. Khả thi nguyên thủy: Biểu thức $f_i(x^{\ast })\le 0$ với mọi $i=1,\dots ,m$ và $A{x}^{\ast }=b$.
2. Khả thi đối ngẫu: Điều kiện ${\lambda }_i^{\ast }\ge 0$ với mọi $i=1,\dots ,m$.
3. Triệt tiêu Lagrange: Ta có $\mathrm{\nabla }{f}_0(x^{\ast })+Df(x^{\ast }{)}^T{\lambda }^{\ast }+A^T{\nu }^{\ast }=0$.
4. Bù trừ tương hỗ: Tích ${\lambda }_i^{\ast }{f}_i(x^{\ast })=0$ với mọi $i=1,\dots ,m$.

Hệ KKT bị xáo trộn (Perturbed KKT Conditions)

Thay vì giải trực tiếp điều kiện bù trừ rời rạc ${\lambda }_i{f}_i(x)=0$, ta nới lỏng tích này về một đại lượng dương $\eta =1/t>0$:

$$\begin{array}{rl}\mathrm{\nabla }{f}_0(x)+\sum _{i=1}^m{\lambda }_i\mathrm{\nabla }{f}_i(x)+A^T\nu & =0,\\ -{\lambda }_i{f}_i(x)& =\eta ,i=1,\dots ,m,\\ Ax& =b,\end{array}$$

với điều kiện $f_i(x)<0$ và ${\lambda }_i>0$ cho mọi $i=1,\dots ,m$.

Khi $\eta \to 0$ (tương đương $t\to \mathrm{\infty }$), nghiệm $(x^{\ast }(\eta ),{\lambda }^{\ast }(\eta ),{\nu }^{\ast }(\eta ))$ của hệ phương trình trên sẽ hội tụ chính xác về nghiệm tối ưu $(x^{\ast },{\lambda }^{\ast },{\nu }^{\ast })$ của bài toán gốc. Tập hợp các nghiệm $(x^{\ast }(\eta ),{\lambda }^{\ast }(\eta ),{\nu }^{\ast }(\eta ))$ khi $\eta >0$ thay đổi quét nên đường trung tâm nguyên thủy - đối ngẫu (Primal-Dual Central Path).

Độ lệch đối ngẫu đại diện (Surrogate Duality Gap)

Tại một điểm bất kỳ $(x,\lambda ,\nu )$ thỏa mãn điều kiện miền trong $f_i(x)<0$ và ${\lambda }_i>0$, điểm này có thể chưa thỏa mãn ràng buộc đẳng thức $Ax=b$ hoặc chưa cân bằng đối ngẫu. Do đó, khoảng cách đối ngẫu lý thuyết chuẩn có thể chưa xác định. Ta định nghĩa độ lệch đối ngẫu đại diện:

$$\hat{\eta }(x,\lambda )=-\frac{1}{m}\sum _{i=1}^m{\lambda }_i{f}_i(x)=-\frac{1}{m}{\lambda }^{T}f(x).$$

Khai triển tường minh:

$$\hat{\eta }(x,\lambda )=\frac{1}{m}(-{\lambda }_1{f}_1(x)-{\lambda }_2{f}_2(x)-\cdots -{\lambda }_m{f}_m(x)).$$

Đại lượng $\hat{\eta }(x,\lambda )$ đo lường mức độ vi phạm trung bình của điều kiện bù trừ tương hỗ. Nếu điểm $(x,\lambda ,\nu )$ đồng thời khả thi nguyên thủy và đối ngẫu, thì tổng khoảng cách đối ngẫu chính bằng $m\hat{\eta }(x,\lambda )$.

---

2. Các Vector Phần Dư KKT

Để đo lường mức độ thỏa mãn hệ bị xáo trộn tại điểm hiện tại $(x,\lambda ,\nu )$, ta chia sai số thành ba thành phần phần dư:

1. Phần dư đối ngẫu (Dual residual):

   $$r_{\text{dual}}(x,\lambda ,\nu )=\mathrm{\nabla }{f}_0(x)+Df(x{)}^T\lambda +A^T\nu \in {\mathbb{R}}^n,$$

   trong đó ma trận Jacobi $Df(x)=\left[\begin{array}{c}\mathrm{\nabla }{f}_1(x{)}^T\\ ⋮\\ \mathrm{\nabla }{f}_m(x{)}^T\end{array}\right]\in {\mathbb{R}}^{m\times n}$.

2. Phần dư bù trừ trung tâm (Centering residual):

   $$r_{\text{cent}}(x,\lambda )=-\mathrm{diag}(\lambda )f(x)-\frac{1}{t}\mathbf{1}\in {\mathbb{R}}^m,$$

   trong đó $\mathrm{diag}(\lambda )=\mathrm{diag}({\lambda }_1,\dots ,{\lambda }_m)$ và $\mathbf{1}=(1,\dots ,1{)}^T$. Thành phần thứ $i$ của vector này là:

   $$(r_{\text{cent}}{)}_i=-{\lambda }_i{f}_i(x)-\frac{1}{t}.$$

3. Phần dư nguyên thủy (Primal residual):

   $$r_{\text{pri}}(x)=Ax-b\in {\mathbb{R}}^p.$$

Gộp ba phần dư thành vector tổng thể $r(x,\lambda ,\nu )\in {\mathbb{R}}^{n+m+p}$:

$$r(x,\lambda ,\nu )=\left[\begin{array}{c}{r}_{\text{dual}}(x,\lambda ,\nu )\\ r_{\text{cent}}(x,\lambda )\\ r_{\text{pri}}(x)\end{array}\right].$$

Hệ phương trình bị xáo trộn tương đương với phương trình phi tuyến $r(x,\lambda ,\nu )=0$.

---

3. Hướng Tìm Kiếm Primal-Dual và Phương Pháp Newton

Để tìm bước cập nhật $(\mathrm{\Delta }x,\mathrm{\Delta }\lambda ,\mathrm{\Delta }\nu )$, ta áp dụng xấp xỉ tuyến tính Taylor bậc nhất cho hệ phi tuyến $r(x+\mathrm{\Delta }x,\lambda +\mathrm{\Delta }\lambda ,\nu +\mathrm{\Delta }\nu )=0$:

$$r(x+\mathrm{\Delta }x,\lambda +\mathrm{\Delta }\lambda ,\nu +\mathrm{\Delta }\nu )\approx r(x,\lambda ,\nu )+\mathrm{\nabla }r(x,\lambda ,\nu )\left[\begin{array}{c}\mathrm{\Delta }x\\ \mathrm{\Delta }\lambda \\ \mathrm{\Delta }\nu \end{array}\right]=0.$$

Lấy từng khối của $r$ theo $(x,\lambda ,\nu )$, ta thu được hệ phương trình ma trận tuyến tính khối:

$$\left[\begin{array}{ccc}H& Df(x{)}^T& A^T\\ -\mathrm{diag}(\lambda )Df(x)& -\mathrm{diag}(f(x))& 0\\ A& 0& 0\end{array}\right]\left[\begin{array}{c}\mathrm{\Delta }x\\ \mathrm{\Delta }\lambda \\ \mathrm{\Delta }\nu \end{array}\right]=-\left[\begin{array}{c}{r}_{\text{dual}}\\ r_{\text{cent}}\\ r_{\text{pri}}\end{array}\right],$$

trong đó kết hợp $H\in {\mathbb{R}}^{n\times n}$ được xác định bởi:

$$H={\mathrm{\nabla }}^2{f}_0(x)+\sum _{i=1}^m{\lambda }_i{\mathrm{\nabla }}^2{f}_i(x).$$

Do tính lồi của các hàm $f_i$ và điều kiện ${\lambda }_i>0$, ma trận $H$ luôn (và xác định dương nếu ít nhất một hàm là lồi nghiêm ngặt).

Phân rã hướng Affine-Scaling và Hướng Centering

Trong thực tế, ta thường chọn đích $1/t=\sigma \hat{\eta }$, với $\sigma \in [0,1]$ được gọi là tham số định tâm (Centering parameter):

• Khi $\sigma =0$: $1/t=0$, hướng tìm kiếm thuần túy nhằm triệt tiêu phần dư và giảm khoảng cách đối ngẫu về 0. Hướng này gọi là hướng affine-scaling (Affine-scaling direction).
• Khi $\sigma =1$: Thuật toán tập trung kéo điểm lặp về trục đối xứng của đường trung tâm.
• Thuật toán nổi tiếng Mehrotra Predictor-Corrector giải hệ trên hai lần trong mỗi bước lặp: Lần đầu tính hướng dự đoán affine-scaling $(\mathrm{\Delta }{x}_{\text{aff}},\mathrm{\Delta }{\lambda }_{\text{aff}})$, xác định bước nhảy tối đa cho phép, từ đó tính độ giảm khoảng cách đối ngẫu để chọn $\sigma$ thích nghi, rồi giải lần hai có bổ sung số hạng hiệu chỉnh phi tuyến bậc hai $(\mathrm{\Delta }{\lambda }_{\text{aff}}{)}_i(\mathrm{\Delta }{x}_{\text{aff}}{)}_i$.

---

4. Chiến Lược Bước Nhảy và Line Search Backtracking

Sau khi tính được hướng tìm kiếm $(\mathrm{\Delta }x,\mathrm{\Delta }\lambda ,\mathrm{\Delta }\nu )$, ta cần chọn độ dài bước nhảy $s>0$ sao cho:

1. Biến đối ngẫu vẫn giữ dương nghiêm ngặt: $\lambda +s\mathrm{\Delta }\lambda >0$.
2. Biến nguyên thủy vẫn nằm trong miền xác định và thỏa mãn bất đẳng thức nghiêm ngặt: $f_i(x+s\mathrm{\Delta }x)<0$.
3. Chuẩn của vector phần dư $\parallel r(x,\lambda ,\nu ){\parallel }_2$ giảm đáng kể.

Xác định cận trên bước nhảy $s_{max}$

Đầu tiên, ta chặn bước nhảy đối ngẫu để đảm bảo ${\lambda }_i+s\mathrm{\Delta }{\lambda }_i>0$:

$$s_{max}^{\text{dual}}=sup\{s\in [0,1]\mid \lambda +s\mathrm{\Delta }\lambda \ge 0\}=min(1,\underset{i:\mathrm{\Delta }{\lambda }_i<0}{min}(-\frac{{\lambda }_i}{\mathrm{\Delta }{\lambda }_i})).$$

Tương tự, với các hàm ràng buộc bất đẳng thức (nếu là hàm tuyến tính $f_i(x)=a_i^{T}x-b_i$), ta có thể tính chính xác:

$$s_{max}^{\text{pri}}=min(1,\underset{i:a_i^T\mathrm{\Delta }x>0}{min}(-\frac{f_i(x)}{a_i^T\mathrm{\Delta }x})).$$

Để tránh điểm chạm vào biên quá sớm, ta đặt cận bước khởi tạo:

$$s_{max}=0.99min(s_{max}^{\text{pri}},s_{max}^{\text{dual}}).$$

Thuật toán Line Search theo chuẩn phần dư

Bắt đầu với $s=s_{max}$, ta thực hiện co bước $s:=\beta s$ ($\beta \in (0.5,0.8)$) cho đến khi thỏa mãn hai điều kiện:

1. Tính khả thi miền trong: Điểm $x+s\mathrm{\Delta }x\in \mathbf{dom}{f}_0$ và $f_i(x+s\mathrm{\Delta }x)<0$ với mọi $i=1,\dots ,m$.
2. Điều kiện giảm chuẩn phần dư Armijo:
   $$\parallel r(x+s\mathrm{\Delta }x,\lambda +s\mathrm{\Delta }\lambda ,\nu +s\mathrm{\Delta }\nu ){\parallel }_2\le (1-\alpha s)\parallel r(x,\lambda ,\nu ){\parallel }_2,$$
   với $\alpha \in (0.01,0.1)$.

---

5. Kỹ Thuật Số Học Giải Hệ Tuyến Tính Khối KKT

Hệ phương trình ở Mục 3 có kích thước lớn $(n+m+p)\times (n+m+p)$ và không đối xứng do phương trình thứ hai. Việc giải trực tiếp hệ này rất tốn kém. Trong thực tế tính toán, ta luôn thực hiện kỹ thuật khử biến để đưa về hệ đối xứng nhỏ hơn.

Khử biến đối ngẫu $\mathrm{\Delta }\lambda$

Từ phương trình thứ hai trong hệ :

$$-\mathrm{diag}(\lambda )Df(x)\mathrm{\Delta }x-\mathrm{diag}(f(x))\mathrm{\Delta }\lambda =-r_{\text{cent}}.$$

Vì $f_i(x)<0$ với mọi $i$, ma trận đường chéo $\mathrm{diag}(f(x))$ khả nghịch hoàn toàn. Rút $\mathrm{\Delta }\lambda$ theo $\mathrm{\Delta }x$:

$$\mathrm{\Delta }\lambda =-\mathrm{diag}(f(x){)}^{-1}(r_{\text{cent}}+\mathrm{diag}(\lambda )Df(x)\mathrm{\Delta }x).$$

Khai triển cho từng tọa độ:

$$\mathrm{\Delta }{\lambda }_i=-\frac{(r_{\text{cent}}{)}_i+{\lambda }_i\mathrm{\nabla }{f}_i(x{)}^T\mathrm{\Delta }x}{f_i(x)}=-\frac{-{\lambda }_i{f}_i(x)-1/t+{\lambda }_i\mathrm{\nabla }{f}_i(x{)}^T\mathrm{\Delta }x}{f_i(x)}.$$

Hệ KKT rút gọn đối xứng

Thế biểu thức $\mathrm{\Delta }\lambda$ vào phương trình thứ nhất:

$$H\mathrm{\Delta }x+Df(x{)}^T[-\mathrm{diag}(f(x){)}^{-1}(r_{\text{cent}}+\mathrm{diag}(\lambda )Df(x)\mathrm{\Delta }x)]+A^T\mathrm{\Delta }\nu =-r_{\text{dual}}.$$

Gộp các số hạng chứa $\mathrm{\Delta }x$:

$$(H+Df(x{)}^T\mathrm{diag}(-\frac{\lambda }{f(x)})Df(x))\mathrm{\Delta }x+A^T\mathrm{\Delta }\nu =-r_{\text{dual}}+Df(x{)}^T\mathrm{diag}(f(x){)}^{-1}{r}_{\text{cent}}.$$

Đặt ma trận trọng số đường chéo $D=\mathrm{diag}(-\frac{{\lambda }_1}{f_1(x)},\dots ,-\frac{{\lambda }_m}{f_m(x)})$. Vì ${\lambda }_i>0$ và $f_i(x)<0$, mọi phần tử trên đường chéo của $D$ đều dương nghiêm ngặt:

$$D_{ii}=-\frac{{\lambda }_i}{f_i(x)}>0.$$

Đặt tương đương:

$$H_{\text{eff}}=H+Df(x{)}^{T}DDf(x)\succ 0.$$

Hệ tuyến tính rút gọn chỉ còn ẩn $(\mathrm{\Delta }x,\mathrm{\Delta }\nu )$ với kích thước $(n+p)\times (n+p)$:

$$\left[\begin{array}{cc}{H}_{\text{eff}}& A^T\\ A& 0\end{array}\right]\left[\begin{array}{c}\mathrm{\Delta }x\\ \mathrm{\Delta }\nu \end{array}\right]=-\left[\begin{array}{c}{r}_{\text{dual}}-Df(x{)}^T\mathrm{diag}(f(x){)}^{-1}{r}_{\text{cent}}\\ r_{\text{pri}}\end{array}\right].$$

Hệ phương trình này là hệ đối xứng kinh điển, có thể giải bằng một trong hai phương án hiệu năng cao:

1. Khử khối ma trận Schur: Khi $p$ nhỏ hơn nhiều so với $n$, ta tính phân tích Cholesky của $H_{\text{eff}}=L{L}^T$, sau đó giải hệ bù Schur kích thước $p\times p$:
   $$(A{H}_{\text{eff}}^{-1}{A}^T)\mathrm{\Delta }\nu =A{H}_{\text{eff}}^{-1}g-r_{\text{pri}}.$$
2. Phân tích $LD{L}^T$ không xác định đối xứng: Khi ma trận $A$ có cấu trúc thưa lớn, ta giải trực tiếp hệ khối $(n+p)\times (n+p)$ bằng thuật toán $LD{L}^T$ với kỹ thuật xoay trục đường chéo (Bunch-Kaufman pivoting).

---

6. So Sánh Hiệu Năng: Barrier Method và Primal-Dual

Bảng dưới đây tổng kết sự khác biệt cốt lõi giữa hai họ phương pháp điểm trong:

Tiêu chí	Phương pháp Hàm chắn (Barrier Method)	Phương pháp Primal-Dual
Khởi tạo nghiệm	Bắt buộc khả thi nghiêm ngặt (cần chạy Pha I)	Cho phép khởi đầu phi khả thi (Infeasible Start)
Số vòng lặp	Hai tầng (vòng lặp ngoài cập nhật $t$, vòng lặp trong chạy Newton)	Một tầng duy nhất (cập nhật đồng thời $x,\lambda ,\nu$)
Tốc độ hội tụ	Tuyến tính theo $t$	Siêu tuyến tính (Superlinear) ở lân cận nghiệm
Độ nhạy	Phụ thuộc vào việc chọn nhân $\mu \approx 10-20$	Rất linh hoạt, $\sigma$ tự thích nghi
Độ chính xác	Đạt ${10}^{-6}$ ổn định, khó đạt ${10}^{-10}$ do suy biến	Dễ dàng đạt ${10}^{-10}$ đến ${10}^{-14}$

---

7. Bài Tập Tự Luyện Kèm Lời Giải Chi Tiết

Bài tập 1: Hệ phương trình Primal-Dual cho Quy hoạch Tuyến tính (LP)

Cho bài toán quy hoạch tuyến tính dạng chuẩn:

$$\underset{x}{min}{c}^{T}x\text{s.t.}Ax=b,x\ge 0,$$

với $A\in {\mathbb{R}}^{p\times n}$ có hạng đủ $\mathrm{rank}(A)=p$.

1. Hãy viết hệ phương trình bị xáo trộn với $\eta =1/t>0$.
2. Thiết lập xác định hướng primal-dual $(\mathrm{\Delta }x,\mathrm{\Delta }s,\mathrm{\Delta }\nu )$ (với $s\ge 0$ là biến bù hoặc biến nhân tử đối ngẫu liên kết với $x\ge 0$).
3. Biến đổi để khử $\mathrm{\Delta }s$, đưa về hệ phương trình đối xứng theo $(\mathrm{\Delta }x,\mathrm{\Delta }\nu )$.

Lời giải chi tiết:

1. Đặt biến đối ngẫu tương ứng với ràng buộc bất đẳng thức $-x\le 0$ là $s\in {\mathbb{R}}^n$ ($s>0$), và với ràng buộc đẳng thức $Ax=b$ là $\nu \in {\mathbb{R}}^p$.

   Hệ bị xáo trộn:

   $$$$

c - s + A^T \nu &= 0 \quad (\text{Dual feasible}), \ X S \mathbf{1} &= \eta \mathbf{1} \quad (\text{Centering}), \ A x &= b \quad (\text{Primal feasible}), \ &x > 0, \quad s > 0, \end

$$trongđó\$X=\mathrm{diag}(x_1,\dots ,x_n)\$và\$S=\mathrm{diag}(s_1,\dots ,s_n)\$.2.Cácvectorphầndưtạiđiểmhiệntại\$(x,s,\nu )\$:$$

\begin{aligned} r_{\text{dual}} &= c - s + A^T \nu, \ r_{\text{cent}} &= X S \mathbf{1} - \eta \mathbf{1}, \ r_{\text{pri}} &= A x - b. \end

$$Tuyếntínhhóahệphươngtrìnhtạibướclặphiệntại:$$

\begin{bmatrix} 0 & -I & A^T \ S & X & 0 \ A & 0 & 0 \end{bmatrix} \begin{bmatrix} \Delta x \ \Delta s \ \Delta \nu \end

-\begin{bmatrix} r_{\text{dual}} \ r_{\text{cent}} \ r_{\text{pri}} \end{bmatrix}.

$$3.Từphươngtrìnhthứhai:\$S\mathrm{\Delta }x+X\mathrm{\Delta }s=-r_{\text{cent}}\$.Vì\$x_i>0\$,matrận\$X\$khảnghịchhoàntoàn,suyra:$$

\Delta s = -X^{-1} r_{\text{cent}} - X^{-1} S \Delta x.

$$Thế\$\mathrm{\Delta }s\$vàophươngtrìnhthứnhất:$$

-\Delta s + A^T \Delta \nu = -r_{\text{dual}} \implies X^{-1} S \Delta x + A^T \Delta \nu = -r_{\text{dual}} - X^{-1} r_{\text{cent}}.

$$Đặtmatrậnđườngchéo\$\mathrm{\Theta }=S^{-1}X\succ 0\$với\${\mathrm{\Theta }}_{ii}=x_i/s_i\$.Nhâncảhaivếvới\$\mathrm{\Theta }\$:$$

\Delta x + \Theta A^T \Delta \nu = -\Theta r_{\text{dual}} - S^{-1} r_{\text{cent}}.

$$Nhânmatrận\$A\$vàohaivếvàkếthợpvớiphươngtrìnhthứba\$A\mathrm{\Delta }x=-r_{\text{pri}}\$,tathuđượcphươngtrìnhchuẩnxácđịnh\$\mathrm{\Delta }\nu \$:$$

(A \Theta A^T) \Delta \nu = -r_{\text{pri}} + A \left( \Theta r_{\text{dual}} + S^{-1} r_{\text{cent}} \right).

$$\text{Ma trận \$A Theta A^T in mathbb{R}^{p times p}\$ là ma trận đối xứng xác định dương, giải được bằng phân tích Cholesky với chi phí \$O(p^3) + O(p^2 n)\$. Sau khi có \$Delta nu\$, ta tính ngược lại \$Delta x\$ và \$Delta s\$ hoàn toàn bằng các phép nhân ma trận - vector. --- \#\#\# Bài tập 2: Tính Xác Định Dương của Hệ KKT Rút Gọn trong Quy hoạch Toàn phương (QP) Xét bài toán quy hoạch toàn phương lồi có ràng buộc bất đẳng thức:}$$

\min_{x} \quad \frac{1}{2} x^T P x + q^T x \quad \text{s.t.} \quad G x \le h,

$$\text{với \$P in mathbb{S}\_+^n\$ và \$G in mathbb{R}^{m times n}\$. 1. Thiết lập ma trận Hessian hiệu dụng \$H\_{text{eff}}\$ của hệ KKT rút gọn. 2. Giả sử \$P\$ chỉ nửa xác định dương (\$P succeq 0\$, có thể có trị riêng bằng 0) nhưng \$ker(P) cap ker(G) = {0}\$. Chứng minh rằng ma trận \$H\_{text{eff}}\$ luôn xác định dương nghiêm ngặt (\$H\_{text{eff}} succ 0\$) tại mọi bước lặp của thuật toán primal-dual. \#\#\#\# Lời giải chi tiết: 1. Với hàm mục tiêu \$f\_0(x) = frac{1}{2} x^T P x + q^T x\$, ta có \$nabla^2 f\_0(x) = P\$. Các hàm ràng buộc bất đẳng thức là hàm afin: Cụ thể \$f\_i(x) = g\_i^T x - h\_i\$ với \$g\_i\$ là dòng thứ \$i\$ của ma trận \$G\$. Do đó \$nabla^2 f\_i(x) = 0\$ và ma trận Jacobi \$Df(x) = G\$. Theo công thức ở Mục 5, ma trận Hessian hiệu dụng là:}$$

H_{\text{eff}} = P + G^T D G,

$$trongđó\$D=\mathrm{diag}(-\frac{{\lambda }_1}{g_1^{T}x-h_1},\dots ,-\frac{{\lambda }_m}{g_m^{T}x-h_m})\$.Dotínhkhảthimiềntrong,taluôncó\${\lambda }_i>0\$và\$g_i^{T}x-h_i<0\$,dẫnđến\$D_{ii}>0\$vớimọi\$i=1,\dots ,m\$.2.Đểchứngminh\$H_{\text{eff}}\succ 0\$,taxétdạngtoànphương\$v^T{H}_{\text{eff}}v\$vớimộtvectorbấtkỳ\$v\in {\mathbb{R}}^n\$:$$

v^T H_{\text{eff}} v = v^T P v + v^T G^T D G v.

$$Vì\$P⪰0\$,tacó\$v^{T}Pv\ge 0\$.Vì\$D\$làmatrậnđườngchéovớicácphầntửdươngnghiêmngặt\$D_{ii}>0\$,đặt\$w=Gv\in {\mathbb{R}}^m\$,tacó:$$

v^T G^T D G v = w^T D w = \sum_{i=1}^m D_{ii} w_i^2 \ge 0.

$$Dođó\$v^T{H}_{\text{eff}}v\ge 0\$.Bâygiờ,giảsử\$v^T{H}_{\text{eff}}v=0\$.Vìcảhaisốhạngđềukhôngâm,đẳngthứcxảyrakhivàchỉkhi:$$

v^T P v = 0 , \quad w^T D w = 0.

$$-Do\$P⪰0\$,điềukiện\$v^{T}Pv=0\$kéotheo\$Pv=0\$,tứclà\$v\in \ker (P)\$.-Do\$D_{ii}>0\$vớimọi\$i\$,điềukiện\$\sum _{i=1}^m{D}_{ii}{w}_i^2=0\$đòihỏi\$w_i=0\$vớimọi\$i\$,tứclà\$w=Gv=0\$,suyra\$v\in \ker (G)\$.Kếthợphaiđiềukiệntrên:$$

v \in \ker(P) \cap \ker(G).

$$\text{Theo giả thiết đề bài, \$ker(P) cap ker(G) = {0}\$, suy ra bắt buộc \$v = 0\$. Như vậy, với mọi vector \$v ne 0\$, ta luôn có \$v^T H\_{text{eff}} v > 0\$. Điều này chứng minh \$H\_{text{eff}} succ 0\$, đảm bảo hệ tuyến tính KKT luôn có nghiệm duy nhất và giải được ổn định bằng phân tích Cholesky. --- \#\#\# Bài tập 3: Mô Phỏng Một Bước Lặp Primal-Dual Trực Quan Xét bài toán tối ưu trên \$mathbb{R}\$:}$$

\min_{x} \quad x \quad \text{s.t.} \quad -x \le 0.

$$\text{Tại bước lặp hiện tại, nghiệm thử là \$x = 2\$ và nhân tử đối ngẫu là \$lambda = 1\$. 1. Tính độ lệch đối ngẫu đại diện \$hat{eta}\$ tại điểm này. 2. Với tham số định tâm \$sigma = 0.5\$, hãy tính giá trị mục tiêu \$eta\$ và các vector phần dư KKT. 3. Giải hệ phương trình KKT để tìm hướng di chuyển \$(Delta x, Delta lambda)\$. 4. Xác định cận bước nhảy tối đa \$s\_{max}\$ và giá trị nghiệm mới sau khi cập nhật với bước \$s = 0.8\$. \#\#\#\# Lời giải chi tiết: 1. Hàm mục tiêu \$f\_0(x) = x\$ có đạo hàm \$f\_0'(x) = 1\$. Hàm ràng buộc \$f\_1(x) = -x\$ có \$f\_1'(x) = -1\$. Tại \$x = 2\$, hàm ràng buộc nhận giá trị \$f\_1(2) = -2 < 0\$. Độ lệch đối ngẫu đại diện:}$$

\hat{\eta} = -\lambda f_1(x) = -(1)(-2) = 2.

$$2.Vớithamsốđịnhtâm\$\sigma =0.5\$:$$

\eta = \frac{1}{t} = \sigma \hat{\eta} = 0.5 \times 2 = 1.

$$Tínhcácvectorphầndư(trongbàitoán1chiều,chúnglàcácsốthực):-Phầndưđốingẫu:$$

 r_{\text{dual}} = f_0'(x) + \lambda f_1'(x) = 1 + (1)(-1) = 0.
 $$
 (Điểm hiện tại đã thỏa mãn cân bằng đối ngẫu).

• Phần dư bù trừ trung tâm:
  $$r_{\text{cent}}=-\lambda f_1(x)-\eta =-(1)(-2)-1=2-1=1.$$
• Phần dư nguyên thủy: Không có ràng buộc đẳng thức nên $r_{\text{pri}}=0$.

3. Thiết lập hệ phương trình :

   • $H=f_0^{″}(x)+\lambda f_1^{″}(x)=0+0=0$.
   • Ma trận Jacobi $Df(x)=[-1]$.

   Hệ phương trình tìm $(\mathrm{\Delta }x,\mathrm{\Delta }\lambda )$:

   $$\left[\begin{array}{cc}0& -1\\ -(1)(-1)& -(-2)\end{array}\right]\left[\begin{array}{c}\mathrm{\Delta }x\\ \mathrm{\Delta }\lambda \end{array}\right]=-\left[\begin{array}{c}0\\ 1\end{array}\right]⟺\left[\begin{array}{cc}0& -1\\ 1& 2\end{array}\right]\left[\begin{array}{c}\mathrm{\Delta }x\\ \mathrm{\Delta }\lambda \end{array}\right]=\left[\begin{array}{c}0\\ -1\end{array}\right].$$

   Giải hệ phương trình đại số:

   • Từ phương trình thứ nhất: $-\mathrm{\Delta }\lambda =0⟹\mathrm{\Delta }\lambda =0$.
   • Thế vào phương trình thứ hai: $\mathrm{\Delta }x+2(0)=-1⟹\mathrm{\Delta }x=-1$.

   Vậy hướng tìm kiếm là $(\mathrm{\Delta }x,\mathrm{\Delta }\lambda )=(-1,0)$.

4. Đánh giá bước nhảy:

   • Vì $\mathrm{\Delta }\lambda =0$, nhân tử đối ngẫu không đổi nên $s_{max}^{\text{dual}}=1$.
   • Với biến nguyên thủy: Ta cần $x+s\mathrm{\Delta }x=2-s>0⟺s<2$. Do đó bước nhảy bị chặn bởi 1, tức là $s_{max}=1$.

   Cập nhật với bước $s=0.8$:

   $$$$

x_{\text{new}} &= x + s \Delta x = 2 + 0.8(-1) = 1.2, \ \lambda_{\text{new}} &= \lambda + s \Delta \lambda = 1 + 0.8(0) = 1. \end

$$Kiểmtrađộlệchđốingẫuđạidiệnmới:$$

\hat{\eta}{\text{new}} = -\lambda{\text{new}} f_1(x_{\text{new}}) = -(1)(-1.2) = 1.2.

$$\text{Khoảng cách đối ngẫu đã giảm từ \$2\$ xuống còn \$1.2\$, đưa điểm lặp tiến gần hơn về nghiệm tối ưu \$x^* = 0\$. --- \#\# Tài liệu tham khảo - Stephen Boyd, Lieven Vandenberghe, *Convex Optimization*, Cambridge University Press. - Jorge Nocedal, Stephen J. Wright, *Numerical Optimization*, Springer.}$$