3
$\begingroup$

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

Improve this question
$\endgroup$
1
  • $\begingroup$ I just learned this problem may be called: quadratically constrained linear programing. But I have no clues. $\endgroup$
    – user3909401
    Sep 26, 2014 at 11:21

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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}}$. $\endgroup$
    – user3909401
    Sep 26, 2014 at 15:55
  • 1
    $\begingroup$ 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. $\endgroup$
    – Christian Clason
    Sep 27, 2014 at 18:13
  • $\begingroup$ @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$). $\endgroup$
    – Christian Clason
    Sep 27, 2014 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.