3

If I have a nested absolute value equation such as:

y = |||3x-2|-|8-7x|| -2|x+3||

where all terms in absolute values are linear, what is the complexity (Big -O) of the upper bound on the amount of "pieces" in the equivalent piecewise equation, in terms of the amount of absolute values, or nesting depth of absolute values?

Edit: I found a similar problem and solution here: Minimizing the sum of absolute values with a linear solver I'm wondering how the introduction of nested absolute values changes the answer. Edit2: I was planning on doing this to solve an optimization question where I minimize the max over n linear terms, like in the link, but polynomial time is required, so since my method is turning my optimization problem into exponentially many linear programming problems, I can't do this. Does the method in the link apply to nested absolute values?

Phillip Feldman
  • 171
  • The method in the link only applies to absolute value expressions of a very specific form: when we minimize the sum of absolute values. Even minimizing something like $|x|, - ,|x-1|$ is out of the question, since this is no longer a convex function. We could write the problem as an integer linear program without too much trouble, but that doesn't get you to polynomial time algorithms. – Misha Lavrov Nov 14 '22 at 23:25

1 Answers1

3

Let's define the "complexity" of a piecewise linear function as the number of intervals on which we need to give it separate definitions.

Suppose that $f(x)$ and $g(x)$ are piecewise linear functions with complexity $c_f$ and $c_g$ respectively.

  • To write $|f(x)|$ as a piecewise linear expression, we might need to break up each of $f$'s intervals in two: one where $f$ is positive and one where $f$ is negative. Therefore the complexity of $|f(x)|$ is at most $2c_f$.
  • The sum $f(x) + g(x)$ changes behavior at up to $(c_f - 1) + (c_g - 1)$ points: the points where $f$ or $g$ changes behavior. Therefore the complexity of $f(x) + g(x)$ is at most $c_f + c_g - 1$.
  • Some simple modification like $a f(x) + b$ has the same complexity as $f$.

So we can inductively argue that an expression with $k$ absolute values has complexity at most $2^k$. This is tight, for example for an expression like $$ |||||x-16|-8|-4|-2|-1|. $$ We can give better bounds with some assumptions on the "shape" of the expression, since nesting absolute values doubles the complexity at each step, but adding together two expressions is only additive. For example, if we add together two expressions with $5$ absolute values in each, that has complexity at most $2^5 + 2^5 - 1 = 63$, rather than the $2^{10} = 1024$ we could get from a single expression with $10$ absolute values in it.

Misha Lavrov
  • 142,276