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

$\endgroup$
  • $\begingroup$ I just learned this problem may be called: quadratically constrained linear programing. But I have no clues. $\endgroup$ – user3909401 Sep 26 '14 at 11:21
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.

$\endgroup$
  • $\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 '14 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 '14 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 '14 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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