Trong hình học lồi và tối ưu hóa số trị, một phức tạp (chẳng hạn như một đa diện có hàng ngàn mặt biên hoặc bao lồi của hàng triệu điểm dữ liệu) thường rất khó thao tác trực tiếp. Để đơn giản hóa tính toán, người ta tìm cách xấp xỉ tập lồi đó bằng một ellipsoid (hình bầu dục nhiều chiều). Trong tất cả các hình học lồi, ellipsoid là đối tượng duy nhất vừa giữ được tính trơn bậc hai hoàn hảo, vừa có thể biểu diễn gọn gàng qua ánh xạ affine của quả cầu Euclid.

Hai bài toán hình học kinh điển nảy sinh một cách tự nhiên:

1. Tìm ellipsoid có thể tích nhỏ nhất bao trùm toàn bộ tập dữ liệu (Ellipsoid Loewner–John).
2. Tìm ellipsoid có thể tích lớn nhất nằm lọt hoàn toàn bên trong một đa diện.

Đi kèm với các ellipsoid này là các khái niệm tâm hình học (Tâm Chebyshev và Tâm giải tích), đóng vai trò sống còn trong việc chọn điểm khởi đầu cho các thuật toán tối ưu hóa quy mô lớn và đánh giá độ bền vững (adversarial robustness) của các mô hình học máy.

1. Biểu diễn toán học của Ellipsoid

Một ellipsoid $\mathcal{E}$ trong không gian $n$ chiều ${\mathbb{R}}^n$ có thể được hóa theo hai cách tương đương:

Cách 1: Dạng ma trận nghịch đảo và tâm (Dạng định chuẩn)

$$\mathcal{E}=\{x\in {\mathbb{R}}^n\mid (x-x_c{)}^T{P}^{-1}(x-x_c)\le 1\},$$

trong đó $x_c\in {\mathbb{R}}^n$ là tâm của ellipsoid và $P\in {\mathbb{S}}_{++}^n$ là đối xứng xác định dương. Nếu viết $P^{-1}=A^2$ với $A\in {\mathbb{S}}_{++}^n$ và đặt $b=-A{x}_c$, ta có:

$$\mathcal{E}=\{x\in {\mathbb{R}}^n\mid \parallel Ax+b{\parallel }_2\le 1\}.$$

Thể tích của ellipsoid khi đó tỷ lệ nghịch với định thức của $A$:

$$\mathrm{Vol}(\mathcal{E})\propto det(A^{-1})=\frac{1}{detA}.$$

Cách 2: Dạng ánh xạ affine của quả cầu đơn vị (Dạng sinh)

$$\mathcal{E}=\{Bu+d\mid \parallel u{\parallel }_2\le 1\},$$

trong đó $d\in {\mathbb{R}}^n$ là tâm và $B\in {\mathbb{S}}_{++}^n$ là định dạng các trục bán kính. Thể tích của ellipsoid tỷ lệ thuận trực tiếp với định thức của $B$:

$$\mathrm{Vol}(\mathcal{E})\propto detB.$$

Cách biểu diễn 1 rất thuận tiện khi xét bài toán bao ngoài (ràng buộc điểm nằm trong ellipsoid), trong khi cách biểu diễn 2 rất thuận lợi cho bài toán nội tiếp (ràng buộc ellipsoid nằm trong đa diện).

2. Ellipsoid Loewner–John (Bao ngoài thể tích cực tiểu)

Cho bị chặn $C\subset {\mathbb{R}}^n$ có phần trong khác rỗng. Ta tìm ellipsoid $\mathcal{E}=\{x\mid \parallel Ax+b{\parallel }_2\le 1\}$ có thể tích nhỏ nhất chứa $C$.

Cực tiểu hóa thể tích tương đương với việc cực đại hóa $detA$, hay cực tiểu hóa $-\log detA$:

$$\begin{array}{rl}& \underset{A,b}{min}-\log detA\\ & \text{sao cho}\underset{x\in C}{sup}\parallel Ax+b{\parallel }_2\le 1,\\ & \phantom{\text{subject to}}A\in {\mathbb{S}}_{++}^n.\end{array}$$

Trường hợp $C$ là bao lồi của tập hữu hạn điểm

