5
$\begingroup$

I have a problem similar to Markowitz portfolio optimization that I would like to transform into second-order cone programming. I have a linear objective function with a quadratic constraint (assuming that I can take the square on both sides of the constraint to make it quadratic).

Assume that $X$ is a vector of decision variables. The objective function and the constraint are below. How can I transform it into a second-order cone constraint? \begin{align}\min&\quad c^\top X\\\text{s.t.}&\quad\sqrt{\sum_{i,j}^n(W_i\cdot X)^2+(W_j\cdot X)^2+2\rho_{i,j}(W_i\cdot X)\cdot(W_j\cdot X)}\le b\end{align} where

  • $W_i$ and $W_j$ are matrices of constant values of the same dimension as $c^\top$

  • $\rho_{i,j}$ are correlation coefficients, the matrix generated by it can be assumed to be positive semi-definite

  • $b$ is a constant.

For example, when $n=2$, the constraint is given by $$\sqrt{(W_1\cdot X)^2+(W_2\cdot X)^2+2\rho_{1,2}(W_1\cdot X)\cdot(W_2\cdot X)}\le b.$$

I would like to understand this both when it is expressed in a more compact matrix form and also when written in the more simplified summation form (as in the question).

For example, enter image description here

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Revamp of my answer given the example now provided.

Let there be $n$ VaR factors. Let $R$ = $n$ by $n$ matrix of correlations (the 2nd matrix in your example) of the VaR factors.

Let $W$ = $n$ by $1$ vector whose ith element is $W_i$.

The VaR portfolio constraint can be expressed as $$W^TRW \le b^2.$$

This constraint can be rewritten in terms of $X$ as follows:

Let $M$ be the 1st matrix in your example. Then it is the case that $$W = MX.$$ Using that, the VaR portfolio constraint can then be expressed as a convex quadratic inequality constraint in terms of $X$ (resulting in QCQP, or actually, QCLP)

$$X^T(M^TRM)X \le b^2.$$

Let $F$ be the upper triangular Cholesky factor of $M^TRM$. I.e., $M^TRM = F^\top F$. Then the quadratic inequality constraint can alternatively be expressed as a Second Order Cone Constraint

$$\|FX\|_2 \le b.$$

That is because $X^\top M^TRMX = X^\top F^\top FX = (FX)^\top(FX) = \|FX\|^2_2$.

Alternatively, if $G$ is the upper triangular Choelsky factor of $R$, the Second Order Cone constraint can be expressed as $$\|GMX\|_2 \le b.$$

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thank you Mark. $W_i$ represents the value-at-risk of risk $i$ (such as market, credit risk, etc) of assets $X$. $W_i$ is a vector in the sense it contains value-at-risk for each asset. So $W_1$ and $W_2$ will have different values as they represent VaR for different risks. May I clarify: 1. what does the subscript $2$ represent in your transformation or is it square? 2. In terms of optimization, do I need to set two constraints i.e. $\|FX\|^2\le b$ and $\|FX\|^2\le-b$ in order to deal with the modulus sign? $\endgroup$
    – Sam
    Commented Mar 22, 2020 at 16:41
  • $\begingroup$ Your description is still unclear - we would have to see the original source to resolve that. The subscript 2 means the two-norm, i.e., the Euclidean norm, i.e., the square root of sum of squares. The superscript 2 means squaring. You can either use $X^\top CX \le b^2.$ for a quadratic constraint, or use $\|FX\|_2 \le b.$ for a Second Order Cone Constraint. There is no second branch or constraint needed for $-b$. Presumably, $b\ge 0$; and norm, whether squared or not, is nonnegative. $\endgroup$
    – Mark L. Stone
    Commented Mar 22, 2020 at 17:28
  • $\begingroup$ It appears that your problem is based on some type of quadratic combining of individual risk factors, perhaps somewhat, but not exactly like, the approach in "Portfolio Optimization using Second Order Conic Programming Approach" researchgate.net/publication/… . My original answer does not directly address this formulation. $\endgroup$
    – Mark L. Stone
    Commented Mar 22, 2020 at 19:22
  • $\begingroup$ For clarity reasons, I have edited the question to include an example. Hopefully it should be clearer now $\endgroup$
    – Sam
    Commented Mar 22, 2020 at 20:37
  • $\begingroup$ Answer now revamped based on your example. That answer should now provide SOCP formulation of your exact problem. $\endgroup$
    – Mark L. Stone
    Commented Mar 22, 2020 at 21:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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