第12章 其它优化问题及算法

《第12章 其它优化问题及算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、12其它优化问题及算法其它优化问题及算法二次多项式近似方法针对特殊问题的专门算法整数规划二次规划几何规划动态规划目标规划最优控制12.1二次多项式近似方法12.1.1直接二次近似12.1.1直接二次近似例12.1.1直接二次近似12.1.1直接二次近似……12.1.2Lagrange函数二次近似12.1.3约束问题的准牛顿法≈12.1.3约束问题的准牛顿法算法的关键惩罚函数线性搜索二阶导数近似BFGS公式：12.2二次规划二次规划问题目标函数为二次函数约束函数为线性函数矩阵形式：Kuhn–Tucker条件线性规划问题Kuhn–Tucker条件由于二次规划问题的约

2、束条件为线性的，所以Kuhn–Tucker必要性条件所要求的“约束限定”条件自动满足。另外，如果Q为正定或半正定矩阵，则目标函数为凸函数，满足了Kuhn–Tucker充分性条件。所以对于二次规划问题，我们只需求解相应的Kuhn–Tucker问题。QP问题求解方法线性规划算法互补主元法(complementarypivotmethod)12.3几何规划几何规划(GeometricPragramming)解决特殊类型的非线性优化问题：要求函数形式为正项式（posynomials），即指数可以为非整数的多项式特点：不直接搜索最优点的坐标（设计变量值），而是首先确定最优

3、的函数值。因而可以省略对设计变量的搜索。可以把复杂的优化问题化为线性代数方程组的求解。12.3.1正项式（Posynomial）函数形式：ci>0,(x1,…xn)>0,aij为实数12.3.2无约束问题的几何规划算法目标函数：最优值：的求解：的意义：困难度（DegreeofDifficulty）：几何规划不能用于困难度为负的情况正交条件规一条件最优点坐标值x*的确定求解方程组：ci>0,(x1,…xn)>0无约束几何规划算法的导出根据无约束最优化准则，有：对优化问题：min最优点坐标满足：无约束几何规划算法的导出令最优函数值为f*，定义：正交条件规一条件无约束

4、几何规划算法的导出最优函数值为f*的计算：无约束几何规划算法的导出正交条件无约束几何规划算法使用条件目标函数为正项式ci>0,(x1,…xn)>0困难度N–n–1>=0前后侧面例：无约束几何规划算法把粮食从仓库运到工厂，所用敞口容器长x1米，宽x2米，高x3米。容器的材料成本：底面80￥/m2，前后侧面10￥/m2，左右侧面20￥/m2。运输成本：往返一次1￥。求运输80m3的粮食的最低成本。解：=正项式系数：困难度：4–(3+1)=0例：无约束几何规划算法正交与规一条件：例：无约束几何规划算法最优值：=200例：无约束几何规划算法最优点坐标值x*方法一：=f(

5、x)例：无约束几何规划算法最优点坐标值x*方法二：12.3.3主函数——对偶函数关系算术平均——几何平均不等式(Cauchy不等式)（1）算术平均——几何平均不等式(Cauchy不等式)（2）正交条件：对偶函数由（1）式和（2）式有f(x)的对偶函数：=主函数——对偶函数定理主函数的最小值等于对偶函数的最大值：=主函数——对偶函数对应关系12.3.4约束问题的几何规划目标函数和约束都为正项式的优化问题ckj>0,(x1,…xn)>0形式变换minmin对偶问题minmax正交条件规一条件对偶定理困难度如果困难度D为0，且不等式约束的符号为≤，则可由正交条件和规一

6、条件解出，得到对偶函数的最大值，即主函数的最小值：如果困难度D>0，不等式约束的符号为≤，则可由Lagrange乘子法或其它等式约束算法解出对偶问题的解，得到对偶函数的最大值，即原问题的最小值最优点坐标的计算求解代数方程组：12.4动态规划多阶段决策过程(Multi-StageDecisionMaking)优化问题的全过程可划分为若干个相互联系的阶段（子过程），以便按照一定的次序去求解每个阶段的输出为下一个阶段的输入将多变量优化问题化为N个单变量优化问题例：多阶段决策过程例：多阶段决策过程转化多阶段决策过程数学表示决策变量状态变量状态转移方程:准则函数:描述阶

7、段的变量称为阶段变量，可用i表示.从第i个阶段开始点到全过程终点的过程称为后部子过程，或i子过程.状态表示每个阶段开始时所处的自然状况或客观条件.描述过程状态的变量称为状态变量无后效性与最优性原理无后效性（马尔科夫性质）：当某阶段的状态一旦确定,则此后过程的演变不再受此前各状态和决策的影响,或者说“未来与过去无关”.即由状态si出发的后部子过程可以看成一个以si为初始状态的独立过程.最优性原理：最优策略的任一后部子策略都是最优的动态规划问题min目标函数可分：或动态规划算法例：水池设计，承受一定重量，成本最低动态规划算法最优性定理动态规划算法……例：动态规划算法

8、四杆桁架在A点受力2×1