Nếu $C=\mathrm{conv}\{x_1,x_2,\dots ,x_m\}$, một ellipsoid chứa $C$ khi và chỉ khi nó chứa toàn bộ $m$ điểm mút $x_1,\dots ,x_m$. Ràng buộc vô hạn được thu gọn thành đúng $m$ bất đẳng thức chuẩn bậc hai:

$$\begin{array}{rl}& \underset{A,b}{min}-\log detA\\ & \text{sao cho}\parallel A{x}_i+b{\parallel }_2\le 1,\mathrm{\forall }i=1,\dots ,m,\\ & \phantom{\text{subject to}}A\in {\mathbb{S}}_{++}^n.\end{array}$$

Vì hàm mục tiêu $-\log detA$ là ngặt và các ràng buộc $\parallel A{x}_i+b{\parallel }_2\le 1$ là các ràng buộc lồi theo biến $(A,b)$, bài toán này là một bài toán tối ưu lồi giải được chuẩn xác bằng phương pháp điểm trong.

Định lý Loewner–John về tỷ lệ kẹp

Định lý kinh điển của nhà toán học Charles Loewner và Fritz John chỉ ra rằng: Nếu $\mathcal{E}$ là ellipsoid Loewner–John của $C$, và ta co ellipsoid này lại quanh tâm $x_c$ của nó theo tỷ lệ $1/n$:

$$x_c+\frac{1}{n}(\mathcal{E}-x_c)\subseteq C\subseteq \mathcal{E}.$$

Hệ số co $1/n$ này là cận chặt nhất trong trường hợp tổng quát (đạt được tại một hình đơn hình). Nếu tập $C$ đối xứng qua gốc tọa độ ($C=-C$), tỷ lệ kẹp tăng vọt lên tới $1/\sqrt{n}$. Đây là bảo đảm lý thuyết vững chắc cho thấy mọi nhiều chiều đều có thể xấp xỉ xích sao bằng một ellipsoid.

3. Ellipsoid nội tiếp thể tích cực đại bên trong đa diện

Bây giờ ta đảo ngược bài toán: Cho một tập đa diện bị chặn được mô tả bởi hệ $m$ bất đẳng thức tuyến tính:

$$\mathcal{P}=\{x\in {\mathbb{R}}^n\mid a_i^{T}x\le b_i,\mathrm{\forall }i=1,\dots ,m\}.$$

Ta muốn tìm một ellipsoid $\mathcal{E}=\{Bu+d\mid \parallel u{\parallel }_2\le 1\}$ có thể tích lớn nhất nằm lọt hoàn toàn bên trong $\mathcal{P}$.

Điều kiện $\mathcal{E}\subseteq \mathcal{P}$ đồng nghĩa với việc với mọi vector $u$ có $\parallel u{\parallel }_2\le 1$ và mọi mặt biên $i$:

$$a_i^T(Bu+d)\le b_i.$$

Lấy giá trị lớn nhất theo $u$ trên quả cầu đơn vị:

$$\underset{\parallel u{\parallel }_2\le 1}{sup}{a}_i^T(Bu+d)=a_i^{T}d+\underset{\parallel u{\parallel }_2\le 1}{sup}(B{a}_i{)}^{T}u=a_i^{T}d+\parallel B{a}_i{\parallel }_2.$$

Do đó, điều kiện hình học phức tạp được rút gọn thành một hệ bất đẳng thức nón bậc hai rất gọn gàng:

$$a_i^{T}d+\parallel B{a}_i{\parallel }_2\le b_i,\mathrm{\forall }i=1,\dots ,m.$$

Bài toán tìm ellipsoid nội tiếp lớn nhất trở thành bài toán tối ưu lồi:

$$\begin{array}{rl}& \underset{B,d}{max}\log detB\\ & \text{sao cho}\parallel B{a}_i{\parallel }_2+a_i^{T}d\le b_i,\mathrm{\forall }i=1,\dots ,m,\\ & \phantom{\text{subject to}}B\in {\mathbb{S}}_{++}^n.\end{array}$$

Hàm mục tiêu $\log detB$ là hàm lõm, các ràng buộc $\parallel B{a}_i{\parallel }_2+a_i^{T}d\le b_i$ là các ràng buộc lồi theo cặp biến $(B,d)$. Ta có thể giải bài toán này để tìm được hình dạng và hướng xoay lý tưởng của cấu trúc bên trong đa diện.

