1
$\begingroup$

I have the following cost function for portfolio allocation:

$$ w^T\mu-\frac{1}{2}\gamma w^T\Sigma w+\frac{1}{6}\gamma^2 w^TM_3(w\otimes w), $$

which considers also the co-skewness ($M_3$ tensor), $\gamma$ is the risk aversion (a constant)

This function is cubic and non convex, so I cannot use the typical convex optimisation with cvxpy in python. However, it should be possible to transform/replace the cubic term with a quadratic term and adding a new constraint in order to have a non-convex but now quadratic form, which can be solved probably more easily.

Can anyone help please to reformulate the above equation in order to make it quadratic? Can I still use cvxpy for non-convex optimisation?

This question is a follow-up to:

$\endgroup$
7
  • $\begingroup$ I think you could use any other multivariate optimisation routine from scipy.optimize, no for this problem if you want to introduce positivity constraints on your portfolio weights. If you can make do with unconstrained weights, you can simply derive the FOCs and run some multidimensional root finder on it. NB: For some reason there seems to be an upsurge in questions related to Skew/Kurtosis based optimisation... $\endgroup$ Oct 23, 2020 at 7:22
  • $\begingroup$ thanks. Well no I have plenty of contraints on my asset classes and in turn on my weighs. So I would say making this quadratic non-convex should be easier to solve it than let it cubic non-convex.. $\endgroup$
    – Luigi87
    Oct 23, 2020 at 7:30
  • $\begingroup$ A quadratic form $x^T A x + b^T x + c$ is convex if A is semi-positive definite. Therefore for your reformulated optimisation problem to be non-convex would require a reformulated quadratic coefficient matrix to be neither semi-positive definite, nor semi-negative definite. $\endgroup$
    – Attack68
    Oct 23, 2020 at 8:50
  • $\begingroup$ that is clear thanks, but I do not want to impose the reformulated optimisation problem to be convex or not..because I guess that would be even harder imposition. The point is to remove/modify the cubic term and set it as constraint to have a quadratic form. Nevermind convex or not..if the new problem will have hessian positive semidefinite thus convex is better but if not I may use some non convex optimiser for quadratic problem (I guess they exist). all I want is to make the above function quadratic somehow, if this can be done..the question is asking how to do this reformulation..thanks $\endgroup$
    – Luigi87
    Oct 23, 2020 at 8:59
  • $\begingroup$ I suggest to move this question over to math? $\endgroup$ Oct 24, 2020 at 4:02

1 Answer 1

0
$\begingroup$

I don't think you can reformulate the problem as written to be quadratic, but you can "cheat", and approximate it as a quadratic problem locally. That's the general idea behind using Newton's method in optimization. If

$$ f(w) := w^T\mu-\frac{1}{2}\gamma w^T\Sigma w+\frac{1}{6}\gamma^2 w^TM_3(w\otimes w) $$

is your optimization function, then, thanks to the Taylor series, at any $w_k \in \mathbb{R}$ with all the required derivatives defined,

$$ f(w_k) \approx f(w_k) + \nabla f(w_k)^Tw_k + \frac{1}{2}w_k^T\nabla^2f(w_k)w_k^T $$

in some neighborhood of $w_k$. Here $\nabla f(w_k)$ and $\nabla^2 f(w_k)$ are the gradient and Hessian matrix, respectively. Under some fairly general conditions, like boundedness near the minimum, or constraints on the size of the derivative, you can show that Newton's method will converge superlinearly to a minimum.

That solves one of your two problems, which is how to deal with cubic terms. You iteratively approximate your function as a quadratic at each step, until you find a minimum. In practice, this can work quite well for a wide class of problems.

The second problem you mentioned is that the function is non-convex, which poses some risks:

  1. The function has local minimum, and your optimization method converges on a non-global, local minimum.
  2. The function has no minimum at all, and your optimization method sputters on until it hits some maximum number of steps and gives up.

There are some techniques that can be used to deal with local minimum, but there's usually not a guarantee that they will find a global minimum. Stochastic optimization methods are built to deal with this type of problem, but you don't always need the complexity these introduce. In particular, if you have some domain knowledge you can use to find a "close" initial guess of the minimum, Newton's method should converge to the global minimum when it exists.

$\endgroup$

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.