Chủ đề trước định nghĩa SDP nhưng để lại một câu hỏi thực tế: Những ràng buộc nào viết được thành bất đẳng thức tuyến tính? Một ràng buộc như $\parallel A(x){\parallel }_2\le t$, chuẩn phổ của một ma trận phụ thuộc vào $x$, trông hoàn toàn phi tuyến. Công cụ biến những ràng buộc như vậy thành LMI là phần bù Schur, một kết quả nhỏ của đại số tuyến tính nhưng được dùng ở khắp nơi trong tối ưu lồi.

Bài giảng này tiếp cận phần bù Schur dưới góc nhìn tối ưu hóa, tức nghiệm của một bài toán cực tiểu dạng toàn phương, rồi vận dụng công cụ này để chuyển hóa ba dạng ràng buộc phi tuyến phổ biến thành LMI và giải bài toán cực tiểu trị riêng lớn nhất.

1. Phần bù Schur

Xét một đối xứng chia khối

$$X=\left[\begin{array}{cc}A& B\\ B^T& C\end{array}\right],A\in {\mathbb{S}}^k.$$

Nếu $A$ khả nghịch,

$$S=C-B^T{A}^{-1}B$$

được gọi là phần bù Schur của $A$ trong $X$. Nó xuất hiện trong nhiều công thức, chẳng hạn $detX=detA\cdot detS$, và nó là nghịch đảo của khối dưới phải trong $X^{-1}$.

Cách hiểu hữu ích nhất cho tối ưu là qua một bài toán cực tiểu. Giả sử $A\succ 0$ và xét dạng toàn phương của $X$ tại vector $(u,v)$, cực tiểu theo $u$ với $v$ cố định:

$$\underset{u}{inf}{\left[\begin{array}{c}u\\ v\end{array}\right]}^T\left[\begin{array}{cc}A& B\\ B^T& C\end{array}\right]\left[\begin{array}{c}u\\ v\end{array}\right]=\underset{u}{inf}(u^{T}Au+2v^T{B}^{T}u+v^{T}Cv).$$

Đạo hàm theo $u$ bằng 0 khi $u=-A^{-1}Bv$, và thay vào cho giá trị nhỏ nhất $v^{T}Sv$. Phần bù Schur chính là "phần còn lại" của dạng toàn phương sau khi đã tối ưu hết theo khối biến thứ nhất. Đây đúng là phép cực tiểu theo từng nhóm biến đã gặp ở đầu chương, ở đó với ví dụ $3x_1^2+2x_1{x}_2+2x_2^2$.

Từ cách hiểu này suy ra ngay tiêu chuẩn của khối:

• $X\succ 0$ khi và chỉ khi $A\succ 0$ và $S\succ 0$.
• Nếu $A\succ 0$, thì $X⪰0$ khi và chỉ khi $S⪰0$.

Lý do cho ý thứ hai: Điều kiện $X⪰0$ nghĩa là dạng toàn phương không âm tại mọi $(u,v)$, tức là giá trị nhỏ nhất theo $u$, chính là $v^{T}Sv$, không âm với mọi $v$. Ví dụ nhỏ: Với $X=\left[\begin{array}{cc}2& 1\\ 1& 1\end{array}\right]$, ta có $S=1-\frac{1}{2}=\frac{1}{2}>0$, nên $X\succ 0$, khớp với hai trị riêng khoảng $0.382$ và $2.618$. Một ví dụ khối: $3\times 3$ với khối $A=2I_2$, cột $B=(1,1)$ và góc $C=c$ có phần bù Schur $S=c-\frac{1+1}{2}=c-1$, nên nó đúng khi $c\ge 1$. Tại $c=1$, trị riêng nhỏ nhất của nó đúng bằng 0.

2. Biến ràng buộc phi tuyến thành LMI

Đọc tiêu chuẩn trên theo chiều ngược lại: Một ràng buộc phi tuyến dạng "$C-B^T{A}^{-1}B⪰0$", với $A\succ 0$, tương đương với một khối . Nếu $A$, $B$, $C$ phụ thuộc affine vào biến, ma trận khối ấy là một LMI. Ba ví dụ quan trọng:

Tỉ số bậc hai trên tuyến tính. Với $y>0$, ràng buộc ${\displaystyle \frac{x^{T}x}{y}}\le t$ tương đương với

$$\left[\begin{array}{cc}yI& x\\ x^T& t\end{array}\right]⪰0,$$

