MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.