A Prediction-Correction Proximal Method for Convex Optimization With Linear Equality and Inequality Constraints

This paper presents a prediction-correction proximal method (PCPM) for the general non-smooth convex optimization problem with linear equality and inequality constraints. The proposed algorithm includes three crucial points, i.e., proximal-point regularizer, primal-dual method, and inertial update rule. For the first point, we use a proximal quadratic-form term to regularize the Lagrangian function to maintain the strong-convex property for the primal and dual subproblems. Then a primal-dual method is adopted to update the predicted solutions of primal and dual subproblems, which are subsequently corrected by an inertial update rule. An alternating iterative procedure is carried out between the primal-dual method and the inertial update rule to find the optimal solution. We present the convergence analysis based on the strongly convex characteristic of the proximal operator and the saddle-point theorem and prove that our algorithm has the worst-case <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal {O}({1}/{k})$</tex-math></inline-formula> convergence rate for the general non-smooth convex optimization problems. Furthermore, we present an algorithmic extension, i.e., E-PCPM, to solve the separable convex optimization problems. The numerical experiments on a non-smooth convex optimization problem, a multi-block separable convex optimization problem, and a networked optimization problem have verified the validity and performance of our method.