2
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$
    – Piero D'Ancona
    Aug 31, 2010 at 15:35

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.