怎么样做网站卖东西,织梦图片瀑布流网站模板,女人动漫做受网站,合肥市建设投资有限公司数学建模#xff1a;最优化问题及其求解概述 最优化问题定义分类离散优化问题连续优化问题 求解 此博客围绕运筹学以及最优化理论的相关知识#xff0c;通俗易懂地介绍了最优化问题的定义、分类以及求解算法。
最优化问题
定义
数学优化#xff08;Mathematical Optimiza… 数学建模最优化问题及其求解概述 最优化问题定义分类离散优化问题连续优化问题 求解 此博客围绕运筹学以及最优化理论的相关知识通俗易懂地介绍了最优化问题的定义、分类以及求解算法。
最优化问题
定义
数学优化Mathematical Optimization问题也叫最优化问题属于运筹学研究的主要内容它是指在一定约束条件下求解一个目标函数的最大值或最小值问题。这种问题在生活中很常见例如如何利用有限的资源实现最大的收益。下面给出最优化问题的数学定义 给定一个函数 f f f寻找一个变量 x 0 ∈ D x_0 \in D x0∈D使得对于 D D D中所有的 x x x f ( x 0 ) ≤ f ( x ) f(x_0) \leq f(x) f(x0)≤f(x)最小化或者 f ( x 0 ) ≥ f ( x ) f(x_0) \geq f(x) f(x0)≥f(x)最大化。函数 f f f被称为目标函数或代价函数通常集合 D D D需要满足一定的约束 D D D中的元素被称为可行解一个最小化或者最大化目标函数的可行解被称为最优解。 分类
根据变量 x x x 的定义域是否为实数域数学优化问题可以分为离散优化问题和连续优化问题。
离散优化问题
离散优化Discrete Optimization问题是目标函数的输入变量为离散变量比如为整数或有限集合中的元素。离散优化问题的求解一般都比较困难优化算法的复杂度都比较高。离散优化问题主要有两个分支
组合优化Combinatorial Optimization其目标是从一个有限集合中找出使得目标函数最优的元素。在一般的组合优化问题中集合中的元素之间存在一定的关联可以表示为图结构。典型的组合优化问题有旅行商问题TSP又称最短路径问题、背包问题Knapsack ProblemKP、最小费用最大流Minimum Cost Maximum FlowMCMF等。很多机器学习问题都是组合优化问题比如特征选择、聚类问题、超参数优化问题以及结构化学习Structured Learning中标签预测问题等。通常小规模的组合优化问题可以采用精确求解算法进行最优解的计算而大规模的组合优化问题一般采用启发式算法进行求解。整数规划Integer Programming输入变量为整数。一般常见的整数规划问题为整数线性规划Integer Linear ProgrammingILP。整数线性规划的一种最直接的求解方法是1去掉输入必须为整数的限制将原问题转换为一般的线性规划问题这个线性规划问题为原问题的松弛问题2求得相应松弛问题的解3把松弛问题的解四舍五入到最接近的整数。但是这种方法得到的解一般都不是最优的因此原问题的最优解不一定在松弛问题最优解的附近但可能可以为问题求解提供一个较好的可行解因为这种方法得到的解也不一定满足约束条件。所以常用小规模整数规划问题的求解方法是采用精确求解算法而对于大规模的整数规划问题一般采用启发式算法求解虽然启发式算法不能求得整数规划的最优解但是却能在短时间通常多项式时间内给出一个较好的可行解。
连续优化问题
连续优化Continuous Optimization问题是目标函数的输入变量为连续变量。在连续优化问题中根据是否有变量的约束条件可以将此类优化问题分为无约束优化问题和约束优化问题
无约束优化问题Unconstrained Optimization中变量 x 无任何约束其可行域为整个实数域。针对连续优化中的无约束问题通常的求解方法时梯度下降法例如随机梯度下降算法、带动量的随机梯度下降算法和Adam算法等等。约束优化问题Constrained Optimization中变量 x 需要满足一些等式或不等式的约束。约束优化问题最经典的算法是使用拉格朗日乘数法来进行求解。这种方法将一个有 n 个变量与 k 个约束条件的最优化问题转换为一个有 ( n k ) 个变量的方程组的极值问题其变量不受任何约束。
此外根据目标函数和约束条件是否线性可以将此类优化问题分为线性优化问题和非线性优化问题
如果目标函数和所有的约束函数都为线性函数则该问题为线性规划问题Linear ProgrammingLP。如果目标函数或任何一个约束函数为非线性函数则该问题为非线性规划问题Nonlinear ProgrammingNLP。在非线性优化问题中有一类比较特殊的问题是凸优化问题Convex Programming。凸优化问题是一种特殊的约束优化问题需满足目标函数为凸函数约束条件为凸集即对于集合中任意两点它们的连线全部位于在集合内部。在凸优化中如果目标函数是关于变量的二次函数那此类问题称为二次规划问题Quadratic programmingQP。
求解
对于最优化问题的求解可谓是一门艺术无数数学家将实际问题抽象成一个数学问题并对此提出了各种各样的求解算法那么最常见、经典的求解方法主要有以下几种精确算法、近似算法和启发式算法。
精确算法是指能够求出问题最优解的算法。当问题的规模较小时精确算法能够在可接受的时间内得到最优解当问题的规模较大时精确算法一方面可以提供问题的可行解另一方面可以为启发式算法提供初始解以便搜索到更好的解。精确算法有分支定界法、割平面法、动态规划法等。近似算法是指用近似方法来解决优化问题的算法通常与 NP-hard 问题相关由于无法有效地在多项式时间内精确地求得最优解所以考虑在多项式时间内求得一个有质量保证的近似解。近似算法包括贪婪算法、局部搜索算法、松弛算法等。启发式算法是一种基于直观或经验构造的算法能在可接受的计算成本内尽可能地逼近最优解得到一个相对优解但无法预计所得解与最优解的近似程度。启发式算法可分为传统启发式算法和元启发式算法传统启发式算法包括构造性方法、局部搜索算法、松弛方法和解空间缩减算法等。元启发式算法包括禁忌搜索算法、模拟退火算法、遗传算法、蚁群算法、粒子群算法和人工神经网络等。
相关最优化问题的求解软件或算法库有lingo、Matlab、PythonGurobi、pulp等等。
