Các câu “gần nghiệm”, “nằm trong miền” và “độ cong không âm” đều cần một cách diễn đạt toán học cụ thể. Chuẩn xác định khoảng cách, hình cầu xác định lân cận, còn ma trận đối xứng giúp đọc độ cong qua trị riêng.

1. Nhắc lại bài toán và sự tồn tại nghiệm

Với $f:{\mathbb{R}}^n\to \mathbb{R}$ và $D\subseteq {\mathbb{R}}^n$, xét min $f(x)$ trên $x\in D$. Một phương án tối ưu toàn cục $x^{\star }$ phải thỏa

$$\begin{array}{rl}& x^{\star }\in D,\\ f(y)& \ge f(x^{\star }),\mathrm{\forall }y\in D.\end{array}$$

Phương án tối ưu địa phương chỉ yêu cầu so sánh với các điểm khả thi trong một hình cầu đủ nhỏ quanh nó. Dạng miền thường dùng gồm mọi $x\in {\mathbb{R}}^n$ thỏa

$$\begin{array}{rl}{f}_i(x)& \le 0,i=1,\dots ,m,\\ h_j(x)& =0,j=1,\dots ,p.\end{array}$$

Khi $m=p=0$ và hàm xác định trên toàn không gian, đây là bài không ràng buộc trên ${\mathbb{R}}^n$.

Ví dụ $f(x)=-1/x$ trên $D=(0,1)$ không có giá trị nhỏ nhất hữu hạn, vì hàm tiến tới $-\mathrm{\infty }$ khi $x\to 0^{+}$. Viết lại miền thành $[0,1]$ không tự giải quyết được vấn đề: Biểu thức không xác định tại 0. Muốn dùng định lý hàm liên tục đạt cực trị trên tập compact, phải có cả miền compact lẫn tính liên tục trên toàn miền. Ví dụ này giữ rõ sự khác nhau giữa điều kiện về miền và điều kiện về hàm.

2. Chuẩn của vector

Vector $x$ có $n$ tọa độ, viết dưới dạng cột $(x_1,\dots ,x_n{)}^T$. Chuẩn là một số không âm biểu thị độ lớn và thỏa ba tính chất: Bằng không chỉ tại vector không, đồng nhất theo trị tuyệt đối của hệ số nhân và bất đẳng thức tam giác.

Với $1\le p<\mathrm{\infty }$, chuẩn $p$ là

$$\begin{array}{rl}\parallel x{\parallel }_p& =(|x_1{|}^p+\cdots +|x_n{|}^p{)}^{1/p}\\ & ={(\sum _{i=1}^n|x_i{|}^p)}^{1/p}.\end{array}$$

Ba trường hợp cần dùng là

$$\begin{array}{rl}\parallel x{\parallel }_1& =|x_1|+\cdots +|x_n|,\\ \parallel x{\parallel }_2& =\sqrt{x_1^2+\cdots +x_n^2},\\ \parallel x{\parallel }_{\mathrm{\infty }}& =max\{|x_1|,\dots ,|x_n|\}.\end{array}$$

Chuẩn vô cùng là tọa độ có trị tuyệt đối lớn nhất. Nó được định nghĩa riêng, không thay số vô cùng vào biểu thức $1/p$. Với $x=(3,-4)$, ba chuẩn trên lần lượt là 7, 5 và 4. Cùng một vector nhưng mỗi chuẩn nhấn mạnh một kiểu độ lớn khác nhau.

Quả cầu đơn vị của ‖x‖ₚ khi p thay đổi

p = 1.50 Lấy p = ∞

Với x = (0.70, 0.45): ‖x‖₁ = 1.15, ‖x‖₂ = 0.83, ‖x‖∞ = 0.70, còn ‖x‖ₚ = 0.92. Điểm x thuộc vùng tô.

Với p ≥ 1, tập là lồi và đối xứng qua gốc. Ba đường nét đứt là quả cầu đơn vị của p = 1, 2 và ∞ để so sánh.

Gợi ý thao tác

1. Kéo p từ 1 lên 8. Hình thoi dần biến thành hình gì?
2. Kéo p xuống dưới 1. Chỗ nào của tập bị "lõm" vào?
3. Đặt x = (0.6, 0.6). Điểm này thuộc quả cầu của chuẩn nào trong ba chuẩn tham chiếu?

Các quả cầu đơn vị của chuẩn 1, chuẩn 2 và chuẩn vô cùng trong mặt phẳng có dạng hình thoi, đĩa tròn và hình vuông. Hình tròn chỉ đặc trưng cho chuẩn Euclid, không phải mọi chuẩn.

3. Hình cầu, điểm trong và điểm biên

Với tâm $x$ và bán kính $r>0$, hình cầu mở và đóng là

$$\begin{array}{rl}B(x,r)& =\{y:\parallel y-x\parallel <r\},\\ \bar{B}(x,r)& =\{y:\parallel y-x\parallel \le r\}.\end{array}$$

