Dual approaches to the minimization of strongly convex functionals with a simple structure under affine constraints

A. S. Anikin   ; A. V. Gasnikov   ; P. E. Dvurechensky   ; A. I. Tyurin   ; A. V. Chernov

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 57 (2017) no. 8, pp. 1270-1284

Résumé

A strongly convex function of simple structure (for example, separable) is minimized under affine constraints. A dual problem is constructed and solved by applying a fast gradient method. The necessary properties of this method are established relying on which, under rather general conditions, the solution of the primal problem can be recovered with the same accuracy as the dual solution from the sequence generated by this method in the dual space of the problem. Although this approach seems natural, some previously unpublished rather subtle results necessary for its rigorous and complete theoretical substantiation in the required generality are presented.

Bibliographie

[1] Gasnikov A. V., Gasnikova E. V., Nesterov Yu. E., Chernov A. V., “Ob effektivnykh chislennykh metodakh resheniya zadach entropiino-lineinogo programmirovaniya”, Zh. vychisl. matem. i matem. fiz., 56:4 (2016), 523–534, arXiv: 1410.7719 | DOI | Zbl

[2] Nesterov Y., “Primal-dual subgradient methods for convex problems”, Math. Program. Ser. B, 120:1 (2009), 261–283 | DOI | MR

[3] Nemirovski A., Onn S., Rothblum U. G., “Accuracy certificates for computational problems with convex structure”, Mathematics of Operation Research, 35:1 (2010), 52–78 | DOI | MR | Zbl

[4] Devolder O., Exactness, inexactness and stochasticity in first-order methods for large-scale convex optimization, PhD thesis, CORE UCL, March 2013

[5] Nesterov Yu. E., Algoritmicheskaya vypuklaya optimizatsiya, Diss. dokt. fiz.-matem. nauk, MFTI, Dolgoprudnyi, 2013 http://www.mathnet.ru/php/seminars.phtml?option_lang=rus&presentid=8313

[6] Nesterov Yu., “New primal-dual subgradient methods for convex optimization problems with functional constraints”, International Workshop “Optimization and Statistical Learning” (January 11–16, France, Les Houches, 2015) http://lear.inrialpes.fr/workshop/osl2015/program.html

[7] Nesterov Yu., Complexity bounds for primal-dual methods minimizing the model of objective function, CORE Discussion Papers No 2015/03, 2015

[8] Anikin A., Dvurechensky P., Gasnikov A., Golov A., Gornov A., Maximov Yu., Mendel M., Spokoiny V., “Modern efficient numerical approaches to regularized regression problems in application to traffic demands matrix calculation from link loads”, Proc. Internat. conference ITAS-2015 (Russia, Sochi, September, 2015), arXiv: 1508.00858

[9] Gasnikov A. V., Gasnikova E. V., Ershov E. I., Dvurechenskii P. E., Lagunovskaya A. A., “Poisk stokhasticheskikh ravnovesii v transportnykh modelyakh ravnovesnogo raspredeleniya potokov”, Tr. MFTI, 7:4 (2015), 114–128, arXiv: 1505.07492

[10] Gasnikov A. V., Dvurechenskii P. E., Dorn Yu. V., Maksimov Yu. V., “Chislennye metody poiska ravnovesnogo raspredeleniya potokov v modeli Bekmana i modeli stabilnoi dinamiki”, Matem. modelirovanie, 28:10 (2016), 40–64, arXiv: 1506.00293

[11] Gasnikov A. V., Dvurechenskii P. E., Kamzolov D. I., Nesterov Yu. E., Spokoinyi V. G., Stetsyuk P. I., Suvorikova A. L., Chernov A. V., “Poisk ravnovesii v mnogostadiinyikh transportnykh modelyakh”, Tr. MFTI, 7:4 (2015), 143–155 https://mipt.ru/upload/medialibrary/ffe/143-155.pdf

[12] Gasnikov A. V., Dvurechenskii P. E., Nesterov Yu. E., Spokoinyi V. G., Suvorikova A. L., “Superpozitsiya metoda balansirovki i universalnogo gradientnogo metoda dlya poiska entropiino-sglazhennogo baritsentra Vassershteina i ravnovesii v mnogostadiinykh modelyakh transportnykh potokov”, Tr. MFTI, 8:3 (2016), 5–24, arXiv: 1506.00292

