6
$\begingroup$

When doing Sharpe optimization

$$ \max_x \frac{\mu^T x}{\sqrt{x^T Q x}} $$

there is a common trick (section 5.2) used to put the problem in convex form. You add a variable $\kappa$ such that $x = y/\kappa$ choose $\kappa$ s.t. $\mu^T y=1$. Changing the problem to the simple convex problem

$$ \min_{y,\kappa} y^T Q y \; \text{where} \; \mu^T y = 1, \kappa > 0 $$

which is easy to solve.

Unfortunately, my problem also has a second-order constraint that becomes non-convex in $(y,\kappa)$ $$ x^T P x \leq \sigma^2 \implies y^T P y \leq \kappa^2 \sigma^2 $$

Is there a trick to keep this problem convex and allow the use of second-order cone programming algorithms?

$\endgroup$
  • $\begingroup$ The KKT theorem can still be applied, as it does not have to have linear inequality constraint. $\endgroup$ – Gordon Jun 26 '15 at 12:41
  • $\begingroup$ Can you expand? I read some about the KKT theorem but I'm not sure how this helps me solve the problem. $\endgroup$ – rhaskett Jun 26 '15 at 18:29
2
$\begingroup$

There is no generic solution. However, the KKT conditions are of the forms \begin{align*} \begin{cases} Qy + \lambda_1 \mu +\lambda_2 Py = 0,\\ \mu^T y = 1,\\ y^TPy \leq k^2 \sigma^2,\\ \lambda_2 \big( y^TPy - k^2 \sigma^2\big) = 0. \end{cases} \end{align*} Here, the condition $$\lambda_2 \big( y^TPy - k^2 \sigma^2\big) = 0 $$ means that two cases need to considered, that is, the one on the boundary $y^TPy = k^2 \sigma^2$ and the one inside the domain $y^TPy < k^2 \sigma^2.$

On the boundary, it is the standard Lagrange problem with conditions \begin{align*} \begin{cases} Qy + \lambda_1 \mu +\lambda_2 Py = 0,\\ \mu^T y = 1,\\ y^TPy = k^2 \sigma^2. \end{cases} \end{align*}

Inside the domain, the constraints are \begin{align*} \begin{cases} Qy + \lambda_1 \mu = 0,\\ \mu^T y = 1,\\ y^TPy < k^2 \sigma^2. \end{cases} \end{align*}

The final solution $(y^T, k)$ is the one so that the global overall minimum is reached.

$\endgroup$
  • $\begingroup$ Thanks. Interesting. This looks close but I'm still confused on how the quadratic form was converted to a linear form here $Qy$ by adding $\lambda_1$? Do you have a reference? Also, this final problem is still not convex, correct? What sort of numerical solver could be used in this case? $\endgroup$ – rhaskett Jun 29 '15 at 19:25
  • $\begingroup$ @rhaskett: The form $Qy$ is the vector derivative $\frac{\partial y^T Qy}{\partial y}$. The final problem is actually easier: you only need to find a solution from the linear system and then check whether it satisfies the inequality -- it does not have to be a convex problem. $\endgroup$ – Gordon Jun 29 '15 at 19:45
  • $\begingroup$ @Gordan This is really interesting. You mention linear inequality constraints as an issue earlier. Does that mean this doesn't work if say an additional $0 \leq x_i \leq 1$ ($0 \leq y_i \leq \kappa$) constraint is imposed? $\endgroup$ – rhaskett Jun 29 '15 at 21:33
  • $\begingroup$ @rhaskett, See Section 2.2 of this lecture notes homes.soic.indiana.edu/classes/spring2012/csci/b553-hauserk/… may be helpful. $\endgroup$ – Gordon Jun 30 '15 at 12:37

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.