《数值最优化》笔记 第1章

ChuanXin

引言

      优化是决策学中一个很重要的工具，在其他学科，比如说物理学、金融、化学、计算机科学中都有广泛的应用。那么什么是优化呢？通常情况下我们的系统存在一个问题，我们用数学语言对其进行描述，这个过程叫做建模，用数学模型来描述这个问题，可能这个模型有很多的变量和约束，我们想找到最优的答案或者解。求解这个最优解的过程就叫做优化。
数学描述



      其中，f为目标函数，即待优化的函数；x为变量；c分别为等式约束和不等式约束。下面是一个例子：


它的几何描述如Figure 1.1 所示：


优化的分类

• 连续优化与离散优化
  
• 约束优化与无约束优化
  
• 全局优化与局部优化
  
• 随机优化与确定性优化
  

凸性

       凸集（convex set）：凸集合中的任意两点连接组成的线段，线段上的点仍然处在集合中。
       凸函数（convex function）：如果目标函数的自变量x为凸集，并且目标函数满足下式，则函数为凸函数。


优化算法

       上面我们对优化问题有了一个简单宏观的了解，知道了优化问题的种类，列出了优化问题的数学描述，有了数学描述，怎么解这个数学问题就用到了算法，下面我们对解优化问题的算法进行简单的概述。
       优化算法都是一个迭代的过程。从一个起始点开始，生成一系列优化目标函数的迭代，直到达到我们想要的结果，或者触发了某个终止条件。大部分算法的策略都是利用目标函数值，约束方程的值，或者这些函数方程的一阶或者二阶偏导。有的算法（Trust Region）要考虑并收集之前的迭代结果来决定下一次动作，但是有的算法（Line Search）只考虑当前阶段的系统信息来对之后的迭代进行决策。不管算法采用的何种策略都应具备如下属性：

• 鲁棒性：对当前问题的不同输入具有鲁棒性
  
• 高效：计算时间尽可能的短，并且消耗的计算资源小
  
• 精确性：能够精确地确定解决方案，而不会对数据错误或在计算机本身产生的数值截断错误过于敏感.
  

       当然，鱼和熊掌不可兼得，鲁棒的算法可能很慢，在收敛速度、计算资源的消耗和算法的鲁棒性之间的权衡是数值优化的核心问题，也是本书的讨论重点。
NOTES

       优化通常也被叫做数值规划（mathematic programing）有时会和计算机中的编程混淆。再就是对实际问题的建模不是本书的讨论范围，因为本书的重点是教会大家对已经建模好的数学问题进行求解，使用何种算法等。
总结

       作为《数值最优化》的第一章，作者给我们讲述了数值优化的总体框架，比如说数值优化的种类，包括对优化问题的数学描述，解优化问题的算法的整体思路，并告知了我们算法应该具备的一些属性。对整个数值优化问题具有一个框架性的认知是尤为重要的，对系统性学习优化算法有非常大的益处，比如说我们常见的最小二乘问题，它是属于优化问题的哪一类，如果我们能确定该问题属于哪一类，我们就可以使用对应的算法对我们的问题进行求解，随着对书中后续章节的学习，这些问题都会一一给出答案。
首发于公众号：EigenVision