Một ràng buộc đẳng thức tuyến tính như $x_1+x_2+x_3=1$ trông như một điều kiện phải canh chừng suốt quá trình giải. Thực ra nó còn là một thông tin: Nó nói rằng chỉ có hai trong ba biến được tự do, biến còn lại bị xác định. Dùng thông tin ấy, ta có thể bỏ hẳn ràng buộc và giải một bài toán ít biến hơn, không còn ràng buộc nào.

Trang này trình bày hai phép biến đổi cùng một tinh thần: Khử ràng buộc đẳng thức bằng cách hóa tập nghiệm của nó, và tối ưu theo từng nhóm biến, tức giải trước phần dễ của bài toán rồi mới giải phần còn lại. Cả hai đều cho bài toán tương đương theo nghĩa của chủ đề trước. Ta sẽ xem chúng giữ tính lồi ra sao, và cả cái giá phải trả khi dùng chúng.

1. Tham số hóa tập nghiệm của một hệ tuyến tính

Giả sử bài toán lồi có ràng buộc đẳng thức $Ax=b$, với $A\in {\mathbb{R}}^{p\times n}$. Nếu hệ vô nghiệm thì bài toán bất khả thi và không còn gì để làm. Nếu hệ có nghiệm, gọi $x_0$ là một nghiệm bất kỳ và $F\in {\mathbb{R}}^{n\times k}$ là một có không gian ảnh bằng đúng không gian hạch của $A$, tức $\mathcal{R}(F)=\mathcal{N}(A)$. Khi đó mọi nghiệm của $Ax=b$ có dạng

$$x=Fz+x_0,z\in {\mathbb{R}}^k.$$

Lý do rất đơn giản: Hiệu của hai nghiệm nằm trong hạch của $A$, và mọi vector trong hạch đều viết được thành $Fz$. Có thể chọn $F$ có các cột độc lập, khi đó $k=n-\mathrm{rank}A$. Thay vào bài toán, ta được

$$\begin{array}{rl}& \text{minimize}{f}_0(Fz+x_0)\\ & \text{subject to}{f}_i(Fz+x_0)\le 0,i=1,\dots ,m,\end{array}$$

theo biến $z$, không còn ràng buộc đẳng thức nào và ít hơn $\mathrm{rank}A$ biến. Từ nghiệm $z^{\star }$ ta lấy lại $x^{\star }=F{z}^{\star }+x_0$. Ngược lại, mọi nghiệm $x^{\star }$ của bài toán gốc đều khả thi, nên viết được thành $Fz+x_0$ với một $z$ nào đó, và $z$ ấy là nghiệm của bài toán mới.

Tính lồi được giữ nguyên, vì hợp của một với một ánh xạ affine là hàm lồi. Về nguyên tắc lý thuyết, ta hoàn toàn có thể quy việc nghiên cứu các bài toán lồi có ràng buộc đẳng thức về bài toán không có ràng buộc đẳng thức.

2. Ví dụ: Kết hợp ba phép đo

Ba cảm biến cùng đo một đại lượng, cho ba kết quả không chệch, độc lập, với phương sai lần lượt là 1, 2 và 3. Ta muốn lấy trung bình có trọng số $x_1,x_2,x_3$ của ba kết quả. Để ước lượng vẫn không chệch, các trọng số phải cộng lại bằng 1. Phương sai của ước lượng tổng hợp là $x_1^2+2x_2^2+3x_3^2$, nên bài toán là

$$\text{minimize}{x}_1^2+2x_2^2+3x_3^2\text{subject to}{x}_1+x_2+x_3=1.$$

Chọn $x_0=(1,0,0)$ và hóa $x_2=z_1$, $x_3=z_2$, $x_1=1-z_1-z_2$. Bài toán thành cực tiểu không ràng buộc

$$g(z)=(1-z_1-z_2{)}^2+2z_1^2+3z_2^2.$$

Cho hai đạo hàm riêng bằng 0, ta được hệ $3z_1+z_2=1$ và $z_1+4z_2=1$, với nghiệm $z_1=\frac{3}{11}$, $z_2=\frac{2}{11}$. Vậy các trọng số tối ưu là

