Graph-Matrix Calculus for Computational Convex Analysis

Bryan Gardiner () and Yves Lucet
Additional contact information
Bryan Gardiner: University of British Columbia Okanagan

Chapter Chapter 12 in Fixed-Point Algorithms for Inverse Problems in Science and Engineering, 2011, pp 243-259 from Springer

Abstract: Abstract We introduce a new family of algorithms for computing fundamental operators arising from convex analysis. The new algorithms rely on the fact that the graph of the subdifferential of most convex operators depends linearly on the graph of the subdifferential of the function. By storing the subdifferential information, the computation of the conjugate is reduced to a matrix multiplication. We explain how other operators can be computed similarly, and present numerical experiments that compare graph-matrix calculus algorithms with piecewise-linear quadratic algorithms from computational convex analysis (CCA), and with a bundle method using warmstarting. Our results show that the new algorithms are an order of magnitude faster. They also add subdifferential calculus to our numerical library, and are very simple to implement.

Keywords: Computer-Aided convex analysis; Computational convex analysis; Convex function; Fenchel conjugate; Legendre–Fenchel transform; Proximal average; Proximal mapping; Subdifferential operator. (search for similar items in EconPapers)
Date: 2011
References: Add references at CitEc
Citations: View citations in EconPapers (2)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-1-4419-9569-8_12

Ordering information: This item can be ordered from
http://www.springer.com/9781441995698

DOI: 10.1007/978-1-4419-9569-8_12

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().