什么是最优化问题？
最优化问题一般可以写为：
$$\min f(x)\quad \text{s.t. } x\in\mathcal{X}$$这里 “s.t.” 是 “subject to” 的缩写，表示“在……条件下”，因此
$$\text{s.t.}\quad x\in \mathcal{X}$$表示变量要满足一定的约束条件．︀
上式完整的读法：在 $x$ 属于集合 $\mathcal{X}$ 的条件下，使 $f(x)$ 取得最小值．︀
集合 $\mathcal{X}$ 也被称为可行域，而 $f(x)$ 则被称为目标函数．︀
优化问题的分类：无约束问题 & 有约束问题
要了解如何求解优化问题，需要先来明确一些基本定义．︀
当问题的可行域覆盖整个实数域时（也即 $\mathcal{X}=\mathbb{R}^n$ ），最优化问题转变为无约束优化问题，即：
$$ \min_{x\in\mathbb{R}^n} f(x) $$而现实中很多情况下是存在约束的，例如最常见的不等式约束：
$$ \min f(x)\quad \text{s.t. } g(x)\le 0 $$等式约束：
$$ \min f(x)\quad \text{s.t. } h(x)=0 $$这些概念都是相对比较好理解的，下一节我们来探讨如何求解最优化问题．︀
如何求解最优化问题：最优化算法
无约束问题的求解方法很多都比较直观，很多时候只是一个简单的函数最值问题，大多都在初高中和大学数学中学习过，例如经典的牛顿迭代法，这里就不再花时间讨论了，我们直接来看有约束问题如何分析．︀
对于一个典型的不等式约束问题：
$$ \min f(x)\quad \text{s.t. } g(x)\le 0 $$数学上有非常非常多的方法可以求解，如罚函数法、增广拉格朗日法（ALM）、交替方向乘子法（ADMM）、有兴趣的读者可以参考 最优化：建模、算法与理论（第二版），这里我们只挑一些比较简单的形式进行分析．︀
罚函数法求解有约束优化问题
罚函数的思想比较直观，既然无约束问题求解较为简单，那我们能否把有约束问题转化为无约束问题然后求解呢？答案是肯定的，例如不等式约束：
$$ \min f(x)\quad \text{s.t. } g(x)\le 0 $$该问题希望在满足约束的前提下，让 $f(x)$ 最小，既然如此，我们不妨直接构造一个新的函数：
$$ \text{新目标} = f(x) + \rho \cdot \text{“违反约束的程度”} $$只要能找到这个新目标（也称“罚函数”）的最小值，就可以求解出符合原问题要求的解．︀
需要注意，优化问题算法多为数值求解方法，并不是直接求出原问题的精确解析解，例如这里就是一种近似求解的方法．︀
有些特定的优化问题可以直接求出解析解．
很显然，这里最困难的就是如何去量化“违反约束的程度”（文章灌水的点）．︀量化方法其实非常多，已经超出了本文的范畴，这里我们仅介绍一种最常用的形式，二次罚函数：
虽然看起来很复杂，但其实很简单，$F(x,\rho)$ 就是希望求出最小值的罚函数，这里写为分段函数的意思就是，如果 $g(x)\le0$，说明满足要求，不罚；如果 $g(x) > 0$，说明不符合要求，该罚！因此还可以进一步简写为：
$$ F(x, \rho)= f(x) + \rho (\max(0,g(x)))^2 $$深入思考的话，还有一个有意思的点，为什么常用平方项 $g(x)^2$ 而非 $g(x)$ 或 $|g(x)|$？
$g(x)$ 肯定是不对的．︀如果 $g(x)<0$，会让目标变小，这显然不符合逻辑；$|g(x)|$ 其实也可以用，后面我们会看到一个实际的例子．︀不过 $g(x)^2$ 与 $|g(x)|$ 相比，$g(x)^2$ 既可以让大的误差被强烈放大，又在零点光滑可导，因而方便工程求解．︀
一个实际的例子，LASSO 回归问题
LASSO（Least Absolute Shrinkage and Selection Operator）是机器学习中非常经典的一种回归模型．︀它和普通的线性回归几乎一样，只是多了一个限制条件，希望模型参数不要太大．︀
我们举一个实际的例子，假设我们在研究如何预测一个地区的房价，为了实现这一点，我们提前调研了相当多的变量：
- 房屋面积
- 地铁距离
- 房龄
- 楼层
- 小区绿化
- 附近学校
- 商场距离
- 医院距离
- 噪音
假设我们收集了包含上述变量在内的 100 个变量，希望用线性模型预测：
$$ y = β_0 + β_1x_1 + β_2x_2 + ... + β_px_p $$如果按照最小二乘法，我们希望：
$$ \min \sum_i (\text{真实值}_i-\text{预测值}_i)^2 $$用更数学的语言，是最小化残差平方和
$$ \min_w \sum_{i=1}^n (y_i - x_i^\top \beta)^2 $$于是我们会得到一个笨重的、包含 100 个变量的模型．︀这就有了一个问题，虽然房价可能受很多因素影响，但有些因素可能影响非常小（例如表现为系数非常小），其实是没有必要的噪声．︀
LASSO 就是为了在保证拟合效果尽量好的同时，尽量让模型“简单一点”而被引入的．︀LASSO 认为，参数太多、太大的模型往往容易过拟合，因此，希望大部分系数都尽量接近 $0$，最好直接变成 $0$．︀如何实现这一点呢？引入约束：限制所有参数绝对值之和（L1 范数）：
$$ \sum_j |β_j| = |β_1| + |β_2| + ... + |β_p| $$于是问题变成：
$$ \min \sum_i (\text{真实值}_i-\text{预测值}_i)^2 \quad \text{s.t. } \sum_j |β_j| \le t $$这就是一个典型的有约束最优化问题．︀根据前面讲过的罚函数法，我们完全可以不直接处理约束，而是把“违反约束”这件事变成一种惩罚，加入目标函数中，于是就得到 LASSO 更常见的写法：
$$ \min \sum_i (\text{真实值}_i-\text{预测值}_i)^2 + \lambda \sum_j |w_j| $$从而把“约束优化问题”经过罚函数思想改写后得到的一个无约束问题：
$$ \min_w \sum_{i=1}^n (y_i - x_i^\top \beta)^2 + \lambda \sum_{j=1}^p |\beta_j| $$前面介绍罚函数法时，我们举的是二次罚函数，而 LASSO 里面用的不是平方项，而是绝对值之和．︀这就是前面提到的，罚函数并不只有一种形式．︀只要某一项能够表达“我不希望某种情况发生”，它就可以作为罚项．︀
这里深入思考就会引入新问题，为什么 LASSO 可以让小系数更可能变为零呢？
问题的关键，就在于零点附近不光滑的绝对值运算上，这个“尖角”会带来一种很强的往 0 拉的效果，而平滑的平方项通常不会把系数精确地压到 $0$．︀
事实上，也有平方项做罚项的回归方法，称为 Ridge 回归．︀