分 数: ___________
任课教师签字:___________
华北电力大学研究生结课作业
学 年 学 期:2013-2014第二学期
课 程 名 称:优化理论和最优控制 学 生 姓 名:
学 号:
提 交 时 间:2014年4月26日
《优化理论和最优控制》结课总结
摘 要: 最优控制理论是现代控制理论的核心,控制理论的发展来源于控制对象的要求。尽50年来,科学技术的迅速发展,对许多被控对象,如宇宙飞船、导弹、卫星、和现代工业设备的生产过程等的性能提出了更高的要求,在许多情况下要求系统的某种性能指标为最优。这就要求人们对控制问题都必须从最优控制的角度去进行研究分析和设计。最优控制理论研究的主要问题是:根据已建立的被控对象的时域数学模型或频域数学模型,选择一个容许的控制律,使得被控对象按预定要求运行,并使某一性能指标达到最优值[1]。
关键字:最优控制理论,现代控制理论,时域数学模型,频域数学模型,控制率
Abstract: The Optimal Control Theory is the core of the Modern Control Theory,the development of control theory comes from the requires of the controlled objects.During the 50 years, the rapid development of the scientific technology puts more stricter requires forward to mang controlled objects,such as the spacecraft,the guide missile,the satellite,the productive process of modern industrial facilities,and so on,and requests some performance indexes that will be best in mang cases.To the control problem,it requests people to research ,analyse,and devise from the point of view of the Optimal Control Theory. There are mang major problems of the Optimal Control Theory studying,such as the building the time domain’s model or the frenquency domain’s model according to the controlled objects,controlling a control law with admitting, making the controlled objects to work according to the scheduled requires, and making the performance index to reseach to a best optimal value.
Keywords: The Optimal Control Theroy, The Modern Control Theroy, The
Time Domaint’s Model, The Frequency domain’s Model,The Control Law 0 引言
最优控制理论的形成和发展和整个现代自动控制理论的形成和发展十分不开的。在20世纪50年代初期,就有人开始发表从工程观点研究最短时间控制问题的文章,尽管其最优性的证明多半借助于几何图形,仅带有启发性质,但毕竟为发展现代控制理论提供了第一批实际模型。由于最优控制问题引人注目的严格表述形式,特别是空间技术的迫切需求,从而吸引了大批科学家的密切注意。经典变分理论只能解决一类简单的最优控制问题,因为它只对无约束或开集性约束是有效的。而实际上碰到的更多的是容许控制属于闭集的一类最优控制问题,这就要求人们去探索、求解最优控制问题的新途径。
下面介绍本课程的主要内容,线性规划:单纯形法和对偶规划;非线性规划:共轭梯度法、最速下降法和牛顿法,还有最优控制问题。
1 优化理论的数学模型
1.1 基本数学概述
线性规划的标准形式:
nmaxf(x1,x2,,xn)cjxj
j1a11x1a12x2a1nxnb1(LP)
axaxaxb
mnnmm11m22
x1,x2,,xn0
方程解的情况:
无可行解无最优解 有可行解有唯一最优解有最优解有无穷多最优解
有规划数学的基本知识可以知道:二维线性规划问题若有最优解,则最优解一定可在可行域的某个顶点上达到。
1.2 一维搜索
1.2.1 进退法
进退法特点&适用条件:
->可以用相同的试点数计算出最精确的解的估计区间.
->所用函数f(t)为下单峰函数
基本算法:
->确定试点个数n
->根据相对精度,得出Fibonacci数Fn
->使n是满足1的最小数。 Fn
->对于初始区间[a0,b0] Fn1tb(a0b0)01Fn令 Ftan1(ba)1000Fn
),比较其大小 计算函数值f(t1),f(t1
),则令a1a0,b1t1,t2t1,并令t2b1若f(t1)f(t1Fn2(a1b1) Fn1
,并令t2a1否则,令a1t1,b1b0,t2t1
如第3步继续迭代,通式为 Fn2(b1a1) Fn1
Fnktb(ak1bk1)k1kFnk1,k1,2,,n2 taFnk(ba)kk1k1k1Fnk1
1t(abn2)n12n2
令,其中是充分小的数
ta(1)(ba)n1n2n2n22
1两点中以函数值较小的为近似极小点,相应的函数值为近似极小在tn1,tn
1]或[tn1,bn2] 值,并得最终区间[an2,tn
1.2.2 黄金分割法
黄金分割法实际上是试探法的一种,它根据单峰函数构造。设F(x)是搜索区间[a,b]上的单峰函数。为了进行一维搜索,求一维目标函数的极小点,我们可以采用试探方法来进行。为了逐步缩小单峰区间.在区间内任取两点x1,x2算函数值为F(x1)和F(x2)),比较这两个函数值的大小,将出现以下三种情况。
(1)当F(x1)
(2)当F(x1)>F(x2)时,同理.极小点必在区间[x1 b]内.把搜索区间缩小为
[x1 b] 。
(3)当F(x1)=F(x2)时,这时极小点应在区间[x1 x2]内,缩小了区间。若计算出搜索区间内两个点函数值,能把搜索区间缩短,这样不断的重复,就可越来越精确的估出区间x0的位置,这就是试探法的基本思想。
F(x2F(x1)
ax1x2b
若第一次选取的试点为x1x2,则下一步保留区间为[a,x2]或[x1,b],两者的
机会是均等的,因此选取试点时希望x2-a=b-x1,实际计算取近似值:
x1a0.382(ba),x2a0.618(ba)
黄金分割法是Fibonacci法的极限形式。每次缩小区间的比例是一致的,每次将区间长度缩小到原来的0.618倍。
2 线性规划
2.1 单纯形法
线性规划问题的可行域是 n维向量空间Rn中的多面凸集,其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是:先找出一个基本可行解,对它进行鉴别,看是否是最优解;若不是,则按照一定法则转换到另一改进的基本可行解,再鉴别;若仍不是,则再转换,按此重复进行。因基本可行解的个数有限,故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。
根据单纯形法的原理,在线性规划问题中,决策变量(控制变量)x1,x2,…x n的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值(或最小值)的可行解称为最优解。这样,一个或多个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值(或最小值)。求解线性规划问题的目的就是要找出最优解。
最优解可能出现下列情况之一:①存在着一个最优解;②存在着无穷多个最优解;③不存在最优解,这只在三种情况下发生,即没有可行解或各项约束条件不阻止目标函数的值无限增大(或向负的方向无限增大)。
单纯形法的一般解题步骤可归纳如下:①把线性规划问题的约束方程组表达成典范型方程组,找出基本可行解作为初始基本可行解。②若基本可行解不存在,即约束条件有矛盾,则问题无解。③若基本可行解存在,从初始基本可行解作为起点,根据最优性条件和可行性条件,引入非基变量取代某一基变量,找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优
性条件(这时目标函数值不能再改善),即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界,则终止迭代。
用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解,对于具有10^6个决策变量和10^4个约束条件的线性规划问题已能在计算机上解得。
2.2 对偶规划
原始规划与对偶规划是同一组数据参数,只是位置有所不同,所描述的问题实际上是同一个问题从另一种角度去描述。
推论若x0是原始线性规划的可行解,y1是对偶线性规划的可行解,
cTx0bTy0,则x0与y1分别是原始线性规划问题与对偶线性规划问题的最优解。
对偶的线性规划都有最优解的充要条件是两者都有可行解。若原始线性规划问题与对偶线性规划问题之一具有无界的目标函数值,则另一个无可行解。若原始线性规划问题与对偶线性规划问题之一有最优解,则另一个也有最优解,并且它们目标函数的最优值相等.
3 非线性规划
3.1 最速下降法
最速下降法又称为梯度法,是1847年由著名数学家Cauchy给出的,它是解析法中最古老的一种,其他解析方法或是它的变形,或是受它的启发而得到的,因此它是最优化方法的基础。作为一种基本的算法,他在最优化方法中占有重要地位。其优点是工作量少,存储变量较少,初始点要求不高;缺点是收敛慢,效率不高,有时达不到最优解。
最速下降法迭代公式是
迭代步骤如下:
(1)给定初点x0,允许误差>0,令k=0。
(2)计算搜索方向gkg(xk)
(3)若gk,则 xxk,停止;否则令 pkgk,由一维搜索步长k,使得f(xkkpk)minf(xkpk) 0f(xkkpk)minf(xkpk) 0
(4)令 xk1xkkpk ,k=k+1,转步骤(2)。
3.2 共轭梯度法
共轭梯度法(Conjugate Gradient)是介于最速下降法与牛顿法之间的一个方法,它仅需利用一阶导数信息,但克服了最速下降法收敛慢的缺点,又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点,共轭梯度法不仅是解决大型线性方程组最有用的方法之一,也是解大型非线性最优化最有效的算法之一。 在各种优化算法中,共轭梯度法是非常重要的一种。其优点是所需存储量小,具有步收敛性,稳定性高,而且不需要任何外来参数。
二次函数的共轭方向法的迭代步骤:
已知具有正定矩阵G的二次目标函数 f(x)
(1)给定初始点x0下降方向1TxGxbTxc和终止限 。 2p0 ,置k=0。
0(2)作精确一维搜索 f(xkkpk)minf(xkpk),求步长k。
(3)令xk1xkkpk。
(4)若 gk,则xxk1,停;否则,转步骤(5)。
(5)取共轭方向pk1使得 piTGpj=0,i=0,1,……,k
(6)令k=k+1,转步骤(2)。
3.3 牛顿法
(1)基本思想:用二次函数逼近目标函数,用二次函数的极小值点逼近目标函
数的极小值点。
(2)计算方法将f(X)在Xk点展成二阶泰勒级数,即
f(X)p(X)f(Xk)[f(Xk](XXk)1(XXk)TH(Xk)(XXk) T
2
令p(X)0,即 f(Xk)H(Xk)(XXk)0
若H(Xk)正定,由上式解出X,并把它记作Xk1得
Xk1Xk[H(Xk)]1f(Xk)
以此作为迭代公式就是牛顿法。
(3)广义牛顿法
牛顿法中:pk[H(Xk)]1f(Xk) k1
此方法对二次严格凸函数是非常有效的,迭代一步即可求出最优解。一般不能保证点列{Xk}收敛。
广义牛顿法基本思想:
Pk[H(Xk)]1f(Xk),按最佳步长确定和X
minf(XkPk)f(XkkPk) 0kk1,即
Xk1Xkk[H(Xk)]1f(Xk)
3.4 单纯形法
1>n维单纯形:不在同一超平面上的n1个点生成的凸多面体。
1维、2维、3维单纯形例子。
2>基本思想:比较目标函数在单纯形的n1个顶点处的函数值,去掉其中最差点,代之以新点构成新的单纯形。重复上述过程,使单纯形逐步逼近于极小值点。
(1)反射
设Xi(i0,1,n)为单纯形的n1个顶点,记
fif(Xi)fhmaxfif(Xh)0in sfsmaxfi|0in,ihf(X)
fminff(Xl)l0ini
求Xh反射点Xr,
XrXc(XcXh)2XcXh
其中
Xc1Xi nih
Xc是去掉Xh后所有顶点的形心。
(2)扩张
1>若frf(Xr)fl,
XeXc(XcXh) (1)
2>若f(Xe)f(Xr),以X代替X构成新的单纯形;否则,用Xr代替Xh构成新的单纯形,并返回(1)。
3>若flf(Xr)fs,则以Xr代替Xh构成新的单纯形,并返回(1)。 (3)收缩
1>如果fsf(Xr)fh,
令:XhXr,然后压缩求点Xp, eh
XpXc(XhXc) (01)
2>若f(Xr)fh,将点X压缩在X与Xh之间,Xp仍上式确定。 3>若f(Xp)f(Xh),则以Xp代替Xh得新的单纯形;否则,令 pc
Xi(XiXl)/2,i0,1,,n
得新的单纯形,返回(1)。
如此继续计算,直至满足某个收敛指标为止。
3.5 DFP
DFP校正是第一个拟牛顿校正是1959年由Davidon提出的后经Fletcher和Powell改进故名之为DFP算法它也是求解无约束优化问题最有效的算法之一. DFP算法基本原理
考虑如下形式的校正公式
THk1HkkUkUkkVkVkT (7)
其中Uk,Vk是特定n维向量,k,k是待定常数.这时,校正矩阵是
TEkkUkUkkVkVkT.
现在来确定Ek.
根据拟Newton条件,Ek必须满足(6),于是有
T(kUkUkkVkVkT)ykSkHkyk
或
TkUkUkykkVkVkTykSkHkyk.
满足这个方程的待定向量Uk和Vk有无穷多种取法,下面是其中的一种:
TkUkUkykSk,
kVkVkTykHkyk
T注意到Ukyk和VkTyk都是数量,不妨取
UkSk,VkHkyk,
同时定出
k
将这两式代回(5.32)得 11,. kTTSkykykHkyk
Hk1
这就是DFP校正公式. TTSkSkHkykykHk. (8) HkTTSkykykHkyk
3.6 罚函数法
罚函数法是利用原问题的目标函数和约束条件构造新的目标函数--罚函数, 把约束最优化问题转化为相应的罚函数的无约束最优化问题来求解。罚函数分为内罚函数法、外罚函数法、广义乘子法法。
罚函数根据约束条件的不同构造的辅助函数也不相同。不等式约束问题的辅助函数与等式约束的辅助函数情形不同,但构造辅助函数的基本思想是一致的,这就是:在可行点辅助函数等于原来的目标函数值,在不可行点,辅助函数值等于原来的目标函数值加上一个很大的正数。 无约束优化问题的最优解趋于一个极限点,这个极限点正是原来的约束问题的最优解。此外,无约束问题的最优解往往不满足原来问题的约束条件,它是从可行域外部趋向原问题的最优点。因此 也称为外罚函数,相应的最优化方法称为外点法或外罚函数法。内点法在迭代总是从内点出发,并保持在可行域内部进行搜索。因此,这种方法适 用于不等式约束的问题。
4 最优控制
最优控制,就是将通常的最优控制问题抽象成一个数学问题,并且用数学语言严格的表示出来,最优控制可分为静态最有和动态最有两类。
静态最优是指在稳定情况下实现最优,它反映系统达到稳态后的静态关系。系统中的各变量不随时间变化,而只表示对象在稳定情况下各参数之间的关系,其特性用代数方程来描述。大多数的生产过程受控对象可以用静态最优控制来处理,并且具有足够的精度。静态最有一般可用一个目标函数J=f(x)和若干个等式约束条件或不等式约束条件来描述。要求在满足约束条件下,使目标函数J为最大或最小[4]。
动态最优是指系统从一个工况变化到另一个工况的变化过程中,应满足最有要求。在动态系统中,所有的参数都是时间的函数,其特性可用微分方程或差分方程来描述。动态最优控制要求寻找出控制作用的一个或一组数值,是特性指标在满足约束条件下为最优值。这样,目标函数不再是一般函数,而是函数的函数。
因此,在数学上这是属于泛函数求极值的问题。
受控系统的模型
受控系统的数学模型即系统的微分方程,它反映了动态系统在运动过程中所应遵循的物理或化学规律。在集中参数情况下,动态系统的运动规律可以用一组一阶常微分方程即状态方程来描述,即
.
xtf[xt,ut,t] (2-1)
式(2-1)中:x(t)表示n维状态变量;u(t)表示为r维控制向量;f()是x(t)、u(t)和t的n维函数向量;t是实数变量,可以概括一切具有集中参数的受控数学模型。
总结
随着工业自动化的不断进步,最优控制在理论和实践两方面都得到了充分的发展。在理论方面,关于最优化算法的改进将是今后研究的卞要方向之一。在应用方面,最优控制己经在很多领域发挥了重要的作用,在随机最优控制、分散最优控制、时间最短、能耗最小、线性一次型指标最优、跟踪问题、调节问题、伺服机构问题等中起到关键的作用。
通过对本课程的学习,加深了对优化理论的理解,并且对最优控制有了一定的了解。经过日常作业的练习,对本来不太熟悉的matlab编程有了更加熟悉的操作,提高了运筹学在最优控制中应用的认识。
分 数: ___________
任课教师签字:___________
华北电力大学研究生结课作业
学 年 学 期:2013-2014第二学期
课 程 名 称:优化理论和最优控制 学 生 姓 名:
学 号:
提 交 时 间:2014年4月26日
《优化理论和最优控制》结课总结
摘 要: 最优控制理论是现代控制理论的核心,控制理论的发展来源于控制对象的要求。尽50年来,科学技术的迅速发展,对许多被控对象,如宇宙飞船、导弹、卫星、和现代工业设备的生产过程等的性能提出了更高的要求,在许多情况下要求系统的某种性能指标为最优。这就要求人们对控制问题都必须从最优控制的角度去进行研究分析和设计。最优控制理论研究的主要问题是:根据已建立的被控对象的时域数学模型或频域数学模型,选择一个容许的控制律,使得被控对象按预定要求运行,并使某一性能指标达到最优值[1]。
关键字:最优控制理论,现代控制理论,时域数学模型,频域数学模型,控制率
Abstract: The Optimal Control Theory is the core of the Modern Control Theory,the development of control theory comes from the requires of the controlled objects.During the 50 years, the rapid development of the scientific technology puts more stricter requires forward to mang controlled objects,such as the spacecraft,the guide missile,the satellite,the productive process of modern industrial facilities,and so on,and requests some performance indexes that will be best in mang cases.To the control problem,it requests people to research ,analyse,and devise from the point of view of the Optimal Control Theory. There are mang major problems of the Optimal Control Theory studying,such as the building the time domain’s model or the frenquency domain’s model according to the controlled objects,controlling a control law with admitting, making the controlled objects to work according to the scheduled requires, and making the performance index to reseach to a best optimal value.
Keywords: The Optimal Control Theroy, The Modern Control Theroy, The
Time Domaint’s Model, The Frequency domain’s Model,The Control Law 0 引言
最优控制理论的形成和发展和整个现代自动控制理论的形成和发展十分不开的。在20世纪50年代初期,就有人开始发表从工程观点研究最短时间控制问题的文章,尽管其最优性的证明多半借助于几何图形,仅带有启发性质,但毕竟为发展现代控制理论提供了第一批实际模型。由于最优控制问题引人注目的严格表述形式,特别是空间技术的迫切需求,从而吸引了大批科学家的密切注意。经典变分理论只能解决一类简单的最优控制问题,因为它只对无约束或开集性约束是有效的。而实际上碰到的更多的是容许控制属于闭集的一类最优控制问题,这就要求人们去探索、求解最优控制问题的新途径。
下面介绍本课程的主要内容,线性规划:单纯形法和对偶规划;非线性规划:共轭梯度法、最速下降法和牛顿法,还有最优控制问题。
1 优化理论的数学模型
1.1 基本数学概述
线性规划的标准形式:
nmaxf(x1,x2,,xn)cjxj
j1a11x1a12x2a1nxnb1(LP)
axaxaxb
mnnmm11m22
x1,x2,,xn0
方程解的情况:
无可行解无最优解 有可行解有唯一最优解有最优解有无穷多最优解
有规划数学的基本知识可以知道:二维线性规划问题若有最优解,则最优解一定可在可行域的某个顶点上达到。
1.2 一维搜索
1.2.1 进退法
进退法特点&适用条件:
->可以用相同的试点数计算出最精确的解的估计区间.
->所用函数f(t)为下单峰函数
基本算法:
->确定试点个数n
->根据相对精度,得出Fibonacci数Fn
->使n是满足1的最小数。 Fn
->对于初始区间[a0,b0] Fn1tb(a0b0)01Fn令 Ftan1(ba)1000Fn
),比较其大小 计算函数值f(t1),f(t1
),则令a1a0,b1t1,t2t1,并令t2b1若f(t1)f(t1Fn2(a1b1) Fn1
,并令t2a1否则,令a1t1,b1b0,t2t1
如第3步继续迭代,通式为 Fn2(b1a1) Fn1
Fnktb(ak1bk1)k1kFnk1,k1,2,,n2 taFnk(ba)kk1k1k1Fnk1
1t(abn2)n12n2
令,其中是充分小的数
ta(1)(ba)n1n2n2n22
1两点中以函数值较小的为近似极小点,相应的函数值为近似极小在tn1,tn
1]或[tn1,bn2] 值,并得最终区间[an2,tn
1.2.2 黄金分割法
黄金分割法实际上是试探法的一种,它根据单峰函数构造。设F(x)是搜索区间[a,b]上的单峰函数。为了进行一维搜索,求一维目标函数的极小点,我们可以采用试探方法来进行。为了逐步缩小单峰区间.在区间内任取两点x1,x2算函数值为F(x1)和F(x2)),比较这两个函数值的大小,将出现以下三种情况。
(1)当F(x1)
(2)当F(x1)>F(x2)时,同理.极小点必在区间[x1 b]内.把搜索区间缩小为
[x1 b] 。
(3)当F(x1)=F(x2)时,这时极小点应在区间[x1 x2]内,缩小了区间。若计算出搜索区间内两个点函数值,能把搜索区间缩短,这样不断的重复,就可越来越精确的估出区间x0的位置,这就是试探法的基本思想。
F(x2F(x1)
ax1x2b
若第一次选取的试点为x1x2,则下一步保留区间为[a,x2]或[x1,b],两者的
机会是均等的,因此选取试点时希望x2-a=b-x1,实际计算取近似值:
x1a0.382(ba),x2a0.618(ba)
黄金分割法是Fibonacci法的极限形式。每次缩小区间的比例是一致的,每次将区间长度缩小到原来的0.618倍。
2 线性规划
2.1 单纯形法
线性规划问题的可行域是 n维向量空间Rn中的多面凸集,其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是:先找出一个基本可行解,对它进行鉴别,看是否是最优解;若不是,则按照一定法则转换到另一改进的基本可行解,再鉴别;若仍不是,则再转换,按此重复进行。因基本可行解的个数有限,故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。
根据单纯形法的原理,在线性规划问题中,决策变量(控制变量)x1,x2,…x n的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值(或最小值)的可行解称为最优解。这样,一个或多个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值(或最小值)。求解线性规划问题的目的就是要找出最优解。
最优解可能出现下列情况之一:①存在着一个最优解;②存在着无穷多个最优解;③不存在最优解,这只在三种情况下发生,即没有可行解或各项约束条件不阻止目标函数的值无限增大(或向负的方向无限增大)。
单纯形法的一般解题步骤可归纳如下:①把线性规划问题的约束方程组表达成典范型方程组,找出基本可行解作为初始基本可行解。②若基本可行解不存在,即约束条件有矛盾,则问题无解。③若基本可行解存在,从初始基本可行解作为起点,根据最优性条件和可行性条件,引入非基变量取代某一基变量,找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优
性条件(这时目标函数值不能再改善),即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界,则终止迭代。
用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解,对于具有10^6个决策变量和10^4个约束条件的线性规划问题已能在计算机上解得。
2.2 对偶规划
原始规划与对偶规划是同一组数据参数,只是位置有所不同,所描述的问题实际上是同一个问题从另一种角度去描述。
推论若x0是原始线性规划的可行解,y1是对偶线性规划的可行解,
cTx0bTy0,则x0与y1分别是原始线性规划问题与对偶线性规划问题的最优解。
对偶的线性规划都有最优解的充要条件是两者都有可行解。若原始线性规划问题与对偶线性规划问题之一具有无界的目标函数值,则另一个无可行解。若原始线性规划问题与对偶线性规划问题之一有最优解,则另一个也有最优解,并且它们目标函数的最优值相等.
3 非线性规划
3.1 最速下降法
最速下降法又称为梯度法,是1847年由著名数学家Cauchy给出的,它是解析法中最古老的一种,其他解析方法或是它的变形,或是受它的启发而得到的,因此它是最优化方法的基础。作为一种基本的算法,他在最优化方法中占有重要地位。其优点是工作量少,存储变量较少,初始点要求不高;缺点是收敛慢,效率不高,有时达不到最优解。
最速下降法迭代公式是
迭代步骤如下:
(1)给定初点x0,允许误差>0,令k=0。
(2)计算搜索方向gkg(xk)
(3)若gk,则 xxk,停止;否则令 pkgk,由一维搜索步长k,使得f(xkkpk)minf(xkpk) 0f(xkkpk)minf(xkpk) 0
(4)令 xk1xkkpk ,k=k+1,转步骤(2)。
3.2 共轭梯度法
共轭梯度法(Conjugate Gradient)是介于最速下降法与牛顿法之间的一个方法,它仅需利用一阶导数信息,但克服了最速下降法收敛慢的缺点,又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点,共轭梯度法不仅是解决大型线性方程组最有用的方法之一,也是解大型非线性最优化最有效的算法之一。 在各种优化算法中,共轭梯度法是非常重要的一种。其优点是所需存储量小,具有步收敛性,稳定性高,而且不需要任何外来参数。
二次函数的共轭方向法的迭代步骤:
已知具有正定矩阵G的二次目标函数 f(x)
(1)给定初始点x0下降方向1TxGxbTxc和终止限 。 2p0 ,置k=0。
0(2)作精确一维搜索 f(xkkpk)minf(xkpk),求步长k。
(3)令xk1xkkpk。
(4)若 gk,则xxk1,停;否则,转步骤(5)。
(5)取共轭方向pk1使得 piTGpj=0,i=0,1,……,k
(6)令k=k+1,转步骤(2)。
3.3 牛顿法
(1)基本思想:用二次函数逼近目标函数,用二次函数的极小值点逼近目标函
数的极小值点。
(2)计算方法将f(X)在Xk点展成二阶泰勒级数,即
f(X)p(X)f(Xk)[f(Xk](XXk)1(XXk)TH(Xk)(XXk) T
2
令p(X)0,即 f(Xk)H(Xk)(XXk)0
若H(Xk)正定,由上式解出X,并把它记作Xk1得
Xk1Xk[H(Xk)]1f(Xk)
以此作为迭代公式就是牛顿法。
(3)广义牛顿法
牛顿法中:pk[H(Xk)]1f(Xk) k1
此方法对二次严格凸函数是非常有效的,迭代一步即可求出最优解。一般不能保证点列{Xk}收敛。
广义牛顿法基本思想:
Pk[H(Xk)]1f(Xk),按最佳步长确定和X
minf(XkPk)f(XkkPk) 0kk1,即
Xk1Xkk[H(Xk)]1f(Xk)
3.4 单纯形法
1>n维单纯形:不在同一超平面上的n1个点生成的凸多面体。
1维、2维、3维单纯形例子。
2>基本思想:比较目标函数在单纯形的n1个顶点处的函数值,去掉其中最差点,代之以新点构成新的单纯形。重复上述过程,使单纯形逐步逼近于极小值点。
(1)反射
设Xi(i0,1,n)为单纯形的n1个顶点,记
fif(Xi)fhmaxfif(Xh)0in sfsmaxfi|0in,ihf(X)
fminff(Xl)l0ini
求Xh反射点Xr,
XrXc(XcXh)2XcXh
其中
Xc1Xi nih
Xc是去掉Xh后所有顶点的形心。
(2)扩张
1>若frf(Xr)fl,
XeXc(XcXh) (1)
2>若f(Xe)f(Xr),以X代替X构成新的单纯形;否则,用Xr代替Xh构成新的单纯形,并返回(1)。
3>若flf(Xr)fs,则以Xr代替Xh构成新的单纯形,并返回(1)。 (3)收缩
1>如果fsf(Xr)fh,
令:XhXr,然后压缩求点Xp, eh
XpXc(XhXc) (01)
2>若f(Xr)fh,将点X压缩在X与Xh之间,Xp仍上式确定。 3>若f(Xp)f(Xh),则以Xp代替Xh得新的单纯形;否则,令 pc
Xi(XiXl)/2,i0,1,,n
得新的单纯形,返回(1)。
如此继续计算,直至满足某个收敛指标为止。
3.5 DFP
DFP校正是第一个拟牛顿校正是1959年由Davidon提出的后经Fletcher和Powell改进故名之为DFP算法它也是求解无约束优化问题最有效的算法之一. DFP算法基本原理
考虑如下形式的校正公式
THk1HkkUkUkkVkVkT (7)
其中Uk,Vk是特定n维向量,k,k是待定常数.这时,校正矩阵是
TEkkUkUkkVkVkT.
现在来确定Ek.
根据拟Newton条件,Ek必须满足(6),于是有
T(kUkUkkVkVkT)ykSkHkyk
或
TkUkUkykkVkVkTykSkHkyk.
满足这个方程的待定向量Uk和Vk有无穷多种取法,下面是其中的一种:
TkUkUkykSk,
kVkVkTykHkyk
T注意到Ukyk和VkTyk都是数量,不妨取
UkSk,VkHkyk,
同时定出
k
将这两式代回(5.32)得 11,. kTTSkykykHkyk
Hk1
这就是DFP校正公式. TTSkSkHkykykHk. (8) HkTTSkykykHkyk
3.6 罚函数法
罚函数法是利用原问题的目标函数和约束条件构造新的目标函数--罚函数, 把约束最优化问题转化为相应的罚函数的无约束最优化问题来求解。罚函数分为内罚函数法、外罚函数法、广义乘子法法。
罚函数根据约束条件的不同构造的辅助函数也不相同。不等式约束问题的辅助函数与等式约束的辅助函数情形不同,但构造辅助函数的基本思想是一致的,这就是:在可行点辅助函数等于原来的目标函数值,在不可行点,辅助函数值等于原来的目标函数值加上一个很大的正数。 无约束优化问题的最优解趋于一个极限点,这个极限点正是原来的约束问题的最优解。此外,无约束问题的最优解往往不满足原来问题的约束条件,它是从可行域外部趋向原问题的最优点。因此 也称为外罚函数,相应的最优化方法称为外点法或外罚函数法。内点法在迭代总是从内点出发,并保持在可行域内部进行搜索。因此,这种方法适 用于不等式约束的问题。
4 最优控制
最优控制,就是将通常的最优控制问题抽象成一个数学问题,并且用数学语言严格的表示出来,最优控制可分为静态最有和动态最有两类。
静态最优是指在稳定情况下实现最优,它反映系统达到稳态后的静态关系。系统中的各变量不随时间变化,而只表示对象在稳定情况下各参数之间的关系,其特性用代数方程来描述。大多数的生产过程受控对象可以用静态最优控制来处理,并且具有足够的精度。静态最有一般可用一个目标函数J=f(x)和若干个等式约束条件或不等式约束条件来描述。要求在满足约束条件下,使目标函数J为最大或最小[4]。
动态最优是指系统从一个工况变化到另一个工况的变化过程中,应满足最有要求。在动态系统中,所有的参数都是时间的函数,其特性可用微分方程或差分方程来描述。动态最优控制要求寻找出控制作用的一个或一组数值,是特性指标在满足约束条件下为最优值。这样,目标函数不再是一般函数,而是函数的函数。
因此,在数学上这是属于泛函数求极值的问题。
受控系统的模型
受控系统的数学模型即系统的微分方程,它反映了动态系统在运动过程中所应遵循的物理或化学规律。在集中参数情况下,动态系统的运动规律可以用一组一阶常微分方程即状态方程来描述,即
.
xtf[xt,ut,t] (2-1)
式(2-1)中:x(t)表示n维状态变量;u(t)表示为r维控制向量;f()是x(t)、u(t)和t的n维函数向量;t是实数变量,可以概括一切具有集中参数的受控数学模型。
总结
随着工业自动化的不断进步,最优控制在理论和实践两方面都得到了充分的发展。在理论方面,关于最优化算法的改进将是今后研究的卞要方向之一。在应用方面,最优控制己经在很多领域发挥了重要的作用,在随机最优控制、分散最优控制、时间最短、能耗最小、线性一次型指标最优、跟踪问题、调节问题、伺服机构问题等中起到关键的作用。
通过对本课程的学习,加深了对优化理论的理解,并且对最优控制有了一定的了解。经过日常作业的练习,对本来不太熟悉的matlab编程有了更加熟悉的操作,提高了运筹学在最优控制中应用的认识。