$$x^{\star }=(\frac{6}{11},\frac{3}{11},\frac{2}{11}),$$

và phương sai nhỏ nhất bằng $\frac{6}{11}\approx 0.545$, nhỏ hơn cả phương sai của cảm biến tốt nhất. Các trọng số tỉ lệ với $1,\frac{1}{2},\frac{1}{3}$, tức tỉ lệ nghịch với phương sai: Cảm biến càng nhiễu càng được tin ít. Quy tắc trọng số theo nghịch đảo phương sai này là một kết quả kinh điển của thống kê, và ở đây nó rơi ra từ một phép khử biến.

Mô phỏng dưới đây cho thấy điều tương tự với một hàm hai biến. Đường thẳng $a^{T}x=b$ được hóa bởi một số $z$, và bài toán có ràng buộc trở thành bài toán cực tiểu một parabol.

Đi dọc ràng buộc thay vì giữ ràng buộc

Các đường ellipse là đường mức của f. Mọi điểm khả thi nằm trên đường thẳng aᵀx = b và được mô tả bởi một số duy nhất z, nên bài toán còn lại chỉ là cực tiểu một parabol theo z.

đường ràng buộc và điểm x(z)đường mức qua nghiệmgradient tại nghiệm

Góc của pháp tuyến a: 45°Vế phải b = 0.71Tham số z = −1.20 Hiện gradient tại nghiệm

a = (0.71, 0.71), x₀ = (0.50, 0.50), d = (−0.71, 0.71). Điểm x(z) = (1.35, −0.35) cho g(z) = 4.048.

Cực tiểu của parabol: z* = −0.237, nên x* = (0.669, 0.335) và f(x*) = 2.656.

Tại x*, ∇f = (−2.661, −2.661) = ν·a với ν = −3.764: gradient vuông góc với đường ràng buộc, nên đường mức tiếp xúc với nó.

Gợi ý thao tác

1. Kéo z cho tới khi chấm tím trùng chấm vàng. Lúc đó đồ thị g(z) ở dưới có gì đặc biệt?
2. Đặt góc 45° và b ≈ 0.71, tức ràng buộc x₁ + x₂ = 1. So x* với kết quả tính tay (2/3, 1/3).
3. Đổi b để đường thẳng đi qua tâm (2, 1) của các ellipse. Khi đó ν bằng bao nhiêu, và vì sao?
4. Xoay góc mà giữ b. Gradient tại nghiệm có bao giờ không vuông góc với đường ràng buộc không?

Mô phỏng còn cho thấy một điều sẽ trở thành trung tâm của Lecture 03. Tại nghiệm, gradient của $f$ vuông góc với đường ràng buộc, tức $\mathrm{\nabla }f(x^{\star })=\nu a$ với một số $\nu$ nào đó. Con số $\nu$ ấy chính là của ràng buộc đẳng thức.

3. Khi nào không nên khử

Nếu khử ràng buộc luôn khả thi về mặt lý thuyết, vì sao trong thực hành người ta vẫn giữ chúng? Câu trả lời nằm ở cấu trúc tính toán: Phép khử có thể làm bài toán mất đi trực giác vật lý ban đầu và phá hỏng cấu trúc đặc thù mà thuật toán cần, đặc biệt là tính thưa khi số biến rất lớn.

Ví dụ trên cho thấy điều đó ở quy mô nhỏ. Hessian của hàm mục tiêu gốc theo $x$ là đường chéo $\mathrm{diag}(2,4,6)$, nhưng Hessian của $g$ theo $z$ là

$${\mathrm{\nabla }}^{2}g=\left[\begin{array}{cc}6& 2\\ 2& 8\end{array}\right],$$

không còn đường chéo nữa. Với $n$ biến và ràng buộc ${\mathbf{1}}^{T}x=1$, khử $x_n=1-x_1-\cdots -x_{n-1}$ biến Hessian đường chéo thành một đường chéo cộng một ma trận hạng một mà mọi phần tử đều khác 0. Với $n$ cỡ một triệu, như khi tối ưu trên một phân phối xác suất có rất nhiều trạng thái, ma trận đường chéo lưu được dễ dàng, còn ma trận dày thì không. Phép khử còn phá vỡ tính đối xứng giữa các biến, vì một biến bị chọn ra để "chịu" ràng buộc. Vì thế phương pháp Newton cho bài toán có ràng buộc đẳng thức ở Lecture 04 giữ nguyên ràng buộc và xử lý nó trực tiếp bằng hệ Newton–KKT.

