Quy hoạch tuyến tính dùng thứ tự của từng thành phần: Điều kiện $Gx⪯h$ nghĩa là mọi thành phần của $h-Gx$ không âm. Lecture 01 đã cho thấy thứ tự này chỉ là một trường hợp của bất đẳng thức suy rộng, sinh bởi nón không âm. Thay nón không âm bằng một nón chính quy khác, ta được những họ bài toán mới có cùng cấu trúc với LP. Quan trọng nhất trong số đó là quy hoạch nửa xác định (semidefinite program, SDP), dùng nón các .

Trang này định nghĩa bài toán dạng nón và SDP, rồi nhìn của SDP qua một câu hỏi rất cụ thể của thống kê: Ba biến ngẫu nhiên có thể có những bộ hệ số tương quan nào?

1. Ràng buộc bất đẳng thức suy rộng

Ta mở rộng bài toán lồi dạng chuẩn bằng cách cho phép hàm ràng buộc nhận giá trị vector và dùng bất đẳng thức suy rộng:

$$\begin{array}{rl}& \text{minimize}{f}_0(x)\\ & \text{subject to}{f}_i(x){⪯}_{K_i}0,i=1,\dots ,m,\\ & \phantom{\text{subject to}}Ax=b,\end{array}$$

với $K_i$ là các nón chính quy và mỗi $f_i$ lồi theo nón $K_i$. Bài toán lồi thông thường là trường hợp $K_i={\mathbb{R}}_{+}$. Những tính chất quan trọng nhất vẫn giữ nguyên: , các tập mức dưới và tập nghiệm đều lồi, mọi cực tiểu cục bộ là toàn cục, và điều kiện tối ưu bậc nhất vẫn đúng mà không cần sửa gì.

2. Bài toán dạng nón

Bài toán đơn giản nhất thuộc loại này có hàm mục tiêu tuyến tính và một ràng buộc affine theo nón:

$$\text{minimize}{c}^{T}x\text{subject to}Fx+g{⪯}_{K}0,Ax=b.$$

Đây là bài toán dạng nón. Khi $K$ là nón không âm, nó chính là LP, nên có thể xem bài toán dạng nón như một LP mà thứ tự từng thành phần được thay bằng một thứ tự tổng quát hơn. Tương tự như với LP, ta gọi bài toán cực tiểu $c^{T}x$ với $x{⪰}_{K}0$, $Ax=b$ là dạng chuẩn, và bài toán không có ràng buộc đẳng thức là dạng bất đẳng thức. Chủ đề trước đã gặp một trường hợp riêng: SOCP là bài toán dạng nón với $K$ là tích của các nón bậc hai.

3. Quy hoạch nửa xác định

Khi $K={\mathbb{S}}_{+}^k$, nón các ma trận nửa xác định dương cỡ $k\times k$, bài toán dạng nón được gọi là quy hoạch nửa xác định:

$$\begin{array}{rl}& \text{minimize}{c}^{T}x\\ & \text{subject to}{x}_1{F}_1+\cdots +x_n{F}_n+G⪯0,\\ & \phantom{\text{subject to}}Ax=b,\end{array}$$

với $G,F_1,\dots ,F_n\in {\mathbb{S}}^k$. Ràng buộc thứ nhất là một bất đẳng thức tuyến tính (linear matrix inequality, LMI). Nó nói rằng ma trận $-(x_1{F}_1+\cdots +x_n{F}_n+G)$, phụ thuộc affine vào $x$, phải . Đó không phải điều kiện về từng phần tử, mà về mọi dạng toàn phương: Biểu thức $v^T(\cdots )v\le 0$ phải thỏa mãn với mọi vector $v$. Vì vậy một LMI tương đương với vô hạn bất đẳng thức tuyến tính theo $x$, mỗi bất đẳng thức ứng với một $v$, và là giao của vô hạn nửa không gian.

Nếu mọi $G,F_1,\dots ,F_n$ đều chéo, LMI tách thành $k$ bất đẳng thức tuyến tính, một cho mỗi phần tử đường chéo, và SDP trở thành LP. Dạng chuẩn của SDP, tương tự dạng chuẩn của LP, dùng biến ma trận $X\in {\mathbb{S}}^n$:

$$\text{minimize}\mathrm{tr}(CX)\text{subject to}\mathrm{tr}(A_{i}X)=b_i,i=1,\dots ,p,X⪰0.$$

Ở đây tích trong Frobenius $\mathrm{tr}(CX)=\sum _{i=1}^n\sum _{j=1}^n{C}_{ij}{X}_{ij}$ là dạng tổng quát của một hàm tuyến tính trên không gian các đối xứng. So với LP dạng chuẩn, vector không âm $x⪰0$ được thay bằng $X⪰0$, và tích vô hướng $c^{T}x$ được thay bằng $\mathrm{tr}(CX)$.

