Research Initiation: Projective Methods for Global Optimization of Quadratic Programs

研究了Karmarkar算法在二次规划全局优化问题上的推广。单纯形上的二次可行性（QFS）是指确定给定的二次形式在单纯形上是否达到零值的问题。这个问题是二次规划的基础。我们的可行性算法本质上是一种具有正半定形式的QFS算法，它包括重复以下步骤：基于在一个边界球体上的优化，为一个适当定义的势（障）函数计算一个“良好”的下降方向，对势函数进行直线搜索，并使用投影变换进行集中。建议将这种方法推广到不确定情况。尽管不确定情况具有np -硬度，但这种方法的收敛性通常适用于某些特殊情况（甚至在最坏情况下的指数时间），这将导致非凸规划的替代算法，该算法有望与那些在最坏情况下具有指数时间和空间复杂性的算法竞争。在研究了收敛性之后，计划研究这种过程的计算方法。作为计算下降方向的一种替代方法，本文将研究具有投影变换的可行方向方法。我们还计划在我们之前的非凸二次规划方法中研究投影算法的有效性，这些方法需要反复应用线性或凸二次规划算法。最后，计划使用并行架构（如NCUBE10或ETA10超级计算机）实现所得算法。

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.