凸优化理论（一）数学优化问题的分类

超、凢脫俗 2022-10-22 09:21 333阅读 0赞

# 凸优化学习------数学优化问题的分类 #

#### 一、 无约束优化和有约束优化 ####

在连续优化问题中，根据是否有变量的约束条件，可以将优化问题分为无约束优化问题和约束优化问题。有变量的约束条件则为约束优化问题，反之则为无约束优化问题。

#### 二、 线性优化和非线性优化 ####

目标函数和所有的约束函数都为**线性函数**，则该问题为**线性规划问题（Linear Programming）**。相反，如果目标函数或任何一个约束函数**为非线性函数**，则该问题**为非线性规划问题（Nonlinear Programming）**。  
       在**非线性优化问题**中，有一类比较特殊的问题是凸优化问题（Convex Programming）。在凸优化问题中，变量 x 的可行域为凸集，即**对于集合中任意两点，它们的连线全部位于在集合内部**。目标函数 f 也必须为凸函数，即满足  
![在这里插入图片描述][20210325162425777.png]

凸优化问题是一种特殊的约束优化问题，需满足目标函数为凸函数，并且等式约束函数为线性函数，不等式约束函数为凹函数。

#### 三、 连续优化和离散优化 ####

根据输入变量 x 的值域是否为实数域，数学优化问题可以分为离散优化问题和连续优化问题。

###### 3.1 连续优化问题 ######

**连续优化（Continuous Optimization**问题是目标函数的输入变量为连续变量 x ∈ Rd，即目标标函数为实函数。

###### 3.2 离散优化问题 ######

**3.2.1 组合优化（Combinatorial Optimization）：**  
       其目标是从一个有限集合中找出使得目标函数最优的元素。在一般的组合优化问题中，集合中的元素之间存在一定的关联，可以表示为图结构。典型的组合优化问题有旅行商问题、最小生成树问题、图着色问题等。很多机器学习问题都是组合优化问题，比如特征选择、聚类问题、超参数优化问题以及\*\*结构化学习（Structured Learning）\*\*中标签预测问题等。  
**3.2.2 整数优化**  
       输入变量 x ∈ Zd为整数。一般常见的整数规划问题为整数线性规划（Integer Linear Programming，ILP）。整数线性规划的一种最直接的求解方法是：（1）去掉输入必须为整数的限制，将原问题转换为一般的线性规划问题，这个线性规划问题为原问题的松弛问题；（2）求得相应松弛问题的解；（3）把松弛问题的解四舍五入到最接近的整数。但是这种方法得到的解一般都不是最优的，因此原问题的最优解不一定在松弛问题最优解的附近。另外，这种方法得到的解也不一定满足约束条件。

#### 四、 单目标优化和多目标优化 ####

###### 4.1 单目标优化（Single-Objective Optimization） ######

所评测目标只有一个，只需要根据具体的满足函数条件，求得最值

###### 4.2 多目标优化（Multi-objective Optimization） ######

多个评测函数的存在，而且使用不同的评测函数的解，也是不同的。也即是说：多目标优化问题中，同时存在多个最大化或是最小化的目标函数，并且，这些目标函数并不是相互独立的，也不是相互和谐融洽的，他们之间会存在或多或少的冲突，使得不能同时满足所有的目标函数。**一般情况下多目标优化情况并没有唯一的全局最优解**

#### 五、 静态规划和动态规划 ####

###### 5.1 静态规划（Static Programming） ######

**静态规划简单来说是穷举事件所有解决方法，从中选出最优的一个解。静态规划最大的特点是时间复杂度特别高**，当问题规划很大时计算量是一个天文数字。同时这种方法也有优点，就是穷举过程中我们始终存在着一个可行解。这种方法，**从一个或多个可行解开始，通过不断迭代对现有可行解优化，最后得到最优解。这种方法称为静态规划。**

###### 5.2 动态规划（Dynamic Programming） ######

动态规划是运筹学的一个分支，是求解决策过程最优化的过程。是通过比较当前决策状态和未来几个状态的比较进行选取最优，**关键点是找到状态转移方程。**

###### 5.2.1 动态规划概念引入： ######

有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要做决策，从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线．这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策问题。**在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化的过程为动态规划方法。**

###### 5.2.2 动态规划基本思想 ######

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

###### 5.2.3 动态规划局限性： ######

