Convex optimization closed-form solution

Question

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.

Answer 1

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.

Answer 2

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.