Các bài giảng trước đã trang bị cho chúng ta hệ thống điều kiện toán học để nhận diện và chứng nhận một nghiệm tối ưu. Bài giảng này chuyển giao trọng tâm từ lý thuyết nhận diện sang bài toán thuật toán tính toán: Bắt đầu từ một điểm khởi tạo tùy ý trong không gian, làm thế nào để xây dựng một dãy điểm lặp hội tụ nhanh chóng, chính xác và ổn định về nghiệm tối ưu toàn cục?

Quá trình tìm đường trong không gian tối ưu hóa đòi hỏi thuật toán phải đưa ra ba quyết định độc lập tại mỗi bước lặp:

1. Chọn hướng di chuyển (Descent Direction): Đi theo vector nào để hàm mục tiêu suy giảm?
2. Chọn độ dài bước (Step Size / Learning Rate): Di chuyển bao xa theo hướng đã chọn để không bị vọt qua đáy thung lũng?
3. Tiêu chí dừng (Stopping Criteria): Khi nào mức độ tiệm cận nghiệm đã đủ tin cậy để dừng tính toán?

Chúng ta sẽ khảo sát một phổ rộng các thuật toán: Từ phương pháp dốc nhất theo các chuẩn khác nhau ($L_2,L_1,L_{\mathrm{\infty }}$), kỹ thuật Backtracking (Armijo), phương pháp Newton bậc hai và đại lượng Newton decrement, mở rộng sang tối ưu ràng buộc đẳng thức qua hệ Newton–, lý thuyết hàm Nesterov–Nemirovski, và đỉnh cao là Phương pháp điểm trong (Interior-Point Methods), cỗ máy giải các bài toán tối ưu lồi tổng quát có ràng buộc bất đẳng thức.

---

1. Hướng giảm và Độ dài bước di chuyển

Tại điểm hiện tại $x\in {\mathbb{R}}^n$, thuật toán lặp cập nhật vị trí mới theo quy tắc:

$$x^{+}=x+t\mathrm{\Delta }x,$$

trong đó $\mathrm{\Delta }x\in {\mathbb{R}}^n$ là vector hướng di chuyển và $t>0$ là độ dài bước nhảy.

định hướng của hàm số $f$ dọc theo tia $t\mapsto f(x+t\mathrm{\Delta }x)$ tại $t=0$ được tính bằng tích vô hướng $\mathrm{\nabla }f(x{)}^T\mathrm{\Delta }x$. Một vector $\mathrm{\Delta }x$ được gọi là hướng giảm (descent direction) nếu tích vô hướng này âm:

$$\mathrm{\nabla }f(x{)}^T\mathrm{\Delta }x<0.$$

Khi điều kiện này thỏa mãn, giải tích bảo đảm rằng luôn tồn tại một bước nhảy $t>0$ đủ nhỏ sao cho $f(x+t\mathrm{\Delta }x)<f(x)$.

---

2. Phương pháp dốc nhất theo các chuẩn khác nhau (Steepest Descent)

Khái niệm "hướng dốc nhất" phụ thuộc trực tiếp vào cách chúng ta đo lường độ dài của một bước di chuyển. Với một chuẩn tổng quát $\parallel \cdot \parallel$ trên ${\mathbb{R}}^n$, hướng dốc nhất chuẩn hóa (normalized steepest descent direction) được định nghĩa là hướng làm cho định hướng âm nhất trên quả cầu đơn vị của chuẩn đó:

$$\mathrm{\Delta }{x}_{\mathrm{nsd}}=\arg \underset{v}{min}\{\mathrm{\nabla }f(x{)}^{T}v\mid \parallel v\parallel \le 1\}.$$

Hướng dốc nhất chưa chuẩn hóa (unnormalized steepest descent direction) được tỷ lệ hóa theo độ lớn của : $\mathrm{\Delta }{x}_{\mathrm{sd}}=\parallel \mathrm{\nabla }f(x){\parallel }_{\ast }\mathrm{\Delta }{x}_{\mathrm{nsd}}$, trong đó $\parallel \cdot {\parallel }_{\ast }$ là chuẩn đối ngẫu.

2.1. Chuẩn Euclid ($L_2$): Phương pháp Gradient Descent cổ điển

Khi sử dụng $\parallel v{\parallel }_2=\sqrt{v^{T}v}$, bất đẳng thức Cauchy–Schwarz khẳng định:

$$\mathrm{\nabla }f(x{)}^{T}v\ge -\parallel \mathrm{\nabla }f(x){\parallel }_2\parallel v{\parallel }_2=-\parallel \mathrm{\nabla }f(x){\parallel }_2.$$

Đẳng thức đạt được khi và chỉ khi $v$ chỉ ngược chiều với :

$$\mathrm{\Delta }{x}_{\mathrm{nsd}}=-\frac{\mathrm{\nabla }f(x)}{\parallel \mathrm{\nabla }f(x){\parallel }_2},\mathrm{\Delta }{x}_{\mathrm{sd}}=-\mathrm{\nabla }f(x).$$

Đây chính là thuật toán Descent: Di chuyển thẳng theo hướng ngược chiều vector gradient.

2.2. Chuẩn toàn phương: Mối liên hệ với Phương pháp Newton

Xét chuẩn toàn phương xác định bởi ma trận đối xứng dương xác định $P\succ 0$: $\parallel v{\parallel }_P=(v^{T}Pv{)}^{1/2}$. Hướng dốc nhất theo chuẩn này là:

$$\mathrm{\Delta }{x}_{\mathrm{sd}}=-P^{-1}\mathrm{\nabla }f(x).$$

Khi ta chọn $P={\mathrm{\nabla }}^{2}f(x)$ ( tại điểm hiện tại), hướng dốc nhất theo chuẩn địa phương này trở thành:

$$\mathrm{\Delta }{x}_{\mathrm{nt}}=-[{\mathrm{\nabla }}^{2}f(x){]}^{-1}\mathrm{\nabla }f(x).$$

Đây chính là hướng Newton! Kết quả này cho thấy một trực giác sâu sắc: Phương pháp Newton thực chất chính là phương pháp dốc nhất, nhưng được đo lường trong hệ chuẩn elip tự nhiên tạo bởi độ cong tại từng điểm.

2.3. Chuẩn $L_1$: Phương pháp Tọa độ (Coordinate Descent)

Với chuẩn $\parallel v{\parallel }_1=\sum |v_i|$, quả cầu đơn vị là một khối bát diện đều (cross-polytope). Giá trị nhỏ nhất của $\mathrm{\nabla }f(x{)}^{T}v$ đạt được tại một trong các đỉnh của quả cầu đơn vị, tức là tại tọa độ $i^{\ast }$ có trị tuyệt đối riêng lớn nhất:

$$i^{\ast }=\arg \underset{i=1,\dots ,n}{max}|(\mathrm{\nabla }f(x){)}_i|.$$

Hướng dốc nhất theo chuẩn $L_1$ chỉ dịch chuyển duy nhất trên tọa độ $i^{\ast }$:

$$\mathrm{\Delta }{x}_{\mathrm{nsd}}=-\mathrm{sign}\left(\frac{\partial f(x)}{\partial x_{i^{\ast }}}\right)e_{i^{\ast }}.$$

Đây chính là phương pháp Coordinate Descent (Hạ dốc theo tọa độ): Mỗi bước chỉ cập nhật đúng một nhạy cảm nhất.

2.4. Chuẩn $L_{\mathrm{\infty }}$: Bước đi hình hộp

Với chuẩn cực đại $\parallel v{\parallel }_{\mathrm{\infty }}=max|v_i|$, quả cầu đơn vị là khối siêu lập phương $[-1,1{]}^n$. Hướng dốc nhất đạt được tại một đỉnh của khối lập phương:

$$(\mathrm{\Delta }{x}_{\mathrm{nsd}}{)}_i=-\mathrm{sign}\left(\frac{\partial f(x)}{\partial x_i}\right)\mathrm{\forall }i=1,\dots ,n.$$

Mỗi tọa độ đều di chuyển một bước có độ dài cố định $\pm 1$ tùy theo dấu của .

---

3. Tìm kiếm bước bằng thuật toán Backtracking (Điều kiện Armijo)

Trong thực tế tính toán, việc tìm kiếm độ dài bước tối ưu chính xác (exact line search) đòi hỏi giải một bài toán tối ưu phụ một chiều rất tốn kém. Kỹ thuật Line Search tìm kiếm một bước nhảy chấp nhận được với chi phí cực thấp.

Thuật toán chọn hai : $\alpha \in (0,0.5)$ (hệ số giảm chấp nhận được) và $\beta \in (0,1)$ (hệ số thu nhỏ bước). Bắt đầu với bước thử $t=1$, ta liên tục co ngắn bước $t\leftarrow \beta t$ cho tới khi điểm thử nghiệm nằm trong miền xác định và thỏa mãn điều kiện Armijo:

$$f(x+t\mathrm{\Delta }x)\le f(x)+\alpha t\mathrm{\nabla }f(x{)}^T\mathrm{\Delta }x.$$

Ý nghĩa hình học: Vì $\mathrm{\nabla }f(x{)}^T\mathrm{\Delta }x<0$, vế phải là một đường thẳng xấp xỉ tuyến tính dốc xuống với độ dốc bằng một tỷ lệ $\alpha$ so với độ dốc thực tế. Điều kiện yêu cầu hàm mục tiêu phải thực sự giảm ít nhất một tỷ lệ $\alpha$ so với mức giảm kỳ vọng tuyến tính.

def backtracking_line_search(f, grad_f, x, dx, alpha=0.1, beta=0.5):
    """Tìm độ dài bước nhảy thỏa mãn điều kiện Armijo."""
    t = 1.0
    slope = grad_f(x).dot(dx)
    while f(x + t * dx) > f(x) + alpha * t * slope:
        t *= beta
    return t

---

4. Phương pháp Newton và Mô hình xấp xỉ bậc hai

4.1. Hướng Newton và Đại lượng Newton Decrement

Phương pháp Newton khai thác thông tin độ cong của $H={\mathrm{\nabla }}^{2}f(x)\succ 0$. Tại điểm hiện tại, phương pháp Newton dựng một mô hình xấp xỉ Taylor bậc hai theo vector độ dời $v$:

$$q(v)=f(x)+\mathrm{\nabla }f(x{)}^{T}v+\frac{1}{2}{v}^T{\mathrm{\nabla }}^{2}f(x)v.$$

Cực tiểu hóa mô hình toàn phương này dẫn tới hệ phương trình Newton:

$${\mathrm{\nabla }}_{v}q(v)=\mathrm{\nabla }f(x)+{\mathrm{\nabla }}^{2}f(x)v=0⟺\boxed{{\displaystyle {\mathrm{\nabla }}^{2}f(x)\mathrm{\Delta }{x}_{\mathrm{nt}}=-\mathrm{\nabla }f(x).}}$$

Trong phương pháp Newton, đại lượng Newton decrement $\lambda (x)$ được định nghĩa là:

$$\lambda (x)={(\mathrm{\nabla }f(x{)}^T[{\mathrm{\nabla }}^{2}f(x){]}^{-1}\mathrm{\nabla }f(x))}^{1/2}={(\mathrm{\Delta }{x}_{\mathrm{nt}}^T{\mathrm{\nabla }}^{2}f(x)\mathrm{\Delta }{x}_{\mathrm{nt}})}^{1/2}.$$

Đại lượng này mang ba ý nghĩa toán học đặc biệt:

1. Ước lượng độ giảm mục tiêu: Đại lượng $\frac{1}{2}\lambda (x{)}^2$ chính là mức độ suy giảm hàm mục tiêu mà mô hình xấp xỉ bậc hai dự đoán:
   $$f(x)-\underset{v}{inf}q(v)=\frac{1}{2}\lambda (x{)}^2.$$
2. Tính bất biến Affine: Khác với $\parallel \mathrm{\nabla }f(x){\parallel }_2$ (vốn thay đổi mạnh khi đổi hệ đơn vị đo), đại lượng $\lambda (x)$ hoàn toàn bất biến dưới mọi phép đổi tọa độ affine tuyến tính ($x=Ty$).
3. Tiêu chí dừng chuẩn xác: Khi $\frac{1}{2}\lambda (x{)}^2\le ϵ$, ta dừng thuật toán với bảo đảm chắc chắn rằng sai số mục tiêu không vượt quá $ϵ$.

4.2. Tốc độ hội tụ hai pha của Phương pháp Newton

Phương pháp Newton có hai pha hội tụ phân biệt rõ rệt:

1. Pha giảm chậm (Damped Newton phase): Khi điểm bắt đầu ở xa nghiệm, $\lambda (x)\ge \gamma$. Mỗi bước lặp làm hàm mục tiêu giảm ít nhất một đại lượng hằng số hữu hạn $\gamma >0$. Số bước lặp trong pha này bị chặn trên bởi:
   $$\frac{f(x^{(0)})-p^{\ast }}{\gamma }.$$
2. Pha hội tụ bậc hai (Quadratic convergence phase): Khi $\lambda (x)<\gamma$ (bước vào lân cận nghiệm), thuật toán luôn chọn bước đầy đủ $t=1$. Sai số suy giảm với tốc độ bậc hai:
   $$\lambda (x^{(k+1)})\le c\lambda (x^{(k)}{)}^2.$$
   Tại pha này, số chữ số thập phân chính xác của nghiệm tăng gấp đôi sau mỗi bước lặp! Thông thường chỉ cần từ 5 đến 6 bước lặp Newton trong pha này để đạt độ chính xác máy tối đa.

---

5. Hàm tự tương hợp (Self-concordant Functions)

Một thách thức kinh điển của giải tích tối ưu truyền thống là tốc độ hội tụ của phương pháp Newton phụ thuộc vào các hằng số độ cong không xác định trong từng hệ tọa độ. Yurii Nesterov và Arkadi Nemirovski đã giải quyết triệt để vấn đề này qua lý thuyết Hàm (Self-concordant Functions).

Một hàm lồi một biến khả vi ba lần $f:\mathbb{R}\to \mathbb{R}$ được gọi là nếu nó thỏa mãn bất đẳng thức:

$$|f^{‴}(x)|\le 2[f^{″}(x){]}^{3/2}\mathrm{\forall }x\in \mathrm{dom}f.$$

Ý nghĩa bản chất: Tốc độ thay đổi của độ cong ( bậc ba) bị khống chế chặt chẽ bởi chính độ cong bậc hai tại điểm đó.

Đối với hàm nhiều biến, hàm $f:{\mathbb{R}}^n\to \mathbb{R}$ là nếu hàm một biến thu hẹp $t\mapsto f(x+tv)$ là tự tương hợp trên mọi đường thẳng đi qua miền xác định.

• Hàm toàn phương lồi là vì bậc ba triệt tiêu: $f^{‴}=0$.
• Hàm chắn logarit $f(x)=-\log x$ với $x>0$ là vì:
  $$|f^{‴}(x)|=\frac{2}{x^3}=2{\left(\frac{1}{x^2}\right)}^{3/2}=2[f^{″}(x){]}^{3/2}.$$

Lý thuyết khẳng định rằng: Số bước lặp của phương pháp Newton để giải một bài toán tự tương hợp bị chặn trên bởi một hằng số chỉ phụ thuộc vào độ chính xác $ϵ$ và giá trị mục tiêu khởi đầu, hoàn toàn độc lập với hệ tọa độ và số chiều biến!

---

6. Tối ưu có Ràng buộc Đẳng thức và Hệ phương trình Newton–KKT