Một bài toán có nhiều LMI và cả bất đẳng thức tuyến tính vẫn được gọi là SDP, vì có thể gộp chúng lại. Một khối chéo khi và chỉ khi từng khối nửa xác định dương, nên các ràng buộc $F^{(1)}(x)⪯0,\dots ,F^{(K)}(x)⪯0$ và $Gx⪯h$ tương đương với một LMI duy nhất:

$$\mathrm{diag}(Gx-h,F^{(1)}(x),\dots ,F^{(K)}(x))⪯0.$$

4. Ví dụ: Ba hệ số tương quan

Cho ba biến ngẫu nhiên, tương quan của chúng là

$$R=\left[\begin{array}{ccc}1& {\rho }_{12}& {\rho }_{13}\\ {\rho }_{12}& 1& {\rho }_{23}\\ {\rho }_{13}& {\rho }_{23}& 1\end{array}\right].$$

Mỗi hệ số tương quan nằm trong $[-1,1]$, nhưng điều kiện ấy chưa đủ. Một như trên là ma trận tương quan của ba biến ngẫu nhiên nào đó khi và chỉ khi nó , vì $v^{T}Rv$ là phương sai của tổ hợp tuyến tính $\sum _i{v}_i{X}_i/{\sigma }_i$. Điều kiện $R⪰0$ là một LMI theo ba biến $({\rho }_{12},{\rho }_{13},{\rho }_{23})$.

Hãy hỏi một câu cụ thể: Nếu biến 1 tương quan 0.8 với biến 2, và biến 2 tương quan 0.8 với biến 3, thì biến 1 và biến 3 có thể tương quan bao nhiêu? Đó là hai SDP, cực tiểu và cực đại ${\rho }_{13}$ với ràng buộc $R⪰0$ khi ${\rho }_{12}={\rho }_{23}=0.8$. Với $3\times 3$ có các phần tử đường chéo bằng 1, điều kiện ở đây quy về định thức không âm, tức

$$-{\rho }_{13}^2+1.28{\rho }_{13}-0.28\ge 0,$$

nên ${\rho }_{13}\in [0.28,1]$. Tương quan không có tính bắc cầu tùy ý: Biến 1 và biến 3 bắt buộc phải tương quan dương ít nhất 0.28. Tổng quát hơn, với ${\rho }_{12}$ và ${\rho }_{23}$ cho trước,

$${\rho }_{13}\in [{\rho }_{12}{\rho }_{23}-\sqrt{(1-{\rho }_{12}^2)(1-{\rho }_{23}^2)},{\rho }_{12}{\rho }_{23}+\sqrt{(1-{\rho }_{12}^2)(1-{\rho }_{23}^2)}].$$

Giữ ${\rho }_{23}=c$ cố định, miền các cặp $({\rho }_{12},{\rho }_{13})$ hợp lệ là ellipse ${\rho }_{12}^2+{\rho }_{13}^2-2c{\rho }_{12}{\rho }_{13}\le 1-c^2$, nằm trọn vẹn bên trong hình vuông $[-1,1{]}^2$. Diện tích của nó là $\pi \sqrt{1-c^2}$: Khoảng 78.5% hình vuông khi $c=0$, nhưng chỉ còn khoảng 47% khi $c=0.8$. của một LMI là một có thể có biên cong, và người ta gọi nó là một spectrahedron. Trong không gian ba chiều, tập các tương quan $3\times 3$ có hình dạng giống một chiếc gối phồng, với bốn đỉnh nhọn ứng với những ma trận chỉ gồm các phần tử $\pm 1$.

Những bộ hệ số tương quan có thể xảy ra

Ba biến ngẫu nhiên có ma trận tương quan R. Giữ ρ₂₃ cố định, các cặp (ρ₁₂, ρ₁₃) làm R nửa xác định dương lấp đầy một ellipse, nhỏ hơn hẳn hình vuông [−1, 1]². Kéo điểm để xem trị riêng của R.

cặp hệ số làm R ⪰ 0hình vuông [−1, 1]² (nhạt)các giá trị ρ₁₃ được phép khi ρ₁₂ cố định

ρ₂₃ = 0.80 Cố định ρ₁₂ và tìm khoảng của ρ₁₃

R có hàng (1, 0.80, 0.50), (0.80, 1, 0.80), (0.50, 0.80, 1). Trị riêng: 0.091, 0.500, 2.409.

