内点法的迭代步骤 (1)给定允许误差E>0,取>0,0<B<1; (2)求出约束集合D的一个内点X∈D9,令k=1 (3)以∈D为初始点,求解min(X,),其中 X∈D X∈Dy的最优解,设为Xk=X()∈D (4)检验是否满足-rng(X)≤E或x E,满 足,停止迭代,XxX;否则取1=Bk,令k=k+1, 返回(3)
11 内点法的迭代步骤 (1) 给定允许误差 0，取r1 0,0 1； (2) 求出约束集合 D 的一个内点 0 0 X D ，令k =1； (3) 以 1 0 X D k − 为 初 始 点 ， 求 解 ( ) k X D min I X,r 0 ， 其 中 0 X D 的最优解，设为 ( ) 0 X X rk D k = ； (4) 检验是否满足 − ( ) = m i k r gi X 1 ln 或 ( ) = m i i k g X r 1 1 ， 满 足，停止迭代， k X X * ；否则取 k k r r +1 = ， 令k = k +1， 返回(3）．
近似规划法 近似规划法的基本思想:将问题(3)中的目标函数(x) 和约束条件g、(X)≥0(i=1,…m);h(X)=0(=1,…,D 近似为线性函数,并对变量的取值范围加以限制,从 而得到一个近似线性规划问题,再用单纯形法求解之, 把其符合原始条件的最优解作为(3)的解的近似 每得到一个近似解后,都从这点出发,重复以上步骤 这样,通过求解一系列线性规划问题,产生一个 由线性规划最优解组成的序列,经验表明,这样的序 列往往收敛于非线性规划问题的解 12
12 近似规划法的基本思想：将问题(3)中的目标函数 和约束条件 近似为线性函数，并对变量的取值范围加以限制，从 而得到一个近似线性规划问题，再用单纯形法求解之， 把其符合原始条件的最优解作为(3)的解的近似． f (X ) g (X ) 0 (i 1,...,m); h (X ) 0 ( j 1, ,l) i = j = = 近似规划法 每得到一个近似解后，都从这点出发，重复以上步骤． 这样，通过求解一系列线性规划问题，产生一个 由线性规划最优解组成的序列，经验表明，这样的序 列往往收敛于非线性规划问题的解
近似规划法的算法步骤如下 (1)给定初始可行点x1={x,x2,…,x},步长限制8(G=1…n), 步长缩小系数B∈(0,),允许误差E,令k=1 (2)在点x处,将f(x),g(x),b(x)按泰勒级数展开并 取一阶近似,得到近似线性规划问题 minf(x)f(rk)+v(rk)(x-Xk) g(x)≈g;(x)+Vg(x)(x-x)201=1…,m h(x)≈h/(x)+Vh,(x)(x-x)=0j=1…1
13 近似规划法的算法步骤如下 (2) 在 点 k X 处，将 f (X )，g (X ) h (X ) i j , 按泰勒级数展开并 取一阶近似，得到近似线性规划问题： ( ) ( ) ( ) ( ) k T k k min f X f X + f X X − X g (X ) g (X ) g (X ) (X X ) i m k T k i k i i + − 0 =1,, h (X ) h (X ) h (X ) (X X ) l k T k j k j j + − = 0 j =1,, ； (1)给定初始可行点 1 1 2 1 1 1 , , , n X = x x x ，步长限制 ( j n) j 1, , 1 = ， 步长缩小系数 (0,1)，允许误差，令 k=1；
(3)在上述近似线性规划问题的基础上增加一组限制步长的线 性约東条件.因为线性近似通常只在展开点附近近似程度较 高,故需要对变量的取值范围加以限制,所增加的约束条件是: x,≤O 求解该线性规划问题,得到最优解X+; (4)检验ⅹ点对原约束是否可行。若X对原约束可行, 则转步骤(5);否则,缩小步长限制,令δ=B6(=1…,n), 返回步骤(3),重解当前的线性规划问题; 5)判断精度:若<(=1…m),则点X为近似最优解; 否则,令⑧+=6 n),k=k+1,返回步骤(2) 返回
14 5 ) 判断精度：若 ( j n) k j =1,, ，则点 k+1 X 为近似最优解； 否则，令 ( j n) k j k j 1, , +1 = = ，k=k+1，返回步骤(2)． (3)在上述近似线性规划问题的基础上增加一组限制步长的线 性约束条件．因为线性近似通常只在展开点附近近似程度较 高，故需要对变量的取值范围加以限制，所增加的约束条件是： x x ( j n) k j k j j − =1,, 求解该线性规划问题，得到最优解 k +1 X ； (4) 检验 k+1 X 点对原约束是否可行。若 k+1 X 对原约束可行， 则转步骤(5)；否则，缩小步长限制，令 ( j n) k j k j = =1,, ， 返回步骤(3)，重解当前的线性规划问题； 返回
1、二次规划 标准型为: Min Z= X HX+C X s.t.Ax<=bAeg·X=beq VLB≤X≤VUB 用 MATLAB软件求解,其输入格式如下 1. x=quadprog(h, C, a, b) 2. x=quadprog(h, C, a, b, Aeg, beg 3. x=quadprog(h, C, a, b, Aeg, beg, VLB, VUB) 4. -quadprog(, C, A, b, Aeq, beq, VLB, VUB, X) 5. x=quadprog(h, C, a, b, Aeg, beg, VLB, VUB, Xo, options) LX, fval]=quaprog ..) 7. Lx, fval, exitflag]=quaprog(.) 8. LX, fval, exitflag, output]=quaprog(.) 15
15 用MATLAB软件求解,其输入格式如下: 1. x=quadprog(H,C,A,b); 2. x=quadprog(H,C,A,b,Aeq,beq); 3. x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB); 4. x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X0); 5. x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X0,options); 6. [x,fval]=quaprog(...); 7. [x,fval,exitflag]=quaprog(...); 8. [x,fval,exitflag,output]=quaprog(...); 1、二次规划 标准型为： Min Z= 2 1 X T HX+cT X s.t. AX<=b Aeq X = beq VLB≤X≤VUB