Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Lets say I have an piecewise affine convex function $f(x_1,x_2)$, on which the following operations are possible:

  • Computing $f(x_1,x_2)$.
  • Computing a subgradient to $f$ at $(x_1,x_2)$
  • Computing all breakpoints along a line $a_1x_1 + a_2x_2 = a_3$

What is an efficient algorithm to compute $f$ completely, i.e. to compute all its breakpoints? Are there any general methods?

share|cite|improve this question
Just my first thought: how can you finish your computation without some a priori information on the number of affine pieces? It seems this problem is actually two different problems, the first of which is not too well posed, namely 1) find a point in each affine component, and 2) compute the extent and slopes of each component – Piero D'Ancona Aug 31 '10 at 15:35

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.