Optimization - Optimize Algorith

一般的优化算法

在我们解决optimization问题时，有很多优化算法：
大致可以分为Derivative-based[0][1][2][6]以及Derivative-free [5] 的方法。其中Derivative-free的方法其实非常多，很多随机、启发式的算法都可以归类于此：譬如EE中的multi-arm bandit，非线性规划中的Nelder-Mead method (simplex推广)，很多meta heuristic的方法如GA，simulated annealing等。
注意，实际运用这些算法中，既有Numerical的，也有Analytical的。在OR与ML中，都有不同种的算法被运用，譬如Linear Regression中解析解与牛顿法迭代或者随机梯度下降类的算法都能得到一致的解。

机器学习ML中的优化算法

机器学习中的优化器Optimizer（适用于ML，具体实现了特定的优化算法）：其实就是一系列“无约束非凸优化问题的求解算法”（当然，不少线性模型是凸优化问题）
机器学习的本质，是建模了一个目标与特征之间的函数，机器学习的优化算法本身就在求解这个函数的“形式”以及参数。也可以理解为一个求解“复杂函数的优化问题？”的算法？
现代的DNN网络和最根本的训练模式Back Propogation极大地拓展了的表达能力，同时大规模的分布式框架也使得工业级的深度运用得以实现。

OR中的优化算法

由于OR中要研究的问题往往更加specific。而且往往，区别于ML，问题都是Constrainted。（虽然ML也可以通过一些特定的方式提供限制。）因此，在OR中，有更多特定的算法以及理论被提出以及研；究。譬如Interior Point method(numerical iterative)，Lagrangian approach(constrainted to unconstainted)，Primal and Dual theory(dual problem)等等

ML/OR的运用场景（不同的modeling，不同的 optimization）

1、ML中涉及很多的modeling，optimization的理论，但是现代Machine Learning的框架，已经把optimization的部分都封装起来了，同时，由于ML中的Modeling的方式相对比较单一，所以也由框架提供了很大的支持（大部分就是些loss函数的组合，同时模型结构上的设计提供先验【类似提供了一种函数形式】）。ML本身是个非常强大体系化的框架，能解决很多特定的predictive问题的建模与求解。
2、而在传统的OR中，也很多mathematical modeling的问题。要求解这些问题，也涉及到许多优化算法的运用，譬如牛顿法，Duality等理论（这些理论在ML中的优化算法也被大量被运用）。但是在OR中，由于建模的方式更复杂，更灵活，同时很多时候我们关心的可能也不单单是求得的“解”（Solution）的数值本事，可能也会关心其中的一些关系和模式，从而帮助我们更深入的认知与决策。因此OR没有像ML现在这样又那么“强大无脑”的infrastructure可以帮助我们一并“解决”其中的优化问题（当然，OrTools等工具还是提供了一些算法的工具实现）。所以OR中这些优化算法的使用，往往需要更多的一些计算与推导。

• 关于ML与OR在相关建模领域扮演的不同角色：You can understand this new concept in the following way. ML is the predictive part of the analysis, whereas OR is the prescriptive part. [7]
  1、Descriptive Analytics tells you what happened in the past.
  2、Diagnostic Analytics helps you understand why something happened in the past.
  3、Predictive Analytics predicts what is most likely to happen in the future.
  4、Prescriptive Analytics recommends actions you can take to affect those outcomes.

Diff Summarize

1、ML优化的问题往往是unconstrainted，或者一些特定的，比较局限的constraint，最普遍加入优化目标以及penalties[8]，不过基本最终都转化为unconstrained来求解。而OR中更多是constrainted problem的研究。
2、OR不仅仅涉及到求得解。往往问题的变化与变量之间的变化，其关联也是我们关心的，常常可以帮助我们更深入地理解问题，以及作出决策。比如说shadow price。

Refer：

[0]：Newton method：

• 求根
  牛顿法用于寻找方程的根的迭代算法（https://en.wikipedia.org/wiki/Newton%27s_method_in_optimization），对于一阶可导函数，使用 Jacobian matrix（一阶导数的矩阵）寻找方程的根。
  多元函数方程组：http://fourier.eng.hmc.edu/e176/lectures/NM/node21.html
• 求极值
  进而可以推广到寻找函数极值（min，max，当然也可能是saddle），等价于寻找gradient方程为0的根（要求函数二阶可导，即求一阶导数方程组的根）。对于高维向量空间来说，Newton' Method使用Hessian matrix（二阶导数矩阵）来求解极值。
• 近似数值替代？
  跟newton method类似的如Secant method（https://en.wikipedia.org/wiki/Secant_method）其实就是用Finite difference [4]来逼近函数导数的类newton method（可以计算即可，不用每一步计算导数）。