vì phần bù Schur của khối $yI$ là $t-x^{T}x/y$.

Nón bậc hai. Với $t>0$, ràng buộc $\parallel u{\parallel }_2\le t$ tương đương $t-u^{T}u/t\ge 0$, tức

$$\left[\begin{array}{cc}tI& u\\ u^T& t\end{array}\right]⪰0.$$

Trường hợp $t=0$ cũng khớp: khi đó chỉ khi $u=0$. Vì vậy mọi ràng buộc nón bậc hai đều là một LMI, và mọi SOCP đều là SDP, như chủ đề trước đã báo trước. Chẳng hạn với $u=(3,4)$, ma trận trên nửa xác định dương đúng khi $t\ge 5=\parallel u{\parallel }_2$.

Chuẩn phổ. Chuẩn phổ $\parallel A{\parallel }_2$, giá trị kỳ dị lớn nhất của $A\in {\mathbb{R}}^{p\times q}$, thỏa $\parallel A{\parallel }_2\le t$ khi và chỉ khi $A^{T}A⪯t^{2}I$ và $t\ge 0$. Áp dụng phần bù Schur, điều kiện này tương đương với

$$\left[\begin{array}{cc}t{I}_p& A\\ A^T& t{I}_q\end{array}\right]⪰0.$$

Nếu $A(x)=A_0+x_1{A}_1+\cdots +x_n{A}_n$ phụ thuộc affine vào $x$, khối là một LMI theo $(x,t)$, và bài toán cực tiểu chuẩn phổ $\parallel A(x){\parallel }_2$ là SDP: Cực tiểu $t$ với ràng buộc trên.

3. Cực tiểu trị riêng lớn nhất

Với một đối xứng $A(x)$ phụ thuộc affine vào $x$, trị riêng lớn nhất là

$${\lambda }_{max}(A(x))=\underset{\parallel u{\parallel }_2=1}{sup}{u}^{T}A(x)u.$$

Với mỗi $u$ cố định, $u^{T}A(x)u$ là hàm affine của $x$, nên ${\lambda }_{max}$ là supremum của một họ hàm affine, do đó lồi. Ràng buộc ${\lambda }_{max}(A(x))\le t$ tương đương $tI-A(x)⪰0$, một LMI, nên bài toán cực tiểu trị riêng lớn nhất là SDP:

$$\text{minimize}t\text{subject to}tI-A(x)⪰0.$$

Bài toán này có một đặc điểm quan trọng: Nó thường không trơn tại nghiệm. Ví dụ tự đặt $A(x)=\left[\begin{array}{cc}x& \epsilon \\ \epsilon & 1-x\end{array}\right]$ có hai trị riêng $\frac{1}{2}\pm \sqrt{(x-\frac{1}{2}{)}^2+{\epsilon }^2}$. Trị riêng lớn nhất nhỏ nhất bằng $\frac{1}{2}+\epsilon$ tại $x=\frac{1}{2}$. Với $\epsilon >0$, hai trị riêng không bao giờ bằng nhau và ${\lambda }_{max}$ khả vi. Khi $\epsilon =0$, chéo, ${\lambda }_{max}=max\{x,1-x\}$ có một góc nhọn đúng tại nghiệm $x=\frac{1}{2}$, nơi hai trị riêng bằng nhau. Hiện tượng này không phải ngẫu nhiên. Cực tiểu trị riêng lớn nhất có xu hướng đẩy nhiều trị riêng lên cùng một mức, và tại những điểm trị riêng lớn nhất có bội lớn hơn 1, hàm không khả vi. Vì vậy các phương pháp gradient thông thường xử lý bài toán này kém, còn cách viết SDP thì không gặp vấn đề gì.

Trị riêng lớn nhất là một hàm lồi

Hai đường cong là hai trị riêng của A(x) = [[x, ε], [ε, 1 − x]] theo x. Đường phía trên, λ_max, là hàm lồi, và cực tiểu nó là một bài toán SDP. Kéo ε về 0 để thấy chuyện gì xảy ra khi hai trị riêng chạm nhau.

λ_max(A(x))tiếp tuyến dưới tại xcực tiểu của λ_max

x = 0.00Phần tử ngoài đường chéo ε = 0.30

A(x) có hai trị riêng −0.083 và 1.083.

Giá trị nhỏ nhất của λ_max là 1/2 + ε = 0.800, đạt tại x = 1/2. SDP tương ứng: cực tiểu t với tI − A(x) ⪰ 0.

