1、0内点法基本原理 摘要：内点法是求解含不等式约束最优化问题的一种十分有效的算法。内点法通过构造障碍函数，求解一系列只含等式约束最优化问题，逐步得到原问题的最优解，具有找初始点容易、线性收敛、迭代次数少等特点。本文主要介绍了内点法的基本原理，障碍方法的一般步骤并分析了该方法的优缺点，进行了算例实践。关键词：内点法；障碍方法；Newton 法The Theory of Interior Point MethodAbstract: Interior point method is a very effective algorithm for solving optimization problems
2、 with inequality constrained. Interior point method is constructed to solve a series of optimization problems with equality constraints, and the optimal solution of the original problem is obtained, which has the characteristics of finding the initial point easier, linear convergence, less iteration
3、 number and so on. This paper mainly introduces the theory of interior point method, the general steps of barrier method and analyzing the advantages and disadvantages of the method. Key words: interior point method; barrier method;Newton method11 引言内点法是由 John von Neumann 利用戈尔丹的线性齐次系统提出的，后被 Narendra
4、 Karmarkar 于 1984年推广应用到线性规划，即 Karmarkar 算法。内点法是凸优化算法递阶结构中新层次的方法，其思想是对于线性等式和不等式约束的优化问题，通过将其简化成一系列线性等式约束问题求解 1。主要是通过构造对数障碍函数将不等式约束与原目标函数结合，将原问题转化为新的等式约束下的优化问题，之后再运用 Newton 方法进行求解 2。而罚函数法是将不等式约束与等式约束全部进行加权处理后与原目标函数结合，将原问题转化为新的无约束优化问题，通过求解该新的无约束优化问题，间接得到原约束优化问题的最优解 6。两者在算法思想上有本质的不同，但是当原问题中只有不等式约束时，两者求解是
5、相同的。下面主要介绍内点法的基本原理及算法思想，并对障碍法与原对偶内点法的优缺点进行了探究与分析，并给出了一个实际算例来加以说明。2 内点法原理2.1 对数障碍函数和中心路径含有不等式约束的凸优化问题的标准形式如下：（1）bAxmifi,0)(subject ominz其中 是二次可微的凸函数， ， 。并且设最优的点 ，最优Rfnm:,0 npRnprakx值为 。满足如下 KKT 条件：)(xp（2）mixfAxfixfbAimi Tii ,1,0)()( ,)(,10 通过定义对数障碍函数及加入正参数 t： ,0)(|)(),(log)(1 mi ini ixfRdfx 将原问题（1）近似
6、转化为（3）bAxftsubject o)(inz10随着参数 t 的不断增加问题（ 3）的近似精度也会不断改进。而后我们可以通过让参数 t 逐渐增加，运用Newton 方法来求解一系列形如（3）的优化问题，从而得到原问题（ 1）的最优解。为了简化符号，考虑（3）的等价问题：2（4）bAxtfsubjec o)(minz0两则的最优解集相同，最优值差一个常参数 t。从开始假定问题（4）能够用 Newton 方法求解，并特别假定对任何 t0 都存在唯一解 。我们称 为中心点，而这些点的集合定义为问题（1）的中心路径。)(tx)(并且所有中心路劲上的点都由以下充要条件所界定： 是严格可行，即满足：
7、)(tx,21,0,)( mifbtAxi 并且存在 使pR )()(0TAtxtxft 成立。再定义 ,/)( ,21,)()( tmitxftii 我们可以将中心路径的条件解释为 KKT 最优性条件（2）的连续变形。即 等于 的充要条件是存在x)(t满足：，（5）mitxfAfixfbimTii 2,1,1/)(0)( ,)(,10 中心路径条件（5）与 KKT 条件（ 2）的唯一不同在于互补松弛条件 被条件0)(-xfi所替换。特别是，对于很大的 t， 和对应的对偶解 “几乎”满足问题txfi1/)(- )(x t，（1）的 KKT 最优性条件。并且在实际计算过程中求解 是相当有难度的，
8、而通过将其转化为0)(-xfi就相对容易求解。txfi/)(-2.2 障碍方法障碍方法是对无约束极小化方法进行简单的扩充，通过顺序求解一系列无约束（或线性约束）对的极小化问题，每次用所获得的最新的点作为求解下一个问题的初始点，也就是说，通过逐渐增加 t 的值得到相应的 ，直到满足所需要的精度。)(tx障碍算法的步骤如下：给定严格可行点 误差阈值 。，1,0:,t 03重复进行：1.中心点步骤。从 x 开始，在 的约束下极小化 ，最终确定 。bAx0tf)(tx2.改进。 。)(:t3.停止准则。如果对偶间隙小于 。4.增加 t。 。t:每步迭代中我们都从上次获得的中心点开始计算当前中心点 ，然
9、后通过乘比因子 增加 t。)(tx 1在中心点步骤中我们主要采用 Newton 方法来求解。我们将中心点步骤中的 Newton 迭代或步骤称为内部迭代。每次内部迭代我们都可以得到原问题可行解；但是仅在外部迭代结束时我们才有对偶可行解。2.3 障碍方法优缺点分析（1）对初始点选择要求不高对于初始点的选择可以通过求解下面优化问题得到，（6）bAxmisfi2,1)(subject ominz并且根据上述优化问题的最优值 的符号可以区分三种情况。当 则原不等式约束有严格可行解；p0p当 则原不等式约束不可行；当 则原不等式约束可行，但是没有严格可行解。0p0并且只需要选择的初始点严格满足不等式约束，
10、在接下去的迭代中只要中心步骤的某个迭代点选取了完整的 Newton 步径，那么之后的所有迭代点都是原问题可行点。（2）中心点的精度不需要十分精确在求解过程中不需要对 进行精确计算，因为中心路径的作用仅是随着 将中心点引向原点)(tx t的最优解，无其他意义；不精确的中心点计算方法同样能够产生收敛于最优点的点列 。并且另一个)(kx方面，计算 的十分精确的极小解只会增加少量的 Newton 迭代，因此也可以假定在计算中心点步骤0tf中产生的都是精确的中心点。（3） 值的选择不敏感参数 的选择需要同时兼顾所需要的内部迭代和外部迭代的次数。当 值较小时可以期望每次外部迭代所需要进行较少次数的 New
11、ton 迭代，但是由于每次外部迭代只减少了较小的间隙，所需要的外部迭代次数会比较多。当 较大时，相反的情况也会发生。但是经过实践表明， 的选择对总的计算量并非特别敏感，取值从 10 到 20 或附近都能取得较好的效果，这位算法选择 提供了极大的便利。4（4）随着问题维数的增加所需要的 Newton 迭代次数的增量非常小在具体算例中，可以发现应用障碍方法当问题的维数增加时，所需要的 Newton 迭代次数非常缓慢地增加，几乎总是围绕数十次的数量变动。不过，进行每次 Newton 迭代的计算量会随着问题规模的增加而同步增加。（5）对偶间隙呈现近似线性收敛对于大于 10 或者附近数值的 值，障碍方法
12、能够很好地在大约经过 30 次左右的 Newton 迭代就可以把对偶间隙从 减少到 。每次 Newton 迭代问题的对偶间隙近似缩小为原来的 。但是通过实践，210-6 1/我们也发现当 大于 10 或附近的数值时， 的选择几乎不影响所需要的总的 Newton 迭代次数。为了改进障碍方法的线性收敛速度，又提出了原对偶内点法，该方法具有超线性收敛性质，并且能够有效处理可行但不严格可行的问题 5。3 算法实践为了编程的方便，令 ，则 。给定精度等参数后按照上述算法可tr10lim ,k10 krr以得到如下程序框图：从 点出发求解 ：(0)1,rC开始在可行域内选取(0)Xk = 1(1)kX*(
13、)min,kr得1()krf(1)(krC*()kXrf停止图 1：内点法程序框图以下面简单的优化问题为例对内点进行进一步的说明。5（7）01)(subject ominz2xf首先通过构造内点障碍函数 2()111(,)(ln()ln)mkk kuuXrfrgXrx用极值条件进行求解可得，()120krx20x联立上式求得，()*()12kkrxr*()20kx由于约束条件的限制，可得无约束极值点为，()*()1,TkkrXr当取 时，可得最优解为0kr， 。*1,0T*()1fX利用 matlab 也得到了相同的结果，如附录程序所示 7。而从如下图像中也可以直观看出当 时求出的最优解约近似
14、于原问题的最优解。kr1 1.2 1.41.6 1.8 2-2-10120102030401 1.2 1.41.6 1.8 2-2-101201020304061 1.2 1.41.6 1.8 2-2-1012024681 1.2 1.41.6 1.8 2-2-101202468图 2：当 r 分别取 4、1、0.1、0.01 时障碍函数图像参考文献：1 Stephen Boyd, Lieven Vandenberghe.Convex OptimizationM.New York: Cambridge University Press, 2004,561-615. 2 刘红英, 夏勇, 周水生
15、.数学规划基础M.北京:北京航空航天大学出版社 ,2012,205-239.3 刘明波, 王晓村 . 内点法在求解电力系统优化问题中的应用综述J. 电网技术, 1999, 23(8):61-64.4 汪超群, 韦化, 吴思缘,等. 七种最优潮流分解协调算法的性能比较J. 电力系统自动化, 2016, 40(6).5 刘志鹏. 基于原对偶内点法的最优潮流研究D. 山东科技大学, 2009.6 张菊亮, 章祥荪 . 不等式约束最优化的非光滑精确罚函数的一个光滑近似J. 系统科学与数学, 2000, 20(4):499-505.7 薛定宇,陈阳泉.高等应用数学问题的 Matlab 求解M.北京:清华
16、大学出版社,2004,37-42.附录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 为 1/tx1=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 f1f2h3=h2+st;f3
17、=fh(x0,h3,s,r);while f2f37h1=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 f2f3h1=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)
18、;f2=fh(x0,h2,s,r);while abs(a-b)0.0001if f1f2a=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);8f1=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
19、=x1;endwhile norm(x1-x00)epson x00=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 函数的最优解为x16.算例函数图像clc;clear;9xx=1.01:0.01:2;yy=-2:0.01:2;r=0.001;x,y=meshgrid(xx,yy);z1=x.2+y.2-r.*log2(x-1);surf(x,y,z1),shading flat