Mọi trị riêng không âm: đây là một ma trận tương quan hợp lệ.

Với ρ₁₂ = 0.80 và ρ₂₃ = 0.80, hai bài toán SDP cực tiểu và cực đại ρ₁₃ cho khoảng [0.280, 1.000].

Diện tích ellipse là π√(1 − c²) ≈ 1.885, khoảng 47.1% hình vuông.

Gợi ý thao tác

1. Đặt ρ₂₃ = 0.8 và kéo điểm tới ρ₁₂ = 0.8. ρ₁₃ nhỏ nhất có thể là bao nhiêu? Kết quả này nói gì về "tính bắc cầu" của tương quan?
2. Đưa ρ₂₃ về 0. Ellipse thành hình gì, và điều kiện R ⪰ 0 khi đó đơn giản thành gì?
3. Kéo ρ₂₃ gần 1. Ellipse dẹt lại về đường nào, và vì sao?
4. Đặt điểm ở góc (0.9, −0.9) với ρ₂₃ = 0.5. Trị riêng nhỏ nhất bằng bao nhiêu?

Đây cũng là bài toán thực tế. Trong tài chính hay trong thống kê nhiều chiều, các hệ số tương quan thường được ước lượng riêng lẻ từ những nguồn dữ liệu khác nhau. Ghép chúng lại có thể cho một không , và mọi phép tính dựa trên nó, chẳng hạn phương sai của một danh mục, có thể cho kết quả âm vô nghĩa. Tìm ma trận tương quan hợp lệ gần nhất là một SDP.

5. LP, SOCP và SDP lồng vào nhau

Ta đã có LP $\subset$ QP $\subset$ QCQP $\subset$ SOCP. SDP còn tổng quát hơn nữa: Một ràng buộc nón bậc hai $\parallel u{\parallel }_2\le t$ tương đương với LMI

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

một hệ quả của phần bù Schur mà chủ đề tiếp theo sẽ chứng minh. Vì vậy mọi SOCP đều là một SDP. Cái giá của sự tổng quát là chi phí tính toán: Một LMI cỡ $k\times k$ nặng hơn nhiều so với $k$ bất đẳng thức tuyến tính, nên trong thực hành người ta luôn dùng dạng bài toán hẹp nhất đủ để mô tả bài toán.

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

Câu 1. Ràng buộc $X⪰0$ có tương đương với "mọi phần tử của $X$ không âm" không?

Xem lời giải thích

Không, theo cả hai chiều. $\left[\begin{array}{cc}1& 2\\ 2& 1\end{array}\right]$ có mọi phần tử dương nhưng định thức $-3<0$, nên có một trị riêng âm, không . Ngược lại, $\left[\begin{array}{cc}1& -1\\ -1& 1\end{array}\right]$ có phần tử âm nhưng nửa xác định dương, vì dạng toàn phương là $(v_1-v_2{)}^2\ge 0$. Đây là lý do LMI được viết bằng ký hiệu $⪰$ riêng: Nó là thứ tự theo nón PSD, khác hẳn thứ tự từng phần tử.

Câu 2. Với ${\rho }_{23}=0.5$, điểm $({\rho }_{12},{\rho }_{13})=(0.9,-0.9)$ có cả hai hệ số trong $[-1,1]$. tương quan tương ứng có hợp lệ không? Hãy giải thích bằng trực giác.

Xem lời giải thích

Không. có trị riêng nhỏ nhất khoảng $-0.547$. Trực giác: Biến 1 gần như cùng chiều với biến 2 và gần như ngược chiều với biến 3, nên biến 2 và biến 3 phải gần như ngược chiều nhau, tức ${\rho }_{23}$ phải gần $-1$. Thế mà ${\rho }_{23}=0.5$ lại nói chúng cùng chiều vừa phải. Ba thông tin mâu thuẫn, và LMI $R⪰0$ chính là cách diễn đạt chính xác sự nhất quán mà trực giác ấy cảm nhận được.

Câu 3. của một LMI có thể có biên cong, thậm chí có những góc nhọn. Điều gì bảo đảm nó vẫn luôn là một ?

Xem lời giải thích

Có hai cách nhìn. Cách thứ nhất: Nón ${\mathbb{S}}_{+}^k$ lồi, và là ảnh ngược của nón ấy qua một ánh xạ affine $x\mapsto -(x_1{F}_1+\cdots +x_n{F}_n+G)$, nên lồi. Cách thứ hai: LMI tương đương với họ vô hạn bất đẳng thức $v^T(x_1{F}_1+\cdots +G)v\le 0$, mỗi bất đẳng thức tuyến tính theo $x$ với $v$ cố định. Giao của vô hạn nửa không gian là . Biên cong vì các nửa không gian có pháp tuyến thay đổi liên tục theo $v$. Góc xuất hiện ở những điểm mà có trị riêng 0 bội cao, như các ma trận tương quan chỉ gồm $\pm 1$.

