论文标题
适用于二阶锥体程序的四二次收敛顺序编程方法
A Quadratically Convergent Sequential Programming Method for Second-Order Cone Programs Capable of Warm Starts
论文作者
论文摘要
我们为线性二阶程序提出了一种新方法。它基于用于非线性编程的顺序二次编程框架。与内点方法相反，它可以利用主动设定的二次编程子问题求解器的温暖启动功能，并达到局部二次收敛速率。 为了克服在圆锥约束的非线性公式中观察到的非差异性或奇异性，子问题在整个迭代过程中都具有精炼的多面体外近似值近似锥体。对于非重组实例，该算法隐含地识别了最佳溶液在极端位置的锥集。结果，最终步骤与适用的非线性优化问题的常规顺序二次编程步骤相同，从而产生局部二次收敛。 我们证明了该方法的全局和局部收敛保证，并提出了数值实验，这些实验证实该方法可以利用良好的起点，并且与最先进的内部点求解器相比，可以实现更高的精度。
We propose a new method for linear second-order cone programs. It is based on the sequential quadratic programming framework for nonlinear programming. In contrast to interior point methods, it can capitalize on the warm-start capabilities of active-set quadratic programming subproblem solvers and achieve a local quadratic rate of convergence. In order to overcome the non-differentiability or singularity observed in nonlinear formulations of the conic constraints, the subproblems approximate the cones with polyhedral outer approximations that are refined throughout the iterations. For nondegenerate instances, the algorithm implicitly identifies the set of cones for which the optimal solution lies at the extreme points. As a consequence, the final steps are identical to regular sequential quadratic programming steps for a differentiable nonlinear optimization problem, yielding local quadratic convergence. We prove the global and local convergence guarantees of the method and present numerical experiments that confirm that the method can take advantage of good starting points and can achieve higher accuracy compared to a state-of-the-art interior point solver.
