最小二乘法
最小二乘法没有约束条件，目标函数是若干项的平方和，每一项具有形式
a
i
⊤
x
−
b
i
a_i^\top x-b_i
ai⊤x−bi，具体形式如下：
m
i
n
f
0
(
x
)
=
∥
A
x
−
b
∥
2
2
=
∑
i
=
1
k
(
a
i
⊤
x
−
b
i
)
2
min \quad f_0(x)=\| Ax-b\|^2_2=\sum_{i=1}^k (a_i^\top x-b_i)^2
minf0(x)=∥Ax−b∥22=i=1∑k(ai⊤x−bi)2
其中，
A
∈
R
k
×
n
(
k
≥
n
)
A \in R^{k\times n}(k\geq n)
A∈Rk×n(k≥n),
a
i
⊤
a_i^\top
ai⊤是矩阵A的行向量，相邻
x
∈
R
n
x\in R^n
x∈Rn是优化变量。最优化问题的目标函数是二次的，自然是可微的。
如何求解最小二乘问题
最小二乘问题可以转为求解一组线性方程
(
A
⊤
A
)
x
=
A
⊤
b
(A^\top A)x=A^\top b
(A⊤A)x=A⊤b
可以得到解析解为
x
=
(
A
⊤
A
)
−
1
A
⊤
b
x=(A^\top A)^{-1}A^\top b
x=(A⊤A)−1A⊤b。 最小二乘问题可以在有限时间内进行求解。此时间和
n
2
k
n^2k
n2k近似成正比，且比例系数已知。
如何使用最小二乘
最小二乘问题是回归分析，最优控制以及很多参数估计和数据拟合方法的基础。最小二乘问题有很多统计意义，例如，给定包含高斯噪声的线性测量值时，向量x的最大似然估计即等价于最小二乘问题的解。
判别有个优化问题是否是最小二乘问题非常简单，只需要检验目标函数是否是二次函数（然后检验此二次函数是否半正定）。
基本最小二乘问题只有一个简单固定的表达式，因此，人们提出了一些标准的技术，使得最小二乘问题 在实际应用中更为灵活。
加权最小二乘
我们最小化加权的最小二乘成本
∑
i
=
1
k
ω
i
(
a
i
⊤
x
−
b
i
)
\sum_{i=1}^k \omega_i(a_i^\top x-b_i)
i=1∑kωi(ai⊤x−bi)
其中，加权系数
ω
1
,
⋯
,
ω
k
\omega_1,\cdots, \omega_k
ω1,⋯,ωk均大于0，加权系数
ω
i
\omega_i
ωi反映了求和项
a
i
T
−
b
i
a_i^T-b_i
aiT−bi的重要程度或者对解的影响程度。在统计应用中，当给定的线性观测值包含不同方差的噪声时，我们用加权最小二乘来估计向量x。
正则化
正则化是解决最小二乘问题的另一个技术，它通过在成本函数中增加一些多余的项来实现，一个最简单的形式是在成本函数中增加一项和变量平方和成正比的项
∑
i
=
1
k
(
a
i
⊤
x
−
b
i
)
2
+
ρ
∑
i
=
1
n
x
i
2
\sum^k_{i=1}(a_i^\top x-b_i)^2+\rho \sum_{i=1}^n x_i^2
i=1∑k(ai⊤x−bi)2+ρi=1∑nxi2
其中
ρ
>
0
\rho>0
ρ>0，当x的值较大时，增加的项对其施加一个惩罚，其得到的解比仅优化第一项时更加切合实际。参数
ρ
\rho
ρ的选择取决于使用者，选择原则是使原始目标函数值尽可能小而保证
∑
i
=
1
n
x
i
2
\sum^n_{i=1} x_i^2
∑i=1nxi2的值不能太大，在二者之间取得一个较好的平衡。在统计估计中，当待估计向量x的分布预先知道，可以采用正则化方法。