动态规划对于解决多阶段决策问题的效果是明显的，但是动态规划也有一定的局限性。首先，它没有统一的处理方法，必须根据问题的各种性质并结合一定的技巧来处理；另外当变量的维数增大时，总的计算量及存贮量急剧增大。因而，受计算机的存贮量及计算速度的限制，当今的计算机仍不能用动态规划方法来解决较大规模的问题，这就是\*\*“维数障碍”\*\*。

#### 六、 随机规划 ####

随机规划是规划论的一个分支，线性规划的推广。研究约束条件中的系数和目标函数中的参数均为随机变量时的线性规划问题。用于研究具有不确定性的决策问题。随机规划的中心问题是选择参数，使收益的数学期望达到最大，或使成本的数学期望达到极小。根据数学模型求得问题的最优解，但这个最优解一般不是一个确定值而是一个期望值。在随机规划中，需对随机变量进行描述，分析其概率分布，往往还要考虑各随机变量的自相关和互相关，因而在理论上和求解方法上都比确定性规划复杂得多。实际上，求解随机规划问题时，总是设法把它转化成确定性数学规划问题，再进行求解。如果随机变量的非确定性或者量的变化很小，对系统的性能不产生严重影响，可以用其数学期望代替这个非确定值，并用确定性方法求解；然后通过敏感性分析来估计非确定性因素对方案的影响程度。如果随机变量变化很大，用期望值可能使方案性能的评价受到很大影响，这时就要用随机规划方法求解。  
**常见的随即规划问题：报童问题。**  
**常用方法：样本均值方法。**

#### 七、 鲁棒规划 ####

###### 7.1 鲁棒优化定义 ######

鲁棒优化的目的是求得这样一个解，**对于可能出现的所有情况，约束条件均满足，并且使得最坏情况下的目标函数的函数值最优。** 其核心思想是将原始问题以一定的近似程度转化为一个具有多项式计算复杂度的凸优化问题。鲁棒优化的关键是建立相应的鲁棒对等模型。然后利用相关的优化理论将其转化为可求解的“近似”鲁棒对等问题，并给出鲁棒最优解。

###### 7.2 鲁棒优化原理 ######

鲁棒优化与其它不确定优化方法的最大区别在于：  
       ①鲁棒优化强调的是所谓的硬约束，寻求一个对于不确定输入的所有实现都能有良好性能的解，即不确定优化问题的解对于任何一个可能参数的实现都必须是可行的，而其它不确定优化问题并没有这个要求。  
       ②鲁棒优化的建模思想与其它优化方法不同，它是以最坏情况下的优化为基础，这代表了一个保守的观点。得到的优化方案并不是最优的，但是，当参数在给定的集合内发生变化时，仍能确保优化方案是可行的，使模型具有一定的鲁棒性,即优化方案对参数扰动不敏感。  
       ③鲁棒优化对于不确定参数没有分布假定，只是给出不确定参数集，不确定参数集合内的所有值都同等重要

###### 7.3 鲁棒优化适用范围 ######

鲁棒优化是解决内部结构和外部环境不确定环境下的一种新的优化方法。鲁棒优化解决内部结构变动问题时,主要是约束条件参数的不确定性或目标函数参数的不确定性解决外部环境变化时，主要是外界不确定性扰动。鲁棒优化己经从最初的线性优化鲁棒方法，发展到鲁棒优化理论的经典体系。与其它不确定优化问题的处理方法不同的是,鲁棒优化更加适用于如下情况：  
       ①不确定优化问题的参数需要估计,但是有估计风险；  
       ②优化模型中不确定参数的任何实现都要满足约束函数；  
       ③目标函数或者优化解对于优化模型的参数扰动非常敏感；  
       ④决策者不能承担小概率事件发生后所带来的巨大风险。

#### 八、 随即规划和鲁棒优化区别 ####

随机优化需要“不确定参数的分布模型”，鲁棒优化不需要“不确定参数的分布模型”。  
       随机优化通过对随机参数取期望，将模型转化为确定性模型求解，它的解并不满足所有参数取值。  
       鲁棒优化，只要不确定参数属于给定的不确定集合，它的解严格满足所有约束。

###### 最后求一波三连,hh. ######

[20210325162425777.png]: /images/20221022/6afef35cca754adc94d01fd3b0f87320.png