---

[TOC]

无约束优化问题——求导

首先我们复习下：

给定一个目标函数$f=R^n\rightarrow R^n$,求出目标函数的最小值，记为：

$$\large{ min f(x)\\ s.t\ x \in X }$$

找出最小值的办法很简单，就是单纯的对$f(x)$求导，令导数等于0，得到的解$x^*$就是目标函数的极小值点了

等式约束优化问题——拉格朗日乘子法

首先，梯度方向是函数值增长最快的方向。

给定一个目标函数$f = R^n \rightarrow R^n$，在满足约束条件$g(x) = 0$的前提下，使得$f(x)$有最小值。这个约束问题记为：

$$\large{ min\ f(x) \\ s.t\ g(x) = 0\\ }$$

假如P点是f（x）在约束条件g（x）下的极值点，假设一个参数方程$\large{r(t)=(x_1(t),x_2(t)…x_n(t))}$是一个曲线，它在约束条件的表面，切$\large{r(0)=P}$点，假设$\large{h(t)=f(x_1(t),x_2(t)….,x_n(t))} = f(r(t))$

则有$\large{h’(t)=\nabla f(x)|_{r(t)}\cdot r’(t)}$

又因为P点为极值点，所以$\large{h’(t)=\nabla{f}|_{P}\cdot{r’(t)}=0}$

所以$\large{f|_{P}}$在点P处垂直于$\large{r(t)}$。而$\large{r(t)}$是约束面上的任意曲线，所以$\large{f|_{p}}$在P处垂直于$\large{g(x)=0}$

所以$\large{\nabla{f|_{P}=\lambda{\nabla{g_P}}}}$

所以$\large{\nabla{f(x)=\lambda{\nabla g(x)}}} \rightarrow \nabla f(x)-\lambda\nabla g(x) =0$

所以令$\large{L(x,\lambda)=f(x)-\lambda g(x)}$。对它求导，令导数=0得到的点就是极值点.即

$$\large{\left\{ \begin{aligned} \nabla f(x) &= \lambda \nabla g(x) \\ g(x) &= 0 \end{aligned} \right.}$$

不等式约束优化问题——KKT条件

对于不等式约束的优化

$$\large{min\ f(x)\\s.t\quad g(x)\leq 0}$$

等价于

$$\large{ min_x\ max_\lambda\ f(x) + \lambda{g(x)}\\ s.t \quad \lambda \ge 0 }$$

对于等式约束，由于$\large \lambda{g(x)}=0$恒成立，所以对因子没有约束，但是不等式约束中，我们必须对因子进行约束

对于$\large{g(x)\leq0}$，我们引入一个松弛变量$\large{a^2}$，使得$\large{g(x)+a^2}=0$，这样我们把不等式约束转化为等式约束问题了

对等式约束使用拉格朗日乘子法，有拉格朗日函数

$\large{L(x,\lambda, a)=f(x) + \lambda(g(x)+a^2)}$，则有

$$\large{\left\{ \begin{aligned} \frac{\partial L}{\partial x^*} &= \nabla f(x^*) + \sum_i^{m}\lambda_i\nabla g_i(x^*) = 0(i=1,2,...,m) \quad (1)\\ \frac{\partial L}{\partial \lambda} &= \sum_i^{m}g_i(x^*) + a^2 = 0(i=1,2,...,m) \quad (2)\\ \frac{\partial L}{\partial a} &= 2a\lambda_i = 0(i=1,2,...,m) \quad(3)\\ \end{aligned} \right.}$$

对(3)式

$\lambda$等于0，a不等于0时，得到g(x)<0，$\lambda g(x)$=0，可认为g(x)不起约束

a等于0，$\lambda$不等于0，得到g(x)=0，所以$\lambda>0$。g(x)起到了约束作用

综上，可以发现

1. $\large{\lambda\geq0}\quad(4)$。乘子大于等于0从目标函数就可以看出，不等式约束小于0，目标函数又是最小化，乘子肯定大于等于0。

2. $\large{\lambda g(x) = 0}$，因为$\large g(x)和\lambda$总有一个为0

所以我们的得到，对不等式约束

$\large{min\ f(x) \\ s.t\quad g(x)\leq 0}$

我们有

$$\large{ \left\{ \begin{align} & \nabla f(x^*) + \sum_i^{m}\lambda_ig_i(x^*) = 0(i=1,2...m)\\ & \lambda_ig_i(x^*) = 0(i=1,2...m)\\ & \lambda_i > 0(i=1,2...m) \end{align} \right. }$$

更一般的，有约束问题

$$\large{ \begin{align} min&f(x) \\ s.t.\ &g_j(x)\leq0(j=1,2,...,m)\\ &h_j\ (x) = 0(j=1,2,...,m) \end{align} }$$

KKT条件为：

$$\large{\left\{ \begin{align} & \nabla f(x) + \sum_{j=1}^{m}\mu_j\nabla{g_j(x)} + \sum_{k=1}^{l}\lambda_k\nabla{h_k(x)}=0,(i=1,2,...,n)\\ & h_k(x) = 0(k=1,2,...,l) \\ & \mu_j{g_j(x)} = 0(j=1,2,...,m)\\ & g_j(x) < 0(j=1,2,...,m)\\ & \mu_j \geq 0(j=1,2,...,m) \end{align} \right. }$$