Xét bài toán tối ưu với ràng buộc đẳng thức affine:

$$\underset{x}{min}f(x)\text{s.t.}Ax=b.$$

6.1. Phương pháp Khử biến (Elimination Method)

Nếu ta tìm được một nghiệm riêng $\hat{x}$ thỏa mãn $A\hat{x}=b$ và một ma trận $F\in {\mathbb{R}}^{n\times (n-p)}$ có các cột tạo thành cơ sở của không gian hạch $\mathrm{null}(A)$ ($AF=0$), mọi đều có thể biểu diễn duy nhất dưới dạng:

$$x=Fz+\hat{x},z\in {\mathbb{R}}^{n-p}.$$

Bài toán có ràng buộc đẳng thức quy về bài toán không ràng buộc theo biến $z$:

$$\underset{z\in {\mathbb{R}}^{n-p}}{min}\tilde{f}(z)=f(Fz+\hat{x}).$$

Phương pháp khử biến thích hợp khi số ràng buộc $p$ nhỏ hoặc ma trận $A$ có cấu trúc đơn giản.

6.2. Phương pháp Newton Khả thi (Feasible Newton Method)

Nếu điểm hiện tại $x$ đã khả thi ($Ax=b$), để điểm mới $x+\mathrm{\Delta }x$ tiếp tục khả thi, vector hướng di chuyển bắt buộc phải nằm trong không gian hạch của $A$: $A\mathrm{\Delta }x=0$.

Cực tiểu hóa mô hình bậc hai dưới điều kiện $A\mathrm{\Delta }x=0$ dẫn đến hệ phương trình Newton–:

$$\left[\begin{array}{cc}{\mathrm{\nabla }}^{2}f(x)& A^T\\ A& 0\end{array}\right]\left[\begin{array}{c}\mathrm{\Delta }{x}_{\mathrm{nt}}\\ w\end{array}\right]=\left[\begin{array}{c}-\mathrm{\nabla }f(x)\\ 0\end{array}\right].$$

6.3. Phương pháp Newton Khởi đầu Không khả thi (Infeasible Start Newton)

Nếu ta không có sẵn một thỏa mãn $Ax=b$, ta có thể xuất phát từ một điểm $x$ tùy ý và để phương pháp Newton đồng thời giải quyết hai nhiệm vụ: Tiến tới nghiệm tối ưu và triệt tiêu sai số ràng buộc.

Định nghĩa hai phần dư của hệ :

• Phần dư đối ngẫu: $r_{\mathrm{dual}}=\mathrm{\nabla }f(x)+A^T\nu$.
• Phần dư gốc: $r_{\mathrm{pri}}=Ax-b$.

Hệ phương trình Newton– khởi tạo không khả thi:

$$\left[\begin{array}{cc}{\mathrm{\nabla }}^{2}f(x)& 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}_{\mathrm{dual}}\\ r_{\mathrm{pri}}\end{array}\right].$$

Tiêu chuẩn Backtracking trong trường hợp này đo bằng chuẩn phần dư tổng hợp:

$$\parallel r(x+t\mathrm{\Delta }x,\nu +t\mathrm{\Delta }\nu ){\parallel }_2\le (1-\alpha t)\parallel r(x,\nu ){\parallel }_2.$$

6.4. Kỹ thuật giải số học Hệ phương trình Newton–KKT (Phụ lục C)

Mỗi bước lặp của phương pháp Newton đòi hỏi phải giải khối Newton–:

$$\left[\begin{array}{cc}H& A^T\\ A& 0\end{array}\right]\left[\begin{array}{c}\mathrm{\Delta }x\\ w\end{array}\right]=-\left[\begin{array}{c}g\\ h\end{array}\right].$$

Trong thực tế tính toán, ta không bao giờ tính ma trận nghịch đảo trực tiếp mà lựa chọn một trong hai chiến lược số học chuyên biệt:

1. Phương pháp Khử ma trận khối bằng Phần bù Schur: Vì $H={\mathrm{\nabla }}^{2}f(x)\succ 0$, ta tính phân tích Cholesky của $H$: $H=L{L}^T$ ($\frac{1}{3}{n}^3$ flops). Từ phương trình thứ nhất, $\mathrm{\Delta }x=-H^{-1}g-H^{-1}{A}^{T}w$. Thay vào phương trình thứ hai, ta giải hệ phương trình rút gọn kích thước $p\times p$ theo nhân tử đối ngẫu $w$:
   $$(A{H}^{-1}{A}^T)w=h-A{H}^{-1}g.$$
   Ma trận $M=A{H}^{-1}{A}^T\succ 0$ là ma trận đối xứng xác định dương. Ta giải hệ $p\times p$ bằng phân tích Cholesky trên $M$ với chi phí $\frac{1}{3}{p}^3$ flops, sau đó thu hồi $\mathrm{\Delta }x$. Phương pháp này tối ưu vượt trội khi số ràng buộc nhỏ ($p\ll n$) hoặc khi $H$ có cấu trúc thưa, đường chéo (như trong phương pháp điểm trong).
2. Phương pháp Phân tích $LD{L}^T$ trực tiếp: Khi số ràng buộc lớn ($p\approx n$) hoặc khi $H$ không thuận tiện để đảo khối, ta phân tích toàn bộ ma trận hệ kích thước $(n+p)\times (n+p)$ bằng phân tích $PLD{L}^T{P}^T$ (thuật toán Bunch–Kaufman) với chi phí $\frac{1}{3}(n+p{)}^3$ flops. Phương pháp này bảo đảm độ ổn định số học tối ưu ngay cả khi ma trận KKT có các giá trị riêng mang dấu đối nghịch.

---

7. Phương pháp Điểm trong (Interior-Point Methods)

Đỉnh cao của giải tích tối ưu hóa lồi hiện đại là Phương pháp điểm trong, được thiết kế để giải bài toán lồi tổng quát có ràng buộc bất đẳng thức:

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

Giả sử bài toán khả thi ngặt (thỏa mãn điều kiện Slater).

7.1. Hàm chắn Logarit (Logarithmic Barrier)

Ý tưởng của phương pháp là xấp xỉ hàm chỉ thị của bất đẳng thức bằng một hàm số trơn khả vi bên trong miền khả thi ngặt:

$$\varphi (x)=-\sum _{i=1}^m\log (-f_i(x)),\mathrm{dom}\varphi =\{x\in \mathcal{D}\mid f_i(x)<0,i=1,\dots ,m\}.$$

và của hàm chắn logarit:

$$\begin{array}{rl}\mathrm{\nabla }\varphi (x)& =\sum _{i=1}^m\frac{1}{-f_i(x)}\mathrm{\nabla }{f}_i(x),\\ {\mathrm{\nabla }}^2\varphi (x)& =\sum _{i=1}^m\frac{1}{f_i(x{)}^2}\mathrm{\nabla }{f}_i(x)\mathrm{\nabla }{f}_i(x{)}^T+\sum _{i=1}^m\frac{1}{-f_i(x)}{\mathrm{\nabla }}^2{f}_i(x).\end{array}$$

7.2. Đường trung tâm (Central Path)

Với mỗi trọng số $t>0$, ta xét bài toán tối ưu có ràng buộc đẳng thức:

$$\underset{x}{min}t{f}_0(x)+\varphi (x)\text{s.t.}Ax=b.$$

Nghiệm duy nhất của bài toán này được ký hiệu là $x^{\ast }(t)$. Tập hợp tất cả các điểm $\{x^{\ast }(t)\mid t>0\}$ tạo thành một đường cong trơn trong không gian khả thi ngặt, được gọi là đường trung tâm (central path).

Điểm $x^{\ast }(t)$ thỏa mãn điều kiện tối ưu : Tồn tại $\hat{\nu }\in {\mathbb{R}}^p$ sao cho $A{x}^{\ast }(t)=b$ và:

$$t\mathrm{\nabla }{f}_0(x^{\ast }(t))+\mathrm{\nabla }\varphi (x^{\ast }(t))+A^T\hat{\nu }=0.$$

Chia cả hai vế cho $t>0$:

$$\mathrm{\nabla }{f}_0(x^{\ast }(t))+\sum _{i=1}^m\underset{{\lambda }_i^{\ast }(t)}{\underbrace{\left(\frac{1}{-t{f}_i(x^{\ast }(t))}\right)}}\mathrm{\nabla }{f}_i(x^{\ast }(t))+A^T\underset{{\nu }^{\ast }(t)}{\underbrace{\left(\frac{\hat{\nu }}{t}\right)}}=0.$$

Đặt ${\lambda }_i^{\ast }(t)=-\frac{1}{t{f}_i(x^{\ast }(t))}>0$ và ${\nu }^{\ast }(t)=\hat{\nu }/t$. Bộ nhân tử này hoàn toàn thỏa mãn tính khả thi đối ngẫu! Giá trị hàm đối ngẫu tương ứng là:

$$g({\lambda }^{\ast }(t),{\nu }^{\ast }(t))=f_0(x^{\ast }(t))+\sum _{i=1}^m{\lambda }_i^{\ast }(t)f_i(x^{\ast }(t))=f_0(x^{\ast }(t))-\frac{m}{t}.$$

Hệ quả nền tảng: Khoảng cách đối ngẫu tại điểm $x^{\ast }(t)$ đúng bằng $m/t$:

$$\boxed{{\displaystyle f_0(x^{\ast }(t))-p^{\ast }\le \frac{m}{t}.}}$$

Khi cho $t\to +\mathrm{\infty }$, khoảng cách đối ngẫu $m/t\to 0$, và điểm trên đường trung tâm $x^{\ast }(t)$ tiến thẳng về nghiệm tối ưu toàn cục $x^{\ast }$ của bài toán gốc!

7.3. Thuật toán Hàm chắn (Barrier Method)

Thuật toán hàm chắn giải một chuỗi các bài toán tối ưu không ràng buộc (hoặc chỉ có ràng buộc đẳng thức) bằng phương pháp Newton:

1. Khởi tạo: Chọn ngặt $x=x^{(0)}$, $t=t^{(0)}>0$, hệ số tăng $\mu >1$ (thường chọn $\mu =10\sim 20$), và ngưỡng dung sai sai số $ϵ>0$.
2. Vòng lặp trong (Centering step): Giải bài toán tìm cực tiểu của $t{f}_0+\varphi$ với ràng buộc $Ax=b$ bằng phương pháp Newton, lấy điểm xuất phát là nghiệm $x$ hiện tại.
3. Cập nhật: Đặt $x:=x^{\ast }(t)$.
4. Kiểm tra tiêu chí dừng: Nếu $m/t<ϵ$, dừng thuật toán và trả về nghiệm $x$.
5. Tăng phạt: Đặt $t:=\mu t$ và quay lại bước 2.

Vì mỗi bước ngoài tăng $t$ lên $\mu$ lần, khoảng cách đối ngẫu giảm theo cấp số nhân. Số vòng lặp ngoài để đạt độ chính xác $ϵ$ bị chặn trên chặt chẽ bởi:

$$\lceil \frac{\log (m/(t^{(0)}ϵ))}{\log \mu }\rceil .$$

Thực tế kiểm chứng: Thuật toán hàm chắn luôn kết thúc trong khoảng từ 20 đến 50 bước lặp ngoài, bất kể bài toán có kích thước hàng triệu biến và ràng buộc.

---

8. Hệ thống Bài tập Tự luyện Chuyên sâu

Bài tập 1: Hướng dốc nhất theo chuẩn L1 và chuẩn cực đại L-infinity

Cho hàm số hai biến $f(x_1,x_2)$ có tại điểm hiện tại là $\mathrm{\nabla }f(x)=(3,-4{)}^T$.

1. Tìm hướng dốc nhất chuẩn hóa $\mathrm{\Delta }{x}_{\mathrm{nsd}}$ theo $L_2$.
2. Tìm hướng dốc nhất chuẩn hóa theo chuẩn $L_1$ và chuẩn $L_{\mathrm{\infty }}$.

Lời giải

Lời giải:

1. của : $\parallel \mathrm{\nabla }f(x){\parallel }_2=\sqrt{3^2+(-4{)}^2}=5$. Hướng dốc nhất theo chuẩn $L_2$:

   $$\mathrm{\Delta }{x}_{\mathrm{nsd},2}=-\frac{\mathrm{\nabla }f(x)}{\parallel \mathrm{\nabla }f(x){\parallel }_2}=-\frac{1}{5}\left[\begin{array}{c}3\\ -4\end{array}\right]=\left[\begin{array}{c}-0.6\\ 0.8\end{array}\right].$$

2. Theo chuẩn $L_1$: Tọa độ có trị tuyệt đối lớn nhất là tọa độ thứ hai vì $|-4|=4>|3|=3$. Do đó hướng dốc nhất theo chuẩn $L_1$ chỉ di chuyển trên tọa độ thứ hai:

   $$\mathrm{\Delta }{x}_{\mathrm{nsd},1}=-\mathrm{sign}(-4)e_2=\left[\begin{array}{c}0\\ 1\end{array}\right].$$

   Tích vô hướng đạt được là $\mathrm{\nabla }f(x{)}^T\mathrm{\Delta }x=3(0)+(-4)(1)=-4$.

3. Theo chuẩn $L_{\mathrm{\infty }}$: Mọi tọa độ đều nhận giá trị cực biên $\pm 1$:

   $$\mathrm{\Delta }{x}_{\mathrm{nsd},\mathrm{\infty }}=-\mathrm{sign}(\mathrm{\nabla }f(x))=\left[\begin{array}{c}-\mathrm{sign}(3)\\ -\mathrm{sign}(-4)\end{array}\right]=\left[\begin{array}{c}-1\\ 1\end{array}\right].$$

   Tích vô hướng đạt được là $\mathrm{\nabla }f(x{)}^T\mathrm{\Delta }x=3(-1)+(-4)(1)=-7$.

Bài tập 2: Đường trung tâm và Khoảng cách đối ngẫu của Quy hoạch Tuyến tính

Xét bài toán quy hoạch tuyến tính một biến:

$$\underset{x\in \mathbb{R}}{min}cx\text{s.t.}x\ge 0(\text{i.e., }-x\le 0),$$

với hằng số $c>0$.

1. Thiết lập hàm chắn logarit $\varphi (x)$ và bài toán tìm điểm trên đường trung tâm $x^{\ast }(t)$.
2. Tìm nghiệm $x^{\ast }(t)$ và tính khoảng cách đối ngẫu tương ứng.

Lời giải

Lời giải:

1. Ràng buộc chuẩn tắc: $f_1(x)=-x\le 0$. Hàm chắn logarit:

   $$\varphi (x)=-\log (-f_1(x))=-\log (x),x>0.$$

   Hàm mục tiêu trên đường trung tâm với $t>0$:

   $${\psi }_t(x)=tcx-\log (x).$$

2. Tìm cực tiểu bằng cách theo $x$:

   $${\psi }_t^{\prime }(x)=tc-\frac{1}{x}=0⟺x^{\ast }(t)=\frac{1}{tc}.$$

   bậc hai ${\psi }_t^{″}(x)=1/x^2>0$, chứng minh $x^{\ast }(t)=\frac{1}{tc}$ là nghiệm duy nhất. Giá trị hàm mục tiêu gốc tại điểm này là:

   $$f_0(x^{\ast }(t))=c\left(\frac{1}{tc}\right)=\frac{1}{t}.$$

   Vì nghiệm tối ưu thực tế là $x^{\ast }=0$ với chi phí $p^{\ast }=0$, khoảng cách đối ngẫu thực tế là:

   $$f_0(x^{\ast }(t))-p^{\ast }=\frac{1}{t}-0=\frac{1}{t}.$$

   Kết quả này hoàn toàn trùng khớp với công thức lý thuyết tổng quát $m/t$ với số ràng buộc $m=1$. Khi $t\to +\mathrm{\infty }$, điểm $x^{\ast }(t)\to 0$ tiệm cận chính xác về nghiệm tối ưu toàn cục.

