2016/05/10 by Chernov, Alexey, Dvurechensky, Pavel, Gasnikov, Alexander
#49M29 #49M37 #65K05 #90C06 #90C25 #90C30 #FOS: Mathematics #G.1.6 #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.1605.02970
In this paper we consider a class of optimization problems with a strongly convex objective function and the feasible set given by an intersection of a simple convex set with a set given by a number of linear equality and inequality constraints. A number of optimization problems in applications can be stated in this form, examples being the entropy-linear programming, the ridge regression, the elastic net, the regularized optimal transport, etc. We extend the Fast Gradient Method applied to the dual problem in order to make it primal-dual so that it allows not only to solve the dual problem, but also to construct nearly optimal and nearly feasible solution of the primal problem. We also prove a theorem about the convergence rate for the proposed algorithm in terms of the objective function and the linear constraints infeasibility.