24.1. Bình phương tối thiểu với ràng buộc tuyến tính

Định nghĩa

Một biến thể thú vị của bài toán bình phương tối thiểu thông thường bao gồm các ràng buộc đẳng thức đối với biến quyết định $x$:

\[
\min _x\|A x-y\|_2^2 ; \quad C x=d
\]

trong đó $C \in \mathbb{R}^{p \times n}$, và $d \in \mathbb{R}^p$ là các dữ liệu đã cho.

Xem thêm: Danh mục đầu tư có phương sai nhỏ nhất.

Nghiệm

Ta có thể biểu diễn nghiệm bằng cách tính không gian hạt nhân của $C$ trước. Giả sử tập khả thi của bài toán LS có ràng buộc là không rỗng, tức là $d$ thuộc không gian ảnh của $C$, tập này có thể được biểu diễn là

\[
\mathbf{X}=\left\{x_0+Nz: z \in \mathbb{R}^k\right\}
\]

trong đó $k$ là số chiều của không gian hạt nhân của $C$, $N$ là một ma trận có các cột là một cơ sở của không gian hạt nhân của $C$, và $x_0$ là một nghiệm riêng của phương trình $C x=d$.

Biểu diễn $x$ theo biến tự do $z$, ta có thể viết lại bài toán có ràng buộc thành một bài toán không ràng buộc:

\[ \min _{\bar{s}}\|\overline{A} z-\bar{y}\|_2 \] where \( \overline{A}:=A N \), and \( \bar{y}=y-A x_0 \).

24.2. Nghiệm có chuẩn nhỏ nhất của hệ phương trình tuyến tính

Một trường hợp đặc biệt của bài toán LS có ràng buộc tuyến tính là

\[ \min _x\|x\|_2: A x=y \]

trong đó ta ngầm giả định rằng hệ phương trình tuyến tính theo $x: Ax=y$, có nghiệm, tức là $y$ thuộc không gian ảnh của $A$.

Bài toán trên cho phép chọn một nghiệm riêng của một hệ phương trình tuyến tính, trong trường hợp có thể có nhiều nghiệm, tức là, hệ phương trình tuyến tính $A x=y$ là hệ thiếu xác định.

Như ở đây, khi $A$ có hạng hàng đầy đủ, tức là, ma trận $A A^T$ khả nghịch, bài toán trên có nghiệm dạng đóng là

\[
x^*=A^T\left(A A^T\right)^{-1} y
\]

Xem thêm: Định vị điều khiển một khối lượng.

24.3. Bình phương tối thiểu chính quy hóa

Trong trường hợp ma trận $A$ trong bài toán OLS không có hạng cột đầy đủ, nghiệm dạng đóng không thể được áp dụng. Một phương pháp thường được sử dụng trong thực tế là biến đổi bài toán ban đầu thành một bài toán mà tính chất hạng cột đầy đủ được thỏa mãn.

Bài toán \textit{bình phương tối thiểu chính quy hóa} có dạng

\[ \min_x \|A x-y\|_2^2 + \lambda \|x\|_2^2 \]

trong đó $\lambda>0$ là một tham số (thường là số nhỏ).

Bài toán chính quy hóa có thể được biểu diễn như một bài toán bình phương tối thiểu thông thường, trong đó ma trận dữ liệu có hạng cột đầy đủ. Thật vậy, bài toán trên có thể được viết dưới dạng bài toán LS thông thường

\[ \min_x \|\bar{A} x-\bar{y}\|_2^2 \]

trong đó

\begin{align*} \bar{A} :=\begin{pmatrix} A \\ \sqrt{\lambda} I_n \end{pmatrix}, \quad \bar{y} :=\begin{pmatrix} y \\ 0 \end{pmatrix}. \end{align*}

Sự có mặt của ma trận đơn vị trong ma trận $(m+n) \times n$ $\bar{A}$ đảm bảo rằng nó có hạng (cột) đầy đủ.

Nghiệm

Vì ma trận dữ liệu trong bài toán LS chính quy hóa có hạng cột đầy đủ, công thức đã thấy tại đây có thể được áp dụng. Nghiệm là duy nhất và được cho bởi

\[
x^*=(\tilde{A}^T\tilde{A})^{-1}\tilde{A}^T\tilde{y}=(A^TA+\lambda I_n)^{-1}A^Ty
\]

Với $\lambda=0$, ta thu được lại biểu thức LS thông thường vốn hợp lệ khi ma trận dữ liệu ban đầu có hạng đầy đủ.

Công thức trên giải thích một trong những động lực để sử dụng bình phương tối thiểu chính quy hóa trong trường hợp ma trận $A$ thiếu hạng: nếu $\lambda>0$, nhưng nhỏ, biểu thức trên vẫn được định nghĩa, ngay cả khi $A$ thiếu hạng.

Bình phương tối thiểu chính quy hóa có trọng số

Đôi khi, như trong các phương pháp hạt nhân, chúng ta gặp các bài toán có dạng

\[
\min _{x}\ ||Ax-y||_2^2+x^TWx
\]

trong đó $W$ là xác định dương (tức là, $x^TWx>0$ với mọi $x$ khác không). Nghiệm là duy nhất và được cho bởi

\[
x^*=(A^TA+W)^{-1}A^Ty
\]