Optimization pre

最优化简介

定量决策问题，对有限资源合理分配达到某种意义的最优

• [ ] All todo done

最优化问题概括

一般形式

$min \quad f(x),\qquad s.t.\ x\in X$

其中$x$为$n$维决策变量，$f$为$R^n$映射到$R$的目标函数，$X\subseteq R^n$ 为可行域 $s.t.:subject \ to$，

可行解：可行域中的点。最优解：$x^*$

基本概念

最优化算法研究可大致分为

• 构造最优化模型
• 确定最优化问题的类型和设计算法
• 实现算法或调用算法软件包
• 最优化模型的构造

下面选择几个比较经典的最优化问题简单介绍

连续与离散优化问题

主要根据决策变量的可行集合来区分，常见的离散规划便是整数规划

简单对比

• 连续优化可以通过某点的邻域取值信息来判断该点是否最优，但是显然离散优化不可

导致离散优化相对而言往往更难求解，不过实际中离散优化往往可以转为多个连续优化问题进行求解。如分支定界法等，不出意外的话后面也会简单介绍并说明下大致原理。

于是便可重点关注连续优化问题了

无约束与约束优化问题

分类标准即是约束是否存在，无约束优化的决策变量的取值为整个$n$维空间。

但是在某种程度上，约束优化问题也是无约束优化问题，可以通过一些方法将其转化为无约束优化，常见的方法有增广拉格朗日函数，罚函数。

然而笔者此时对这个算法还不太了解，所以先写下日后再看

• [ ] 简单查看相关算法，并作介绍

随机与确定性优化问题

随机优化即是目标函数或者约束函数中涉及到了随机变量从而具有一系列不确定性。

确定性优化即这两者都是确定的

随着今年人工智能的发展，随机优化的研究得到了一定的发展，在一般机器学习、深度学习， 强化学习等有重要应用，在后续博客会简单介绍相关具体的应用。

• [ ] 后续博客链接

并且由于目标的未知性，导致实际往往利用堆积样本来逼近目标函数。也由于样本较多，也往往采用期望形式，利用随机优化方法求解。

值得注意的是，确定性优化的随机版本往往有着更低的复杂度。

不过笔者还是不了解具体的算法，所以下次一定

• [ ] 随机版本优化算法复杂度较低的原因

线性与非线性规划问题

线性规划为目标函数与约束函数都是线性的。相应的非线性则是至少一个非线性

一些相关里程碑$\Downarrow$

• 1947 $George \ Bernard \ Dantzig$提出单纯型法
• 1979 $Leonid$证明线性规划的多项式算法存在性。
• 1984 $Narendra$ 提出内点法求解线性规划问题。

后续也会介绍 主要方法：单纯型与内点法\

凸和非凸优化问题

凸优化问题是最小化问题的目标函数与可行域都是凸函数和凸集，

（对于最大化问题要相应改为凹函数）

实际中显然凸优化问题相对更容易求解，而将非凸问题转为凸函数也是比较重要的问题

求解时常用技巧

• $Taylor$展开：对于非线性目标或约束函数，可采用线性函数或二次函数来逼近，简化问题
• 对偶：”正难则反“
• 拆分：查分目标变量，化为多个简单子问题
• 块坐标下降：对于较高维问题，通过逐步分解分量转化为多个低维空间的问题

两种收敛速度

• $Q$收敛速度：$quotient$

  $Q$$-$$n$次收敛

  $\frac{||x^{k+1}-x^*||}{||x^k-x^*||^n}\le a$

• $R$收敛速度：$root$

  若存在$Q-n$阶收敛的非负点列$t_k$，$s.t.$ $||x^k-x^*||\le t_k$ 则是$R-n$次收敛

• [ ] 最优化实例：稀疏优化、低秩矩阵恢复、深度学习

参考资料

1. 最优化：建模、算法与理论 刘浩洋,户将,李勇锋,文再文著
2. 最优化理论与算法 第2版第二版 陈宝林 清华大学出版社
3. 数学规划基础 刘红英，夏勇，周水生 编 北京航空航天大学出版社
4. 1509学长的本课程旧作业记录