# How to deal with the quadratic programming in practice when there is no minimal value

Here is a quadratic programming problem: $$\min\limits_{\textbf{x}} f(\textbf{x}) = \textbf{x}\ M \ \textbf{x}^T$$ $$0.04 \leq \sum\limits_{i=1}^n x_i\leq 0.35$$ $$0 \leq x_i\leq 0.08$$ $$1 \leq \sum\limits_{i=1}^n x_iR_i\leq 2$$ where $\textbf{x} = (x_1,\cdots,x_n),$ $M$ the covariance matrix and $\textbf{R} = (R_1,\cdots,R_n)$ return vector are given.

When I deal with this problem in practice, the dimension of covariance matrix $M$ is very large, then it may be not positive defined and there is no minimal value(maybe there are some additional issues). Is there any method in optimization to manage such case, like looking for a approximate positive defined matrix of $M$ with small error?

In theory a covariance matrix is pos def (in practice we can see some issues). Sometimes it helps to use a slightly different formulation where we use the original data explicitly. Using the mean adjusted returns

$$a_{i,t} = r_{i,t}-\mu_i$$

we can form

\begin{align} \min\>&\sum_t w_t^2\\ &w_t = \sum_i a_{i,t} x_i\end{align}

This formulation sometimes behaves better (guaranteed pos def with a nice diagonal $Q$ matrix). (Complete derivation here).

• thx, but the reasons why there is no minimal value in the real practice when $n$ is very large are weakness of code library or theoretically there is no minimal value for the given problem(include M is not semi-positive)? – A.Oreo Apr 22 '17 at 13:22
• The QP is not convex when the Q matrix is not pos def. Most QP solvers only support convex QPs. – Erwin Kalvelagen Apr 22 '17 at 13:39
• but, the sample covariance matrix computed as this way is always semi-positive, I think theoretically it should be a minimal value(?) – A.Oreo Apr 22 '17 at 14:31
• Minimum value has little to do with convexity (even concave problems have a minimum value -- unless unbounded). For numerical reasons a covariance matrix may not be pos def (see the first sentence in my answer). – Erwin Kalvelagen Apr 22 '17 at 14:59
• yeah, but I am also doubt is it possible because of the weakness of the compute programming when the dimension is too large. – A.Oreo Apr 22 '17 at 15:32