文档介绍：关于投影梯度法
第1页，讲稿共41张，创作于星期一
求解算法分类
(1)将这种约束问题转化为无约束问题进行求解
(因无约束问题已有较好的求解方法比如BFGS,DFP等)
(2)直接从这种约束问题出发来求解
数学模型
m x1,x2,x3≥0
求出在点x(0)=(1,1,0)T处的一个可行方向。
这个问题的不等式约束有四个，从而可写出
在x(0)处可看出它的有效约束：A’=(0,0,1),b’=(0)
解不等式：A’d≥0,Ed=0
0·d1+ 0·d2+ 1·d3 ≥0,1·d1+1·d2+1·d3=0
比如d=(1,-1,0)T就是一个容许方向(但未必是下降方向！)
解
第12页，讲稿共41张，创作于星期一
例(自作) 考虑问题min x12+x1x2+2x22-6x1-2x2-12x3
. x1+x2+x3=2
-x1+2x2 ≤3
x1,x2,x3≥0
求出在点x(0)=(1,1,0)T处的一个下降可行方向。
解 A’d≥0,Ed=0得到的d即为一个容许方向
0·d1+ 0·d2+ 1·d3 ≥0, 1·d1+1·d2+1·d3=0
再结合下降的要求 ▽f(x(0))Td<0即(-3,3,-12) d<0
即 -3d1+3d2-12d3<0
从而由d3 ≥0,
d1+d2+d3=0
-d1+d2-4d3<0
解出一个d即为下降可行方向
比如(1,-1,0)T
第13页，讲稿共41张，创作于星期一
下降容许方向的进一步确定
在所有的可行方向中
x
-
找一个使得▽f( )Td最小的方向
(即:使得f下降最多)
x
-
意即：min ▽f( )Td
. A’d≥0
Ed=0
(1)求一个下降容许方向就转化为一个子问题的求解，
子问题是一个线性规划问题，可调用单纯形法求解.
(2)这个子问题得到的将是一个无界解,需对这个问题加以修正.
则td也满足此三式,t可无穷大
x
-
d满足▽f( )Td<0,A’d≥0,Ed=0
第14页，讲稿共41张，创作于星期一
由于我们关心的是确定d的方向，而不是具体长度
所以，我们在上述问题中可加上对方向d的长度的限制
从而得子问题
x
-
min▽f( )Td
. A’d≥0
Ed=0
-1≤dj≤1，j=1:n
因d=0是容许解且▽f( )T0=0
x
-
此子问题最优值必非正( )
（*）
第15页，讲稿共41张，创作于星期一
直线搜索
从x(k)出发，确定新的迭代点x(k+1) 。使得：
(1) 在下降容许方向d上目标函数值下降
(2) 新的点x(k+1)是一个容许点.
这也就是这样的一个一元问题：min f(x(k)+td)
. A(x(k)+td) ≥b
E(x(k)+td)=e
事实上这个问题还可以简化：
首先，由x(k)是容许点，d是容许方向,知:E(x(k)+td)=e恒成立。
故上述问题中的第二组等式约束可以直接去掉。
min f(x(k)+td)
. A(x(k)+td) ≥b
其次：对现在所得的这个一元问题还可简化.
不等式约束分为两部分：A’(x(k)+td) ≥b’,A”(x(k)+td) ≥b”
由A’d≥0,A’x(k)=b’知第一部分也可以直接去掉。
从而得一个约束已大大减少的一元问题
min f(x(k)+td)
. A”(x(k)+td) ≥b”
分析： A”(x(k)+td) ≥b”,即A”x(k)-b” ≥-tA”d
设A”x(k)-b”=u=(u1,…,u)T,A”d=v=(v1,…,v)T,从而要u ≥-tv
当v≥0时，显然问题变成min f(x（k）+td),对t无要求；
当v ≥0不成立即v有分量<0,而为使ui ≥-tvi,i=1: 都成立 ，
就必须 t≤uj/(-vj),j{j|vj<0}
也就是:令