凸优化读书笔记——概述
数学定义中的优化问题，可以写成以下的表达形式：
\[min \, f_0(x) \\ s.t. \, f_i(x) \le b_i,i=1,...,m\]其中，$x=(x_1,…,x_n)$是优化参数，$f_0$为目标函数，$f_i$为约束方程。对于满足约束方程的$x^{\alpha}$，若任意一个满足约束方程的解$z$，都有$f_0(z) \ge f_0(x^{\alpha})$，则称$x^{\alpha}$为优化方程的解，或者是最优值。
如果对于一个优化问题，其目标方程和约束方程都满足：
\[f_i(\alpha x + \beta y) = \alpha f_i(x) + \beta f_i(y)\]则称其为线性规划问题。
如果优化问题的目标方程和约束方程都满足：
\[f_i(\alpha x + \beta y) \le \alpha f_i(x) + \beta f_i(y)\]其中需要满足$\alpha+\beta=1, \alpha>0, \beta>0$，这样的问题可以归类为凸优化问题。可以发现线性规划是凸优化的一种特殊情况，而凸优化可以看作线性规划的一种推广。
对于求解一般形式的优化问题，根据目标函数与约束函数的具体形式、变量与约束条件的数量、以及稀疏性等特殊结构等情况在求解时具有显著的差异，即便当目标函数和约束函数均为光滑函数（例如多项式）时，一般形式的优化问题的求解难度仍远超预期。因此针对此类通用问题的求解方法往往需要作出某种妥协，例如接受超长计算时间或无法保证找到解的风险。
然而，对于某些特定类型的问题，我们拥有高效算法，即使面对包含数百甚至上千个变量和约束条件的大规模问题也能可靠求解，比如最小二乘问题以及线性规划问题，相较而言，凸优化也可以通过特定算法对其结果进行求解。
最小二乘问题
最小二乘问题指的是一类没有约束方程且优化目标是$a_i^T x - b_i$的平方和的问题，即
\[min \, f_0(x) = ||Ax-b||_2^2 = \sum_{i=1}^k(a_i^T x - b_i)^2\]其中$A \in R^{k\times n}, n\le k$。
当$a_i^T x - b_i$为线性方程时，求解最小二乘问题可以通过
\[(A^TA)x = (A^T)b\]来进行求解，对于稠密的矩阵求解，其耗时为$n^2k$量级，对于稀疏的矩阵求解，其求解速度则远快于$n^2k$。
最小二乘问题是回归分析、最优控制以及众多参数估计与数据拟合方法的基础。该问题具有多种统计学解释，例如可视为：当线性测量值受到高斯测量噪声干扰时，对向量x进行极大似然估计的过程。最小二乘问题有着众多的推广，比如加权最小二乘问题以及正则化问题，可以构建成形如下面的形式：
\[\sum_{i=1}^k \omega_i(a_i^T x - b_i)^2 \qquad \sum_{i=1}^k (a_i^T x - b_i)^2+\rho\sum_{i=1}^n x_i^2\]线性规划问题
线性规划问题可以表示为
\[min \, c^Tx \\ s.t. \, a_i^Tx\le b_i, i=1,...,m\]线性规划问题的求解并不存在简单的解析公式（如最小二乘法那样），但已有多种高效求解方法，包括单纯形法以及内点法。虽然无法像最小二乘法那样精确给出求解所需的算术运算次数，但可以严格证明：采用内点法在给定精度下求解线性规划问题时所需的运算次数存在确定界限。实际计算复杂度约为n²m量级（假设m≥n），但其常数项的特征不如最小二乘法明确。这些算法具有较高可靠性——尽管可能略逊于最小二乘法的求解方法。
某些问题可以直接表示为线性规划问题，但是更多情况下需要对问题进行转化，将其转变为线性规划的形式，比如以切比雪夫逼近为例
\[min \; max_{i=1,...,k}|a_i^T x - b_i|\]对于这种问题可以将其转化为线性规划问题进行求解：
\[min \; t \\ s.t. \; a_i^T x - t \le b_i \\ -a_i^T x - t \le -b_i\]凸优化问题
一般而言，凸优化问题不存在解析解，但（与线性规划问题类似）存在高效的求解方法。内点法在实践中表现优异，某些情况下可被证明能在多项式复杂度的计算量内达到指定精度。
在不考虑问题特殊结构（如稀疏性）的情况下，内点法每次迭代的计算复杂度约为$max{n^3, n^2m, F}$量级，其中F代表计算目标函数$f_0$及约束函数$f_1,…,f_m$一阶和二阶导数的成本。
与线性规划求解方法类似，这些内点法具有高度可靠性。在现代台式计算机上，我们能在数十秒内轻松求解具有数百个变量和数千个约束的问题。若利用问题结构特征（如稀疏性），则可求解包含数千个变量和约束的大规模问题。
使用凸优化方法非常类似于使用最小二乘法或线性规划——只要我们能够将问题表述为凸优化问题，就能高效求解，就像处理最小二乘问题那样。略带夸张地说，当你把一个实际问题转化为凸优化问题时，就相当于已经解决了这个问题。
非线性优化
非线性优化（或称非线性规划）是指当目标函数或约束函数为非线性且无法判定其凸性时的优化问题。遗憾的是，针对一般非线性规划问题，目前并不存在普适的有效解法。即便是仅含十几个变量的简单问题也可能极具挑战性，而涉及数百个变量的问题往往难以求解。
因此，求解一般非线性规划问题的方法发展出多种不同路径，但每种方法都需作出某种妥协。
局部最优解
在局部优化方法中，其妥协之处在于放弃寻找全局最优解，转而寻求局部最优解——即在邻近可行点中使目标函数最小化，但不保证其目标值优于所有其他可行点。大量关于非线性规划的研究聚焦于局部优化方法，因此这类方法已相当成熟。
局部优化方法具有三大优势：计算速度快、能处理大规模问题、适用性广（仅需目标函数和约束函数可微）。这使得该方法在”不求最优，但求较好”的应用场景中被广泛采用。例如在工程设计中，可用局部优化来改进通过人工或其他方法获得的初始设计方案。
然而，局部优化方法存在若干固有缺陷（除可能无法获得全局最优解外）：
-
需要提供优化变量的初始猜测值，该初始点将显著影响最终获得的局部解质量
-
无法评估所得局部解与全局最优解的差距
-
对算法参数敏感，常需针对具体问题进行调整
全局最优解
在全局优化中，我们追求的是找到优化问题的真实全局解，但代价是计算效率的牺牲。全局优化方法的最坏情况复杂度随着问题规模n和m呈指数级增长——尽管实际应用中可能遇到计算速度较快的特例，但这种情况并不常见。
全局优化通常应用于以下场景：
-
变量数量较少
-
计算时间非关键因素
-
获取真实全局解的价值极高
典型应用案例包括高价值或安全关键系统的工程设计与验证：
-
优化变量代表制造过程、环境或运行条件中的不确定参数
-
目标函数为效用函数（数值越小代表性能越差）
-
约束条件表征参数的先验知识范围
通过求解该优化问题，可获得参数的最劣组合。若此时系统性能仍可接受，则可认证其安全性或可靠性。
凸优化在非线性优化中的作用
局部优化的初始化方法
凸优化与局部优化的协同应用，对于非凸问题，可先构造其凸近似模型进行求解。由于凸优化无需初始猜测且求解高效，能快速获得近似问题的精确解。该解可作为初始点，供局部优化算法进一步求解原始非凸问题。
非凸优化的凸启发式方法
-
稀疏向量求解；寻找满足约束的稀疏向量（即非零元素最少的向量）本质上是组合优化难题。基于凸优化的启发式方法常能获得较稀疏的可行解。
-
随机化算法；通过概率分布生成候选解集并择优选取，可近似求解非凸问题。
全局优化的界估计技术
全局优化方法常依赖目标函数最优值的有效下界估计，可以通过基于凸优化的经典方法（松弛法，拉格朗日松弛法）求解理论下界。
Reference
[1] Boyd S P, Vandenberghe L. Convex optimization[M]. Cambridge university press, 2004.