Câu 4. Trong ví dụ, khoảng của ${\rho }_{13}$ được tính bằng tay qua định thức. Vì sao với lớn hơn, ta không thể chỉ đòi định thức không âm?

Xem lời giải thích

Vì định thức không âm không đủ để . $\mathrm{diag}(-1,-1,1)$ có định thức dương nhưng hai trị riêng âm. Ở ví dụ $3\times 3$ với đường chéo bằng 1, các định thức con $2\times 2$ là $1-{\rho }^2\ge 0$ đã được bảo đảm sẵn, và vì vậy chỉ còn phải kiểm định thức toàn phần, theo tiêu chuẩn mọi định thức con chính không âm. Với ma trận tổng quát, phải kiểm mọi định thức con chính, một số lượng tăng theo hàm mũ. Các bộ giải SDP không làm như vậy, mà làm việc trực tiếp với trị riêng và cấu trúc nón.

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

Bài tập 1: Từ LMI chéo về LP

Viết LMI $\mathrm{diag}(1-x_1,2-x_2,x_1+x_2)⪰0$ thành các bất đẳng thức tuyến tính và vẽ .

Lời giải

Một chéo khi và chỉ khi mọi phần tử đường chéo không âm, nên LMI tương đương $x_1\le 1$, $x_2\le 2$ và $x_1+x_2\ge 0$. là phần mặt phẳng nằm bên trái đường $x_1=1$, dưới đường $x_2=2$ và phía trên đường $x_1+x_2=0$. Ba đường thẳng cắt nhau từng đôi tại $(1,-1)$, $(1,2)$ và $(-2,2)$, và cả ba điểm đều thỏa ràng buộc còn lại, nên miền khả thi là tam giác với ba đỉnh ấy. Nó bị chặn, vì $x_1\ge -x_2\ge -2$ và $x_2\ge -x_1\ge -1$.

Bài tập 2: Hệ số tương quan

Biến 1 tương quan $0.6$ với biến 2, biến 2 tương quan $-0.6$ với biến 3. Hệ số tương quan giữa biến 1 và biến 3 có thể nằm trong khoảng nào?

Lời giải

Theo công thức ở mục 4, ${\rho }_{12}{\rho }_{23}=-0.36$ và $\sqrt{(1-0.36)(1-0.36)}=0.64$, nên ${\rho }_{13}\in [-1,0.28]$. Biến 1 và biến 3 có thể ngược chiều hoàn toàn, nhưng không thể cùng chiều quá 0.28.

Bài tập 3: Một LMI hai biến

Với những $(x,y)$ nào thì $\left[\begin{array}{cc}1& x\\ x& y\end{array}\right]⪰0$? Điểm $(1,2)$ và $(2,3)$ có thỏa không?

Lời giải

$2\times 2$ đối xứng khi và chỉ khi hai phần tử đường chéo không âm và định thức không âm. Phần tử đầu là 1, nên điều kiện còn $y\ge 0$ và $y-x^2\ge 0$, gộp lại là $y\ge x^2$: Miền phía trên parabol, một . Điểm $(1,2)$ thỏa vì $2\ge 1$, với hai trị riêng khoảng $0.382$ và $2.618$. Điểm $(2,3)$ không thỏa vì $3<4$, và ma trận có một trị riêng khoảng $-0.236$. LMI này chính là của hàm $x^2$ viết dưới dạng ma trận.

Tóm tắt

Thay thứ tự từng thành phần bằng thứ tự theo một nón chính quy, ta được bài toán với bất đẳng thức suy rộng, vẫn giữ mọi tính chất quan trọng của bài toán lồi. Bài toán dạng nón cực tiểu một hàm tuyến tính với một ràng buộc affine theo nón, và là LP khi nón là nón không âm. Quy hoạch nửa xác định dùng nón các , với ràng buộc là bất đẳng thức tuyến tính. LMI chéo cho LP, nhiều LMI gộp được thành một khối chéo, và mọi SOCP đều là SDP.

của một LMI là một có thể có biên cong và góc. Ví dụ tương quan cho thấy nó mang ý nghĩa rất cụ thể: Không phải bộ hệ số tương quan nào trong $[-1,1]$ cũng hợp lệ, và khoảng giá trị của một hệ số khi biết các hệ số còn lại là nghiệm của hai SDP.

Tài liệu tham khảo

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