this.p={  m:2,
b:2,
loftPermalink:'',
id:'fks_087066084083086074082084095068072084084066087087095066082',
blogTitle:'有两个约束条件的条件极值',
blogAbstract:'
本博文推导三元函数在两个约束条件下取得极值的必要条件。
我们使用的教材(同济大学《高等数学》第六版)给出了有两个约束条件的条件极值的拉格朗日乘数法，但是没有给出推导。现将推导补充于下，供大家参考。
',
blogTag:'',
blogUrl:'blog/static/251319162012230105322207',
isPublished:1,
istop:false,
type:0,
modifyTime:1333367824564,
publishTime:1333076077913,
permalink:'blog/static/251319162012230105322207',
commentCount:0,
mainCommentCount:0,
recommendCount:0,
bsrk:-100,
publisherId:0,
recomBlogHome:false,
currentRecomBlog:false,
attachmentsFileIds:[],
vote:{},
groupInfo:{},
friendstatus:'none',
followstatus:'unFollow',
pubSucc:'',
visitorProvince:'',
visitorCity:'',
visitorNewUser:false,
postAddInfo:{},
mset:'000',
mcon:'',
srk:-100,
remindgoodnightblog:false,
isBlackVisitor:false,
isShowYodaoAd:true,
hostIntro:'',
hmcon:'1',
selfRecomBlogCount:'0',
lofter_single:''
}
{list a as x}
{if !!x}
{if x.visitorName==visitor.userName}
{else}
{/if}
{if x.moveFrom=='wap'}
{elseif x.moveFrom=='iphone'}
{elseif x.moveFrom=='android'}
{elseif x.moveFrom=='mobile'}
{/if}
${fn(x.visitorNickname,8)|escape}
{/if}
{/list}
{if !!a}
    
${fn(a.nickname,8)|escape}
${a.selfIntro|escape}{if great260}${suplement}{/if}
{/if}
{list a as x}
{if !!x}
推荐过这篇日志的人：
{list a as x}
{if !!x}
{if !!b&&b.length>0}
他们还推荐了：
{list b as y}
{if !!y}
{/if}
{list a as x}
{if !!x}
{list a as x}
{if !!x}
{list a as x}
{if !!x}
{list a as x}
{if x_index>4}{break}{/if}
{if !!x}
${fn1(x.title,60)|escape}${fn2(x.publishTime,'yyyy-MM-dd HH:mm:ss')}
{/if}
{/list}
{list a as x}
{if !!x}
{if !!(blogDetail.preBlogPermalink)}
网易新闻
${headlines.title|escape}
{if defined('newslist')&&newslist.length>0}
{list newslist as x}
{if x_index>7}{break}{/if}
被推荐日志
最新日志
该作者的其他文章
博主推荐
随机阅读
首页推荐
{list a as x}
{if !!x}
${x.nickName|escape}  投票给
{var first_option = true;}
{list x.voteDetailList as voteToOption}
{if voteToOption==1}
{if first_option==false},{/if}  “${b[voteToOption_index]}”
{/if}
{/list}
{if (x.role!="-1") },“我是${c[x.role]}”  {/if}
${fn1(x.voteTime)}
{if x.userName==''}{/if}
{/if}
{/list}

约束极值问题的定义及优化方法

带有约束条件的极值问题称为约束极值问题，也叫规划问题。

求解约束极值问题要比求解无约束极值问题困难得多。为了简化其优化工作，可采用下面两种方法:

1.将约束问题转化为无约束问题；

2.将非线性规划问题转化为线性规划问题。

什么样的目标函数可以用二次规划求解呢？

1.非线性规划的目标函数为自变量x的二次函数

2.约束条件是线性的


二次规划数学模型



其中，H是实对称矩阵；f,b,beq,lb,ub是列向量；A,Aeq是相应维数的矩阵。

Matlab中求解二次规划的命令：

[x,fval]=quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options)

返回值x是决策向量x的值，返回值fval是目标函数在x处的值。

二次规划求解的例子

Example：



编写程序如下：

H=[4,-4;-4,8];

f=[-6;-3];

A=[1,1;4,1];

b=[3,9];

[x,fval]=quadprog(H,f,A,b,[ ],[ ],zeros(2,1))

这里x1和x2有下界，没有上界，所以根据第三个约束，lb为两行一列的0矩阵，上界为空。

求解得：x1=1.9500，x2=1.0500，minf（x）=-11.0250

华电北风吹 

最后修改日期 2015/11/7

无约束极值问题可以表述为 
minf(X),X∈Rn

