摘要：现代内点法理论的基本思想是，起点在“宇宙中心”，用梯度法从起点寻找一个下降方向，因 为从起点走出去第一步效果最好，则设法使每一次走出去都是第一步（用非线性的投影变换有回到新的宇 宙中心，就不会碰到边界）Karmarkar提出的内点法是建立在单纯形结构之上的，但与单纯形法沿着可行 域边界寻优不同,内点法从初始内点出发, 沿着最速下降方向, 从可行域内部直接走向最优解内点法是在 可行域内部寻优， 对于大规模线性规划问题， 当约束条件和变量数目增加时 ， 内点法的迭代次数变化较 少内点法是一种具有多项式时间复杂性的线性规划算法，其收敛性和计算速度均优于单纯形法，计算时 间比单纯形法快50倍内点法在形式上与经典障碍法等价，而且对于线性、非线性问题可以统一解法关键词：内点法；梯度法；最优解；线性规划；Interior-point methodABSTRACT：Is the basic idea of modern interior point theory, beginning in the center of the universe ", by using the gradient method from starting point to find a direction, because from the beginning to go out first step effect is best, try to make every going out is the first step (with nonlinear projection transformation has returned to the new center of the universe, won't encounter boundary).Karmarkar interior-point method is proposed based on the simplex structure, but with the simplex optimization method along the feasible region boundary, interior-point method starting from the initial interior point, along the steepest descent direction, directly to the optimal solution from inside the feasible region.Interior point is inside the feasible region optimization, for large-scale linear programming problem, when the number of constraints and variables increases, the less number of iterations change interior-point methods.Interior-point method is a polynomial time complexity of the linear programming algorithm, the convergence and computing speed are better than the simplex method, calculation time 50 times faster than the simplex method.Interior-point method with the method of classic obstacles equivalent in form, but also can be unified solution to the linear and nonlinear problem.Keywords: Interior-point method;Gradient method.The optimal solution;Linear programming;1. 引言1.1内点法求解线性规划问题究背景单纯形法及其变型一直是实际应用中极其有效的计算方法。
但是，在实际计算中单纯形 法有不少缺点随着约束条件和变量数目的增加，迭代次数也迅速增加， 在最坏情况下， 单 纯形法的迭代次数会按指数上升， 收敛很慢1979 年， Khachian 提出了线性规划问题的第 一个多项式时间算法——椭球法， 取得了理论上的重大突破但是由于受有限精度计算的限 制， 椭球法的应用效果还不能与单纯形法相比拟现代内点理论的基本思想是：起点在“宇宙中心”，用梯度法从起点寻找一个下降方向， 因为从起点走出去第一步效果最好，则设法使每一次走出去都是第一步(用非线性的投影变 换有回到新的宇宙中心，就不会碰到边界)Karmarkar提出的内点法是建立在单纯形结构 之上的，但与单纯形法沿着可行域边界寻优不同 ，内点法从初始内点出发， 沿着最速下降方 向， 从可行域内部直接走向最优解内点法是在可行域内部寻优， 对于大规模线性规划问题， 当约束条件和变量数目增加时, 内点法的迭代次数变化较少内点法是一种具有多项式时间 复杂性的线性规划算法，其收敛性和计算速度均优于单纯形法，计算时间比单纯形法快 50 倍内点法在形式上与经典障碍法等价，而且对于线性、非线性问题可以统一解法近年来的内点算法主要有三大类：(1) 投影尺度法,它是Karmarkar算法的原型。
这个方法要求问题具有特殊的单纯形结 构和最优目标值为零, 在实际计算过程中, 需要用复杂的变换将实际问题转换为这种标准 形式因此, 投影尺度法在实际中应用较少2) 仿射尺度法，这是一种已经比较成熟和广泛的算法目前原仿射尺度法和对偶仿 射尺度法虽然应用较多, 但这两种方法的多项式时间复杂性还不能从理论上得到证明3) 路径跟踪法, 又称为跟踪中心轨迹法这种方法将对数壁垒函数与牛顿法结合起来 应用到线性规划问题, 并且已经从理论上证明具有多项式时间复杂性路径跟踪法收敛迅速, 鲁棒性强, 对初值的选择不敏感, 现在已经被推广应用到二次规划领域, 正被进一步发展为 从复杂性角度研究一般非线性规划的内点算法,是目前最有发展潜力的一类内点算法内点法在收敛性、计算速度等方面具有单纯形法无法替代的优势, 因此人们纷纷采用仿 射尺度法和路径跟踪法研究各种大规模、复杂的线性规划问题, 并将其推广应用于求解各种 二次规划和非线性规划问题近年来, 仿射尺度法和路径跟踪法在求解电力系统优化问题中 也得到广泛的应用, 如水库优化调度、安全约束的经济调度、安全控制、状态估计、静态电 压稳定分析、实时电价计算、无功优化和最优潮流等。
但投影尺度法的应用相对较少2. 内点法2.1. 基本原理内点法的特点是将构造的新的无约束目标函数——惩罚函数定义在可行域内，并在可行 域内求惩罚函数的极值点，即求解无约束问题时的探索点总是在可行域内部，这样，在求解 内点惩罚函数的序列无约束优化问题的过程中，所求得的系列无约束优化问题的解总是可行 解，从而在可行域内部逐步逼近原约束优化问题的最优解 内点法是求解不等式约束最优化问题的一种十分有效方法，但不能处理等式约束因为 构造的内点惩罚函数是定义在可行域内的函数，而等式约束优化问题不存在可行域空间，因 此，内点法不能用来求解等式约束优化问题对于目标函数为min f (X )s.t. g ( X ) 0 ( u=1,2,3, „ m)u的最优化问题，利用内点法进行求解时，构造惩罚函数的一般表达式为g (X)u或者 申(X, r(k)) = f (X) + r(k)£In |g (X)| = f (X) 一 r(k送ln [-g (X)]uu=1uu =1申(X,r(k))二 f (X) 一 r(k)£u =1而对于f (X)受约束于g (X) > 0(u = 1,2,m)的最优化问题，其惩罚函数的一般形u式为 m1申(X, r(k)) = f (X) + r-,g (X)u =1 u或申(X, r(k)) = f (X) - r(k)£ ln [g (X)]uu =1式中， r(k) 惩罚因子，是递减的正数序列，即r(o) > r(i) > r(2)> …> r() > r(k+1) > …> 0lim r(k) = 0k T8通常取 r(k)= 1.0,0.1,0.01,0.001,…。
上述惩罚函数表达式的右边第二项，称为惩罚项，有时还称为障碍项说明：当迭代点在可行域内部时，有g (X) < 0( u =1, 2, 3, 4，„m)，而r(k) > 0，则惩罚u项恒为正值，当设计点由可行域内部向约束边界移动时，惩罚项的值要急剧增大并趋向无穷 大，于是惩罚函数的值也急剧增大直至无穷大，起到惩罚的作用，使其在迭代过程中始终不 会触及约束边界2. 内点法的迭代步骤(1) 取初始惩罚因子r(0) > 0，允许误差£ > 0 ；(2) 在可行域D内取初始点X (0)，令k = 1 ；(3) 构造惩罚函数9(X,r(k))，从X (k-1)点出发用无约束优化方法求解惩罚函数甲(X, r(k))的极值点 X * (r(k))；( 4)检查迭代终止准则：如果满足X * (r(k)) — X* (r(k-1)) <8] = 10-5 —10-<8 = 10-3 — 10-42Q (X *, r (k))-Q (X *, r(k-1))Q (X *, r D)iH.则停止迭代计算，并以X*(r(k))为原目标函数f (X)的约束最优解，否则转入下一步;根据情况，终止准则还可有如下的形式：f(X(k))-f(X(k-1)) <8r (k 疋-1 -u=1 gu (X )<8<8rIn|g (X)|uu =15)取r(k+1)二 Cr(k),X(o)二 X*(r(k)),k = k +1，转向步骤 3)。
递减系数C = 0.1 — 0.5，常取0.1，亦可取0.02采用内点法应注意的几个问题：(1)初始点X(o)的选取初始点X(0)必须严格在可行域内，满足所有的约束条件，避免为约束边界上的点如果约束条件比较简单，可以直接人工输入；若问题比较复杂，可采用随机数的方式产 生初始点 X (0)，具体方程参照复合形法介绍2)关于初始惩罚因子r(0)的选择实践经验表明，初始惩罚因子r(0)选的恰当与否，会显著地影响内点法的收敛速度，甚至解题的成败若r(0)值选得太小，则在新目标函数即惩罚函数Q (X,r(k))中惩罚项的作用就会很小， 这时求Q(X, r(k))的无约束极值，犹如原目标函数f (X)本身的无约束极值，而这个极值点 又不大可能接近f (X)的约束极值点，且有跑出可行域的危险相反，若r(0)值取得过大，则开始几次构造的惩罚函数Q(X, r(k))的无约束极值点就会离约束边界很远，将使计算效率“ 口 求出中心路径（x（岀M3Vw（卩）），再令pto,降低可耳取极极）爾即可求得但多数情况是取题的最优解m1在新目u—l u通常，当初始点X（0）是一个严格的内点时，则应使惩罚项r（o）y标函数9 （X,r（k））中所起的作用与原目标函数f （X（0））的作用相当，于是得倘若约束区域是非凸的且初始点X（0）亦不靠近约束边界，贝I打（0）的取值可更。