I am currently studying linear programming and am attempting to solve:

minimize $c^Tx$

subject to $\sum_{i=1}^{n}x_i=0$, and $\sum_{i=1}^{n}x_i^2 = 1$.

From the second constraint I know that: $-1\le x_i \le 1$, which can be split up into two separate inequalities. This in turn implies that $\sum_{i=1}^n|x_i| \le n$. I am unsure what to do from here, and whether or not the last inequality is useful in solving the problem.

Any help would be greatly appreciated, thanks.

  • 2
    $\begingroup$ The second constraint involves a quadratic expression and hence is not linear. $\endgroup$ – Rob Pratt Nov 14 '19 at 2:26

As Rob points out, this is isn't a linear program. However, you can still solve it.

Start by thinking about minimizing $c^t x$ over the unit sphere. If you draw some pictures in $2D$, you will guess an answer. You can verify it using the Cauchy-Schwartz inequality. Now extend to $\mathbb{R}^n$.

Now you can extend your solution to the problem you gave. Does the component of $c$ orthogonal to the plane defined by $\{ \sum x_i = 0 \}$ matter?


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.