# optimization on two "max" function

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

• Lagrange multipliers is for equality constraints. Different methods are needed for inequality constraints. Anyway, in principle you could solve the larger problem $\min ay+bz$, where $y$ and $z$ satisfy some inequality constraints. I am not quite sure how this helps, though. I think in this case I would just write the function piecewise: for $x<-1$ you have one formulation, for $x$ between $-1$ and $1$ you have another, for $x>1$ you have another.
– Ian
May 11, 2015 at 19:58
• Thanks! In general case I think the Lagrange multipliers work for inequal constraint: mat.gsia.cmu.edu/classes/QUANT/NOTES/chap4/node6.html May 11, 2015 at 20:04
• No, at least ordinary Lagrange multipliers are not intended for inequality constraints. They can be adapted with penalty methods in some cases but that's not what the ordinary method is for.
– Ian
May 11, 2015 at 20:04
• I think this question is more like a expansion of optimization problem in hinge loss such as SVM. You offer a good idea to write the function piecewise but I am worried when the functions become more complex, it might be not easy. May 11, 2015 at 20:06
• The KKT formulation is related to the ordinary method of Lagrange multipliers, in that it arises from the construction of a Lagrangian function, but it is misleading to call them the same thing.
– Ian
May 11, 2015 at 20:06

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.

• Thanks! Only one concern about this, do we need an additional constraint for \xi and \psi? Because it looks like one is 1-yf and the other is 1+yf so they are not "independent". May 12, 2015 at 13:36
• I really hope I have 15 reputation to praise your answer... Thanks a lot! May 12, 2015 at 15:20

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?

• Thanks for the quick reply! I see it. Sorry that I asked the question in an unclear way. Let me modify it a bit... May 11, 2015 at 20:09
• I hope it is kind of clear... May 11, 2015 at 20:18