摘要
极大熵方法是求解多约束非线性规划和极大极小问题的一种有效的方法.用它来求解多约束优化问题,一种途径是将多约束用单约束近似,再用增广Lagrange乘子法求解近似问题;另一种途径是用极大熵方法构造精确罚函数的近似.无论是哪一种途径都需要估计乘子的上界.能否构造不引入乘子估计的算法是很有意义的.Karmarkar算法是求解线性规划的一种有效的多项式内点方法.这种方法在每一次迭代时都要作变换,在像空间用内切球近似单纯形的近似问题得到像空间的新的近似解,再作逆变换求得原空间的新的近似解.
An ε-optimal solution to a linear programming problem in Karmarkar standard form is given by reducing its dual problem to a differentiable strictly convex programming via the maximum entropy principle. A perturbation solution of the original linear programming can be achieved by solving this convex programming. Moreover, an algorithm for finding an ε-optimal solution is proposed and the algorithm is proved to be convergent as ε tends to zero. Numerical examples are given to show the high efficiency of the algorithm.
出处
《计算数学》
CSCD
北大核心
1995年第2期160-172,共13页
Mathematica Numerica Sinica
基金
国家自然科学基金资助项目
