一、内点法1. 基本原理内点法的特点是将构造的新的无约束目标函数——惩罚函数定义在可行域内，并在可行域内求惩罚函数的极值点，即求解无约束问题时的探索点总是在可行域内部，这样，在求解内点惩罚函数的序列无约束优化问题的过程中，所求得的系列无约束优化问题的解总是可行解，从而在可行域内部逐步逼近原约束优化问题的最优解。

内点法是求解不等式约束最优化问题的一种十分有效方法，但不能处理等式约束。

因为构造的内点惩罚函数是定义在可行域内的函数，而等式约束优化问题不存在可行域空间，因此，内点法不能用来求解等式约束优化问题。

对于目标函数为min ()f Xs.t. ()0u g X ≤ （u=1,2,3,…m ）的最优化问题，利用内点法进行求解时，构造惩罚函数的一般表达式为()()11(,)()()mk k u uX r f X rg X ϕ==-∑ 或者 ()()()[]11(,)()ln ()()ln ()mmk k k uuu u X rf X rg X f X rg X ϕ===+=--∑∑而对于()f X 受约束于()0(1,2,,)u g X u m ≥=的最优化问题，其惩罚函数的一般形式为()()11(,)()()mk k u uX r f X rg X ϕ==+∑ 或()()[]1(,)()ln ()mk k uu X r f X rgX ϕ==-∑式中，()k r-----惩罚因子，是递减的正数序列，即()()()()()01210k k r r r r r +>>>>>>>()lim 0k k r →∞=通常取()1.0,0.1,0.01,0.001,k r=。

上述惩罚函数表达式的右边第二项，称为惩罚项，有时还称为障碍项。

说明：当迭代点在可行域内部时，有()0u g X ≤（u =1，2，3，4，…m ），而()0k r>，则惩罚项恒为正值，当设计点由可行域内部向约束边界移动时，惩罚项的值要急剧增大并趋向无穷大，于是惩罚函数的值也急剧增大直至无穷大，起到惩罚的作用，使其在迭代过程中始终不会触及约束边界。

2. 内点法的迭代步骤（1）取初始惩罚因子(0)0r>，允许误差0ε>；（2）在可行域D 内取初始点()0X ，令1k =；（3）构造惩罚函数()(,)k X rϕ，从(1)k X -点出发用无约束优化方法求解惩罚函数()(,)k X r ϕ的极值点()()k X r *；（4）检查迭代终止准则：如果满足()()1571()()1010k k X r X r ε-**---≤=-或()()()13421(,)(,)1010(,)k k k X r X r X r ϕϕεϕ-**---*-≤=- 则停止迭代计算，并以()()k X r*为原目标函数()fX 的约束最优解，否则转入下一步；根据情况，终止准则还可有如下的形式：()()1()()k k f X f X ε--≤或()11()mk u urg X ε=≤∑ 或()1ln ()mk uu rg X ε=≤∑5）取()()()()10,(),1k kkrCr X X r k k +*===+，转向步骤3）。

递减系数0.10.5C =-，常取0.1，亦可取0.02。

采用内点法应注意的几个问题： （1）初始点()0X 的选取初始点()0X必须严格在可行域内，满足所有的约束条件，避免为约束边界上的点。

如果约束条件比较简单，可以直接人工输入；若问题比较复杂，可采用随机数的方式产生初始点()0X，具体方程参照复合形法介绍。

（2）关于初始惩罚因子(0)r 的选择。

实践经验表明，初始惩罚因子(0)r 选的恰当与否，会显著地影响内点法的收敛速度，甚至解题的成败。

若()0r值选得太小，则在新目标函数即惩罚函数()(,)k X rϕ中惩罚项的作用就会很小，这时求()(,)k X r ϕ的无约束极值，犹如原目标函数()f X 本身的无约束极值，而这个极值点又不大可能接近()f X 的约束极值点，且有跑出可行域的危险。

