❶ 最优化问题求解方法
在求解最优化问题中,拉格朗日乘子法(Lagrange Multiplier)和KKT(Karush Kuhn Tucker)条件是两种最常用的方法。在有等式约束时使用拉格朗日乘子法,在有不等约束时使用KKT条件。
我们这里提到的最优化问题通常是指对于给定的某一函数,求其在指定作用域上的全局最小值(因为最小值与最大值可以很容易转化,即最大值问题可以转化成最小值问题)。提到KKT条件一般会附带的提一下拉格朗日乘子。对学过高等数学的人来说比较拉格朗日乘子应该会有些印象。二者均是求解最优化问题的方法,不同之处在于应用的情形不同。
一般情况下,最优化问题会碰到一下三种情况:
这是最简单的情况,解决方法通常是函数对变量求导,令求导函数等于0的点可能是极值点。将结果带回原函数进行验证即可。
设目标函数为f(x),约束条件为h_k(x),形如:
s.t. 表示subject to ,“受限于”的意思,l表示有l个约束条件。
则解决方法是消元法或者拉格朗日法。消元法比较简单不在赘述,这里主要讲拉格朗日法,因为后面提到的KKT条件是对拉格朗日乘子法的一种泛化。
作为一种优化算法,拉格朗日乘子法主要用于解决约束优化问题,它的基本思想就是通过引入拉格朗日乘子来将含有n个变量和k个约束条件的约束优化问题转化为含有(n+k)个变量的无约束优化问题。拉格朗日乘子背后的数学意义是其为约束方程梯度线性组合中每个向量的系数。
如何将一个含有n个变量和k个约束条件的约束优化问题转化为含有(n+k)个变量的无约束优化问题?拉格朗日乘数法从数学意义入手,通过引入拉格朗日乘子建立极值条件,对n个变量分别求偏导对应了n个方程,然后加上k个约束条件(对应k个拉格朗日乘子)一起构成包含了(n+k)变量的(n+k)个方程的方程组问题,这样就能根据求方程组的方法对其进行求解。
首先定义拉格朗日函数F(x):
然后解变量的偏导方程:
我们上述讨论的问题均为等式约束优化问题,但等式约束并不足以描述人们面临的问题,不等式约束比等式约束更为常见,大部分实际问题的约束都是不超过多少时间,不超过多少人力,不超过多少成本等等。所以有几个科学家拓展了拉格朗日乘数法,增加了KKT条件之后便可以用拉格朗日乘数法来求解不等式约束的优化问题了。
设目标函数f(x),不等式约束为g(x),有的教程还会添加上等式约束条件h(x)。此时的约束优化问题描述如下:
则我们定义不等式约束下的拉格朗日函数L,则L表达式为:
其中f(x)是原目标函数,hj(x)是第j个等式约束条件,λj是对应的约束系数,gk是不等式约束,uk是对应的约束系数。
常用的方法是KKT条件,同样地,把所有的不等式约束、等式约束和目标函数全部写为一个式子L(a, b, x)= f(x) + a g(x)+b h(x),
首先,我们先介绍一下什么是KKT条件。
KKT条件是指在满足一些有规则的条件下, 一个非线性规划(Nonlinear Programming)问题能有最优化解法的一个必要和充分条件. 这是一个广义化拉格朗日乘数的成果. 一般地, 一个最优化数学模型的列标准形式参考开头的式子, 所谓 Karush-Kuhn-Tucker 最优化条件,就是指上式的最优点x∗必须满足下面的条件:
1). 约束条件满足gi(x∗)≤0,i=1,2,…,p, 以及,hj(x∗)=0,j=1,2,…,q
2). ∇f(x∗)+∑i=1μi∇gi(x∗)+∑j=1λj∇hj(x∗)=0, 其中∇为梯度算子;
3). λj≠0且不等式约束条件满足μi≥0,μigi(x∗)=0,i=1,2,…,p。
❷ 最优化方法
最优化方法,是指解决最优化问题的方法。
所谓最优化问题,指在某些约束条件下,决定某些可选择的变量应该取何值,使所选定的目标函数达到最优的问题。即运用最新科技手段和处理方法,使系统达到总体最优,从而为系统提出设计、施工、管理、运行的最优方案。
由于实际的需要和计算技术的进步,最优化方法的研究发展迅速。
最优化方法(也称做运筹学方法)是近几十年形成的,它主要运用数学方法研究各种系统的优化途径及方案,为决策者提供科学决策的依据。
最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。最优化方法的目的在于针对所研究的系统,求得一个合理运用人力、物力和财力的最佳方案,发挥和提高系统的效能及效益,最终达到系统的最优目标。
实践表明,随着科学技术的日益进步和生产经营的日益发展,最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法,被人们广泛地应用到公共管理、经济管理、工程建设、国防等各个领域,发挥着越来越重要的作用。
将介绍最优化方法的研究对象、特点,以及最胡乱弯优化方法模型的建立和模型的分析、求解、应用。主要是线性规划问题陪芹的模型裤闷、求解(线性规划问题的单纯形解法)及其应用――运输问题;以及动态规划的模型、求解、应用――资源分配问题。
最优化方法:
1、微分学中求极值
2、无约束最优化问题
3、常用微分公式
4、凸集与凸函数
5、等式约束最优化问题
6、不等式约束最优化问题
7、变分学中求极值
❸ 用优化方法解决实际问题的一般步骤是什么
用最优化方法解决实际问题,一般可经过下列步骤:
①提出最优化问题,收集有关数据和资料;
②建立最优化问题的数学模型,确定变量,列出目标函数和约束条件;
③分析模型,选择合适的最优化方法;
④求解,一般通过编制程序,用计算机求最优解;
⑤最优解的检验和实施。上述 5个步骤中的工作相互支持和相互制约,在实践中常常是反复交叉进行。
❹ 数学建模最优化方法
1、多目标优化问题。
对于教师和学生的满意可以用几个关键性的指标,如衡量老师的工作效率和工作强度及往返强度等,如定义
效率w=教师的实际上课时间/(教师坐班车时间+上课时间+在学校逗留时间)。
然后教师的满意度S1为几个关键性指标的加权平均。注意一些无量纲量和有量纲量的加权平均的归一化问题。
对于学生可以定义每门课周频次,每天上课频次等等
对于学校满意,可以定义班车出动次数,这个指标和教师的某一个指标是联动的,教室和多媒体使用周期频次和使用时长等等。
2、根据第一问的模型按照数据进行求解
3、教师、学生和学校的满意度作为指标
4、根据结果提出合理化建议
❺ 解决经济分析的最优化问题的基本步骤是什么
从数学角度看,最优化问题可以分为无约束最优化和约束最优化。所谓无约束最优化问题是比较简单的微分问题,可用微分求解。
管理决策问题往往也就是最优化问题,而比较常用和方便的方法就是边际分析法。
所谓“无约束”,即产品产量、资源投入量、价格和广告费的支出等都不受限制。在这种情况下,最优化的原则是:边际收入等于边际成本,也就是边际利润为零时,利润最大,此时的业务量为最优业务量。管理决策中的诸多最优化问题,比如投入要素之间如何组合才能使成本最低;企业的产量多大,才能实现利润最大,当因变量为自变量的连续函数时,经济学与数学意义是统一的,可用边际分析法解决;而在处理离散数列的最优化问题时则可以用统计的方法先将离散数列拟合成连续函数,求得最优点,然后在原离散数列中找到离拟合曲线最优点最近的前后两点,比较其值及其投入量,既而求得最优点。
有约束条件的最优化包括一个或几个货币、时间、生产能力或其他方面的限制,当存在不等式约束条件时,可以采用线性规划。大多数情况下,管理者知道某些约束是连在一起的,即它们是同样的约束条件,可以采用拉格朗日乘数法解决这些问题。
从数学上比较一般的观点来看,所谓最优化问题可以概括为一种数学模型:结合一个函数F(x)以及自变量应满足一定的条件,求X 为怎样的值时,F(x)取得其最大值或最小值。通常,称F(x)为目标函数,X 应满足的条件为约束条件。求目标函数F(x)
在约束条件X 下的最大值或最小值问题,就是一般最优问题的数学模型,可以用数学符号简洁地表示为MinF(x)或MaxF(x)。解决最优化问题地关键步骤是如何把实际问题,抽象成数学模型,也就是构造出目标函数与约束条件,一旦这一步完成,对于简单问题,可借助图形或微积分来解决,遇到比较复杂地课题,可利用现有地数学软件或最优化软件,比如Matlab,Mathematica,Lindo,Lingo 等来计算。下面举例说明如何计算有约束条件地最优化问题。
例设某种产品的产量是劳动力x和原料y(t)的函数,f(x),y=60X 3y 2,假定每单位劳动力费用100元,每单位原料费用200元,现有2万元资金用于生产,为了得到最多的产品,应如何安排劳动力和原料。
解:依题意,可归结为求函数f(x,y)=60x 3y 2在约束条件100x+200y=20000下的最大值,故可用拉格朗日乘数法求解。
❻ 几种常用最优化方法
学习和工作中遇到的大多问题都可以建模成一种最优化模型进行求解,比如我们现在学习的机器学习算法,大部分的机器学习算法的本质都是建立优化模型,通过最优化方法对目标函数(或损失函数)进行优化,从而训练出最好的模型。常见的优化方法(optimization)有梯度下降法、牛顿法和拟牛顿法、共轭梯度法等等。
1. 梯度下降法(Gradient Descent)
梯度下降法是最早最简单,也是最为常用的最优化方法。梯度下降法实现简单,当目标函数是凸函数时,梯度下降法的解是全局解。一般情况下,其解不保证是全局最优解,梯度下降法的速度也未必是最快的。 梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向,因为该方向为当前位置的最快下降方向,所以也被称为是”最速下降法“。最速下降法越接近目标值,步长越小,前进越慢。
梯度下降 法的缺点:
(1)靠近极小值时收敛速度减慢;
(2)直线搜索时可能会产生一些问题;
(3)可能会“之字形”地下降。
在机器学习中,基于基本的梯度下降法发展了两种梯度下降方法,分别为随机梯度下降法和批量梯度下降法。
比如对一个线性回归(Linear Logistics)模型,假设下面的h(x)是要拟合的函数,J( )为损失函数, 是参数,要迭代求解的值,求解出来了那最终要拟合的函数h( )就出来了。其中m是训练集的样本个数,n是特征的个数。
1)批量梯度下降法(Batch Gradient Descent,BGD)
(1)将J( )对 求偏导,得到每个theta对应的的梯度:
(2)由于是要最小化风险函数,所以按每个参数 的梯度负方向,来更新每个 :
(3)从上面公式可以注意到,它得到的是一个全局最优解,但是每迭代一步,都要用到训练集所有的数据,如果m很大,那么可想而知这种方法的迭代速度会相当的慢。所以,这就引入了另外一种方法——随机梯度下降。
对于批量梯度下降法,样本个数m,x为n维向量,一次迭代需要把m个样本全部带入计算,迭代一次计算量为m*n2。
2)随机梯度下降(Stochastic Gradient Descent,SGD)
(1)上面的风险函数可以写成如下这种形式,损失函数对应的是训练集中每个样本的粒度,而上面批量梯度下降对应的是所有的训练样本:
(2)每个样本的损失函数,对 求偏导得到对应梯度,来更新 :
(3)随机梯度下降是通过每个样本来迭代更新一次,如果样本量很大的情况(例如几十万),那么可能只用其中几万条或者几千条的样本,就已经将
迭代到最优解了,对比上面的批量梯度下降,迭代一次需要用到十几万训练样本,一次迭代不可能最优,如果迭代10次的话就需要遍历训练样本10次。但是,SGD伴随的一个问题是噪音较BGD要多,使得SGD并不是每次迭代都向着整体最优化方向。
随机梯度下降每次迭代只使用一个样本,迭代一次计算量为n2,当样本个数m很大的时候,随机梯度下降迭代一次的速度要远高于批量梯度下降方法。 两者的关系可以这样理解:随机梯度下降方法以损失很小的一部分精确度和增加一定数量的迭代次数为代价,换取了总体的优化效率的提升。增加的迭代次数远远小于样本的数量。
对批量梯度下降法和随机梯度下降法的总结:
批量梯度下降---最小化所有训练样本的损失函数,使得最终求解的是全局的最优解,即求解的参数是使得风险函数最小,但是对于大规模样本问题效率低下。
随机梯度下降---最小化每条样本的损失函数,虽然不是每次迭代得到的损失函数都向着全局最优方向, 但是大的整体的方向是向全局最优解的,最终的结果往往是在全局最优解附近,适用于大规模训练样本情况。
2. 牛顿法和拟牛顿法(Newton's method & Quasi-Newton Methods)
1)牛顿法(Newton's method)
牛顿法是一种在实数域和复数域上近似求解方程的方法。方法使用函数 f ( x )的泰勒级数的前面几项来寻找方程 f ( x ) = 0的根。牛顿法最大的特点就在于它的收敛速度很快。
具体步骤:
首先,选择一个接近函数 f ( x )零点的x0,计算相应的 f ( x 0)和切线斜率 f ' ( x 0)(这里 f ' 表示函数 f 的导数)。然后我们计算穿过点( x 0, f ( x 0))并且斜率为 f '( x 0)的直线和 x 轴的交点的 x 坐标,也就是求如下方程的解:
我们将新求得的点的 x 坐标命名为 x 1,通常 x 1会比 x 0更接近方程 f ( x ) = 0的解。因此我们现在可以利用 x 1开始下一轮迭代。迭代公式可化简为如下所示:
已经证明,如果 f '是连续的,并且待求的零点 x 是孤立的,那么在零点 x 周围存在一个区域,只要初始值 x 0位于这个邻近区域内,那么牛顿法必定收敛。 并且,如果 f ' ( x )不为0, 那么牛顿法将具有平方收敛的性能. 粗略的说,这意味着每迭代一次,牛顿法结果的有效数字将增加一倍。下图为一个牛顿法执行过程的例子。
由于牛顿法是基于当前位置的切线来确定下一次的位置,所以牛顿法又被很形象地称为是"切线法"。
关于牛顿法和梯度下降法的效率对比:
从本质上去看,牛顿法是二阶收敛,梯度下降是一阶收敛,所以牛顿法就更快。如果更通俗地说的话,比如你想找一条最短的路径走到一个盆地的最底部,梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步,牛顿法在选择方向时,不仅会考虑坡度是否够大,还会考虑你走了一步之后,坡度是否会变得更大。所以,可以说牛顿法比梯度下降法看得更远一点,能更快地走到最底部。(牛顿法目光更加长远,所以少走弯路;相对而言,梯度下降法只考虑了局部的最优,没有全局思想。)
根据wiki上的解释,从几何上说,牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面,而梯度下降法是用一个平面去拟合当前的局部曲面,通常情况下,二次曲面的拟合会比平面更好,所以牛顿法选择的下降路径会更符合真实的最优下降路径。
注:红色的牛顿法的迭代路径,绿色的是梯度下降法的迭代路径。
牛顿法的优缺点总结:
优点:二阶收敛,收敛速度快;
缺点:牛顿法是一种迭代算法,每一步都需要求解目标函数的Hessian矩阵的逆矩阵,计算比较复杂。
2)拟牛顿法(Quasi-Newton Methods)
拟牛顿法是求解非线性优化问题最有效的方法之一,于20世纪50年代由美国Argonne国家实验室的物理学家W.C.Davidon所提出来。Davidon设计的这种算法在当时看来是非线性优化领域最具创造性的发明之一。不久R. Fletcher和M. J. D. Powell证实了这种新的算法远比其他方法快速和可靠,使得非线性优化这门学科在一夜之间突飞猛进。
拟牛顿法的本质思想是改善牛顿法每次需要求解复杂的Hessian矩阵的逆矩阵的缺陷,它使用正定矩阵来近似Hessian矩阵的逆,从而简化了运算的复杂度。 拟牛顿法和最速下降法一样只要求每一步迭代时知道目标函数的梯度。通过测量梯度的变化,构造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优于最速下降法,尤其对于困难的问题。另外,因为拟牛顿法不需要二阶导数的信息,所以有时比牛顿法更为有效。如今,优化软件中包含了大量的拟牛顿算法用来解决无约束,约束,和大规模的优化问题。
具体步骤:
拟牛顿法的基本思想如下。首先构造目标函数在当前迭代xk的二次模型:
这里Bk是一个对称正定矩阵,于是我们取这个二次模型的最优解作为搜索方向,并且得到新的迭代点:
其中我们要求步长ak 满足Wolfe条件。这样的迭代与牛顿法类似,区别就在于用近似的Hesse矩阵Bk 代替真实的Hesse矩阵。所以拟牛顿法最关键的地方就是每一步迭代中矩阵Bk的更新。现在假设得到一个新的迭代xk+1,并得到一个新的二次模型:
我们尽可能地利用上一步的信息来选取Bk。具体地,我们要求
从而得到
这个公式被称为割线方程。常用的拟牛顿法有DFP算法和BFGS算法。
原文链接: [Math] 常见的几种最优化方法 - Poll的笔记 - 博客园
❼ 数学优化问题(最优化问题)
数学优化(Mathematical Optimization)问题,也叫最优化问题,是指在一定约束条件下,求解一个目标函数的最大值(或最小值)问题。
数学优化问题的定义为:给定一个目标函数(也叫代价函数) f : A → R ,寻找一个变量(也叫参数) x ∗ ∈ D ,使得对于所有 D 中的 x , f(x ∗ ) ≤ f(x) (最小化);或者 f(x ∗ ) ≥ f(x) (最大化),其中 D 为变量 x 的约束集,也叫可行域; D 中的变量被称为是可行解。
根据输入变量 x 的值域是否为实数域,数学优化问题可以分为离散优化问题和连续优化问题。
离散优化(Discrete Optimization)问题是目标函数的输入变量为离散变量,比如为整数或有限集合中的元素。连续优化(Continuous Optimization)问题是目标函数的输入变量为连续变量 x ∈ R d ,即目标函数为实函数。离散优化问题主要有两个分支:
离散优化问题的求解一般都比较困难,优化算法的复杂度都比较高。后面的内容主要以连续优化为主。
在连续优化问题中,根据是否有变量的约束条件,可以将优化问题分为无约束优化问题和约束优化问题。
无约束优化问题(Unconstrained Optimization) 的可行域为整个实数域 D = R d ,可以写为
其中 x ∈ R d 为输入变量, f : R d → R 为目标函数。
约束优化问题(Constrained Optimization) 中变量 x 需要满足一些等式或不等式的约束。约束优化问题通常使用拉格朗日乘数法来进行求解。
如果目标函数和所有的约束函数都为线性函数,则该问题为 线性规划问题(Linear Programming) 。相反,如果目标函数或任何一个约束函数为非线性函数,则该问题为 非线性规划问题(Nonlinear Programming) 。
在非线性优化问题中,有一类比较特殊的问题是 凸优化问题(Convex Programming) 。在凸优化问题中,变量 x 的可行域为凸集,即对于集合中任意两点,它们的连线全部位于在集合内部。目标函数 f 也必须为凸函数,即满足
凸优化问题是一种特殊的约束优化问题,需满足目标函数为凸函数,并且等式约束函数为线性函数,不等式约束函数为凹函数。
优化问题 一般都是通过 迭代 的方式来求解:通过猜测一个初始的估计 x 0 ,然后不断迭代产生新的估计 x 1 , x 2 , · · · x t ,希望 x t 最终收敛到期望的最优解 x ∗旅散纳 。一个好的优化算法应该是在 一定的时间或空间复杂度下能够快速准确地找到最优解。同时,好的优化算法受初始掘培猜测点的影响较小,通过迭代能稳定地找到最优解 x ∗ 的邻域,然后迅速收敛于 x ∗ 。
优化算法中常用的迭代方法有 线性搜索和置信域方法 等。线性搜索的策略是寻找方向和步长,具体算法有梯度下降法、牛顿拆没法、共轭梯度法等。
对于很多非线性优化问题,会存在若干个局部的极小值。局部最小值,或局部最优解 x ∗ 定义为:存在一个δ > 0,对于所有的满足|| x − x∗|| ≤ δ 的 x ,公式 f(x ∗ ) ≤ f(x) 成立。也就是说,在 x ∗ 的附近区域内,所有的函数值都大于或者等于 f(x ∗ ) 。对于所有的 x ∈ A ,都有 f(x∗) ≤ f(x) 成立,则 x ∗ 为全局最小值,或全局最优解。一般的,求局部最优解是容易的,但很难保证其为全局最优解。 对于线性规划或凸优化问题,局部最优解就是全局最优解 。