Optimization Algorithm And Complexity Analysis For One-side Nonconvex Saddle Point Problem

In recent years,one-side nonconvex saddle point problems pay a lot of attention in the field of machine learning and signal processing.This problem belongs to non-differentiable optimization problem,which cannot be solved directly by traditional optimization algorithms,such as feasible direction method,penalty function method.In this paper,we consider two special cases of one-side non-convex saddle point problem:nonconvex-linear saddle point problem and convex-nonconcave saddle point problem.We propose an alternate projection gradient algorithm for the nonconvex-linear saddle point problem.At each iteration,we precisely solve the inner maximization problem over objective function plus some regularization terms for the maximized variable.For the minimized variable's update,a simple projected gradient descent step is performed.The iteration complexity of the proposed algorithm is proved to be O(?-3)to find an ?-firstorder Nash equilibrium point of the nonconvex-linear saddle point problem.Moreover,we apply it to solve the weighted maximin dispersion problem and numerical results show that it outperforms the state-of-the-art algorithms.For convex-nonconcave saddle point problem,we propose a multi-step projected gradient method.At each iteration,we use the accelerated projection gradient method to solve the outer minimization problem over objective function plus some regularization terms for the minimized variable.For the maximized variable's update,we perform the projection gradient method.We prove that the complexity of multi-step projected gradient method is O(?-3.5 log2 ?-1)to find an ?-first-order Nash equilibrium point of convex-nonconcave saddle point problem.To the best of our knowledge,it is the second method with the best iterative complexity bound for solving convex non-concave saddle point problem by far.Moreover,we apply it to the chebyshev center problem which can be reformulated as a convex non-concave saddle point problem and compare with the unified single-loop alternating gradient projection algorithm which is the first method for solving convex-nonconcave saddle point problem.The numerical results show that our algorithm performs better in most cases.The contents of this paper is divided into four chapters.Chapter 1 is devoted to an overview.We firstly introduces the nonconvex and nonsmooth problem and then we outline the research background and recent related works of one-side nonconvex saddle point problem.Meanwhile,we summarize the structure of this paper and explain the notations and concepts that are used in following.In chapter 2,we consider the nonconvex-linear saddle point problem.We propose an alternate projection gradient algorithm and analyze its complexity for solving this problem.Moreover,we apply it to solve the weighted maximin dispersion problem to evaluate the performance of the algorithm.In chapter 3,we focus on the convex-nonconcave saddle point problem and propose a multi-step projected gradient method to solve it.Then we analyze the complexity of this algorithm and apply it on the chebyshev center problem.Chapter 4 summarizes the whole paper and reflects on the issues that can be studied in the future.