Bài tập 3: Tính số bước lặp ngoài của Thuật toán Hàm chắn

Một bài toán quy hoạch lồi có $m=1000$ ràng buộc bất đẳng thức. Thuật toán hàm chắn khởi tạo với $t^{(0)}=1$ và hệ số nhân $\mu =10$. Hỏi sau bao nhiêu bước lặp ngoài thì thuật toán bảo đảm tìm được nghiệm có sai số hàm mục tiêu không vượt quá $ϵ={10}^{-6}$?

Lời giải

Lời giải: Khoảng cách đối ngẫu sau $k$ bước lặp ngoài là:

$$\frac{m}{t^{(k)}}=\frac{m}{t^{(0)}{\mu }^k}=\frac{1000}{1\cdot {10}^k}=\frac{{10}^3}{{10}^k}={10}^{3-k}.$$

Để bảo đảm sai số không vượt quá $ϵ={10}^{-6}$, ta cần:

$${10}^{3-k}\le {10}^{-6}⟺3-k\le -6⟺k\ge 9.$$

Như vậy, chỉ sau đúng 9 bước lặp ngoài, thuật toán hàm chắn đã đưa sai số mục tiêu từ ngưỡng 1000 ban đầu xuống dưới ${10}^{-6}$.

Bài tập 4: Thuật toán tìm kiếm đường thẳng quay lui Armijo trên hàm bậc hai lệch tỉ lệ

Xét hàm mục tiêu toàn phương có tỉ số điều kiện xấu:

$$f(x)=\frac{1}{2}(3x_1^2+7x_2^2).$$

Khởi tạo từ điểm $x^0=(2,4{)}^T$.

1. Tính $g=\mathrm{\nabla }f(x^0)$ và giá trị hàm số $f(x^0)$. Xét mô hình xấp xỉ tuyến tính có phạt chuẩn $Q_I(d)=f(x^0)+g^{T}d+\frac{1}{2}\parallel d{\parallel }_2^2$. Chứng minh hướng giảm dốc nhất chuẩn hóa chính là hướng gradient ngược $d_G=-g$.
2. Với các quay lui Armijo $\alpha =0,1$ và hệ số co bước $\beta =0,5$, ngưỡng chấp nhận bước $t$ là:
   $$f(x^0+t{d}_G)\le f(x^0)+\alpha t{g}^T{d}_G=62-82t.$$
   Kiểm tra tuần tự các bước thử $t=1$, $t=0,5$, $t=0,25$: Tính tọa độ điểm thử, giá trị hàm số thực tế, so sánh với ngưỡng Armijo và chỉ ra bước nhảy đầu tiên được chấp nhận.
3. Giải thích tại sao bước dài $t=1$ làm hàm số tăng vọt (hiện tượng vọt lố qua hẻm núi), và nêu trực giác tại sao điều kiện Armijo kết thúc sau hữu hạn bước co.

Lời giải

1. và hướng dốc nhất: Gradient của hàm số tại điểm bất kỳ là $\mathrm{\nabla }f(x)=(3x_1,7x_2{)}^T$. Tại điểm khởi đầu $x^0=(2,4{)}^T$:

   $$g=\mathrm{\nabla }f(x^0)=(3\times 2,7\times 4{)}^T=(6,28{)}^T.$$

   Giá trị hàm số:

   $$f(x^0)=\frac{1}{2}(3\times 2^2+7\times 4^2)=62.$$

   Bình phương độ dài : $\parallel g{\parallel }_2^2=6^2+{28}^2=36+784=820$.

   Mô hình cục bộ $Q_I(d)$:

   $$Q_I(d)=f(x^0)+g^{T}d+\frac{1}{2}\parallel d{\parallel }_2^2.$$

   Lấy theo $d$ và giải điều kiện triệt tiêu :

   $${\mathrm{\nabla }}_d{Q}_I(d)=g+d=0⟹d_G=-g=(-6,-28{)}^T.$$

   Vì ma trận đơn vị $I\succ 0$, điểm này là cực tiểu toàn cục duy nhất của mô hình. Tích vô hướng với : $g^T{d}_G=-\parallel g{\parallel }_2^2=-820<0$, khẳng định $d_G$ là một hướng giảm hợp lệ.

2. Kiểm tra quy tắc quay lui Armijo: Ngưỡng chấp nhận Armijo:

   $$62+\alpha t(-820)=62-0,1\times 820t=62-82t.$$
   • Thử $t=1$: Điểm thử là $x=x^0+d_G=(-4,-24{)}^T$. Giá trị hàm số:
     $$f(-4,-24)=\frac{1}{2}(3\times 16+7\times 576)=\frac{1}{2}(48+4032)=2040.$$
     Ngưỡng yêu cầu: $62-82(1)=-20$. Vì $2040>-20$, bước $t=1$ bị từ chối thẳng thừng do vọt lố nghiêm trọng.
   • Thử $t=0,5$: Điểm thử là $x=x^0+0,5d_G=(-1,-10{)}^T$. Giá trị hàm số:
     $$f(-1,-10)=\frac{1}{2}(3\times 1+7\times 100)=\frac{703}{2}=351,5.$$
     Ngưỡng yêu cầu: $62-82(0,5)=62-41=21$. Vì $351,5>21$, bước $t=0,5$ tiếp tục bị loại.
   • Thử $t=0,25$: Điểm thử là $x=x^0+0,25d_G=(0,5;-3{)}^T$. Giá trị hàm số:
     $$f(0,5;-3)=\frac{1}{2}(3\times 0,25+7\times 9)=\frac{1}{2}(0,75+63)=\frac{63,75}{2}=\mathrm{31,875.}$$
     Ngưỡng yêu cầu: $62-82(0,25)=62-20,5=41,5$. Vì $\mathrm{31,875}\le 41,5$, điều kiện Armijo được thỏa mãn.

   Thuật toán quay lui dừng lại và chấp nhận bước nhảy $t^{\ast }=0,25$.

3. Bản chất hình học của hiện tượng vọt lố: Độ cong của hàm số theo phương $x_2$ lớn hơn đáng kể so với phương $x_1$ ($7>3$). Khi bước nhảy theo quá dài ($t=1$), bước nhảy vượt qua đáy thung lũng parabol và leo thẳng lên vách đối diện, khiến hàm số tăng từ $62$ lên $2040$.

   Quy tắc Armijo bảo đảm dừng sau hữu hạn lần co nhờ khai triển Taylor bậc nhất:

   $$f(x^0+td)=f(x^0)+t{g}^{T}d+o(t).$$

   Khi $t\to 0$, số hạng $o(t)$ trở nên không đáng kể so với $(1-\alpha )t{g}^{T}d<0$, bảo đảm bất đẳng thức Armijo luôn nghiệm đúng với mọi $t$ đủ nhỏ.

Bài tập 5: Hướng giảm dốc nhất theo chuẩn metric Hessian và nguồn gốc phương pháp Newton

Xét bài toán tìm hướng giảm dốc nhất dưới ràng buộc chuẩn ellipsoid do ma trận xác định dương $W\succ 0$ quy định:

$$\underset{v\in {\mathbb{R}}^n}{min}{g}^{T}v\text{s.t.}{v}^{T}Wv\le 1,$$

với vector $g\ne 0$.