4. Thêm biến và ràng buộc đẳng thức

Chiều ngược lại cũng hữu ích. Khi một hàm có dạng $f_i(A_{i}x+b_i)$, ta có thể đặt biến mới $y_i=A_{i}x+b_i$ và viết

$$\begin{array}{rl}& \text{minimize}{f}_0(y_0)\\ & \text{subject to}{f}_i(y_i)\le 0,i=1,\dots ,m,\\ & \phantom{\text{subject to}}{y}_i=A_{i}x+b_i,i=0,\dots ,m.\end{array}$$

Bài toán có thêm biến và thêm ràng buộc, nhưng hàm mục tiêu và các ràng buộc bất đẳng thức giờ đây độc lập với nhau, vì chúng phụ thuộc vào những biến khác nhau. Các ràng buộc mới tuyến tính, nên tính lồi được giữ nguyên. Chẳng hạn bài toán cực tiểu $\parallel Ax-b{\parallel }_1$ có thể viết thành cực tiểu $\parallel y{\parallel }_1$ với $y=Ax-b$: Phần không trơn của bài toán, chuẩn ${\ell }_1$, giờ chỉ tác động lên một biến riêng, còn dữ liệu $A,b$ nằm hết trong một ràng buộc tuyến tính. Cách viết này giúp việc thiết lập và tính toán hàm đối ngẫu Lagrange (nội dung trọng tâm của Lecture 03) trở nên thuận tiện và trực tiếp hơn hẳn.

5. Tối ưu theo từng nhóm biến

Với mọi hàm $f$ của hai nhóm biến, ta luôn có

$$\underset{x,y}{inf}f(x,y)=\underset{x}{inf}\tilde{f}(x),\tilde{f}(x)=\underset{y}{inf}f(x,y).$$

Nói cách khác, có thể cực tiểu trước theo một nhóm biến, được một hàm của nhóm còn lại, rồi mới cực tiểu hàm đó. Khi các ràng buộc tách riêng theo từng nhóm, phép biến đổi này cho một bài toán tương đương ít biến hơn. Nó đặc biệt có giá trị khi bước cực tiểu theo $y$ có công thức đóng.

Hàm toàn phương và phần bù Schur. Xét một hàm toàn phương lồi chặt, với ràng buộc chỉ đặt lên $x_1$. Lấy một ví dụ số cụ thể:

$$f(x_1,x_2)=3x_1^2+2x_1{x}_2+2x_2^2.$$

Với $x_1$ cố định, đạo hàm theo $x_2$ là $2x_1+4x_2$, triệt tiêu tại $x_2=-\frac{x_1}{2}$. Thay vào, ta được $\tilde{f}(x_1)=\frac{5}{2}{x}_1^2$. Hệ số $\frac{5}{2}=3-1\cdot \frac{1}{2}\cdot 1$ chính là phần bù Schur của khối $P_{22}=2$ trong $\left[\begin{array}{cc}3& 1\\ 1& 2\end{array}\right]$. Nếu thêm ràng buộc $x_1\ge 1$, bài toán gốc tương đương cực tiểu $\frac{5}{2}{x}_1^2$ với $x_1\ge 1$, có nghiệm $x_1=1$, và ta lấy lại $x_2=-\frac{1}{2}$ từ công thức của bước đầu. Chủ đề phần bù Schur ở cuối chương sẽ khai thác công thức này một cách tổng quát.

Hệ số chặn của hồi quy tuyến tính. Bài toán bình phương tối thiểu với một đặc trưng và hệ số chặn là cực tiểu $\sum _i(y_i-w{u}_i-c{)}^2$ theo $(w,c)$. Cố định $w$, đạo hàm theo $c$ bằng 0 khi $c=\overline{y}-w\overline{u}$, với $\overline{u},\overline{y}$ là trung bình của dữ liệu. Thay vào, phần còn lại là

