2
$\begingroup$

Consider the standard second order cone programming problem:

\begin{equation} \begin{array}{ll} \operatorname{maximize} & \bar{p}^{T} x \\ \text { subject to } & \bar{p}^{T} x+\Phi^{-1}(\beta)\left\|\Sigma^{1 / 2} x\right\|_2 \geq \alpha. \end{array} \end{equation}

This is a problem appearing in portfolio optimization (here for more info). Here we assume $\bar{p},x \in\mathbb{R}^n$ and $\alpha, \beta\in[0,1]$, $\Sigma \in \mathbb{R}^{n\times n}$ is Positive Semi-Definite Matrix and $\Phi^{-1}(\cdot)$ is the inverse Gaussian CDF. The problem is convex for $\beta\leq0.5$.

Is there any closed-form solution for this problem? I tried solving the problem by imposing KKT but it did not lead to anything promising. Thanks.

$\endgroup$
4
  • 1
    $\begingroup$ What are $\|.\|$, $\Phi^{-1}(\beta)$ and $\Sigma$ explicitely? Not everyone is willing to read the paper. $\endgroup$ – Dieter Kadelka Jan 28 at 15:38
  • $\begingroup$ Thanks for your comment @DieterKadelka, I updated the question! $\endgroup$ – Apprentice Jan 28 at 17:30
  • $\begingroup$ Do you assume that $\Sigma$ is symmetric so that $\Sigma^{1/2}$ is uniquely defined? Maybe it doesn't matter. $\endgroup$ – Dieter Kadelka Jan 28 at 21:12
  • $\begingroup$ @DieterKadelka Yes I assume that. It's included in the assumption since Positive semi-definiteness implies symmetry. $\endgroup$ – Apprentice Jan 28 at 21:13
1
$\begingroup$

For this special case an explicit solution is possible. To simplify notation let $A := \Sigma^{1/2}$ and let $A^+$ be the pseudoinverse of $A$ (see f.i. Golub/Van Loan: Matrix Computations (1996), 3rd ed., p. 257). Let $y := Ax$, $z := (E - A^+A)x$, thus $x = A^+y +z$ and the problem is $$p^T(A^+y + z) = max!\\p^T(A^+y+z) + \Phi^{-1}(\beta) \cdot \sqrt{y^TAA^+y} \geq \alpha,$$ since $Az = 0$ and $(AA^+y)^T(AA^+y) = y^TAA^+y$. Now assume that $\beta < 0.5$ (the case $\beta = 0.5$ is uninteresting since then $\Phi^{-1}(\beta) = 0$). Let $F$ be the image of $x \to Ax$ and $\mathbb{R}^n = F+G$, $G$ a subspace. If there is some $z \in G$ with $p^T z \not= 0$, then the problem is unsolvable (take $y = 0$ and $x = \lambda z$ with either $\lambda < 0$ or $\lambda > 0$). Of course this only can happen if $A$ is singular.

Now we can assume w.l.o.g. that $A$ is non-singular. Then $AA^+ = E$, the identity matrix and always $z = 0$. Let $q := (A^+)^Tp$, then the problem is $$q^T y = max!\\q^T y + \Phi^{-1}(\beta) \cdot \sqrt{y^Ty} \geq \alpha$$ This problem is much easier to solve. Simply let $y = \lambda q$. Then the problem is $$\lambda q^Tq = max!\\ \lambda q^Tq + \Phi^{-1}(\beta) \cdot |\lambda| \cdot \|q\|_2 \geq \alpha$$ Which can be solved directly. Also general cases (singular $A$), which are solvable, can be reduced to this special case.

$\endgroup$
2
  • $\begingroup$ Thanks for your nice explanation. I have a question, what is $max!$? Also, is the matrix $E$ the identity matrix? $\endgroup$ – Apprentice Jan 29 at 12:28
  • $\begingroup$ $max!$ simply means: Maximize the left side. And $E$ indeed is the identity matrix. $\endgroup$ – Dieter Kadelka Jan 29 at 13:24
3
$\begingroup$

The problem is convex and is a Second Order Cone problem (SOCP) for $\beta \le 0.5$. The statement that the problem is convex for $\beta > 0.5$ is incorrect.

There is no closed-form solution.

If $\beta \le 0.5$, the SOCP can be numerically solved using an SOCP (conic) solver, of which there are many, including SeDuMi (free), SDPT3 (free), ECOS (free), Mosek (commerical), CPLEX (commercial), Gurobi (commercial), XPRESS (commercial), Knitro (commerical), among others. It is easy to enter the problem in a convex optimization tool, such as CVX, CVXR, YALMIP, CVXPY, and CVXR. Here is CVX code:

cvx_begin
variable x(n)
minimize(p'*x)
subject to
p'*x + norminv(beta)*norm(sqrtm(Sigma)*x) >= alpha
x >= 0 % include this if you want to disallow shorting
sum(x) == 1 % included this even though though is not mentioned in the question
cvx_end 

If $\Sigma$ is non-singular, chol(Sigma) can be used in place of sqrtm(Sigma).

If $\beta > 0.5$, the problem is non-convex, and is not am SOCP. Given enough time (and memory) It can be numerically solved to global optimality using a global optimization solver such as BARON or ANTIGONE.

$\endgroup$
3
  • 1
    $\begingroup$ You are right, I was thinking in terms of $\leq$ inequality. I will update the question, thanks! $\endgroup$ – Apprentice Jan 29 at 8:29
  • $\begingroup$ Further, your question is easier to read if you replace $\Phi^{-1}(\beta)$ by $\beta \leq 0$ (without the assumption $0 \leq \beta \leq 1$). This is completely equivalent to your original problem. By the way, the orignial formulation of your problem is almost useless. If $p^T x > 0$ for some admissible $x$, then maximum = $\infty$. $\endgroup$ – Dieter Kadelka Jan 29 at 9:20
  • $\begingroup$ @Mark L. Stone: Fine list of solvers! $\endgroup$ – Dieter Kadelka Jan 29 at 9:26

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.