4. Các điểm tâm hình học của Đa diện

Khi cần chọn một điểm đại diện "nằm sâu nhất" bên trong một đa diện (ví dụ để làm điểm khởi đầu cho thuật toán tối ưu hoặc chọn bộ an toàn nhất), hai khái niệm tâm hình học đóng vai trò trung tâm:

Tâm Chebyshev (Chebyshev Center)

Tâm Chebyshev là tâm của quả cầu Euclid lớn nhất nội tiếp bên trong đa diện $\mathcal{P}$.

Nếu quả cầu có tâm $x_c\in {\mathbb{R}}^n$ và bán kính $r\ge 0$, điều kiện quả cầu nằm trong $\mathcal{P}$ tương ứng với trường hợp $B=r{I}_n$ ở mục trước:

$$\parallel r{I}_n{a}_i{\parallel }_2+a_i^T{x}_c\le b_i⟺a_i^T{x}_c+r\parallel a_i{\parallel }_2\le b_i.$$

Cực đại hóa bán kính $r$ dẫn trực tiếp tới một Quy hoạch tuyến tính (LP):

$$\begin{array}{rl}& \underset{x_c,r}{max}r\\ & \text{sao cho}{a}_i^T{x}_c+r\parallel a_i{\parallel }_2\le b_i,\mathrm{\forall }i=1,\dots ,m,\\ & \phantom{\text{subject to}}r\ge 0.\end{array}$$

Bán kính tối ưu $r^{\ast }$ chính là khoảng cách từ tâm Chebyshev tới mặt phẳng biên gần nhất của đa diện.

Tâm giải tích (Analytic Center)

Tâm giải tích là điểm cực tiểu hóa hàm chắn logarit (Logarithmic Barrier) của toàn bộ các mặt biên:

$$x_{\mathrm{ac}}=\arg \underset{x\in \mathrm{int}(\mathcal{P})}{min}\varphi (x)=-\sum _{i=1}^m\log (b_i-a_i^{T}x).$$

Hàm số $\varphi (x)$ là ngặt và tiến ra $+\mathrm{\infty }$ khi $x$ tiến tới bất kỳ mặt biên nào. Đạo hàm của hàm chắn tại tâm giải tích triệt tiêu:

$$\mathrm{\nabla }\varphi (x_{\mathrm{ac}})=\sum _{i=1}^m\frac{a_i}{b_i-a_i^T{x}_{\mathrm{ac}}}=0.$$

Về mặt cơ học, điều này có nghĩa là tâm giải tích là điểm cân bằng tĩnh học: Nếu mỗi mặt biên tác dụng một lực đẩy tỉ lệ nghịch với khoảng cách tới điểm đó, thì tâm giải tích là vị trí mà tổng các lực đẩy triệt tiêu hoàn toàn. Tâm giải tích phụ thuộc vào cách biểu diễn các phương trình mặt phẳng (nếu nhân đôi một ràng buộc, lực đẩy từ phía đó tăng gấp đôi).

5. Ví dụ tính toán minh họa

Xét đa diện hai chiều $\mathcal{P}\subset {\mathbb{R}}^2$ được giới hạn bởi tam giác:

$$x_1\ge 0,x_2\ge 0,x_1+x_2\le 1.$$

Viết lại dưới dạng chuẩn $a_i^{T}x\le b_i$:

• Mặt 1: Bất đẳng thức $-x_1\le 0$, cho $a_1=(-1,0{)}^T$, $b_1=0$, $\parallel a_1{\parallel }_2=1$.
• Mặt 2: Bất đẳng thức $-x_2\le 0$, cho $a_2=(0,-1{)}^T$, $b_2=0$, $\parallel a_2{\parallel }_2=1$.
• Mặt 3: Bất đẳng thức $x_1+x_2\le 1$, cho $a_3=(1,1{)}^T$, $b_3=1$, $\parallel a_3{\parallel }_2=\sqrt{2}$.

Tìm tâm Chebyshev

Các ràng buộc bán kính trở thành:

1. $-x_1+r(1)\le 0⟹x_1\ge r$.
2. $-x_2+r(1)\le 0⟹x_2\ge r$.
3. $x_1+x_2+r\sqrt{2}\le 1$.

