What are the possible methods of quadratic cost minimization within the unit $n$-cube?

Question

Before you read this, please understand I'm not a specialist in optimization so I may be ignorant of many well-known results in that field.

I am interested in hearing about methods for minimizing the quadratic cost $L(u) = u^{tr}Mu$, where $u \in R^n$ and $M$ is an $n\times n$ positive semidefinite matrix, subject to the constraint $0 < \sum_{i=1}^n|u_i| \leq 1$.

I have a feeling some form of dynamic programming can do this, but I would need to be pointed to some relevant literature.

Edit: I think this is phrased poorly and most people who tried to help are confused. I have tried deleting it and trying again, but it won't allow me to delete due to there being an answer.

While I was not deliberately trying to redefine the problem after someone answered--$u = 0$ is just not reasonable given the application--trying to make myself clear made it turn out that way.

I also don't think the problem I want to communicate is unsolvable; that would again be unreasonable, so I must have screwed up. I am just going to abandon this failure to launch and try again.

Answer 1

A meta answer:

Have you read the Wikipedia article about quadratic programming? It, and the references it points to, give an overview that might be hard to get from this forum. I have several comments: (1) this is a highly technical and active area of research, so sorting out the landscape is hard, (2) very often practicalities like availability of this or that software package determine your algorithm choice, and (3) each piece of software for convex minimization seems to expect problems to be presented in a slightly different format, which may or may not cause headaches for you.

As an instance of this last point: in your problem statement you use the word cube to describe your feasible set, but in the body of your post you use the formula $\sum_i |u_i|\le 1$ which does not cut out a cube. This matters because a cube in $n$ dimensions is cut out by $2n$ linear inequalities and your figure is cut out by $2^n$ linear inequalities. So any software that demands linear inequality constraints poses a problem for you, if say $n>20$. A fix is to note that figure has only $2n$ vertices, so your feasible points can be represented as convex combinations of vertices, by parameterizing by a $2n+1$-simplex. I offer this not as a recommendation for what to do, but rather as an instance of what kinds of headaches and what kinds of headache-avoiding shifts might be ahead for you.

My advice, if the problem you posed is of importance to you: make friends with a numerical analyst or minimization expert, and be guided by what they say.

Answer 2

Before the OP redefined the problem: Well, I think $u=0$ solves your minimization problem.

After the OP redefined the problem: Let $C$ denote the set of constraint-obeying $u$ vectors. We have $\inf_{u\in C} L(u) = 0$ but the value $0$ is not attained by any $u\in C$. That is, there is a sequence of $u^{(k)}\in C$ such that $\lim_{k\to\infty} L( u^{(k)}) = 0$ and $\lim_{k\to\infty} u^{(k)} = 0.$ The set $C$ is open; its closure $\overline C$ contains $u=0$, which minimizes $L$ on $\overline C$.

By the way, the set cut out by the inequality $\sum_{i=1}^n|u_i|\le1$ is not a cube but some kind of higher-dimensional octohedron. Putting in $0\le \dots$ simply removes the $0$ point.