几何规划(Ⅲ)

【摘要】 <正> 前两章中的对偶理论为正项几何规划提供了一类解法,也就是通过解对偶规划来解原正项几何规划的解法,这类解法称为正项几何规划的对偶解法.另一类方法则是直接解原正项几何规划的算法,称为原算法.我们将从对偶方法开始. 三、正项几何规划的解法前两章中的对偶理论为正项几何规划提供了一类解法,也就是通过解对偶规划来解原正项几何规划的解法,这类解法称为正项几何规划的对偶解法.另一类方法则是直接解原正项几何规划的算法,称为原算法.我们将从对偶方法开始.§3.1. 困难度定义3.1.1. 称d=T-N-1=sum from m=0 to M T_m-N-1 （3.1.1）为（P）与（D）的困难度.我们看到,对偶规划（D）的约束条件ω₀₀=1,（?）^Tω=0 （3.1.2）是一组有 N+1个方程、T（=T₀+T₁+…+T_M）个变量的方程组.如果困难度d=0,（3.1.3）并且 T=N+1就等于系数矩阵的秩,那么方程组（3.1.2）就有唯一的解ω^*.若ω^*不满足非负条件,则对偶规划（D）就没有容许解,于是根据定理2.3.6,原正项规划（P）一定没有约束最小解,甚至也没有正的约束下确界 M_P;而若ω^*≥0,因为它是（D）的唯一容许解,所以它也是（D）的最优解,故若（P）有约束最小解 x^*,那么它一定能够通过（1.5.8）或线性方程组（1.5.16）解得,反之由（1.5.8）或（1.5.16）解得的任何原容许解也一定是（P）的最?更多还原