$$\tilde{f}(w)=\sum _i((y_i-\overline{y})-w(u_i-\overline{u}){)}^2,$$

tức bài toán hồi quy không có hệ số chặn trên dữ liệu đã trừ trung bình. Với dữ liệu tự đặt $u=(1,2,4,7)$ và $y=(3,4,9,14)$, ta có $\overline{u}=3.5$, $\overline{y}=7.5$, và $w^{\star }=\frac{40}{21}\approx 1.905$, rồi $c^{\star }=7.5-w^{\star }\cdot 3.5=\frac{5}{6}$. Lời giải trực tiếp bằng bình phương tối thiểu hai biến cho đúng kết quả ấy. Đây là lý do việc chuẩn hóa dữ liệu về trung bình 0 trước khi huấn luyện không làm mất gì: Hệ số chặn đã được tối ưu sẵn.

Về tính lồi, ta có định lý cơ bản: Cực tiểu một đồng thời theo $(x,y)$ trên một nhóm biến cho một hàm lồi theo nhóm còn lại. Đó chính là phép toán cực tiểu hóa theo một phần biến ở Lecture 01, nay được dùng như một phép biến đổi bài toán.

6. Phép biến đổi nào giữ tính lồi

Bây giờ, ta hãy tổng hợp lại các phép biến đổi của chủ đề trước và chủ đề này, đồng thời phân tích xem phép biến đổi nào giữ được dạng chuẩn lồi.

Phép biến đổi	Giữ tính lồi khi nào	Lý do
Khử ràng buộc đẳng thức $Ax=b$	luôn giữ	hợp của với ánh xạ affine $Fz+x_0$
Thêm biến $y_i=A_{i}x+b_i$	luôn giữ	ràng buộc mới tuyến tính
Thêm biến bù	chỉ cho bất đẳng thức affine	ràng buộc đẳng thức phải affine
Dạng	luôn giữ	$f_0(x)-t$ lồi theo $(x,t)$
Cực tiểu theo một nhóm biến	khi $f_0$ lồi đồng thời theo mọi biến	cực tiểu hóa theo một phần biến giữ tính lồi
Đổi biến	không tự động	chỉ chắc chắn với đổi biến affine

Dòng cuối là dòng dễ quên nhất. Đổi biến qua hàm mũ ở chủ đề trước làm một bài toán không lồi trở thành lồi, còn đổi biến $x=z^2$ thì làm một bài toán lồi mất tính lồi. Không có quy tắc chung, nên mỗi lần đổi biến phải kiểm tra lại.

7. Những câu hỏi để đào sâu

Câu 1. $F$ trong phép hóa $x=Fz+x_0$ không duy nhất. Đổi sang một ma trận $F^{\prime }$ khác, cũng có $\mathcal{R}(F^{\prime })=\mathcal{N}(A)$, thì nghiệm $x^{\star }$ và giá trị tối ưu có đổi không? Còn những gì có thể đổi?

Xem lời giải thích

Nghiệm $x^{\star }$ và giá trị tối ưu không đổi, vì cả hai cách hóa đều mô tả đúng cùng một tập khả thi và cùng một hàm trên tập đó. Thứ thay đổi là biến $z$: Nếu các cột của $F$ và $F^{\prime }$ đều độc lập thì $F^{\prime }=FT$ với một khả nghịch $T$, và $z^{\prime }=T^{-1}z$. Kéo theo đó, Hessian của hàm mới đổi thành $T^T({\mathrm{\nabla }}^{2}g)T$, nên độ cong, số điều kiện và tốc độ của phương pháp gradient đều có thể khác. Chọn $F$ có các cột trực chuẩn là một lựa chọn tốt về mặt số học, vì khi đó phép tham số hóa không làm méo khoảng cách.

Câu 2. Trong ví dụ ba cảm biến, nếu thêm điều kiện mọi trọng số không âm thì nghiệm có đổi không? Còn nếu một cảm biến có phương sai rất lớn, chẳng hạn 1000?

Xem lời giải thích