• 条件
  注：由于Newton Method要通过计算Hessian的逆来迭代求解极值问题，所以要求函数是convex的，Hessian 正定，一定存在逆：https://math.stackexchange.com/questions/2573191/using-newtons-method-to-optimize-a-non-convex-function

[1]：Gauss Newton Method：

• 对于least square问题的简化
  由于Newton Method要计算二阶导数，以及其的逆，非常耗时。由此演化出特化针对Least-square（ objective functions that can be expressed as a sum of squares）的优化方法GNA（Gauss Newton Method），不用计算二阶导数。见https://en.wikipedia.org/wiki/Gauss%E2%80%93Newton_algorithm#:~:text=The%20Gauss%E2%80%93Newton%20algorithm%20is,a%20minimum%20of%20a%20function.中的Derivation from Newton's method，其实就是对于least square问题，在计算Hessian的时候用Jacobian matrix中的值来逼近，忽略掉second derivatives，（注：正是这个逼近，所以只能优化Least-square问题）
  在处，对，求导：
  Jacobian：
  Hessian：
  由于在根附近，很小，所以将第二项直接省去。
  注意：Gauss Newton Matrix能保证更新的矩阵半正定： guaranteed to be positive semi-definite
  https://andrew.gibiansky.com/blog/machine-learning/gauss-newton-matrix/

[2]：Quasi-Newton method：

• 更泛化的方法
  对于Quasi-Newton method[类似BFGS，DFP，Broyden类算法]，Hessian matrix是直接逼近的，因此这类方法能用于求解任意real-value function（general function），而Gauss–Newton（Levenberg–Marquardt）只能用于Least-square问题（因为Gauss–Newton在逼近的过程中，是在Sum-of-squares的基础上符号化地推导后再逼近）参考：
  https://en.wikipedia.org/wiki/Quasi-Newton_method与https://en.wikipedia.org/wiki/Gauss%E2%80%93Newton_algorithm中Related algorithms以及
  https://scicomp.stackexchange.com/questions/21012/difference-between-gauss-newton-method-and-quasi-newton-method-for-optimization
  最早DFP(https://en.wikipedia.org/wiki/Davidon%E2%80%93Fletcher%E2%80%93Powell_formula)，然后出现BFGS（是DFP的dual）
  注：BFGS更新中保证Hessian的近似为正定：https://math.stackexchange.com/questions/209237/why-does-the-standard-bfgs-update-rule-preserve-positive-definiteness

[3]: BFGS

• BFGS中对Hessian逆矩阵的计算：Sherman-Morrison formula迭代更新
  https://math.stackexchange.com/questions/3230770/derive-hessian-inverse-update-using-sherman-morrison-in-quasi-newton-method

[4]数值求导，numerical differentiation：常用方法 finite difference approximations.（计算切线slop即可）
https://en.wikipedia.org/wiki/Numerical_differentiation
*Finite difference method：一些numeric differential工程上实现的方法可以参见https://numdifftools.readthedocs.io/en/latest/src/numerical/derivest.html
analytical gradient or finite-difference：
https://scicomp.stackexchange.com/questions/507/bfgs-vs-conjugate-gradient-method
BFGS与conjugate gradient optimization：
https://math.stackexchange.com/questions/155020/is-nonlinear-conjugate-gradient-a-quasi-newton-optimization-technique等
[5]: Derivative-base的intuition其实很简单，就是在迭代求解过程中为我们搜索的过程提供一个还不错的方向。所以一般情况下，上述的数值解法都需要目标函数有可解析的梯度。
当我们没有programed gradient时，虽然我们可以用infinte difference来逼近某处的梯度，但当计算起来非常耗时，或者本身not smooth，以及有非常多的noisy（譬如抖动），此时利用梯度信息可能都不是很好（太耗时or噪声太大）。对于这些问题，可以参照一下Derivative-free optimization
https://en.wikipedia.org/wiki/Derivative-free_optimization

[6]关于SGD：这也是一种迭代的解法，但是由于这种方法只使用first derivatives，未考虑second oder以及其近似。所以在一些场景中收敛速度会很慢（比如parameters have strong interactions）

[7]ML used in OR：
https://www.quora.com/How-is-machine-learning-used-in-operations-research

[8]Constrainted ML
https://or.stackexchange.com/questions/2904/which-ml-algorithms-work-by-solving-constrained-optimisation-problems
ML中加入constrainted的方式：
https://towardsdatascience.com/augmenting-neural-networks-with-constraints-optimization-ac747408432f