开新坑，我就是当代开坑大师。

学一下这本Boyd的《Convex Optimization》，看的是王书宁翻译的这本，没仔细找英文版，就直接用找到的中文版了。

看评价这本书很牛，冲！

看了一下目录，这个书大概分成三个部分，包括

• 引言
• 第一部分：理论（凸集，凸函数，凸优化问题，对偶）
• 第二部分：应用（逼近与拟合，统计估计，几何问题）
• 第三部分：算法（无约束优化，等式约束优化，内点法）
• 附录（有关的数学知识，双二次函数的问题，有关数值线性代数知识）
• 参考文献
• 符号
• 索引

今天学习的内容就是这本书的引言部分，主要是对数学优化进行简单的回顾，认识一下凸优化的概念和特殊地位，应该是简单的，go——

• 数学优化问题（优化问题）
• 一般形式（见下图）
• 成分（简单列举介绍）
• 优化变量（ ，可以是多维）
• 目标函数（ ）
• 约束函数（ ）
• 约束上限（ ）
• 最优解（ ）

• 特殊形式的优化问题
• 线性规划
• 目标函数和约束函数都是线性函数，即对 和 有
• （这两个公式将线性规划和凸优化相关联我第一次遇见，感觉很不错，我喜欢这种知识存在内部联系的感觉）
• 凸优化问题
• 目标函数和约束函数都是凸函数，即对 和 且满足 有
• ——>小结论：
• 凸性是较线性更为一般的性质：线性函数需要严格满足等式，而凸函数仅仅需要在 取特殊值的情况下满足不等式。
• 凸优化可以看作是线性规划的扩展。

• 优化问题
• 可以看作是在向量空间 的一集备选解中选择最好的解
• 用 表示备选解
• 用 表示解需要满足的条件
• 用 表示选择解所需要的成本（其负则为效益或效用）
• 因此，我们要求的解就是满足约束条件的所有备选解中成本最小（效益最大）的解
• 例子（这些例子就不详细说明了，应该之前学习中经常见到）
• 投资组合优化
• 器件尺寸问题
• 数据拟合
• 大量设计决策（或系统设计、分析与操作）的实际问题可以表示成数学优化问题，或者数学优化问题的变化形式如多目标优化问题
• 嵌入式优化：在没有或极少人为干预的条件下实时做出选择甚至实时执行动作，优化结果必须非常可靠且必须在给定的时间和存储量内解决问题。

• 求解方法
• 指（以给定精度）求解此类优化问题中的某一实例的算法
• 算法的有效性——目标函数和约束函数的形式，优化问题所包含的变量和约束的个数、特殊的结构（如稀疏结构）等因素
• 求解
• 一般形式的问题：是需要付出一些代价的，如较长的计算时间或者可能找不到解
• 特殊形式的问题：存在一些有效的算法，如最小二乘问题和线性规划问题，以及凸优化问题

• 这一节将介绍两类特殊形式的凸优化问题——最小二乘和线性规划
• 第四章会详细讨论，可以等等之后详细看

• 最小二乘问题
• 没有约束条件（即 ），目标函数是若干项的平方和，每一项具有形式
• 具体形式如下
• (很烦跳行这个无序列表就不能接上)
• 其中， , 是矩阵 的行向量，向量 是优化变量
• 求解最小二乘问题
• 最小二乘问题可以简化为求解一组线性方程
• 因此，可得解析解
• 最小二乘算法有不少优秀的求解算法且算法的精度和可靠性都很高。
• 最小二乘问题可以在有限时间内进行求解，该时间与 近似成正比，且比例系数已知。
• 根据摩尔定律（百度了一下是这个意思：摩尔定律是英特尔创始人之一戈登·摩尔的经验之谈，其核心内容为：集成电路上可以容纳的晶体管数目在大约每经过18个月到24个月便会增加一倍。换言之，处理器的性能大约每两年翻一倍，同时价格下降为之前的一半），以后的求解时间还会指数下降。
• 求解最小二乘问题的算法和软件都满足嵌入式优化的要求。
• 若矩阵 具有特殊结构，如稀疏的，则求解速度可以进一步提高。
• 若最小二乘问题规模极大，求解或许会存在一定的难度，但是在大部分的应用中，最小二乘问题的求解都是稳定可靠的。
• 使用最小二乘
• 最小二乘问题是回归分析，最优控制以及很多参数估计和数据拟合方法的基础。
• 判断最小二乘问题：检验目标函数是否是二次函数，然后检验此二次函数是否半正定
• 加权最小二乘问题：
• 最小化加权的最小二乘成本
• 其中，加权系数 均大于零，反映了求和项的重要程度或者说对接的影响程度（在统计应用中当给定的线性观测值包含不同方差的噪声时，可以用加权最小二乘来估计向量 ）
• 正则化
• 在成本函数中增加一些多余的项来实现。
• 最简单的形式
• 这里， ，此问题也可以转为标准最小二乘问题，当 较大时，后一项将施加一个惩罚，其得到的解比仅仅优化第一项时更加贴合实际。
• 参数 的选择取决于使用者，选择原则是使原始目标函数值尽可能小同时保证后一项的值不能太大
• 在统计估计中，在待估计向量 已知时，可以采用正则化方法。
• 加权最小二乘和正则化将在第六章详细介绍，第七章会给出他们在统计学上的意义。

