[科普中国]-哈奇扬方法

哈奇扬方法(Khachyian method)亦称椭球法，它是苏联学者肖尔关于非线性规划的椭球方法的基础上提出的，指一种迭代路径迥然异于单纯形方法的求解线性规划的多项式算法。

基本特点哈奇扬方法指一种迭代路径迥然异于单纯形方法的求解线性规划的多项式算法。它具有如下的特点：

1.它是通过包含线性规划约束条件构成的多面体的椭球搜索最优解，不同于单纯形方法是从该多面体的一个顶点迭代到相邻的一个顶点。

2.迭代过程始终保持一个椭球，每迭代一次都得到一个具有相同性质的更小的椭球，因此，人们常把这个方法称为求解线性规划的椭球方法。

3.从算法复杂性的观点看，它是多项式算法，而单纯形方法并不是多项式算法。

此方法由苏联学者哈奇扬(Л.Г.Хачиян)于1979年给出，所以得此名1。

方法步骤哈奇扬方法为考虑如下特征的问题：求x使之满足，其中A为矩阵，其方法步骤为：

1.(初始准备) 记录迭代次数，tj为第j次迭代的解，初始解为分量全为0的n维列向量，取为n阶对角矩阵，其中I为n阶单位阵，为问题的规模，P为矩阵A及向量b中所有非零分量的乘积，在上述数据中，可逆方阵B是构造椭球的关键成分，初始椭球

2.(检验) 若tj满足，则停止迭代，当前解即为所求，若，则停止迭代，说明问题无解。

3.(迭代) 任选一个不满足的不等式，例如，并记，设

转至第2步。

为n维列向量，为n×n矩阵，虽然，哈奇扬方法是求解线性规划的多项式算法，但是其实际迭代上并不产生真实的优越性，这个方法在理论上的影响对线性规划是突破性的，其后产生了一个新方向，即考虑以约束区域的内点为途径，去搜索问题的解，这个方向把线性规划与非线性规划以及组合规划能够更紧密地结合起来1。

本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所