# How to solve this optimization problem with abs object function?

Helo, every one. May I ask for help about how to solve this problem.

\begin{align} & \text{max}_{x_i} \quad |\sum_{i=1}^{4} a_i x_i | \\ & s.t. \quad \sum_{i=1}^4 x_i^2=1 \end{align}

The goal is to find the optimal $x_i$, the $a_i$ is known.

Thank you very much. Anyone can give me some tips?

Best

• I just learned this problem may be called: quadratically constrained linear programing. But I have no clues. – user3909401 Sep 26 '14 at 11:21

It looks like you are optimizing over the surface of a ball. That constraint is non-convex, but I think with your objective the solution will always be on the surface, so you can relax it to be $\leq 1$ and now its convex - thats a good start. So lets make that change.

Now if you ignore the absolute sign, you are maximizing a linear objective over a ball. Thats easy. So solve two optimization problems

\begin{align} & \text{max}_{x_i} \quad \sum_{i=1}^{4} a_i x_i \\ & s.t. \quad \sum_{i=1}^4 x_i^2 \leq 1 \end{align}

and

\begin{align} & \text{max}_{x_i} \quad -\sum_{i=1}^{4} a_i x_i \\ & s.t. \quad \sum_{i=1}^4 x_i^2 \leq 1 \end{align}

and take the best of the two. Both these problems have a closed form solution - you can use the Karush-Kuhn-Tucker conditions to find it, or just throw it into a solver like Gurobi/CPLEX/Mosek/IPOPT/whatever you have a available that can handle quadratic constraints.

• Thanks, it's very helpful for me. The results should be $x_i=\pm \frac{a_i}{\sqrt{\sum_{k=1}^4 a_k^2}}$. – user3909401 Sep 26 '14 at 15:55
• And the sign can be fixed by noticing that the sum is maximal if all terms have the same sign, so choosing $\mathsf{sign}(x_i)=\mathsf{sign}(a_i)$ removes the redundancy, makes all terms and hence the sum positive, and so the absolute value is redundant. Then, the problem reduces to a standard differentiable optimization problem. – Christian Clason Sep 27 '14 at 18:13
• @user3909401 Sounds about right; your problem is equivalent to computing the projection of the vector $a$ onto the unit ball (assuming $\|a\|_2 \geq 1$). – Christian Clason Sep 27 '14 at 20:01