1. Thiết lập hàm Lagrangian và hệ cho bài toán con trên. Chứng minh nhân tử Lagrange $\zeta >0$, suy ra ràng buộc đạt dấu bằng trên biên ellipsoid.
2. Tìm nghiệm tối ưu $v^{\ast }$ và giá trị nhỏ nhất của $g^T{v}^{\ast }$. Định nghĩa chuẩn đối ngẫu $\parallel g{\parallel }_{\ast }=\sqrt{g^T{W}^{-1}g}$.
3. Khi đổi độ dài thành $d=\parallel g{\parallel }_{\ast }{v}^{\ast }$, chứng minh $d=-W^{-1}g$. Rút ra kết luận: Phương pháp Newton chính là phương pháp giảm dốc nhất khi chuẩn không gian được đo bằng cục bộ $W={\mathrm{\nabla }}^{2}f(x)$.

Lời giải

1. Thiết lập cho bài toán con: Hàm Lagrangian với nhân tử $\zeta \ge 0$:

   $$L(v,\zeta )=g^{T}v+\zeta (v^{T}Wv-1).$$

   Hệ :

   • Triệt tiêu : $g+2\zeta Wv=0$.
   • : $v^{T}Wv\le 1$.
   • Khả thi đối ngẫu: $\zeta \ge 0$.
   • Bù trừ: $\zeta (v^{T}Wv-1)=0$.

   Nếu $\zeta =0$: Phương trình cho $g=0$, mâu thuẫn với giả thiết $g\ne 0$. Do đó bắt buộc $\zeta >0$. Theo điều kiện bù trừ, vì $\zeta >0$, ràng buộc bắt buộc đạt dấu bằng:

   $$v^{T}Wv=1.$$

2. Nghiệm tối ưu và chuẩn đối ngẫu: Từ phương trình :

   $$2\zeta Wv=-g⟹v=-\frac{1}{2\zeta }{W}^{-1}g.$$

   Thay vào ràng buộc $v^{T}Wv=1$:

   $${(-\frac{1}{2\zeta }{W}^{-1}g)}^{T}W(-\frac{1}{2\zeta }{W}^{-1}g)=\frac{1}{4{\zeta }^2}{g}^T{W}^{-1}g=1.$$

   Suy ra nhân tử Lagrange tối ưu:

   $${\zeta }^{\ast }=\frac{1}{2}\sqrt{g^T{W}^{-1}g}.$$

   Đặt chuẩn đối ngẫu $\parallel g{\parallel }_{\ast }=\sqrt{g^T{W}^{-1}g}$, ta tìm được hướng giảm dốc nhất chuẩn hóa:

   $$v^{\ast }=-\frac{W^{-1}g}{\sqrt{g^T{W}^{-1}g}}=-\frac{W^{-1}g}{\parallel g{\parallel }_{\ast }}.$$

   Giá trị hàm mục tiêu tại nghiệm là:

   $$g^T{v}^{\ast }=-\frac{g^T{W}^{-1}g}{\parallel g{\parallel }_{\ast }}=-\frac{\parallel g{\parallel }_{\ast }^2}{\parallel g{\parallel }_{\ast }}=-\parallel g{\parallel }_{\ast }=-\sqrt{g^T{W}^{-1}g}.$$

3. Mối liên hệ với phương pháp Newton: Khi loại bỏ việc chuẩn hóa độ dài đơn vị và co dãn theo độ lớn chuẩn đối ngẫu:

   $$d=\parallel g{\parallel }_{\ast }{v}^{\ast }=\parallel g{\parallel }_{\ast }(-\frac{W^{-1}g}{\parallel g{\parallel }_{\ast }})=-W^{-1}g.$$

   Vector $d$ nghiệm đúng phương trình ma trận $Wd=-g$.

   Khi chọn $W={\mathrm{\nabla }}^{2}f(x)\succ 0$ là tại điểm hiện tại, phương trình trở thành:

   $${\mathrm{\nabla }}^{2}f(x)d=-\mathrm{\nabla }f(x)⟹d_N=-[{\mathrm{\nabla }}^{2}f(x){]}^{-1}\mathrm{\nabla }f(x).$$

   Đây chính là bước lặp Newton kinh điển.

   Kết luận sâu sắc: Phương pháp Newton không phải là một thuật toán xa lạ tách rời, mà chính là phương pháp hạ dốc nhất (steepest descent) tự nhiên nhất của bài toán khi ta trang bị cho không gian vector một metric Riemann cục bộ định hình bởi ma trận độ cong .

Bài tập 6: Bước lặp Newton, đại lượng Newton Decrement và mức giảm mô hình xấp xỉ

Cho hàm số lồi trơn trên miền dương:

$$\phi (s)=s-\log s,s>0.$$

Xét điểm khởi tạo $s^0=0,25$.

1. Tính bậc một ${\phi }^{\prime }(s)$, đạo hàm bậc hai ${\phi }^{″}(s)$ và xác định $g$, $H$ tại $s^0=0,25$.
2. Lập mô hình xấp xỉ Taylor bậc hai $Q_H(d)$ quanh điểm $s^0$. Giải phương trình dừng $Q_H^{\prime }(d)=0$ để tìm bước lặp Newton $d_N$ và điểm mới $s^1$.
3. Tính đại lượng giảm lượng Newton (Newton decrement) $\lambda (s^0)$, bình phương $\lambda (s^0{)}^2$ và mức giảm dự đoán của mô hình $\frac{1}{2}\lambda (s^0{)}^2$.
4. Tính mức giảm thực tế $\phi (s^0)-\phi (s^1)$ và sai số tối ưu thực tế $\phi (s^0)-\phi (s^{\ast })$. Phân biệt rõ sự khác nhau giữa ba đại lượng này.

Lời giải

1. và : Đạo hàm bậc một và bậc hai:

   $${\phi }^{\prime }(s)=1-\frac{1}{s},{\phi }^{″}(s)=\frac{1}{s^2}.$$

   Tại điểm $s^0=0,25=\frac{1}{4}$:

   $$g={\phi }^{\prime }(1/4)=1-4=-3,H={\phi }^{″}(1/4)=\frac{1}{(1/4{)}^2}=16.$$

   Vì $H=16>0$, hàm số lồi chặt tại lân cận điểm đang xét.

2. Mô hình bậc hai và bước lặp Newton: Mô hình xấp xỉ Taylor bậc hai theo độ dời $d$:

   $$Q_H(d)=\phi (1/4)+gd+\frac{1}{2}H{d}^2=\phi (1/4)-3d+8d^2.$$

   theo $d$ và giải điều kiện triệt tiêu:

   $$Q_H^{\prime }(d)=-3+16d=0⟹d_N=\frac{3}{16}=\mathrm{0,187}5.$$

   Điểm cập nhật mới sau một bước Newton thuần túy ($t=1$):

   $$s^1=s^0+d_N=\frac{1}{4}+\frac{3}{16}=\frac{7}{16}=\mathrm{0,437}5.$$

   Kiểm tra tại điểm mới: ${\phi }^{\prime }(7/16)=1-\frac{16}{7}=-\frac{9}{7}\ne 0$, chứng tỏ điểm $s^1$ tiến gần hơn về nghiệm nhưng chưa phải nghiệm tối ưu.

3. Newton decrement và mức giảm mô hình: Đại lượng giảm lượng Newton được định nghĩa:

   $$\lambda (s^0)=\sqrt{g^T{H}^{-1}g}=\sqrt{(-3)\times \frac{1}{16}\times (-3)}=\sqrt{\frac{9}{16}}=\frac{3}{4}=0,75.$$

   Bình phương của nó: $\lambda (s^0{)}^2=\frac{9}{16}=\mathrm{0,562}5$. Mức giảm giá trị được dự đoán bởi mô hình bậc hai:

   $$Q_H(0)-Q_H(d_N)=-g{d}_N-\frac{1}{2}H{d}_N^2=-(-3)\left(\frac{3}{16}\right)-8{\left(\frac{3}{16}\right)}^2=\frac{9}{16}-\frac{9}{32}=\frac{9}{32}=\frac{1}{2}\lambda (s^0{)}^2.$$

   Giá trị mức giảm dự đoán là $\frac{9}{32}=\mathrm{0,281}25$.

