Research Initiation: Projective Methods for Global Optimization of Quadratic Programs

本文研究Karmarkar算法推广到全局优化问题， 二次规划的最优化 单纯形上的二次可行性 (QFS)是指确定给定的二次型 在单纯形上得到零值。 这个问题是根本性的 二次规划。 我们的可行性算法 本质上是具有半正定形式的QFS的算法， 包括重复以下步骤：计算"好" 适当定义的势（势垒）的下降方向 基于外接球体、直线上的优化的函数 搜索潜在的功能，并集中使用 射影变换 建议推广这种方法 不确定的情况下。 尽管不确定性的NP-硬度 在这种情况下，这种方法的收敛性一般为一些特殊的 情况下（即使在最坏情况下的指数时间）将导致 一种非凸规划的替代算法， 与那些在最坏的情况下， 时间和空间的复杂性。 在研究了收敛性之后， 来研究这种程序的计算方法。 作为 下降方向计算的替代方法，可行 将研究具有投影变换的方向方法。 还计划研究投影算法的有效性 在我们早期的非凸二次规划方法中， 需要重复应用线性或凸二次型 编程算法 最后，实现了产生的 使用并行架构的算法，如NCUBE 10或ETA 10 超级计算机计划

It is proposed to study extensions of Karmarkar's algorithm to global optimization of quadratic programs. Quadratic Feasibility over Simplex (QFS) refers to the problem of determining if a given quadratic form attains the value of zero over a simplex. This problem is fundamental to quadratic programming. Our feasibility algorithm, which is essentially an algorithm for QFS with a positive semidefinite form, consists of repeating the following steps: calculation of a "good" descent direction for an appropriately defined potential (barrier) function based on optimization over a circumscribing sphere, a line search for the potential function, and centralization using a projective transformation. It is proposed to generalize this approach to the indefinite case. Despite the NP-hardness of the indefinite case, the convergence of this approach in general for some special cases (even in worst-case exponential time) would result in an alternate algorithm for nonconvex programming which is expected to be competitive with those which, in the worst-case, are of exponential time and space complexity. Having studied convergence, it is planned to investigate computational approaches for such a procedure. As an alternate method for the calculation of descent direction, feasible direction methods with projective transformation will be investigated. It is also planned to study the effectiveness of projective algorithms within our earlier methods for nonconvex quadratic programs which require repeated application of a linear or convex quadratic programming algorithm. Finally, the implementation of the resulting algorithms using parallel architectures, such as NCUBE10 or ETA10 supercomputers, is planned.