0
$\begingroup$

I want to solve a QCQP in Python. It is a problem from finance: maximise return (linear function) given some linear constraints and one quadratic constraint that turns it into a QCQP. Formally,

$$\begin{array}{ll} \text{maximize} & c^T x\\ \text{subject to} & x^T \Sigma x \le \sigma^2\\ & Ax \le b\end{array}$$

The matrix $\Sigma$ is referred to as the covariance matrix and it is a symmetric positive semidefinite matrix. However, matrix $A$ doesn't need to be. In $A$ we have constraints of the type to bound the sum of subsets of $x$, like

$$\sum_{j\in J} a_{ij}x_j\le b_i$$

where $J \subset\{1,\dots,n\}$ with $n$ indicating the dimension of $x$.

I want to solve this is Python. What are reliable packages out there to achieve this? Important is it should be easy to solve it for generic $A$, i.e., one whose dimension (how many constraints) I don't know a priori. For convex problems, I've used cvxopt which works like a charm for this kind of "dynamic" constraints.

An example of A with two rows is given below:

    temp = np.asarray([[-0.02  , -0.025 , -0.0275, -0.0325, -0.035 , -0.0525, -0.05  ,
            -0.025 , -0.0525, -0.0625, -0.0525, -0.055 , -0.0675, -0.0625,
            -0.08  , -0.08  , -0.06  , -0.0725, -0.0625, -0.0425, -0.0375],
           [-1.    , -0.    , -0.    , -0.    , -0.    , -0.    , -0.    ,
            -0.    , -0.    , -0.    , -0.    , -0.    , -0.    , -0.    ,
            -0.    , -0.    , -0.    , -0.    , -0.    , -0.    , -0.    ]])

and the vector `b`

    In [367]: b = np.asarray([[-0.02],[0.]])
    Out[367]: 
    array([[-0.02],
           [ 0.  ]])
$\endgroup$
  • 1
    $\begingroup$ Because $\Sigma$ is psd, your problem is always convex, regardless of $A$.. Is there something else you haven't told us? $\endgroup$ – Mark L. Stone Aug 4 '18 at 13:27
  • $\begingroup$ @MarkL.Stone thanks for your remark. I'm not an expert in optimisation, to make that point right at the beginning :) I've originally posted the question on stackoverflow. There people pointed out that if $A$ is not positive semi-definite the problem is not convex and should be moved here. Wikpedia goes in a similar direction en.wikipedia.org/wiki/… saying all the $P_i$ needs to be positive semi-definite. Since I have for $A$ an inequality constraint, $A$ is essentially a $P_i$ on the wikipedia page, no? $\endgroup$ – math Aug 4 '18 at 19:33
  • $\begingroup$ @MarkL.Stone if it really doesn't matter that $A$ might not be positive semi-definite may you share a reference for this? Moreover, if you are right and it is a convex problem how can I then solve it with cvxopt? I will edit the question to make it more cvxopt specific if it really is a convex problem. As I said, I'm not an expert and was more following the stackoverflow comments and wikipedia $\endgroup$ – math Aug 4 '18 at 19:35
  • $\begingroup$ Matrices on LHS of quadratic $\le$ constraint need to be positive semi-definite for the optimization problem to be convex. However, the matrix A is in a linear constraint. All linear constraints, inequality or equality, are convex Not sure if CVXOPT can do QCQP, but it can do Second Order Cone Problem (SOCP). Let C = upper triangular Choelsky factor of $\Sigma$ such that $C^TC = \Sigma$, then your quadratic constraint is $\|Cx\|_2 \le \sigma$, which matches form at cvxopt.org/userguide/… . Or can call cvxopt through cvxpy,. $\endgroup$ – Mark L. Stone Aug 4 '18 at 20:15
  • $\begingroup$ @MarkL.Stone thanks for pointing this out. You might add it as an answer so I can accept it. $\endgroup$ – math Aug 4 '18 at 20:18
3
$\begingroup$

In order for a QCQP to be convex, the quadratic terms needs be be convex. Linear terms are always convex.

With regard to your specific problem, the objective function is convex because it is linear. The quadratic inequality constraint is convex because $\Sigma$ is symmetric positive semi-definite (psd). All linear equality and inequality constraints are convex, regardless of the matrix involved (which may npot even be square, in which case it can't be symmetric or psd).

So your problem is a convex QCQP. Whether or not you enter it as such, the cvx "family" of modeling systems generally reformulate QCQPs as Second Order Cone Problems (SOCPs), and submit them to a solver as such. In your case, let $C$ = upper triangular Choelsky factor of $\Sigma$ such that $C^TC = \Sigma$, then your quadratic constraint is $\|Cx\|_2 \le \sigma$, which matches the form for an SOCP constraint in cvxopt as shown at http://cvxopt.org/userguide/coneprog.html#second-order-cone-programming. Or you can call cvxopt through cvxpy , which is a higher-level and easier to use modeling interface.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.