无约束优化问题的求解
无约束最优化问题
min f ( x ) , x ∈ R n \min f(x), \, x \in R^n minf(x),x∈Rn
的求解方法。
无约束优化问题的最优性条件
定理 （无约束问题局部解的一阶必要条件）设 f ( x ) f(x) f(x)具有连续的一阶偏导数，若 x ∗ x^* x∗是无约束问题的局部解，则
∇ f ( x ∗ ) = 0. \nabla f(x^*) = 0. ∇f(x∗)=0.
其中， ∇ f ( x ∗ ) \nabla f(x^*) ∇f(x∗)表示函数 f f f在点 x ∗ x^* x∗处的梯度。
极值条件： ∇ f ( x ) = 0 \nabla f(x) = 0 ∇f(x)=0。这表示在函数 f ( x ) f(x) f(x) 的极值点处，其梯度向量为零。这是寻找函数极值（极大值或极小值）的一个必要条件。
无约束优化问题的最速下降法
先考查二维情况。从某一点出发，以“最快”的速度达到极小点 x ∗ \boldsymbol{x}^* x∗。那么，什么方向是函数下降最快的方向呢？是最速下降方向，即负梯度方向。
设 x = x ( t ) \boldsymbol{x} = \boldsymbol{x}(t) x=x(t)为点 x \boldsymbol{x} x所要走的曲线，其中 t t t为参数，那么
d x ( t ) d t = ( d x 1 ( t ) d t , d x 2 ( t ) d t , … , d x n ( t ) d t ) T \frac{\mathrm{d} \boldsymbol{x}(t)}{\mathrm{d} t} = \left( \frac{\mathrm{d} x_1(t)}{\mathrm{d} t}, \frac{\mathrm{d} x_2(t)}{\mathrm{d} t}, \ldots, \frac{\mathrm{d} x_n(t)}{\mathrm{d} t} \right)^T dtdx(t)=(dtdx1(t),dtdx2(t),…,dtdxn(t))T
表示曲线 x = x ( t ) \boldsymbol{x} = \boldsymbol{x}(t) x=x(t)的切线方向，因此有如下关系式
{ d x ( t ) d t = − ∇ f ( x ( t ) ) , x ( t 1 ) = x ( 1 ) , \begin{cases} \frac{\mathrm{d} \boldsymbol{x}(t)}{\mathrm{d} t} = -\nabla f(\boldsymbol{x}(t)), \\ \boldsymbol{x}(t_1) = \boldsymbol{x}^{(1)}, \end{cases} {dtdx(t)=−∇f(x(t)),x(t1)=x(1),
这里 t 1 t_1 t1是初始时刻， x ( 1 ) \boldsymbol{x}^{(1)} x(1)是初始位置。
这是一个一阶非线性常微分方程组。可以证明：解
x
(
t
)
\boldsymbol{x}(t)
x(t)存在，且当
t
→
∞
t \to \infty
t→∞时，有
x
(
t
)
→
x
∗
\boldsymbol{x}(t) \to \boldsymbol{x}^*
x(t)→x∗，即得到无约束问题的最优解。
梯度下降法的迭代公式：
x
k
+
1
=
x
k
−
ρ
∇
f
(
x
k
)
x_{k+1} = x_k - \rho \nabla f(x_k)
xk+1=xk−ρ∇f(xk)。这是一个迭代算法，用于寻找函数
f
(
x
)
f(x)
f(x) 的最小值。其中，
x
k
x_k
xk 是第
k
k
k 次迭代时的位置，
ρ
\rho
ρ 是步长参数，决定了每次迭代时移动的距离。
∇
f
(
x
k
)
\nabla f(x_k)
∇f(xk) 是函数
f
(
x
)
f(x)
f(x) 在
x
k
x_k
xk 处的梯度向量，指向函数增长最快的方向。因此，通过沿着负梯度方向更新
x
x
x，可以逐步接近函数的最小值点。
算法（最速下降法）
(1) 取初始点 x ( 1 ) \boldsymbol{x}^{(1)} x(1)，置 k = 1 k = 1 k=1。
(2) 若 ∇ f ( x ( k ) ) = 0 \nabla f(\boldsymbol{x}^{(k)}) = 0 ∇f(x(k))=0，则停止计算（ x ( k ) \boldsymbol{x}^{(k)} x(k)为无约束问题的最优解）；否则置
d ( k ) = − ∇ f ( x ( k ) ) . \boldsymbol{d}^{(k)} = -\nabla f(\boldsymbol{x}^{(k)}). d(k)=−∇f(x(k)).
(3) 一维搜索。求解一维问题
min α ϕ ( α ) = f ( x ( k ) + α d ( k ) ) , \min_{\alpha} \phi(\alpha) = f(\boldsymbol{x}^{(k)} + \alpha \boldsymbol{d}^{(k)}), αminϕ(α)=f(x(k)+αd(k)),
得 α k \alpha_k αk，置
x ( k + 1 ) = x ( k ) + α k d ( k ) . \boldsymbol{x}^{(k+1)} = \boldsymbol{x}^{(k)} + \alpha_k \boldsymbol{d}^{(k)}. x(k+1)=x(k)+αkd(k).
(4) 置 k = k + 1 k = k + 1 k=k+1，转 (2)。