Để cực đại hóa $r$, ta chọn $x_1=x_2=r$. Thay vào bất đẳng thức thứ ba:

$$2r+r\sqrt{2}\le 1⟺r(2+\sqrt{2})\le 1⟹r^{\ast }=\frac{1}{2+\sqrt{2}}=1-\frac{\sqrt{2}}{2}\approx \mathrm{0,292}9.$$

Tâm Chebyshev tương ứng:

$$x_c^{\ast }=(1-\frac{\sqrt{2}}{2},1-\frac{\sqrt{2}}{2})\approx (\mathrm{0,292}9,\mathrm{0,292}9).$$

Đây chính là tâm đường tròn nội tiếp tam giác vuông cân đơn vị.

Bài tập tự luyện

Bài tập: Tìm tâm giải tích của tam giác đơn vị

Xét tam giác đơn vị ở ví dụ trên với hàm chắn logarit:

$$\varphi (x)=-\log (x_1)-\log (x_2)-\log (1-x_1-x_2).$$

1. Tính gradient của $\varphi (x)$ theo $(x_1,x_2)$.
2. Giải hệ phương trình $\mathrm{\nabla }\varphi (x)=0$ để tìm tọa độ tâm giải tích $x_{\mathrm{ac}}$.
3. So sánh tọa độ của tâm giải tích với tâm Chebyshev và trọng tâm tam giác.

Lời giải

1. Tính đạo hàm riêng:
   $$$$

\frac{\partial \phi}{\partial x_1} &= -\frac{1}{x_1} + \frac{1}{1 - x_1 - x_2}, \ \frac{\partial \phi}{\partial x_2} &= -\frac{1}{x_2} + \frac{1}{1 - x_1 - x_2}. \end

$$2.\ast \ast Tìmnghiệmtriệttiêugradient\ast \ast :Cho\$\mathrm{\nabla }\varphi (x)=0\$:$$

\frac{1}{x_1} = \frac{1}{x_2} = \frac{1}{1 - x_1 - x_2}.

$$Suyra\$x_1=x_2\$.Đặt\$x_1=x_2=u\$,tacó:$$

\frac{1}{u} = \frac{1}{1 - 2u} \iff 1 - 2u = u \iff 3u = 1 \implies u = \frac{1}{3}.

$$Vậytâmgiảitíchlàđiểm\$x_{\mathrm{ac}}=(1/3,1/3)\$.3.\ast \ast Bìnhluậnsosánh\ast \ast :-Trọngtâmhìnhhọctamgiác:$$

 x_{\mathrm{centroid}} = \frac{1}{3}(0,0) + \frac{1}{3}(1,0) + \frac{1}{3}(0,1) = \left(\frac{1}{3}, \frac{1}{3}\right).
 $$
 Trong trường hợp đơn hình chuẩn, tâm giải tích trùng khớp hoàn toàn với trọng tâm.

• Tâm Chebyshev: Điểm $x_c\approx (\mathrm{0,292}9,\mathrm{0,292}9)$ nằm gần gốc tọa độ hơn một chút do chịu lực cản bởi mặt cạnh huyền dốc $\sqrt{2}$.

Tóm tắt

Ellipsoid thể tích cực trị và các điểm tâm hình học cung cấp những công cụ đại số mạnh mẽ để đơn giản hóa cấu trúc của các nhiều chiều:

• Ellipsoid Loewner–John: Bao ngoài chặt chẽ nhất, bảo đảm hệ số co kẹp $1/n$ trong không gian $n$ chiều qua bài toán cực tiểu hóa $-\log detA$.
• Ellipsoid nội tiếp thể tích cực đại: Tìm cấu trúc trơn lớn nhất bên trong đa diện thông qua bài toán cực đại hóa $\log detB$ với các ràng buộc nón bậc hai.
• Tâm Chebyshev & Tâm giải tích: Đưa việc tìm điểm đại diện trung tâm về một Quy hoạch tuyến tính (LP) hoặc bài toán tối ưu hàm chắn không ràng buộc, đóng vai trò bản lề trong phương pháp điểm trong và đánh giá độ bền vững của các mô hình AI.

Tài liệu tham khảo

• Stephen Boyd, Lieven Vandenberghe, Convex Optimization, Cambridge University Press, Chapter 8: Geometric Problems (§§8.4–8.5).