Độ dốc của λ_max tại x là −0.857, và tiếp tuyến nét đứt nằm dưới toàn bộ đường cong, đúng như với mọi hàm lồi.

Gợi ý thao tác

1. Kéo x qua lại với ε = 0.3. Hai trị riêng có bao giờ bằng nhau không? Khoảng cách nhỏ nhất giữa chúng là bao nhiêu?
2. Đặt ε = 0. Hai đường bây giờ là hai đường thẳng nào, và λ_max có dạng gì tại x = 1/2?
3. Đường λ_min ở dưới là hàm lõm. Vì sao, và cực đại λ_min có là bài toán lồi không?
4. Tiếp tuyến nét đứt luôn nằm dưới λ_max. Điều đó nói gì về tính lồi?

Ý tưởng trên mở ra nhiều ứng dụng thực tiễn quan trọng: Tốc độ trộn của một chuỗi Markov đối xứng được đo bằng chuẩn phổ của chuyển trạng thái trừ đi ma trận chiếu lên phân phối đều, do đó bài toán tối ưu xác suất chuyển trên đồ thị để chuỗi trộn nhanh nhất chính là một SDP. Tương tự, bài toán ước lượng rủi ro xấu nhất của danh mục đầu tư khi ma trận hiệp phương sai chỉ được biết một phần (chẳng hạn chỉ biết chặn trên và chặn dưới của từng phần tử) cũng quy về một SDP với biến tối ưu là ma trận hiệp phương sai.

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

Câu 1. Tiêu chuẩn "$X⪰0$ khi và chỉ khi $S⪰0$" cần giả thiết $A\succ 0$. Hãy tìm một $X$ với $A=0$ để thấy giả thiết ấy không thể bỏ.

Xem lời giải thích

Lấy $X=\left[\begin{array}{cc}0& 1\\ 1& 1\end{array}\right]$, với $A=0$ không khả nghịch, nên phần bù Schur không xác định được. này có định thức $-1<0$, nên không , dù khối $C=1>0$. Về mặt cực tiểu, với $A=0$ dạng toàn phương là $2uv+v^2$, tuyến tính theo $u$, nên giá trị nhỏ nhất theo $u$ là $-\mathrm{\infty }$ khi $v\ne 0$. Trong trường hợp $A$ suy biến tổng quát, ta có thể mở rộng bổ đề Schur bằng giả nghịch đảo Moore–Penrose $A^{†}$, kèm theo điều kiện các cột của $B$ phải thuộc không gian ảnh của $A$.

Câu 2. Trị riêng lớn nhất là của . Còn trị riêng nhỏ nhất thì sao, và bài toán cực đại trị riêng nhỏ nhất có lồi không?

Xem lời giải thích

${\lambda }_{min}(A)=\underset{\parallel u{\parallel }_2=1}{inf}{u}^{T}Au$ là của một họ hàm tuyến tính theo $A$, nên lõm. Cực đại một hàm lõm là bài toán lồi, nên cực đại ${\lambda }_{min}(A(x))$ cũng là SDP: Cực đại $t$ với $A(x)-tI⪰0$. Hai bài toán "dễ" là cực tiểu ${\lambda }_{max}$ và cực đại ${\lambda }_{min}$. Hai bài toán ngược lại, cực đại ${\lambda }_{max}$ và cực tiểu ${\lambda }_{min}$, nói chung không lồi. Trong mô phỏng, đường ${\lambda }_{min}$ ở dưới có dạng một cái mái úp, đúng hình dạng của hàm lõm.

Câu 3. Bài toán cực tiểu ${\lambda }_{max}$ thường đưa nhiều trị riêng lên cùng một mức tại nghiệm. Hãy giải thích bằng trực giác, rồi cho biết điều đó ảnh hưởng thế nào tới các phương pháp dùng gradient.

Xem lời giải thích

Nếu tại một điểm chỉ có một trị riêng đạt giá trị lớn nhất, ta thường có thể di chuyển $x$ để kéo nó xuống mà các trị riêng khác chưa kịp vượt lên. Quá trình cực tiểu vì thế dừng lại ở chỗ mà việc kéo một trị riêng xuống buộc một trị riêng khác đi lên, thường là chỗ hai hay nhiều trị riêng lớn nhất bằng nhau. Tại đó ${\lambda }_{max}$ không khả vi, như góc nhọn khi $\epsilon =0$ trong mô phỏng. Phương pháp gradient sẽ dao động qua lại hai bên góc nhọn, vì gradient đổi hướng đột ngột, và không hội tụ tốt. Đây là lý do người ta giải bài toán trị riêng bằng SDP, hoặc bằng các phương pháp dành riêng cho hàm không trơn.

