# Can this problem be solved using convex optimization?

I have the following problem: \begin{align} \max & \quad \frac{\mu^\top x - c^\top|x - x_0|}{x^{\top}\Sigma x} \tag{1} \\ \text{subject to } & \quad x \leq \mathbb{1} \tag{2}\\ & \quad x \geq -\mathbb{1} \tag{3}\\ & \quad |x|_1 \leq 1 \tag{4} \end{align} where $$\Sigma$$ is a covariance matrix, $$x_0$$ is a vector of constants, and $$c_i > 0$$ for all $$i$$.

Using linear fractional programming and relaxing constraint $$(4)$$, I converted the above problem minimization problem below, but I'm not sure if my treatment of $$w_0$$ is correct since it's inside an absolute value sign.

\begin{align} \min &\quad y^{\top}\Sigma y \tag{5}\\ \text{subject to } & \quad \mu^\top y - c^\top | y - w_0| = 1 \tag{6} \\ & \quad y \leq t \\ & \quad y \geq -t \\ \end{align}

Ignoring the absolute value in $$(6)$$, I can simplify to this

\begin{align} \min &\quad y^{\top}\Sigma y \\ \text{subject to } & \quad (\mu - c)^\top y + c^\top x_0 t = 1 \\ & \quad y \leq t \\ & \quad y \geq -t \\ \end{align} This can be solved, but its solution has nothing to do with the original problem unfortunately.

In any case, I'm very new to quadratic / linear programming and I'm not sure if the problem is even solvable. I've been mostly using Cvxpy package to trying things. If it is solvable, I would appreciate any help I can get.

• What do you mean by $| x |_{1}=1$? Do you mean that the sum of the absolute values of the entries in $x$ is one (i.e. $\| x \|_{1}=1$)? Commented Apr 30 at 0:48
• Yes, that’s correct. L1 norm of vector x is equal to 1 Commented Apr 30 at 1:05
• Unfortunately, $\| x \|_{1}=1$ is a non-convex constraint, so your problem can't be addressed by convex optimization. Would $\| x \|_{1} \leq 1$ be sufficient? Commented Apr 30 at 2:29
• Yes, actually that’s better — I was going to solve the less or equal to 1 case to afterwards. The L1 norm equality I had in the question was an intermediate step I set for myself Commented Apr 30 at 2:49

This is not a convex problem. In fact, I don't think it even has a problem. Think about the special case where $$x\in{\mathbb R}^1$$, then your problem has the form \begin{align} \max & \quad \frac{\mu}{\Sigma x} + \frac{c}{\Sigma}\frac{|x - x_0|}{x} \tag{1} \\ \text{subject to } & \quad -1 \leq x \leq \mathbb{1} \tag{2} \end{align} Here, unless $$\mu=0$$, the first term in the objective function is unbounded and at $$x=0$$ the objective function is infinite -- which clearly is a maximum, but not you probably want.

In higher dimensions, the situation is similar: for the zero vector, you get an infinite objective function if you let $$x$$ approach the origin along a direction where $$x$$ is not perpendicular to $$\mu$$.

• My apologies, I made a serious transcription error in my question that reading your answer made me realize. The sign in front of $c/\Sigma$ should be negative. I've updated the question to reflect this change. Commented Apr 30 at 16:42
• @ronburgundy But that doesn't change anything. I can still make the first term infinite at $x=0$. It only changes something if you choose $c>\mu$ and $x_0=0$, in which case you get a negative infinity at that point. Commented May 1 at 15:31

Looking at the comments to the question, I believe the original constraint was $$||x||=1$$. This would exclude the zero vector as an option, but make the problem non-convex.

Reverting the constraints to the original form also doesn't resolve the issue Prof. Bangerth pointed out. It just makes it harder to identify. If the covariance matrix is positive semi-definite, then for some $$||x||=1$$ we will have $$x^T\Sigma x = 0$$. In any small neighborhood of $$x$$, the behaviour of the objective function will depend on $$\mu$$, $$c$$ and $$x_0$$.

For example, if $$x_0 = \vec{0}$$ then the objective value will tend to infinity if $$c < \mu$$, will tend to zero if $$c =\mu$$ and will tend to negative infinity if $$c > \mu$$.

If $$x_0 \neq \vec{0}$$ but $$||x_0|| = 1$$ (e.g. $$x_0$$ is a potential solution) and $$x_0^T\Sigma x_0 \neq 0$$, then the situation is even weirder. Assume that there is a vector $$x^*$$ such that $$||x^*-x_0|| = 2$$ and $${x^*}^T\Sigma x^* = 0$$. If $$2c < \mu$$, the objective value will tend to infinite around $$x^*$$. Looking at the objective function, I feel that the intention is to find the closest $$x$$ to $$x_0$$ which satisfies some constraints. However, this formulation is almost incentivized'' to find the furthest possible point to $$x_0$$ within the feasible region, but only sometimes.

I think you need to go back to the drawing board and reconsider your model. I don't think even if it was somehow solvable, it would give you the results you want.