Optimal Control： 有限维

无约束的情况

连续可微函数在某点取局部极（小）值的一阶必要条件是梯度在这点为0：证明方法，梯度的定义可以直接用公式定义，假设在这点梯度不为0，这里要用到一个梯度的性质（需要证明，方向导数是梯度和方向向量的点积）。由这点$x^*$我们总可以找到一个方向导数为负的方向$v$（和梯度向量夹角大于90度）。如果自变量往方向导数为负的方向移动，不管移动多小，中间取值$f(x^*+hv)$不可能都比这点$f(x^*)$大，可以把方向导数写成极限的形式：
$$\lim_{h\rightarrow 0}\frac{f(x^*+hv)-f(x^*)}{h}$$
如果都比这点大，那么方向导数必然收敛到0或者正数，这和我们选的方向导数为负这个事实矛盾，也就是$f(x^*)$不是极小因为不管多小的$x^*$领域内，总有比$f(x^*)$小的点。

几何上看如果一个线性函数不为0，必可以找到一个向量，线性函数把这个向量映到负值，比如$L(v) \neq 0$，令$u=L(v)v$，计算可以知道$L(u)=[L(v)]^2 > 0$所以$L(-u) < 0$, 梯度为0的点叫critical point (or stationary point) 二阶必要条件是Hessian在这点半正定：对于critical point，这点附近的函数可以用Hessian决定的二次形逼近，Hessian反应了这点的曲率情况。

二阶充要条件梯度为0，Hessian正定。上面必要条件的证明都是用反证法，找到存在比这点函数值更小的值，充分性的证明关键是找到那个最小的$\epsilon$球面，这里要用到球面的紧性。每个单位方向找个$\epsilon$，得到一个单位球面上的函数，利用紧性找到最小的$\epsilon$。

几何背景

二维数量场(也就是目标函数是$x,y$的函数)可以看成三维空间的曲面$(x,y,f(x,y))$，这个曲面上某点的法向量在$x,y$平面上的投影就是数量场的梯度。我们知道梯度总垂直于等值面，二维的时候就是等值线。

曲面切空间在$x,y$平面上的投影给出了一个曲面上曲线和$x,y$平面上曲线的对应，也就是切空间和$x,y$平面同构。

二维空间的线性函数$w=ax + by = (a, b)\cdot (x, y)$可以有一个二维向量决定，数量场的梯度向量决定了一个线性函数，这个函数在选定的点可以用于逼近数量场。

但是如果允许曲面在三维空间旋转，那么总可以使得选定点的法向在$x, y$平面的投影为0,，对应数量场这点的梯度为0。所以对曲面来说选定点的对应的数量场梯度其实反映了切平面和$x, y$平面的夹角的关系。

梯度给出了一种计算任意$x,y$平面方向导数的方法，就是用选定方向的单位向量和梯度做点积。而Hessian则是给出了一种计算任意两个方向二阶导数的办法，任给两个方向$L_{uv}=u^T H v$。

任意两个方向二阶导数可以看成是$x,y$平面上的点先往$v$方向，然后往$u$方向移动，用一个线性函数逼近数量场的变换情况，需要两个向量输入得到一个数量的线性函数显然是一个二次型。后一个，往$u$方向移动可以用线性函数逼近$\nabla f(x^*+\delta_1 v) \cdot \delta_2 u = \nabla ( \nabla f(x^*) \cdot \delta_1 v ) \cdot \delta_2 u $

如果把方向导数看成是一种加权平均(单位向量看成归一化)，梯度给出的是n个正交方向(就是坐标方向)的量，单位向量给出n个正交方向的权重，点积是加权平均得到方向导数。

三维空间上的数量场：

任意约束

在证明无约束情况的必要条件的时候，我们假定了自变量总可以往和梯度夹角大于90度的方向移动，但是加上约束以后这种移动就不一定允许了（这里往那个方向移动的含义是移动的轨迹在这点的切向量和这个方向向量重合）。可移动的方向称为feasible direction，现在考虑如果这个点是极小值，那么离开这个点的方向总是函数值不减少的方向，所以所有从这个点出发的feasible direction和梯度的夹角小于等于90度，也就是点积小于等于0。