Nghiệm không đổi, vì trọng số tối ưu tỉ lệ với nghịch đảo phương sai nên luôn dương: Điều kiện không âm thỏa sẵn, không chặt. Với phương sai 1000, trọng số của cảm biến ấy là $\frac{1/1000}{1+1/2+1/1000}$, khoảng $0.0007$. Cảm biến đó gần như bị bỏ qua, nhưng không bao giờ bị loại hẳn, vì mỗi phép đo độc lập dù nhiễu đến đâu vẫn mang thêm một chút thông tin. Trong mô hình này, trọng số chỉ bằng 0 khi phương sai lớn vô hạn.

Câu 3. Trong bước cực tiểu theo $x_2$ ở mục 5, ta cần $P_{22}=2>0$. Nếu $P_{22}=0$, chẳng hạn $f(x_1,x_2)=3x_1^2+2x_1{x}_2$, chuyện gì xảy ra?

Xem lời giải thích

Với $x_1\ne 0$ cố định, hàm $3x_1^2+2x_1{x}_2$ tuyến tính theo $x_2$ với hệ số $2x_1\ne 0$, nên giảm về $-\mathrm{\infty }$ theo một chiều. Vậy $\tilde{f}(x_1)=-\mathrm{\infty }$ với mọi $x_1\ne 0$, và $\tilde{f}(0)=0$. Bài toán gốc không bị chặn dưới, và bước cực tiểu theo từng nhóm biến cho thấy điều đó ngay. Điều này phù hợp với hình học: $\left[\begin{array}{cc}3& 1\\ 1& 0\end{array}\right]$ có định thức $-1<0$, nên có một trị riêng âm, và hàm toàn phương không lồi. Phần bù Schur chỉ được định nghĩa khi khối bị khử khả nghịch, và nó cho kết luận về tính xác định dương khi khối ấy dương xác định.

Câu 4. Thêm biến $y=Ax-b$ làm bài toán lớn hơn. Vì sao một bài toán lớn hơn lại có thể dễ giải hơn?

Xem lời giải thích

Vì độ khó nằm ở cấu trúc nhiều hơn là ở số biến. Trong cách viết mới, chuẩn ${\ell }_1$ chỉ tác động lên $y$ và tách được theo từng thành phần, nên các phép tính như cực tiểu hóa từng phần hay phép chiếu có công thức đóng cho từng $y_i$. $A$ chỉ còn xuất hiện trong một ràng buộc tuyến tính, nơi đại số tuyến tính xử lý rất hiệu quả. Nhiều thuật toán hiện đại cho bài toán lớn, kể cả trong học máy, dựa đúng vào việc tách bài toán thành những phần mà mỗi phần dễ xử lý. Đây là hình ảnh ngược với mục 3: Ở đó khử biến làm mất cấu trúc, ở đây thêm biến làm lộ cấu trúc.

Câu 5. Hồi quy tuyến tính có điều chuẩn ridge thường không phạt hệ số chặn: Hàm mục tiêu là $\sum _i(y_i-w{u}_i-c{)}^2+\lambda w^2$. Lập luận ở mục 5 còn đúng không?

Xem lời giải thích

Còn đúng. Số hạng phạt không chứa $c$, nên với $w$ cố định, bước cực tiểu theo $c$ vẫn cho $c=\overline{y}-w\overline{u}$. Phần còn lại là ridge không hệ số chặn trên dữ liệu đã trừ trung bình. Nếu ta phạt cả $c$ thì kết luận đổi: Khi đó $c$ bị kéo về 0 và không còn bằng $\overline{y}-w\overline{u}$, và kết quả phụ thuộc vào việc dữ liệu có được trừ trung bình hay không. Đó là lý do người ta thường không phạt hệ số chặn.

8. Bài tập tự luyện

Bài tập 1: Khử một ràng buộc

Giải bài toán cực tiểu $x_1^2+x_2^2+x_3^2$ với $x_1+2x_2+3x_3=14$ bằng cách khử $x_1$. Kiểm tra rằng nghiệm tỉ lệ với vector hệ số $(1,2,3)$ và giải thích điều đó bằng hình học.

Gợi ý

Sau khi khử, cho hai đạo hàm riêng theo $x_2,x_3$ bằng 0 rồi giải hệ hai phương trình.

Lời giải

