Epigraph projections for fast general convex programming

Po-Wei Wang, Matt Wytock, Zico Kolter
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:2868-2877, 2016.

Abstract

This paper develops an approach for efficiently solving general convex optimization problems specified as disciplined convex programs (DCP), a common general-purpose modeling framework. Specifically we develop an algorithm based upon fast epigraph projections, projections onto the epigraph of a convex function, an approach closely linked to proximal operator methods. We show that by using these operators, we can solve any disciplined convex program without transforming the problem to a standard cone form, as is done by current DCP libraries. We then develop a large library of efficient epigraph projection operators, mirroring and extending work on fast proximal algorithms, for many common convex functions. Finally, we evaluate the performance of the algorithm, and show it often achieves order of magnitude speedups over existing general-purpose optimization solvers.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-wangh16, title = {Epigraph projections for fast general convex programming}, author = {Wang, Po-Wei and Wytock, Matt and Kolter, Zico}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {2868--2877}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/wangh16.pdf}, url = {https://proceedings.mlr.press/v48/wangh16.html}, abstract = {This paper develops an approach for efficiently solving general convex optimization problems specified as disciplined convex programs (DCP), a common general-purpose modeling framework. Specifically we develop an algorithm based upon fast epigraph projections, projections onto the epigraph of a convex function, an approach closely linked to proximal operator methods. We show that by using these operators, we can solve any disciplined convex program without transforming the problem to a standard cone form, as is done by current DCP libraries. We then develop a large library of efficient epigraph projection operators, mirroring and extending work on fast proximal algorithms, for many common convex functions. Finally, we evaluate the performance of the algorithm, and show it often achieves order of magnitude speedups over existing general-purpose optimization solvers.} }
Endnote
%0 Conference Paper %T Epigraph projections for fast general convex programming %A Po-Wei Wang %A Matt Wytock %A Zico Kolter %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-wangh16 %I PMLR %P 2868--2877 %U https://proceedings.mlr.press/v48/wangh16.html %V 48 %X This paper develops an approach for efficiently solving general convex optimization problems specified as disciplined convex programs (DCP), a common general-purpose modeling framework. Specifically we develop an algorithm based upon fast epigraph projections, projections onto the epigraph of a convex function, an approach closely linked to proximal operator methods. We show that by using these operators, we can solve any disciplined convex program without transforming the problem to a standard cone form, as is done by current DCP libraries. We then develop a large library of efficient epigraph projection operators, mirroring and extending work on fast proximal algorithms, for many common convex functions. Finally, we evaluate the performance of the algorithm, and show it often achieves order of magnitude speedups over existing general-purpose optimization solvers.
RIS
TY - CPAPER TI - Epigraph projections for fast general convex programming AU - Po-Wei Wang AU - Matt Wytock AU - Zico Kolter BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-wangh16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 2868 EP - 2877 L1 - http://proceedings.mlr.press/v48/wangh16.pdf UR - https://proceedings.mlr.press/v48/wangh16.html AB - This paper develops an approach for efficiently solving general convex optimization problems specified as disciplined convex programs (DCP), a common general-purpose modeling framework. Specifically we develop an algorithm based upon fast epigraph projections, projections onto the epigraph of a convex function, an approach closely linked to proximal operator methods. We show that by using these operators, we can solve any disciplined convex program without transforming the problem to a standard cone form, as is done by current DCP libraries. We then develop a large library of efficient epigraph projection operators, mirroring and extending work on fast proximal algorithms, for many common convex functions. Finally, we evaluate the performance of the algorithm, and show it often achieves order of magnitude speedups over existing general-purpose optimization solvers. ER -
APA
Wang, P., Wytock, M. & Kolter, Z.. (2016). Epigraph projections for fast general convex programming. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:2868-2877 Available from https://proceedings.mlr.press/v48/wangh16.html.

Related Material