I have a convex piecewise linear function defined on some interval $x \in [a,b]$ $$ f(x) = \max(a_0 x + b_0, ..., a_n x + b_n) $$
where $n$ is large, too large to calculate quickly when used as a piece of of a larger optimization problem I'm working on in CVXpy.
I'd like to understand how to find a "reasonable" convex polynomial approximation $p(x)$ (order $m \ll n$) of that function such that $p(a) = f(a)$, $p(b) = f(b)$ and $p(x) \approx f(x)$ in an $L^2$ sense.
A convex $p(x)$ could then be used instead of $f(x)$ to run quickly run a number of slightly different convex optimizations in real time for users with different needs.
$f(x)$ is fairly well behaved ($a_i$ are evenly-ish spaced and increasing) so I think I don't have to worry too much about corner cases.
Edit: Broader Problem:
The problem is part of properly taking into account trading costs when trading assets in a financial portfolio.
The overall goal is to find a new portfolio $X$ that minimizes the trading costs $TC(X, X^0)$ from our current portfolio $X^0$, costs of being off your ideal portfolio $X^*$ called $CEC(X, X^*)$ and costs in the future if you trade to $X$ which are $FC(X, X^*)$.
$$ \min_X J(X,...) = \min_X [TC(X, X^0) + CEC(X, X^*) + FC(X, X^*)] $$
where $TC$, $CEC$ and $FC$ are all a bit complicated but nicely convex. So $J$ is convex and can be solved quickly.
However, I'm making this framework tax-aware so in addition to the other trading costs each asset $x_i$ in the portfolio $X$ has additional costs
$$ TC_i(x_i, x^0_i) = f_i(x^0_i - x_i) $$
if you are selling $x_i \leq x^0_i$, $TC_i = 0$ if you are buying. The $f_i$ are of the convex piecewise linear form at the top with the $a_i$'s corresponding to the different tax rates of each tax lot. This is unfortunately not convex because of the buy/sell difference but can be broken into two convex subproblems. For the whole problem this gives us 2 to the number of assets total subproblems ($\geq \leq$ for each asset). This is ok as the number of assets can be reasonable but the number of tax lots $n_i$ for each asset $i$ is often large which can slow the process to a crawl.
I (well CVXpy at least) can solve all the subproblems and therefore the total problem in a reasonable amount of time if the $n_i$ are small, but takes too long otherwise. I do have all the info I need for the tax problem the night before, however. So if I can preprocess the $f_i$ into some reasonable convex approximation (polynomial?) the night before I can solve the problem in real time the next day.
Blockquote