[13] Gasnikov A. V., Dvurechenskii P. E., Usmanova I. N., “O netrivialnosti bystrykh (uskorennykh) randomizirovannykh metodov”, Tr. MFTI, 8:2 (2016), 67–100, arXiv: 1508.02182 | Zbl

[14] Allen-Zhu Z., Orecchia L., Linear coupling: an ultimate unification of gradient and mirror descent, 2014, arXiv: 1407.1537

[15] Nemirovskii A. S., Yudin D. B., Slozhnost zadach i effektivnost metodov optimizatsii, Nauka, M., 1979 http://www2.isye.gatech.edu/ñemirovs/Lect_EMCO.pdf

[16] Zorich V. A., Matematicheskii analiz zadach estestvoznaniya, MTsNMO, M., 2008

[17] Polyak B. T., Vvedenie v optimizatsiyu, Nauka, M., 1983

[18] Chernov A., Dvurechensky P., Gasnikov A., “Fast primal-dual gradient method for strongly convex minimization problems with linear constraints”, Internat. Conference Discrete Optimizat. and Operat. Research (Vladivostok, Russian Iceland, September 19–23, 2016), Springer, 584–595, arXiv: 1605.02970 | MR

[19] Nemirovski A., Lectures on modern convex optimization analysis, algorithms, and engineering applications, SIAM, Philadelphia, 2013 http://www2.isye.gatech.edu/ñemirovs/Lect_ModConvOpt.pdf

[20] Nesterov Yu., “Gradient methods for minimizing composite functions”, Math. Prog., 140:1 (2013), 125–161 | DOI | MR | Zbl

[21] Nesterov Yu., Universal gradient methods for convex optimization problems, CORE Discussion Paper No 2013/63, 2013

[22] Gasnikov A. V., Dvurechenskii P. E., “Stokhasticheskii promezhutochnyi metod dlya zadach vypukloi optimizatsii”, Dokl. AN, 467:2 (2016), 131–134 | DOI

[23] Dvurechensky R., Gasnikov A., “Stochastic intermediate gradient method for convex problems with inexact stochastic oracle”, J. Optimizat. Theory and Appl., 2016, 1–25, arXiv: 1411.2876 | MR

[24] Gasnikov A. V., Dvurechenskii P. E., Nesterov Yu. E., “Stokhasticheskie gradientnye metody s netochnym orakulom”, Tr. MFTI, 8:1 (2016), 41–91, arXiv: 1411.4218

[25] Gasnikov A. V., Kamzolov D. I., Mendel M. A., “Osnovnye konstruktsii nad algoritmami vypukloi optimizatsii i ikh prilozheniya k polucheniyu novykh otsenok dlya silno vypuklykh zadach”, Tr. MFTI, 8:3 (2016), 25–42, arXiv: 1603.07701 | Zbl

[26] Pǎtraşcu A., Efficient first order methods for sparse convex optimization, PhD Thesis, University Politehnica of Bucharest, 2015 http://acse.pub.ro/person/ion-necoara/

[27] Cox B., Juditsky A., Nemirovski A., Decomposition techniques for bilinear saddle point problems and variational inequalities with affine monotone operators on domains given by linear minimization oracles, 2015, arXiv: 1506.02444 | MR

[28] Gasnikov A. V., Dmitriev D. Yu., “Ob effektivnykh randomizirovannykh algoritmakh poiska vektora PageRank”, Zh. vychisl. matem. i matem. fiz., 55:3 (2015), 355–371, arXiv: 1410.3120 | DOI | Zbl

[29] Nikaido Kh., Vypuklye struktury i matematicheskaya ekonomika, Mir, M., 1972

[30] Gasnikov A. V., Nesterov Yu. E., Universalnyi metod dlya zadach stokhasticheskoi kompozitnoi optimizatsii, arXiv: 1604.05275

[31] O'Donoghue B., Candes E., “Adaptive restart for accelerated gradient schemes”, Foundations of Computational Mathematics, 15 (2015), 715–732 | DOI | MR | Zbl