相反，若()0r 值取得过大，则开始几次构造的惩罚函数()(,)k X r ϕ的无约束极值点就会离约束边界很远，将使计算效率降低。

可取()0r≈1～50，但多数情况是取()01r =。

通常，当初始点()0X是一个严格的内点时，则应使惩罚项()()0011()mu u rg X=∑在新目标函数()(,)k X rϕ中所起的作用与原目标函数()0()f X 的作用相当，于是得()()()001()1()m u u f X rg X==∑倘若约束区域是非凸的且初始点()0X 亦不靠近约束边界，则()0r的取值可更小，约为上式算得值的0.1～0.5倍。

内点法的计算程序框图例题：用内点法求min 2212()f X x x =+s.t. 1()10g X x =-≤ （u=1,2,3,…m ） 的约束最优解。

（取ε=0.001）解：构造内点惩罚函数为()()[][]22()1211(,)()ln ()ln (1)mk k k uu X r f X rgX x x r x ϕ==--=+---∑用极值条件进行求解()111201k r x x x ϕ∂=-=∂-，2220x x ϕ∂==∂ 联立上式求得*()11()2k x r =，*()2()0k x r =由于约束条件的限制，可得无约束极值点为*()()Tk X r ⎤=⎥⎢⎥⎣⎦当()k r 取1，0.1,0.01,…→0时，可得最优解为*[1,0]T X =，*()1f X =编程方式实现：1. 惩罚函数function f=fun(x,r)f=x(1,1)^2+x(2,1)^2-r*log(x(1,1)-1); 2. 步长的函数function f=fh(x0,h,s,r) %h 为步长 %s 为方向 %r 为惩罚因子 x1=x0+h*s; f=fun(x1,r); 3. 步长寻优函数function h=fsearchh(x0,r,s)%利用进退法确定高低高区间，利用黄金分割法进行求解 h1=0;%步长的初始点 st=0.001; %步长的步长 h2=h1+st;f1=fh(x0,h1,s,r); f2=fh(x0,h2,s,r); if f1>f2h3=h2+st;f3=fh(x0,h3,s,r); while f2>f3 h1=h2; h2=h3; h3=h3+st; f2=f3;f3=fh(x0,h3,s,r); endelsest=-st;v=h1;h1=h2;h2=v;v=f1;f1=f2;f2=v;h3=h2+st;f3=fh(x0,h3,s,r);while f2>f3h1=h2;h2=h3;h3=h3+st;f2=f3;f3=fh(x0,h3,s,r);endend%得到高低高的区间a=min(h1,h3);b=max(h1,h3);%利用黄金分割点法进行求解h1=1+0.382*(b-a);h2=1+0.618*(b-a);f1=fh(x0,h1,s,r);f2=fh(x0,h2,s,r);while abs(a-b)>0.0001if f1>f2a=h1;h1=h2;f1=f2;h2=a+0.618*(b-a);f2=fh(x0,h2,s,r); elseb=h2;h2=h1;f2=f1;h1=a+0.382*(b-a);f1=fh(x0,h1,s,r);endendh=0.5*(a+b);4. 迭代点的寻优函数function f=fsearchx(x0,r,epson)x00=x0;m=length(x0);s=zeros(m,1);for i=1:ms(i)=1;h=fsearchh(x0,r,s);x1=x0+h*s;s(i)=0;x0=x1;endwhile norm(x1-x00)>epsonx00=x1;for i=1:ms(i)=1;h=fsearchh(x0,r,s);x1=x0+h*s;s(i)=0;x0=x1;endendf=x1;5. 主程序clearclcx0=[2;2]; %给定初始点r=1;c=0.1;epson=0.001;x1=fsearchx(x0,0.1,epson);while norm(x0-x1)>epsonx0=x1;r=r*c;x1=fsearchx(x0,r,epson) ;enddisp '函数的最优解为'x1运行结果：函数的最优解为x1 =1.0475-0.0005。