An Inexact First-order Primal Dual Algorithm For Convex-concave Saddle-point Problems With Line Search And Its Extension

The convex-concave saddle point problem is a mathematical model,which is currently used in artificial intelligence and practical applications.Its main applications include sparse regression,high-dimensional statistics,image denoising and image reconstruction.The first-order primal dual algorithm is the classical method for solving the saddle point problem,but there are still some shortcomings,such as fixed step size and difficulty in solving certain subproblems exactly.Therefore,based on the idea of inexactly solving subproblems and line search,this paper proposes an inexact primal-dual algorithm with line search,which is discussed in the following three cases.Firstly,the inexact first-order primal pairwise algorithm with line search is proposed and analysed to converge at a rate of O(1/N),where N represents the number of iterations,given that the objective function is convex.Second,the acceleration of the inexact primal dual algorithm with line search is given in the case where some or all of the objective functions are strongly convex,and the convergence rate is shown to be O(1/N~2).At the same time,we generalize the saddle point problem to general problems with additional smooth terms and correspondingly propose an improved inexact primal dual algorithm with line search.The proposed algorithm is a generalised form of the primal dual algorithm,which uses the idea of absolute error to solve the subproblem non-exactly,and introduces a line search step,which changes the drawback that the traditional primal dual algorithm can only take a fixed step,and only needs to update the dual(or primal)variables at each iteration,effectively reducing the computational effort of the algorithm iteration.Finally,numerical experiments were carried out to verify the validity of the proposed algorithms.