Trong một chiều với chuẩn trị tuyệt đối, hình cầu mở là khoảng $(x-r,x+r)$. Khoảng có hai đầu $a<b$ có tâm $c=(a+b)/2$ và bán kính $(b-a)/2$. Trong hai chiều với chuẩn Euclid, đó là đĩa tròn, gồm cả phần diện tích bên trong, không chỉ đường tròn biên.

Điểm $x\in D$ là điểm trong nếu một hình cầu mở đủ nhỏ quanh nó nằm trọn trong $D$. Một điểm là điểm biên nếu mọi hình cầu mở quanh nó đều chạm cả $D$ lẫn phần bù của $D$. Điểm biên không nhất thiết thuộc $D$: Hai đầu của một khoảng mở là điểm biên nhưng không nằm trong khoảng.

Trong hình miền cong trên bảng, hình cầu ở giữa nằm hoàn toàn trong miền mô tả điểm trong. Hình cầu quanh chỗ tiếp giáp phải cắt ra ngoài mô tả điểm biên. Đây là lý do định lý Fermat cần giả thiết điểm trong.

4. Ma trận và đa thức đặc trưng

Một ma trận $A\in {\mathbb{R}}^{m\times n}$ có $m$ hàng, $n$ cột và phần tử $a_{ij}$ ở hàng $i$, cột $j$. Chẳng hạn,

$$A=\left[\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& & ⋮\\ a_{m1}& a_{m2}& \cdots & a_{mn}\end{array}\right].$$

Với ma trận vuông đối xứng thực, $A^T=A$. Đa thức đặc trưng theo quy ước của buổi học là

$${\chi }_A(t)=det(A-t{I}_n).$$

Nghiệm của đa thức là các trị riêng của $A$. Với $A$ đối xứng thực, tất cả trị riêng đều thực và có đủ $n$ trị riêng khi tính cả bội. Quy ước $det(tI-A)$ cũng thông dụng, nhưng khác biểu thức trên bởi hệ số $(-1{)}^n$. Hai đa thức vẫn có cùng nghiệm.

5. Hàm affine

Một hàm vô hướng affine có dạng

$$\ell (x)=a_1{x}_1+\cdots +a_n{x}_n+b=a^{T}x+b.$$

Nếu $b=0$, đây là ánh xạ tuyến tính. Phân biệt này giúp đọc mô hình hồi quy có hệ số chặn và các ràng buộc đẳng thức của bài toán lồi.

6. Dạng toàn phương và hệ số chéo

Với $A$ đối xứng, dạng toàn phương là $Q(x)=x^{T}Ax$. Trong ba chiều, khai triển thành

$$Q(x)=a_{11}{x}_1^2+a_{22}{x}_2^2+a_{33}{x}_3^2+2a_{12}{x}_1{x}_2+2a_{13}{x}_1{x}_3+2a_{23}{x}_2{x}_3.$$

Hệ số 2 xuất hiện vì cả vị trí $(i,j)$ và $(j,i)$ cùng đóng góp vào tích chéo. Trong $n$ chiều,

$$Q(x)=\sum _{i=1}^n{a}_{ii}{x}_i^2+2\sum _{i=1}^{n-1}\sum _{j=i+1}^n{a}_{ij}{x}_i{x}_j.$$

Tổng kép chạy qua các cặp chỉ số $i<j$, tức mỗi cặp khác nhau chỉ được đếm một lần trước khi nhân 2. Dạng ba chiều phía trên đã chỉ rõ từng số hạng của cách viết rút gọn.

7. Xác định dương và nửa xác định dương

Với ma trận đối xứng thực:

• $A$ xác định dương, viết $A\succ 0$, nếu $x^{T}Ax>0$ với mọi $x\ne 0$.
• $A$ nửa xác định dương, viết $A⪰0$, nếu $x^{T}Ax\ge 0$ với mọi $x$.

Nhờ chéo hóa trực giao, tồn tại $U$ trực giao và các trị riêng ${\lambda }_1,\dots ,{\lambda }_n$ sao cho $A=U\mathrm{diag}({\lambda }_i)U^T$. Đặt $z=U^{T}x$, ta có

$$\begin{array}{rl}{x}^{T}Ax& ={\lambda }_1{z}_1^2+\cdots +{\lambda }_n{z}_n^2\\ & =\sum _{i=1}^n{\lambda }_i{z}_i^2.\end{array}$$

Vì vậy PD tương đương mọi trị riêng dương, còn PSD tương đương mọi trị riêng không âm. Không dùng riêng dấu từng phần tử hoặc riêng dấu định thức để suy ra kết luận này.

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

Bài tập: Đọc hệ số của dạng toàn phương

Viết ma trận đối xứng $A$ cho $Q(x,y)=2x^2+2xy+y^2$, rồi kiểm tính dương bằng cách hoàn thành bình phương.

Lời giải

Ma trận là $A=\left[\begin{array}{cc}2& 1\\ 1& 1\end{array}\right]$. Phần tử ngoài đường chéo là 1 vì hai vị trí cùng tạo hệ số $2xy$. Ta có $Q=(x+y{)}^2+x^2$, dương với mọi $(x,y)\ne (0,0)$. Do đó $A\succ 0$.