2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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$)? $\endgroup$ Commented Apr 30 at 0:48
  • $\begingroup$ Yes, that’s correct. L1 norm of vector x is equal to 1 $\endgroup$ Commented Apr 30 at 1:05
  • 1
    $\begingroup$ 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? $\endgroup$ Commented Apr 30 at 2:29
  • $\begingroup$ 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 $\endgroup$ Commented Apr 30 at 2:49

2 Answers 2

1
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Apr 30 at 16:42
  • 1
    $\begingroup$ @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. $\endgroup$ Commented May 1 at 15:31
0
$\begingroup$

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.

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