现代优化方法.doc

摘要：现代内点法理论的基本思想是，起点在“宇宙中心”，用梯度法从起点寻找一个下降方向，因为从起点走出去第一步效果最好，则设法使每一次走出去都是第一步（用非线性的投影变换有回到新的宇宙中心，就不会碰到边界）。Karmarkar 提出的内点法是建立在单纯形结构之上的,但与单纯形法沿着可行域边界寻优不同,内点法从初始内点出发, 沿着最速下降方向, 从可行域内部直接走向最优解。内点法是在可行域内部寻优, 对于大规模线性规划问题, 当约束条件和变量数目增加时, 内点法的迭代次数变化较少。内点法是一种具有多项式时间复杂性的线性规划算法，其收敛性和计算速度均优于单纯形法，计算时间比单纯形法快50倍。内点法在形式上与经典障碍法等价，而且对于线性、非线性问题可以统一解法。 关键词：内点法；梯度法；最优解；线性规划； Interior-point method ABSTRACT：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, wont 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 提出了线性规划问题的第一个多项式时间算法——椭球法, 取得了理论上的重大突破。但是由于受有限精度计算的限制, 椭球法的应用效果还不能与单纯形法相比拟。 现代内点理论的基本思想