Fast primal-dual gradient method for strongly convex minimization problems with linear constraints. (English) Zbl 1391.90471

Chernov, Alexey; Dvurechensky, Pavel; Gasnikov, Alexander

Kochetov, Yury (ed.) et al., Discrete optimization and operations research. 9th international conference, DOOR 2016, Vladivostok, Russia, September 19–23, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-44913-5/pbk; 978-3-319-44914-2/ebook). Lecture Notes in Computer Science 9869, 391-403 (2016).

Summary: 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. Quite a number of optimization problems in applications can be stated in this form, examples being entropy-linear programming, ridge regression, elastic net, 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 residual and the linear constraints infeasibility.
For the entire collection see [Zbl 1346.90008].

MSC:

90C25

Convex programming

Keywords:

convex optimization; algorithm complexity; entropy-linear programming; dual problem; primal-dual method