论文标题
一类线性约束最小优化问题的最佳条件和数值算法
Optimality Conditions and Numerical Algorithms for A Class of Linearly Constrained Minimax Optimization Problems
论文作者
论文摘要
众所周知，有许多用于求解非平滑最小问题问题的数值算法，非平滑度最小值问题的数值算法非常罕见。本文旨在讨论最佳条件，并开发与关节线性约束的最小值问题的实用数值算法。首先，我们使用近端映射和KKT系统的属性来建立最佳条件。其次，我们提出了一个用于最小值问题的交替坐标算法的框架，并分析其收敛属性。第三，我们将近端梯度多步上升效果（PGMSAD）作为数值算法，并证明该方法可以在$ {\ cal o}（\ cal o}（ε^{ε^{ - 2}} $ log log log} \ its $ {\ cal o}中，该方法可以找到$ε$ - 稳定点。最后，我们将PGMSAD应用于广义的绝对值方程，广义线性投影方程和线性回归问题，并报告PGMSAD对大规模优化的效率。
It is well known that there have been many numerical algorithms for solving nonsmooth minimax problems, numerical algorithms for nonsmooth minimax problems with joint linear constraints are very rare. This paper aims to discuss optimality conditions and develop practical numerical algorithms for minimax problems with joint linear constraints. First of all, we use the properties of proximal mapping and KKT system to establish optimality conditions. Secondly, we propose a framework of alternating coordinate algorithm for the minimax problem and analyze its convergence properties. Thirdly, we develop a proximal gradient multi-step ascent decent method (PGmsAD) as a numerical algorithm and demonstrate that the method can find an $ε$-stationary point for this kind of nonsmooth nonconvex-nonconcave problem in ${\cal O}(ε^{-2}\logε^{-1})$ iterations. Finally, we apply PGmsAD to generalized absolute value equations, generalized linear projection equations and linear regression problems and report the efficiency of PGmsAD on large-scale optimization.
