Sequential Quadratic Optimization for Nonlinear Optimization Problems on Riemannian Manifolds
Sequential Quadratic Optimization for Nonlinear Optimization Problems on Riemannian Manifolds
复制标题
DOI：
10.1137/20m1370173
复制
发表时间：
2020-09
期刊：
影响因子：
--
通讯作者：
Mitsuaki Obara;Takayuki Okuno;Akiko Takeda
中科院分区：
文献类型：
--
作者：
Mitsuaki Obara;Takayuki Okuno;Akiko Takeda
我们考虑黎曼流形上的等式和不等式约束的优化问题，我们称之为黎曼非线性优化（RNLO）问题。虽然它们有许多应用，但现有的研究是有限的，特别是在算法方面。在本文中，我们提出了黎曼序列二次优化（RSQO），使用线搜索技术与l1罚函数作为扩展的标准SQO算法的非线性优化问题，在欧氏空间黎曼流形。利用并行迁移和指数映射证明了算法的全局收敛性。通过分析RSQO生成的序列与RiemannianNewton方法之间的关系，证明了其局部二次收敛性。我们的算法是第一个解决RNLO问题，具有全局和局部收敛性能的约束优化。实验结果表明，与现有的黎曼罚函数和增广拉格朗日方法相比，RSQO方法具有更高的精度和更稳定的求解能力。
We consider optimization problems on Riemannian manifolds with equality and inequality constraints, which we call Riemannian nonlinear optimization (RNLO) problems. Although they have numerous applications, the existing studies on them are limited especially in terms of algorithms. In this paper, we propose Riemannian sequential quadratic optimization (RSQO) that uses a line-search technique with an l1 penalty function as an extension of the standard SQO algorithm for nonlinear optimization problems in Euclidean spaces to Riemannian manifolds. We prove its global convergence to a Karush-Kuhn-Tucker point of the RNLO problem by means of parallel transport and exponential mapping. Furthermore, we establish its local quadratic convergence by analyzing the relationship between sequences generated by RSQO and the Riemannian Newton method. Ours is the first algorithm for solving RNLO problems that has both global and local convergence properties for constrained optimization. Empirical results show that RSQO finds solutions more stably and with higher accuracy compared with the existing Riemannian penalty and augmented Lagrangian methods.