5
$\begingroup$

I have written a small code to do a simple min variance optimisation using CVXOPT, you can see the whole code below

By using solvers.qp(P, q, G, h, A, b) in CVXOPT the code runs fine and it finds a solution

solvers.qp(P, q, G, h, A, b)

I wanted to try a different solver too, hence I used MOSEK by solving the same problem with the following parameters

solvers.qp(P, q, G, h, A, b, solver='mosek') 

When using solver='mosek' the code cannot run and it is giving me the following error

MOSEK error 1295: The quadratic coefficient matrix in the objective is not positive semidefinite as expected for a minimization problem

Can anyone explain why I got this error (have I coded something in the wrong way?) and if there is a workaround to solve the issue I am facing with MOSEK?

import numpy as np
import cvxopt as opt
import mosek
from cvxopt import matrix, solvers

def optimize_portfolio(n, Var_Cov):
        P = opt.matrix (Var_Cov)
        q = opt.matrix(np.matrix(np.zeros((n, 1))))
        G = opt.matrix(np.array(-np.identity(n)))
        h = opt.matrix(np.zeros((n,1)))             
        A = opt.matrix(1.0, (1,n))
        b = opt.matrix(1.0)

        # Finding a solution

        sol = solvers.qp(P, q, G, h, A, b, solver='mosek')
        return sol

### Parameters setup

Var_Cov = np.loadtxt('C:\VAR_COV.txt')
n = len (Var_Cov)

### solve
solution = optimize_portfolio(n, Var_Cov)

# Save Results
Port_Opt = np.matrix(solution['x'])
$\endgroup$
2
  • $\begingroup$ Perhaps Mosek is fussier in assessing whether the matrix P is numerically positive semidefinite. Does solvers.qp actually check whether P is positive semidefinite? Presumably, it either does and is not as fussy as Mosek, or maybe it doesn't (I don;t know)? If somehow solvers.QP doesn't check in some manner whether P is positive semidefinite and it is not, perhaps its results would be dubious in such event. You could try a simple example with solvers.qp , such as P=[1 0;0 -1] which is not positive semidefinite, and see what happens. Is $P^T - P$ all zeros? What is the minimum eigenvalue of P? $\endgroup$ – Mark L. Stone Mar 1 '20 at 17:05
  • $\begingroup$ @MarkL.Stone thanks for your answer the minimum eigenvalue of P is -0.001774412. the matrix is 738x738 and all together there are 11 negative eigenvalues PT−P all zeros $\endgroup$ – Marco_sbt Mar 1 '20 at 17:49
8
$\begingroup$

As determined in the comment exchange to the question, because the matrix P has minimum eigenvalue which is negative, it is not positive semidefinite, and therefore it is a non-convex problem. Therefore, Mosek won't accept it, and as you have seen, provided an error message explaining why.

Apparently, despite billing itself as a "software package for convex optimization", CVXOPT is not checking whether the submitted Quadratic Programming problem (QP) is convex, and passes non-convex QP to the specified solver. In the case of Mosek, the solver rejected it as being non-convex. I don't know what type of solution (e.g., local optimum?) solvers.qp provides when provided a non-convex problem. I wouldn't assume it is any kind of valid solution, and I suggest you carefully examine all solvers.qp solver output to see what it says, as well as examining the solution returned.

https://cvxopt.org/userguide/coneprog.html?highlight=solvers%20qp#quadratic-programming does not specifically address whether convexity is required for use of solvers.qp. It does mention Mosek as a solver option, but does not explicitly state, as it should, that Mosek requires the matrix to be positive semidefinite.

If you want to optimize non-convex QPs, there are a variety of options to solve to either local optimality, or to attempt to solve to global optimality. CPLEX, Gurobi 9.x, BARON, and some other global solvers can attempt to solve non-convex QPs to global optimality. CPLEX, MATLAB Optimization Toolbox's LINPROG, and some other (but by no means all, as you have seen) QP solvers, as well as general non-convex nonlinear local solvers can solve for local minimum of non-convex QPs.

Edit: Looking at your code, the matrix P is labeled Var_Cov, presumably meaning Variance Covariance for your portfolio assets. I.e., a covariance matrix, which should ("must") be positive semidefinite. Given that it is not, I suggest you review the procedure used to generate the covariance matrix. it is either flat out wrong, is based on missing or inconsistent data, or has severe numerical difficulties. That might be the subject for another post at https://stats.stackexchange.com/ or https://scicomp.stackexchange.com/ , in which case please post a link here to any such new post. In such case, what you want to do is fix the procedure for generating the covariance matrix, or at least "repair" it to be positive semidefinite; and then use a convex QP solver, such as Mosek.

$\endgroup$
4
  • $\begingroup$ Thanks for all your answer. Indeed this is a Variance Covariance for a portfolio assets and I am going back to see the proc that generates it. Not sure there is something wrong there as it was done in order to take care of several data issue such as missing data, different life time in the market (i.e stock listed in 2015 vs stock listed in 2017). The vectors of return were matched up to the same dates in order to compute the covariance. For market closure in different exchanges the price was set to be equal to the same as the previous day. Will go check that for sure. Thanks $\endgroup$ – Marco_sbt Mar 2 '20 at 6:15
  • 1
    $\begingroup$ Btw this also proves why checking convexity is a good idea but it in pinpoints errors. $\endgroup$ – ErlingMOSEK Mar 2 '20 at 8:46
  • $\begingroup$ @ErlingMOSEK indeed a convexity checking is a good idea. Again, thanks to Mark for pointing out possible errors. It turned up that the proc to calculate the var_covar is correct while I have some odd datapoint on the price table. I am correcting it to see if the issue can be cleaned out just from data prospective. Will keep you posted. Thanks again all $\endgroup$ – Marco_sbt Mar 2 '20 at 13:06
  • $\begingroup$ Even if your process ir "correct" if calculated in exact arithmetic, it could be "wrong" or bad in finite precision floating point arithmetic. Even a single "variance", if computed in a numerically unstable way, for example as in the horrible formula (5) at sciencebuddies.org/science-fair-projects/science-fair/… can result in a negative value for computed variance, despite being correct if done in exact arithmetic. Things only get hairier when computing a 738x738 covariance matrix, as opposed to a 1 by 1. $\endgroup$ – Mark L. Stone Mar 2 '20 at 14:03

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.