Can this problem be solved using convex optimization?

Question

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.

Answer 1

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$.

Answer 2

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.