Câu 4. Dùng phần bù Schur, hãy viết ràng buộc $\parallel Ax-b{\parallel }_2\le t$ thành một LMI theo $(x,t)$.

Xem lời giải thích

Đây là ràng buộc nón bậc hai với $u=Ax-b$, phụ thuộc affine vào $x$. Theo mục 2, nó tương đương với

$$\left[\begin{array}{cc}tI& Ax-b\\ (Ax-b{)}^T& t\end{array}\right]⪰0,$$

một phụ thuộc affine vào $(x,t)$. Cách viết này hữu ích khi ràng buộc phải được ghép chung với những LMI khác thành một SDP. Khi bài toán chỉ có ràng buộc nón bậc hai, giải trực tiếp như một SOCP rẻ hơn nhiều so với chuyển sang SDP.

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

Bài tập 1: Tiêu chuẩn Schur

Với những $t$ nào thì $4\times 4$ có khối trên trái $2I_3$, cột cuối $(1,1,1,t)$ và hàng cuối đối xứng tương ứng, ?

Lời giải

Khối $A=2I_3\succ 0$, cột $B=(1,1,1)$ và $C=t$. Phần bù Schur là $S=t-B^T{A}^{-1}B=t-\frac{3}{2}$. Vậy khi và chỉ khi $t\ge 1.5$. Tại $t=1.5$ trị riêng nhỏ nhất bằng 0, và kiểm bằng số cho thấy tại $t=1.4$ trị riêng nhỏ nhất âm, khoảng $-0.058$.

Bài tập 2: Cực tiểu trị riêng lớn nhất

Tìm $x$ cực tiểu ${\lambda }_{max}\left(\left[\begin{array}{cc}x& 1\\ 1& -x\end{array}\right]\right)$ và giá trị nhỏ nhất. Viết SDP tương ứng.

Lời giải

có vết bằng 0 và định thức $-x^2-1$, nên hai trị riêng là $\pm \sqrt{x^2+1}$. Vậy ${\lambda }_{max}=\sqrt{x^2+1}$, nhỏ nhất bằng 1 tại $x=0$. SDP: Cực tiểu $t$ với $\left[\begin{array}{cc}t-x& -1\\ -1& t+x\end{array}\right]⪰0$. Với $x=0$, ma trận là $\left[\begin{array}{cc}t& -1\\ -1& t\end{array}\right]$, khi $t\ge 1$, khớp với kết quả trên.

Bài tập 3: Từ chuẩn tới LMI

Viết bài toán cực tiểu $\parallel A_0+x_1{A}_1+x_2{A}_2{\parallel }_2$ thành một SDP, với $A_0,A_1,A_2\in {\mathbb{R}}^{3\times 2}$. LMI có cỡ bao nhiêu?

Lời giải

Cực tiểu $t$ với $\left[\begin{array}{cc}t{I}_3& A(x)\\ A(x{)}^T& t{I}_2\end{array}\right]⪰0$, trong đó $A(x)=A_0+x_1{A}_1+x_2{A}_2$. khối có cỡ $(3+2)\times (3+2)=5\times 5$, phụ thuộc affine vào ba biến $(x_1,x_2,t)$.

Tóm tắt

Phần bù Schur $S=C-B^T{A}^{-1}B$ của khối $A$ trong một đối xứng chia khối là giá trị nhỏ nhất của dạng toàn phương theo khối biến thứ nhất. Từ đó, khi $A\succ 0$, ma trận khối khi và chỉ khi $S⪰0$. Đọc ngược tiêu chuẩn này, nhiều ràng buộc phi tuyến trở thành LMI: Tỉ số bậc hai trên tuyến tính, ràng buộc nón bậc hai và ràng buộc chuẩn phổ.

Trị riêng lớn nhất của một đối xứng phụ thuộc affine vào $x$ là , trị riêng nhỏ nhất là hàm lõm, và cực tiểu trị riêng lớn nhất là một SDP. Tại nghiệm, các trị riêng lớn nhất thường bằng nhau và hàm không khả vi, nên cách viết SDP đáng tin cậy hơn các phương pháp gradient thông thường.

Tài liệu tham khảo

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