optimization on two "max" function

Question

Anyone knows how to use lagrange multiplier (or KKT conditions) to minimize an objective function such as

$L(\beta,\beta_0)=\sum_{i=1}^n[a_i(1-y_if(x_i))_++b_i(1+y_if(x_i))_+$]

where $a_i$, $b_i$ are all constant, $x_i$ and $y_i$ are known. Also $f(x_i)=\beta_0+\beta x_i$

I kind of remember this optimization can be changed into

min $\sum_i^n[ a_i\xi_i +b_i\psi_i]$

subject to,

$\xi_i \geq0$ and $\xi_i \geq 1-y_if(x_i)$...

something like that and then use http://mat.gsia.cmu.edu/classes/QUANT/NOTES/chap4/node6.html

Answer 1

As you said, your optimization problem can be reformulated as \begin{align*} \text{minimize} & \quad \sum_{i=1}^n a_i \xi_i + b_i \psi_i \\ \text{subject to} & \quad \xi_i \geq 0, \quad i = 1,\ldots, n \\ & \quad \xi_i \geq 1 - y_i (\beta_0 + \beta^T x_i) , \quad i = 1,\ldots, n\\ & \quad \psi_i \geq 0, \quad i = 1,\ldots, n \\ & \quad \psi_i \geq 1 + y_i (\beta_0 + \beta^T x_i), \quad i = 1,\ldots, n. \end{align*} The variables are $\beta_0,\beta$ and also $\xi_i, \psi_i$ for $i = 1,\ldots, n$.

This problem is a linear program, and can be solved with LP software of your choice, such as CVX.

Answer 2

Your function can be rewritten as

$$f(x) = \begin{cases} a (1-x) & x<-1 \\ a(1-x)+b(1+x) & -1 \leq x \leq 1 \\ b(1+x) & x < 1\end{cases}.$$

The first and third case have no critical points, so the only possible local extrema from there are on the boundary: $f(-1)=2a$,$f(1)=2b$. There could also be a local extremum at a critical point in the middle region. Can you finish from here?