论文标题
在对称锥上线性优化的地球内点方法
A geodesic interior-point method for linear optimization over symmetric cones
论文作者
论文摘要
我们开发了一种新的内点方法（IPM），以进行对称 - 线性，二阶 - 二阶和半决赛编程的共同概括。与经典的IPM相反，我们使用锥体的测量线而不是线性约束的内核进行了更新。这种方法产生了一种原始的偶对称，比例 - 不变和无线搜索算法，该算法仅使用标准原始二极管IPM的一半变量。使用基本参数，我们建立了与标准的平方root-n结合匹配的多项式时间收敛。最后，我们证明了一个长期变体的全局融合，并提供了支持所有对称锥体的实现。对于线性编程，我们的算法还原为日志域中的中央路径跟踪。
We develop a new interior-point method (IPM) for symmetric-cone optimization, a common generalization of linear, second-order-cone, and semidefinite programming. In contrast to classical IPMs, we update iterates with a geodesic of the cone instead of the kernel of the linear constraints. This approach yields a primal-dual-symmetric, scale-invariant, and line-search-free algorithm that uses just half the variables of a standard primal-dual IPM. With elementary arguments, we establish polynomial-time convergence matching the standard square-root-n bound. Finally, we prove global convergence of a long-step variant and provide an implementation that supports all symmetric cones. For linear programming, our algorithms reduce to central-path tracking in the log domain.
