有约束最优化方法(Constrained Optimization)

• unconstrained optimization: maximize or minimize a function $f(x)$ over all possible values of x
• constrained optimization: find the maximal or minimal value of $f(x)$ for values of x in some set $\mathbb{S}$. 集合$\mathbb{S}$内的点称之为 feasible points

方法：

• simply to modify gradient descent taking the constraint into account. （ 比如search only over step sizes that yield new x points that are feasible）
• 构造一个无约束最优化问题使得解能映射回原来的有约束最优化问题。

拉格朗日乘子法和KKT条件

参考深入理解拉格朗日乘子法（Lagrange Multiplier) 和KKT条件

拉格朗日乘子法(Lagrange Multiplier)和KKT(Karush-Kuhn-Tucker)条件是求解约束优化问题的重要方法。首先用等式约束和不等式约束来描绘集合$\mathbb{S}$。在有等式约束时使用拉格朗日乘子法，在有不等约束时使用KKT条件（KKT条件是拉格朗日乘子法的泛化）。只有当目标函数为凸函数时，使用这两种方法才保证求得的是最优解。

通常需要求解的最优化问题

• 无约束优化问题

  $$\min ~ f(x)$$

• 有等式约束的优化问题

\begin{align}
\min & ~ f(x) \nonumber \\
s.t. & ~ h_i(x) = 0, i=1,…,m \label{problem_math}
\end{align}

• 有不等式约束的优化问题
  \begin{align}
  \min & ~ f(x) \nonumber \\
  s.t. & ~ g_i(x) \le 0; i = 1,…,n \nonumber \\
  & ~ h_j(x) = 0, j=1,…,m \label{problem_math2}
  \end{align}

优化方法。

无约束优化问题

Fermat定理，即使用求取f(x)的导数，然后令其为零，可以求得候选最优值，再在这些候选值中验证；如果是凸函数，可以保证是最优解。

有等式约束的优化问题：拉格朗日乘子法

拉格朗日乘子法（Lagrange Multiplier) ，即把等式约束$h_i(x)$用一个系数与$f(x)$写为一个式子，称为拉格朗日函数，而系数称为拉格朗日乘子。通过拉格朗日函数对各个变量求导，令其为零，可以求得候选值集合，然后验证求得最优值。

the generalized Lagrangian or generalized Lagrange function is:

$$L(x,\alpha) = f(x) +\sum_{i=1}^m \alpha_i h_i(x)$$

或向量形式

$$L(x,\alpha) = f(x) + \alpha h(x)$$

这里把$\alpha$和$h(x)$视为向量形式，$\alpha$是横向量，h(x)为列向量

求解方法：对Lagrangian函数分别对$\alpha$ 和 $x$ 求导数，并令导数为0，得到$\alpha$ 和 $x$

$$\nabla_x L(x,\alpha) = 0$$ $$\nabla_\alpha L(x,\alpha) = 0$$

有不等式约束的优化问题：KKT条件

引入KKT multipliers，$\alpha$和$\lambda$,其中，$\alpha_i \ne 0$, $\lambda_j \ge 0$
向量形式：

$$L(x,\alpha,\lambda) = f(x) + \alpha h(x)+\lambda g(x)$$

KKT条件是说最优值必须满足以下条件：

1. $L(x,\alpha, \lambda)$对x求导为零；
2. $h(x) = 0$
3. $\lambda g(x) = 0$

原理推导看拉格朗日乘子法和KKT条件