无约束的时候必要条件为梯度为0，有约束的时候接近这个条件的描述是所有的feasible direction都和极值点的$f$的梯度方向垂直，也就是说梯度约束在feasible direction构成的子空间里（也就是投影）为0. 这时候二阶必要条件约束在feasible direction子空间里还是可以用的。

如果取值区域是凸的，函数也是凸的，那么1）局部极值同时是全局极值，2）一阶必要条件也是充分条件。

等式约束

$$h_1(x)=h_2(x)=\cdots =h_m(x)=0$$

等式约束相当于约束区域是一个低维曲面，看必要条件，点$x^*$是一个极值，任取一条曲面上过$x^*$点的曲线$\gamma(t)$,$t=0$对应$x^*$点，因为曲线在曲面上所以满足曲面方程$h_i(\gamma(t))=0$，对$t$求导
$$\nabla h_i(x^*)\cdot \gamma\ '(0)=0$$
又因为极值的条件可以推出$\gamma(t)$代表的feasible direction和目标函数$f$在这点的梯度是垂直的，由$\gamma(t)$的任意性知道目标函数$f$在$x^*$点的梯度是$\nabla h_i(x^*)$的线性组合。因为$f$在$x^*$点的梯度在有所有feasible direction构成的空间的正交补空间里，而$\nabla h_i(x^*)$是这个空间的一个基。

几何上解释就是如果目标函数$f$在$x^*$点的梯度不和这些曲面垂直，那么存在一条曲线通过$x^*$而且其在$x^*$点的切向量和$f$在$x^*$点的梯度的点积不为0，那么就有一个方向的在曲面上的移动使得目标函数变的更小，像上面的证明一样。

这个条件可以写成向量形式，就是Lagrange multipliers
$$\nabla f(x^*)+\lambda_1 \nabla h_1(x^*) + \cdots + \lambda_m \nabla h_m(x^*) =0$$
梯度是$n$维向量，所以上面的式子是$n$个方程，加上$m$个约束方程，我们得到$n+m$个等式的方程组，而且未知变量的个数正好是$n+m$个，$n$个是极值点的坐标$x^*$，和$m$个$\lambda$。

上面的证明比较几何化，下面的方法比较解析一点，只证明一个约束的情况。设$x^*$是极小值，$d_1, d_2$为任意$R^n$中的单位向量，考虑映射：
$$F:(\alpha_1, \alpha_2) \mapsto (f(x^*+\alpha_1d_1+\alpha_2d_2), h(x^*+\alpha_1d_1+\alpha_2d_2))$$
此映射的性质：1)把$(0,0)$映射到$(f(x^*), 0)$；2)在$(0,0)$点的Jacobian矩阵退化，$(f(x^*), 0)$点往横轴负方向的移动的点的轨迹，这个轨迹代表$h=0$，而且$f$的值减少，这是不可能的，也就是无论$(f(x^*), 0)$多小的领域内总有一点是没有逆像的，所以Jacobian矩阵在这点退化。
$$\left( \begin{array}{lr}
\nabla f(x^*)\cdot d_1 & \nabla f(x^*)\cdot d_2 \\
\nabla h(x^*)\cdot d_1 & \nabla h(x^*)\cdot d_2 \\
\end{array} \right)$$
也就是矩阵行向量一个是另一个的倍数，由$d_1, d_2$的任意性，可以推出$\nabla f(x^*) +\lambda \nabla h(x^*) = 0$.

Augmented Cost：
$$L(x,\lambda):=\sum^{m}_{i=1}\ \lambda_ih_i(x)$$
对这个函数求梯度，可以得到刚才提到的所有的$n+m$个方程，这样就把一个有约束的问题变成了无约束的问题。