Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
复制标题
DOI：
10.1109/tsp.2020.2986363
复制
发表时间：
2019-02
影响因子：
5.4
通讯作者：
Songtao Lu;Ioannis C. Tsaknakis;Mingyi Hong;Yongxin Chen
中科院分区：
文献类型：
--
作者：
Songtao Lu;Ioannis C. Tsaknakis;Mingyi Hong;Yongxin Chen
最小-最大问题，也称为鞍点问题，是一类同时最小化和最大化两个变量子集的优化问题。这类问题可用于制定广泛的信号处理和通信（SPCOM）问题。尽管它的流行，大多数现有的理论，这类主要是发展了一些特殊的凹凸结构的问题。因此，它不能用来指导算法设计的许多有趣的问题，在SPCOM中，各种各样的非凸性出现。在这项工作中，我们考虑了一个块明智的单侧非凸极小极大问题，其中的最小化问题由多个块，是非凸的，而最大化问题是（强）凹。我们提出了一类简单的算法混合块逐次逼近（HiBSA），交替执行梯度下降型步骤的最小化块和梯度上升型步骤的最大化问题。该算法的一个关键因素是使用一定的正则化和惩罚序列，稳定算法，并确保收敛。我们表明，HiBSA收敛到一些适当定义的一阶固定的解决方案，可量化的全球利率。为了验证所提出的算法的效率，我们进行了一些问题的数值测试，包括鲁棒学习问题，非凸最小效用最大化问题，并在干扰信道中出现的某些无线干扰问题。
The min-max problem, also known as the saddle point problem, is a class of optimization problems which minimizes and maximizes two subsets of variables simultaneously. This class of problems can be used to formulate a wide range of signal processing and communication (SPCOM) problems. Despite its popularity, most existing theory for this class has been mainly developed for problems with certain special convex-concave structure. Therefore, it cannot be used to guide the algorithm design for many interesting problems in SPCOM, where various kinds of non-convexity arise. In this work, we consider a block-wise one-sided non-convex min-max problem, in which the minimization problem consists of multiple blocks and is non-convex, while the maximization problem is (strongly) concave. We propose a class of simple algorithms named Hybrid Block Successive Approximation (HiBSA), which alternatingly performs gradient descent-type steps for the minimization blocks and gradient ascent-type steps for the maximization problem. A key element in the proposed algorithm is the use of certain regularization and penalty sequences, which stabilize the algorithm and ensure convergence. We show that HiBSA converges to some properly defined first-order stationary solutions with quantifiable global rates. To validate the efficiency of the proposed algorithms, we conduct numerical tests on a number of problems, including the robust learning problem, the non-convex min-utility maximization problems, and certain wireless jamming problem arising in interfering channels.