• 线性规划
• 目标函数和约束函数均为线性函数
• 其通用表达形式如下 （有没有人知道知乎的公式编辑怎么把公式左对齐啊）
• 其中，向量 是问题参数，它们决定目标函数和约束函数
• 求解线性规划
• 存在非常多有效的求解线性规划问题的方法：Dantzig的单纯形法，内点法（后面将详细介绍内点法）
• 求解线性规划问题的确切运算次数不能给出，可靠性与最小二乘相比略逊一筹
• 也可以运用到嵌入式优化中
• 使用线性规划
• 原始的优化问题可以通过一定的技巧（将在第四章进行介绍）转换为等价的标准形式的线性规划问题。
• 例子
• Chebyshev逼近问题
• 其中，优化变量， 是问题的参数，参数取值确定后即得到一个具体问题。
• 值得注意的是：该形式与最小二乘的形式有相似之处，主要区别包括：一个以平方和为目标函数且最小二乘问题的目标函数可微。
• 对上述问题进行转换，变为如下形式的线性规划问题（真不会左对齐，吐了）——
• （第一次见，不太懂）具体的解释会在第六章介绍，按下不表了
• 判断问题是否能转换为线性规划问题比最小二乘问题要难。

• 凸优化的形式
• （假装左对齐）
• 其中，函数 为凸函数，即对 和 且满足 有
• 容易知道，之前讨论的最小二乘问题和线性规划问题都是凸优化问题

• 凸优化问题的求解并没有一个解析表达式，但是存在很多有效的算法求解凸优化问题
• 内点法
• 可以在多项式时间内以给定精度求解这些凸优化问题
• 每一步需要的操作次数与 成正比
• 求解一般的凸优化问题并不如最小二乘问题和线性规划一样是一项成熟的技术，但是预计未来几年内解决一般的 凸优化问题将成为一项技术。
• 对于凸优化的几类重要问题，如二阶锥规划和几何规划问题（第四章将详细介绍），内点法逐渐成为一项成熟的技术，

• 从概念上来讲，使用凸优化和使用最小二乘以及线性规划类似。如果某个实际问题可以表述为凸优化问题，那么这个问题事实上已经解决。
• 然而，判断某个问题是都是否属于凸优化问题或识别哪些可以转换为凸优化文艺是具有挑战性的工作——这也是这本书的主要目的。

• 非线性优化（非线性规划）
• 优化问题的目标函数或约束函数是非线性函数，且不一定为凸函数
• 对于一般的非线性规划问题，目前还没有有效的求解方法。
• 现有的用于求解非线性规划问题的方法都是在放宽某些指标的条件下，采取不用的途径进行求解。

• 局部优化
• 放宽对解的最优性的要求，不在搜寻使目标函数值最小的最优可行解。取而代之寻找局部最优解——在其小邻域内的所有可行解里是目标函数值最小的那个解，但是不保障优于不在此邻域内的其他可行解。
• 局部优化求解
• 优点：
• 局部优化求解迅速
• 可以处理大规模问题——在满意解（非最优解）同样即便有价值具有价值的应用场合（如工程设计）
• 缺点：
• 需要确认优化变量的初始值且初始值的选取非常重要，对最终得到的局部最优解有着很大的影响。
• 无法估计局部最优解和全局最优解相比到底有多大的差距。
• 局部最优解对算法的参数值一般也较为敏感，通常需要针对某个具体问题或某类问题进行调整。
• 需要更多的技巧——选择合适的算法、调整算法的参数、选取好的初始点。
• 局部优化不仅是一项技术，而且是是一种研究得较为透彻得技巧，常常很有效
• 非线性规划中得局部优化问题 vs 凸优化
• 局部优化——大部分局部优化方法仅仅要求目标函数和约束函数可微，因此将实际问题建模为非线性优化问题是相当直接得，当建模完成后，局部优化得技巧体现在问题的求解上。
• 凸优化——技巧和难点体现在描述问题的环节，因为一旦问题被建模为凸优化问题，其求解过程相对来说就非常简单。