Khử $x_1=14-2x_2-3x_3$, hàm mục tiêu thành $(14-2x_2-3x_3{)}^2+x_2^2+x_3^2$. Đạo hàm theo $x_2$ và $x_3$ bằng 0 cho $-4(14-2x_2-3x_3)+2x_2=0$ và $-6(14-2x_2-3x_3)+2x_3=0$, tức $10x_2+12x_3=56$ và $12x_2+20x_3=84$. Giải ra $x_2=2$, $x_3=3$, rồi $x_1=14-4-9=1$. Nghiệm $(1,2,3)$ đúng bằng vector hệ số, với giá trị tối ưu 14. Về hình học, ta đang tìm điểm gần gốc nhất của một mặt phẳng, và điểm đó là chân đường vuông góc hạ từ gốc, nằm theo hướng pháp tuyến $(1,2,3)$.

Bài tập 2: Cực tiểu theo từng nhóm biến

Cho $f(x,y)=x^2+4xy+5y^2-2y$. (a) Với $x$ cố định, tìm $y$ cực tiểu và hàm $\tilde{f}(x)$. (b) Giải bài toán cực tiểu $f$ với ràng buộc $x\ge 1$.

Lời giải

(a) Đạo hàm theo $y$ là $4x+10y-2$, triệt tiêu tại $y=\frac{1-2x}{5}$. Thay vào, $\tilde{f}(x)=x^2-\frac{(4x-2{)}^2}{20}$, rút gọn thành $\frac{1}{5}{x}^2+\frac{4}{5}x-\frac{1}{5}$. Hệ số $\frac{1}{5}$ của $x^2$ bằng $1-\frac{2\cdot 2}{5}$, đúng phần bù Schur của khối $5$ trong $\left[\begin{array}{cc}1& 2\\ 2& 5\end{array}\right]$. (b) Hàm $\tilde{f}$ là parabol có đỉnh tại $x=-2$, nên trên $x\ge 1$ nó tăng, và nghiệm là $x=1$ với $\tilde{f}(1)=\frac{1}{5}+\frac{4}{5}-\frac{1}{5}=\frac{4}{5}$. Lấy lại $y=\frac{1-2}{5}=-\frac{1}{5}$, và kiểm tra trực tiếp $f(1,-\frac{1}{5})=1-\frac{4}{5}+\frac{1}{5}+\frac{2}{5}=\frac{4}{5}$.

Bài tập 3: Hệ số chặn

Với dữ liệu $u=(0,1,2,5)$ và $y=(1,2,2,7)$, tìm $(w,c)$ cực tiểu $\sum _i(y_i-w{u}_i-c{)}^2$ bằng cách cực tiểu theo $c$ trước.

Lời giải

Trung bình $\overline{u}=2$ và $\overline{y}=3$. Dữ liệu đã trừ trung bình là $u-\overline{u}=(-2,-1,0,3)$ và $y-\overline{y}=(-2,-1,-1,4)$. Khi đó $w^{\star }=\frac{4+1+0+12}{4+1+0+9}=\frac{17}{14}$, khoảng $1.214$, và $c^{\star }=\overline{y}-w^{\star }\overline{u}=3-\frac{17}{7}=\frac{4}{7}$, khoảng $0.571$.

Tóm tắt

Ràng buộc $Ax=b$ có thể khử bằng cách viết mọi nghiệm thành $Fz+x_0$, với $F$ có ảnh bằng hạch của $A$. Bài toán mới tương đương, giữ tính lồi và ít biến hơn, nhưng có thể mất tính thưa và tính đối xứng, nên trong thực tế người ta thường giữ ràng buộc. Chiều ngược lại, thêm biến cùng ràng buộc đẳng thức tuyến tính giúp tách các phần của bài toán ra khỏi nhau.

Cực tiểu theo từng nhóm biến cho một bài toán tương đương ít biến hơn, và giữ tính lồi khi hàm mục tiêu lồi đồng thời. Với hàm toàn phương, bước cực tiểu cho phần bù Schur. Với hồi quy tuyến tính, nó cho thấy hệ số chặn tối ưu chính là phép trừ trung bình của dữ liệu.

Tài liệu tham khảo

• Stephen Boyd, Lieven Vandenberghe, Convex Optimization, Cambridge University Press.