优化问题简介

最优化定义

最优化，是应用数学的一个分支。主要研究在特定情况下最大化或最小化某一特定函数或变量。

数学表示：

$Y$ 是 随机变量 $X$ 的函数，求 $\hat{y}=f_{\theta }(X)$ ，令：

$$\hat{\theta }=\arg \underset{\theta }{\min }(diff(Y,\hat{y}))$$

问题拆解

loss function

损失函数或成本函数是指一种将一个事件（在一个样本空间中的一个元素）映射到一个表达与其事件相关的经济成本或机会成本的实数上的一种函数，借此直观表示的一些"成本"与事件的关联。一个最佳化问题的目标是将损失函数最小化。

平方法

最小二乘法例子：定义最小二乘法 $L_2$ 损失函数 ${\sqrt{\sum _{i=1}^n(Y_i-{\hat{Y}}_i)}}^2$ 同理可定义 距离损失函数 $L_P$

Huber loss

相比平方误差损失，Huber损失对于数据中异常值的敏感性要差一些。

https://blog.csdn.net/u013841196/article/details/89923475

Hinge loss

https://zhuanlan.zhihu.com/p/35708936

Cross Entropy

在机器学习中（特别是分类模型），模型训练时，通常都是使用交叉熵（Cross-Entropy）作为损失进行最小化：

求分布和分布之间的差异：

$$CE(p,q)=-\sum _{i=1}^C{p}_{i}log(q_i)$$

其中 $C$ 代表类别数。$p_i$ 为真实，$q_i$ 为预测。

https://blog.csdn.net/guolindonggld/article/details/79250642v
https://zhuanlan.zhihu.com/p/35709485

method

• 容易计算则直接计算：如最小二乘法
• 不容易计算，则迭代法，如 $\arg {\min }_{x}g(x)$, 令 $x_1=x_0+\Delta x$：
  • 0阶: 直接根据函数值
  • 1阶: 根据函数值加导数
  • 2阶: 根据 Hessian 矩阵
• 随机性
  • 模拟退火
  • 进化

优化问题的要求

• 必须存在最优解
• 解尽量唯一
• 损失函数连续

最速下降法

梯度下降方法基于以下的观察：如果实值函数 $F(\mathbf{x}$)在点 $\mathbf{a}$ 处可微且有定义，那么函数 $F(\mathbf{x}$)在 $\mathbf{a}$ 点沿着梯度相反的方向 $-\nabla F(\mathbf{a}$) 下降最多。

因而，如果

$$\mathbf{b}=\mathbf{a}-\gamma \nabla F(\mathbf{a})$$

对于 $\gamma >0$ 为一个够小数值时成立，那么 $F(\mathbf{a})\ge F(\mathbf{b}$)。

下面先给出最速梯度下降法的计算步骤：

由以上计算步骤可知，最速下降法迭代终止时，求得的是目标函数驻点的一个近似点

https://zhuanlan.zhihu.com/p/32709034

共轭梯度法

共轭梯度法对最优梯度法进行了修正，搜索方向为共轭方向，将负梯度方向旋转了一个角度，每次往最优方向需要在负梯度方向进行修正。算法如下：

https://zhuanlan.zhihu.com/p/64227658
https://blog.csdn.net/qq547276542/article/details/78186050
https://flat2010.github.io/2018/10/26/%E5%85%B1%E8%BD%AD%E6%A2%AF%E5%BA%A6%E6%B3%95%E9%80%9A%E4%BF%97%E8%AE%B2%E4%B9%89/#8-%E5%85%B1%E8%BD%AD%E6%A2%AF%E5%BA%A6%E6%B3%9
https://blog.csdn.net/LittleEmperor/article/details/105073755

牛顿法

为了求 $\Delta x$ 通过把 Hessian 矩阵的逆矩阵转为求线性方程组，避免求逆矩阵。

比之前方法迭代少，但是计算量大。

拟牛顿法

核心思想，构造近似的 Hessian 矩阵的逆矩阵，使得：

$$H_k^{-1}+\Delta H=H_{k+1}^{-1}$$

https://garfielder007.github.io/2015/12/16/Newton-QuasiNewton-Method.html
https://zhuanlan.zhihu.com/p/306635632

约束非线性优化

对偶性

在最优化理论中的对偶（duality）或对偶性原则（duality principle）是指最佳化问题可以用两种观点来看待的理论，两种观点分别是“原始问题”（primal problem）及“对偶问题”（dual problem）。对偶问题的解提供了原始问题（假设是最小化问题）的下限[1]，不过一般而言，原始问题和对偶问题的最佳解不相同。两个最佳解的差距为对偶间隙。若是凸优化问题，对偶间隙也称为是卡鲁什-库恩-塔克条件。

强对偶、弱对偶参考 https://blog.csdn.net/Cyril_KI/article/details/107741019
https://zhuanlan.zhihu.com/p/258762446

KKT条件

在数学中，卡罗需-库恩-塔克条件（英文原名：Karush-Kuhn-Tucker Conditions常见别名：Kuhn-Tucker，KKT条件，Karush-Kuhn-Tucker最优化条件，Karush-Kuhn-Tucker条件，Kuhn-Tucker最优化条件，Kuhn-Tucker条件）是在满足一些有规则的条件下，一个非线性规划（Nonlinear Programming）问题能有最优化解法的一个必要和充分条件。这是一个广义化拉格朗日乘数的成果。

Karush-Kuhn-Tucker (KKT)条件是非线性规划(nonlinear programming)最佳解的必要条件。KKT条件将Lagrange乘数法(Lagrange multipliers)所处理涉及等式的约束优化问题推广至不等式。在实际应用上，KKT条件(方程组)一般不存在代数解，许多优化算法可供数值计算选用。

https://zhuanlan.zhihu.com/p/38163970
https://zhuanlan.zhihu.com/p/33229011
https://blog.csdn.net/qq_36896268/article/details/121588597