• 全局优化
• 寻找优化问题的全局最优解
• 针对变量个数较少的小规模问题，若对计算时间没有苛刻的要求且寻找全局最优解非常有价值，采取全局优化
• 如工程设计中高价值系统或安全性第一的系统最坏情况分析问题或验证问题
• 此时：目标函数是效用函数，关于参数取值的先验知识构成了约束条件，不确定参数是问题的变量。
• 优化问题即为寻找最坏情况下的参数值即参数的最差值
• 如果在最差值的情况下，系统仍然可靠运行，我们认为系统是安全的或者可靠的
• 局部优化 vs 全局优化
• 局部优化方法可以迅速找到一些较差情况下参数的取值，但是不能保证是最差的情况。如果局部优化能够找到一组参数取值使系统的性能不在可接受范围内，那么我们可以说系统的不可靠的。
• ——但是局部优化不能证明系统是可靠的。
• 全局优化能够找到绝对最差的参数取值，如果在此情况下，系统的性能仍然可以接受，我们可以证明系统是安全可靠的。
• ——但是全局优化需要付出的代价是计算时间，即使对参数规模较小的问题都有可能很长（不过在验证系统的可靠性中全局优化还是非常有必要的）

• 本书主要讨论凸优化问题以及可以转化为凸优化问题的一些应用——不过对于非凸问题，凸优化仍然有着非常重要的作用。
• 局部优化中利用凸优化进行初始值的选取
• 将凸优化局与局部优化结合起来
• ——首先将非凸问题表述为近似凸优化问题，通过求解近似凸问题得到其精确解。然后将该精确解作为局部优化算法的初始值来求解原非凸问题
• 非凸优化中的凸启发式算法
• 求解非凸问题的很多启发式算法都是基于凸优化。
• 例子
• eg1：搜寻满足一定约束条件的稀疏向量
• 稀疏向量即含有较少非零元素的向量
• 复杂的组合问题
• 基于凸优化存在一些简单的启发式算法可以找到较稀疏的解（第六章将详细介绍）
• eg2：随机算法
• 随机算法产生服从某个概率分布的一些备选解，在这些备选解中选择最好的那个解作为非凸问题的近似解。
• 假设产生备选解的概率分布可以用参数表征——如均值、方差，那么，我们就可以转为哪个分布可以使得目标函数具有最小的期望——此时，问题或许可以表述为凸问题（习题11.23）
• 全局优化的界
• 非凸问题的全局优化方法基本都需要给出最优解的下界，而且计算代价必须较少
• 现有的求解下界的两个标准方法都是基于凸优化
• ——松弛算法
• 每个非凸约束都用一个松弛的凸约束代替
• 在Lagrange松弛中，求解Lagrange对偶问题（第五章介绍）——此问题是凸的，并给出了原非凸问题最优解的一个下界。

• 介绍基本的定义、概念以及凸分析和凸优化的一些结果
• C1，C2：
• 介绍凸集和凸函数，给出几种常见的凸集和凸函数
• 给出几种凸运算规则，即针对凸集以及凸函数的保凸运算
• 判别一些比较复杂的凸集和凸函数
• C4：
• 介绍将问题表述为凸优化问题的几种变换
• 介绍几类常用的凸优化问题：如线性规划、几何规划以及二阶锥规划和半定规划
• C5：
• Lagrange对偶理论
• KKT最优性条件
• 凸优化问题的局部敏感性和全局敏感性分析

• 介绍凸优化在概率统计、计算几何以及数据拟合中的广泛应用
• 让读者通过例子了解如何在实践中应用凸优化

• 介绍求解凸优化问题的数值算法——主要介绍牛顿法和内点法
• 旨在传达凸优化方法的基本概念和属性
• C9：
• 无约束优化
• C10：
• 等式约束优化
• C11：
• 内点法

• 附录1：列举了本书可能用到的数学知识并定义了本书所使用的数学符号
• 附录2：讨论一类有特殊优化问题——目标函数是二次函数且还有一个二次约束
• 附录3：介绍数值线性代数，主要关注一些方法

• 例子仅仅为读者了解算法的性能提供帮助

• 习题混杂，难度未标出

• 采用标准符号
• 实数集
• 非负实数集
• 正实数集合
• 维实向量集合
• 实矩阵集合
• （剩下的不想打了，略。。。）
• 矩阵集合描述
• 函数描述
• 有限维空间

• 各种大佬写的相关参考文献，感兴趣可以自己看看，包括这些部分——
• 最小二乘
• 非线性规划
• 全局优化
• 凸分析
• 内点法
• 现代凸优化问题
• 其他求解凸优化方法
• 凸优化的应用
• 凸优化问题比较容易求解的思想，这个话看起来很牛，放个图，具体的各位自己看吧——

OK，完事，下班了兄弟们！

希望我下周直接更新第二章，周更 插好了。