On Lipschitz optimization based on gray-box piecewise linearization


Abstract:

We address the problem of minimizing objectives from the class of piecewise differentiable functions whose nonsmoothness can be encapsulated in the absolute value function. They possess local piecewise linear approximations with a discrepancy that can be bounded by a quadratic proximal term. This overestimating local model is continuous but generally nonconvex. It can be generated in its abs-normal form by a minor extension of standard algorithmic differentiation tools. Here we demonstrate how the local model can be minimized by a bundle-type method, which benefits from the availability of additional gray-box information via the abs-normal form. In the convex case our algorithm realizes the consistent steepest descent trajectory for which finite convergence was established earlier, specifically covering counterexamples where steepest descent with exact line-search famously fails. The analysis of the abs-normal representation and the design of the optimization algorithm are geared toward the general case, whereas the convergence proof so far covers only the convex case.

Año de publicación:

2016

Keywords:

  • abs-normal form
  • Algorithmic differentiation
  • Piecewise linearity
  • Nonsmooth optimization
  • bundle methods

Fuente:

scopusscopus

Tipo de documento:

Article

Estado:

Acceso restringido

Áreas de conocimiento:

  • Optimización matemática
  • Optimización matemática
  • Optimización matemática

Áreas temáticas:

  • Ciencias de la computación