4. So sánh mức giảm thực tế và sai số tối ưu:

   • Nghiệm tối ưu toàn cục giải tích của $\phi (s)$ là $s^{\ast }=1$ với giá trị tối ưu $\phi (1)=1-\log 1=1$.
   • Sai số tối ưu thực tế tại điểm khởi đầu:
     $$\phi (s^0)-\phi (s^{\ast })=(\frac{1}{4}-\log \frac{1}{4})-1=-\frac{3}{4}+\log 4\approx -0,75+\mathrm{1,386}3=\mathrm{0,636}3.$$
   • Mức giảm thực tế sau một bước lặp:
     $$$$

\varphi(s^0) - \varphi(s^1) &= \left(\frac{1}{4} + \log 4\right) - \left(\frac{7}{16} - \log\frac{7}{16}\right) \ &= -\frac{3}{16} + \log\frac{64}{7} \approx -0{,}1875 + 2{,}2130 = 0{,}2933. \end

$$\ast \ast Phânbiệtbađạilượng\ast \ast :-Mứcgiảmdựđoán\$\frac{1}{2}{\lambda }^2=\mathrm{0,281}25\$:Dựatrênmôhìnhparabolthuầntúy.-Mứcgiảmthựctế\$\approx \mathrm{0,293}3\$:Mứchạthấpthựccủahàmphituyếnsaumộtbướccậpnhật.-Saisốtốiưuthựctế\$\approx \mathrm{0,636}3\$:Khoảngcáchgiátrịcònlạiđếncựctiểutoàncục.Cảbađạilượngcócùngbậcđộlớnnhưngkhôngbaogiờtrùngnhauđốivớihàmphitoànphương.$$

Bài tập 7: Phương pháp Newton khả thi và khử ràng buộc đẳng thức affine

Xét bài toán tối ưu có ràng buộc đẳng thức:

$$\begin{array}{rl}& \underset{x\in {\mathbb{R}}^3}{min}f(x)=\frac{1}{2}(x_1^2+2x_2^2+3x_3^2)\\ & \text{s.t.}{x}_1+x_2+x_3=1.\end{array}$$

1. Phương pháp Newton-: Thiết lập hệ phương trình KKT bậc nhất cho bước lặp Newton $\mathrm{\Delta }x$ và nhân tử đối ngẫu $w$. Giải hệ phương trình trực tiếp để tìm nghiệm tối ưu $x^{\ast }$ từ điểm xuất phát khả thi $x^0=(1,0,0{)}^T$.
2. Phương pháp khử biến: Dùng ràng buộc $x_1=1-x_2-x_3$ để khử biến $x_1$, đưa bài toán về bài toán tối ưu không ràng buộc theo hai biến $(x_2,x_3)$. Tìm của bài toán rút gọn và kiểm chứng rằng bước lặp Newton trên không gian rút gọn cho cùng kết quả.

Lời giải

1. Phương pháp Newton-: và của hàm mục tiêu:

   $$\mathrm{\nabla }f(x)=\left[\begin{array}{c}{x}_1\\ 2x_2\\ 3x_3\end{array}\right],H={\mathrm{\nabla }}^{2}f(x)=\left[\begin{array}{ccc}1& 0& 0\\ 0& 2& 0\\ 0& 0& 3\end{array}\right].$$

   Ma trận ràng buộc đẳng thức: $A=\left[\begin{array}{ccc}1& 1& 1\end{array}\right]$, $b=1$.

   Tại $x^0=(1,0,0{)}^T$, là $\mathrm{\nabla }f(x^0)=(1,0,0{)}^T$. Hệ phương trình Newton- xác định hướng $\mathrm{\Delta }x$ và nhân tử $w$:

   $$\left[\begin{array}{cc}H& A^T\\ A& 0\end{array}\right]\left[\begin{array}{c}\mathrm{\Delta }x\\ w\end{array}\right]=\left[\begin{array}{c}-\mathrm{\nabla }f(x^0)\\ 0\end{array}\right].$$

   Khai triển hệ phương trình:

   $$$$

\Delta x_1 + w &= -1 \implies \Delta x_1 = -1 - w, \ 2\Delta x_2 + w &= 0 \implies \Delta x_2 = -\frac{w}{2}, \ 3\Delta x_3 + w &= 0 \implies \Delta x_3 = -\frac{w}{3}. \end

$$Thayvàoràngbuộcbảotoàntínhkhảthi\$A\mathrm{\Delta }x=\mathrm{\Delta }{x}_1+\mathrm{\Delta }{x}_2+\mathrm{\Delta }{x}_3=0\$:$$

(-1 - w) - \frac{w}{2} - \frac{w}{3} = 0 \iff -1 - w\left(1 + \frac{1}{2} + \frac{1}{3}\right) = 0 \iff w\left(\frac{11}{6}\right) = -1 \implies w = -\frac{6}{11}.

$$Tínhcácthànhphầncủahướngcậpnhật:$$

\Delta x_1 = -1 - \left(-\frac{6}{11}\right) = -\frac{5}{11}, \quad \Delta x_2 = -\frac{-6/11}{2} = \frac{3}{11}, \quad \Delta x_3 = -\frac{-6/11}{3} = \frac{2}{11}.

$$Cậpnhậtnghiệmmới:$$

x^* = x^0 + \Delta x = \begin{bmatrix} 1 - 5/11 \ 0 + 3/11 \ 0 + 2/11 \end{bmatrix} = \begin{bmatrix} 6/11 \ 3/11 \ 2/11 \end{bmatrix}.

$$Vìhàmmụctiêulàhàmtoànphương,phươngphápNewtontìmranghiệmtốiưutoàncụcchỉsauđúngmộtbướclặp.2.\ast \ast Phươngphápkhửbiến(Elimination)\ast \ast :Thay\$x_1=1-x_2-x_3\$vàohàmmụctiêu:$$

\begin{aligned} \tilde{f}(x_2, x_3) &= \frac{1}{2}(1 - x_2 - x_3)^2 + x_2^2 + \frac{3}{2}x_3^2 \ &= \frac{1}{2}(1 + x_2^2 + x_3^2 - 2x_2 - 2x_3 + 2x_2 x_3) + x_2^2 + \frac{3}{2}x_3^2 \ &= \frac{3}{2}x_2^2 + 2x_3^2 + x_2 x_3 - x_2 - x_3 + \frac{1}{2}. \end

$$GradientvàHessianrútgọn:$$

\nabla \tilde{f} = \begin{bmatrix} 3x_2 + x_3 - 1 \ x_2 + 4x_3 - 1 \end{bmatrix}, \qquad \tilde{H} = \begin{bmatrix} 3 & 1 \ 1 & 4 \end{bmatrix}.

$$Giảiphươngtrìnhdừng\$\mathrm{\nabla }\tilde{f}=0\$:$$

\begin{cases} 3x_2 + x_3 = 1 \ x_2 + 4x_3 = 1 \end{cases} \implies \begin{bmatrix} x_2 \ x_3 \end{bmatrix} = \begin{bmatrix} 3 & 1 \ 1 & 4 \end{bmatrix}^{-1} \begin{bmatrix} 1 \ 1 \end{bmatrix} = \frac{1}{11}\begin{bmatrix} 4 & -1 \ -1 & 3 \end{bmatrix}\begin{bmatrix} 1 \ 1 \end{bmatrix} = \begin{bmatrix} 3/11 \ 2/11 \end{bmatrix}.