对于这类问题的求解一般要用到迭代法。迭代法可分为两大类。一类是要用到函数一阶导数或二阶导数的解析法；另一类是迭代过程中只用到函数值的直接法。常见的解析法有梯度下降法，共轭梯度法，变尺度法。常见的直接法有步长加速法。

一、梯度下降法 

假设Xk表示极小值点的第k次迭代。求解第k+1次迭代过程为 
Xk+1=Xk+λPk
Pk表示函数f(X)在点Xk处的负梯度。λ是步长。 

其中，步长可以设定为一个常数值。当然，也可以通过一维搜索求解使得函数f(X)在点Xk沿方向Pk下降最多的步长(最速下降法)。

二、共轭梯度法

三、变尺度法

四、步长加速法

动机

非数学专业，只是用得到，所以学一下。



问题描述

首先来看一下非线性最优化问题，一般有这么几类。



第一类： 无约束最优化问题

找到一个合适的x，是的f(x)最小： 

minxf(x)
没有任何约束的最优化问题，这个一般解法有 梯度下降法、牛顿法、拟牛顿法等。



第二类： 有等式约束的非线性

minxf(x)subject to hi(x)=0i∈[1,n]
第三类： 有等式和不等式约束的非线性问题

minxf(x)subject to hi(x)=0gj(x)<=0i∈[1,m],j∈[1,n]
上面的式子是说， 在满足m个等式 即 hi(x)=0 和 n个不等式 gj(x)<=0 的条件下求f(x)的最小值。



拉格朗日乘子法

对于第二类问题，可以转化为一下问题



minF(x)=min[f(x)+∑i=1nλihi(x)]
λi 为拉格朗日乘子。 

令 ∂F(x)/∂x=0 , ∂F(x)/∂λ=0 ,该最优化问题即可的解。



拉格朗日乘子法原理分析

上面公式中的x是一个向量，多维的数据难以绘图和理解，这里以二维为例。有这样的最优化问题:



minz=minf(x,y)s.t.g(x,y)=c
如果将 z=f(x,y)绘制成一个三维图像，可以想象必定有波峰有波谷，如果想用二维图像绘制这个函数，只能以等高线的形式（想象一下等高线地形图），下图给出了等高线图。因为极值点必须是一个可行解，即必须满足g(x,y)=c 这个条件，所以极值点处的等高线必定和g(x,y)=c 相较于一点。 假设两条线不相切，那么必定有另外一条等高线与之相切。考虑相切的情况，f(x,y)取得极值，且满足等式条件。

在相切时，其梯度方向平行，即



▽[f(x,y)+λ(g(x,y)−c)]=0λ≠0
给出一个新的函数 F(x,y)=▽[f(x,y)+λ(g(x,y)−c)]=0

在求其极值的时候，令 ▽F(x,y)=0，即可的解。



# 

 第三类与KKT条件

在满足KKT条件时，可以将带有不等式的非线性最优化问题转化为无约束的最优化问题。



首先将原目标公式和等式不等式合为一个公式



F(x,λ,μ)=f(x)+∑iλihi(x)+∑jμjgj(x)


并需满足以下条件

（1） ∂F(x,λ,μ)/∂x=0  这个条件是计算最优化问题的核心。 使用梯度下降法可以迭代求解。

（2） λi≠0 这个条件保证等式约束是成立的，如果该值为零，相当于丢失了约束条件。 

（3） μj>=0 ,原条件中 gj(x)<=0 ,公式加上一个小于等于0的数，符合最小化的方向。如果加一个正数，则与最小化方向相反，所以 这个条件保证了  μjgj(x) 小于等于0 。 

（4） ujgj(x)=0 ,该条件表明只有在该项取最大值时，整个公式取极小值才是真正的极小值。 这个式子最大为0， 所以要求其为0。

进一步思考， 这两项相乘为0，那么至少有一项为0， 如果是 uj 为0 ，说明这个条件并未生效，就是说整个函数的极小值并不在这个条件的边界上。  如果gj(x)=0 极小值说明在这个条件的边界上。

（5）原本的约束条件 gj(x)<=0 , hi(x)=0



证明

证明见 参考文献[1]

参考文献

[1] http://www.cnblogs.com/zhangchaoyang/articles/2726873.html 

[2] http://blog.csdn.net/xianlingmao/article/details/7919597 

[3] https://zh.wikipedia.org/wiki/%E6%8B%89%E6%A0%BC%E6%9C%97%E6%97%A5%E4%B9%98%E6%95%B0