# Minimizing a General n-Dimensional Linear Program

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.

• The second constraint involves a quadratic expression and hence is not linear. – Rob Pratt Nov 14 at 2:26

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?