$$Khôiphụclại\$x_1\$:\$x_1=1-\frac{3}{11}-\frac{2}{11}=\frac{6}{11}\$.KếtquảhoàntoàntrùngkhớpvớiphươngphápNewton-KKT.KhửbiếngiảmsốchiềubàitoánnhưngphávỡcấutrúcthưathớtcủamatrậnHessian,trongkhiNewton-KKTbảotoàncấutrúcthưathớtởkhônggianbiếnmởrộng.$$

Bài tập 8: Tính tự điều chỉnh (Self-concordance) và cận sai số tối ưu độc lập hệ tọa độ

1. Một hàm số lồi $f:\mathbb{R}\to \mathbb{R}$ được gọi là hàm tự điều chỉnh () chuẩn hóa nếu thỏa mãn bất đẳng thức:
   $$|f^{‴}(x)|\le 2f^{″}(x{)}^{3/2}\mathrm{\forall }x\in \mathrm{dom}f.$$
   Chứng minh rằng hàm chắn logarit tự nhiên $f(x)=-\log x$ trên miền $x>0$ là một hàm tự điều chỉnh chuẩn hóa.
2. Với hàm tự điều chỉnh đa chiều, đại lượng giảm lượng Newton $\lambda (x)=\sqrt{\mathrm{\nabla }f(x{)}^T[{\mathrm{\nabla }}^{2}f(x){]}^{-1}\mathrm{\nabla }f(x)}$ là một đại lượng bất biến affine (affine invariant). Khi $\lambda (x)<0,68$, ta có cận sai số tối ưu giải tích:
   $$f(x)-p^{\ast }\le \lambda (x{)}^2.$$
   Giải thích tại sao tính chất này giúp lý thuyết tối ưu hóa giải phóng khỏi sự phụ thuộc vào các hằng số nhạy cảm hệ tọa độ như hằng số Lipschitz của $L$ hay độ lồi mạnh $m$.

Lời giải

1. Chứng minh tính tự điều chỉnh của hàm logarit: Tính các cấp của $f(x)=-\log x$:

   $$f^{\prime }(x)=-\frac{1}{x},f^{″}(x)=\frac{1}{x^2},f^{‴}(x)=-\frac{2}{x^3}.$$

   Lấy giá trị tuyệt đối của bậc ba:

   $$|f^{‴}(x)|=|-\frac{2}{x^3}|=\frac{2}{x^3}.$$

   Biểu thức vế phải của định nghĩa:

   $$2(f^{″}(x){)}^{3/2}=2{\left(\frac{1}{x^2}\right)}^{3/2}=2\left(\frac{1}{x^3}\right)=\frac{2}{x^3}.$$

   Ta thấy $|f^{‴}(x)|=2(f^{″}(x){)}^{3/2}$ đạt dấu bằng với mọi $x>0$. Do đó $f(x)=-\log x$ thỏa mãn định nghĩa hàm tự điều chỉnh chuẩn hóa với hằng số $2$.

2. Ý nghĩa lý thuyết của tính tự điều chỉnh:

   • Tính bất biến Affine: Dưới phép đổi biến tuyến tính khả nghịch $x=Ty$, các đại lượng giải tích bậc nhất truyền thống như chuẩn $\parallel \mathrm{\nabla }f(x){\parallel }_2$ bị biến dạng hoàn toàn phụ thuộc vào ma trận chuyển cơ sở $T$. Trái lại, đại lượng Newton decrement $\lambda (x)$ giữ nguyên giá trị chính xác trên mọi hệ tọa độ:
     $${\lambda }_{\tilde{f}}(y)={\lambda }_f(x).$$
   • Thoát khỏi hằng số điều kiện: Trong phân tích hội tụ descent truyền thống, tốc độ hội tụ phụ thuộc nặng nề vào số điều kiện $\kappa =L/m$. Một phép đổi đơn vị đo lường đơn giản có thể làm $\kappa$ tăng vọt từ $10$ lên ${10}^6$, khiến các cận hội tụ lý thuyết trở nên vô nghĩa.
   • Cận hội tụ phổ quát: Lý thuyết tự điều chỉnh của Nesterov và Nemirovski chứng minh rằng khi $\lambda (x)\le 0,68$, thuật toán Newton bước vào pha hội tụ bậc hai (quadratic convergence) thuần túy. Số bước lặp cần thiết để đạt độ chính xác $ϵ$ bị chặn trên bởi một hàm chỉ phụ thuộc vào sai số ban đầu và tự điều chỉnh, hoàn toàn độc lập với ma trận điều kiện và số chiều không gian.

---

8. Các chủ đề chuyên khảo về Phương pháp Điểm trong Nâng cao

Để làm chủ trọn vẹn họ phương pháp điểm trong từ lý thuyết đến triển khai thuật toán chuẩn công nghiệp, người học có thể đào sâu qua các chuyên đề nghiên cứu độc lập dưới đây:

3 chủ đề · tổng cộng khoảng 25 phút đọc

I. Phương pháp điểm trong nâng cao

Khởi tạo khả thi qua Pha I, độ phức tạp trên nón chính quy và thuật toán Primal-Dual.

1. 1Phương pháp Pha I và tìm điểm khả thi khởi đầuKhi không có sẵn điểm xuất phát khả thi nghiêm ngặt, làm sao bắt đầu phương pháp điểm trong?Khoảng 3 phút
2. 2Độ phức tạp và điểm trong trên nón chính quyPhương pháp điểm trong cần chính xác bao nhiêu bước lặp Newton và mở rộng cho nón Lorentz/PSD thế nào?Khoảng 12 phút
3. 3Phương pháp Điểm trong Primal-DualVì sao cập nhật đồng thời biến nguyên thủy và đối ngẫu lại vượt trội hơn phương pháp hàm chắn truyền thống?Khoảng 10 phút

---

Tóm tắt cốt lõi

1. Phương pháp dốc nhất theo các chuẩn: sinh ra Descent, chuẩn toàn phương ma trận sinh ra phương pháp Newton, và chuẩn $L_1$ sinh ra phương pháp hạ dốc theo tọa độ.
2. Line Search: Điều kiện Armijo bảo đảm mức giảm thực tế tương xứng với xấp xỉ tuyến tính, ngăn chặn hiện tượng bước nhảy quá trớn trong các hẻm núi hẹp.
3. Phương pháp Newton và Newton Decrement: Mô hình xấp xỉ bậc hai đạt tốc độ hội tụ bậc hai ở lân cận nghiệm. Đại lượng $\lambda (x)$ cung cấp tiêu chuẩn dừng bất biến affine chuẩn mực.
4. Hàm : Đặt cơ sở lý thuyết chứng minh số bước lặp Newton bị chặn trên độc lập với hệ tọa độ và số chiều biến.
5. Hệ phương trình Newton–: Công cụ thống nhất giải quyết các bài toán có ràng buộc đẳng thức từ điểm khởi tạo khả thi hoặc không khả thi.
6. Phương pháp Điểm trong và Đường trung tâm: Hàm chắn logarit $-\sum \log (-f_i(x))$ biến bài toán có ràng buộc thành chuỗi bài toán không ràng buộc trơn. Khoảng cách đối ngẫu tại mỗi điểm trên đường trung tâm được kiểm soát chính xác bằng $m/t$.

---

Tài liệu tham khảo

• Stephen Boyd, Lieven Vandenberghe, Convex Optimization, Cambridge University Press. Đọc kỹ Chương 9 (Tối ưu không ràng buộc), Chương 10 (Tối ưu ràng buộc đẳng thức), và Chương 11 (Phương pháp điểm trong).
• Yurii Nesterov, Lectures on Convex Optimization, Springer.
• Jorge Nocedal, Stephen J. Wright, Numerical Optimization, Springer.

Tiếp theo: Bài 05: Tối ưu hóa trong Huấn luyện Học sâu: Mini-batch SGD và Momentum.