Structure in Optimization: Factorable Programming and Functions

Laurent Hascoët (INRIA Sophia-Antipolis, France) Shahadat Hossain (University of Lethbridge, Canada) Trond Steihaug (University of Bergen, Norway)

Proceedings of Computer and Information Sciences III, 27th International Symposium on Computer and Information Sciences, ISCIS 2012, October 3-4, 2012, Paris, France (10 pages)

Abstract: It is frequently observed that effective exploitation of problem structure plays a significant role in computational procedures for solving large-scale nonlinear optimization problems. A necessary step in this regard is to express the computation in a manner that exposes the exploitable structure. The formulation of large-scale problems in many scientific applications naturally give rise to "structured" representation. Examples of computationally useful structures arising in large-scale optimization problems include unary functions, partially separable functions, and factorable functions. These structures were developed from 1967 through 1990. In this paper we closely examine commonly occurring structures in optimization with regard to efficient and automatic calculation of first- and higher-order derivatives. Further, we explore the relationship between source code transformation as in algorithmic differentiation (AD) and factorable programming. As an illustration, we consider some classical examples.

Keywords: Algorithmic Differentiation, Source code Transformation, Factorable Programming

Full text (pdf)


@inproceedings{HHS12,
  author = {Hasco{\"e}t, L. and Hossain, S. and Steihaug, T.},
  title = "Structure in Optimization: Factorable Programming and Functions",
  booktitle = "Proceedings of the 27th International Symposium on Computer and Information Sciences, ISCIS 2012",
  publisher = "Springer"
  location = "Paris, France",
  doi = "10.1007/978-1-4471-4594-3_46",
  year = "2012"
}