0

My problem looks like this:

$$\min x^TAx$$ subject to: $$\|x\|_1 = 1$$

matrix $A$ is $n \times n $ positive semi-definite, $x$ is $n$ dimensional vector.

Constraint is convex because every norm is. Function should also be convex because it is quadratic in $x$, but when I use 'cvxpy' package for convex optimization it tells me that problem is not convex. Is this problem convex or not? If it is not convex what could be possible ways to relax this problem to be convex?

Edit It seems like the norm constraint is not convex. Question can be closed

Kate
  • 191
  • @user807138 I tried, it just gives $0$ vector – Kate Aug 07 '20 at 15:42
  • @user807138 that is why what you suggested doesnt work. It leads to trivial answer – Kate Aug 07 '20 at 15:56
  • @user807138 i want to say that you cant change the constraint $|x|_1 = 1$ to $|x|_1 \leq 1$. It leads to trivial answer. Cant you see that? – Kate Aug 07 '20 at 16:00

1 Answers1

1

When we require a convex function to have exactly a particular value, e.g. $\|x\|_1=1$, that constraint is not necessarily convex. For instance, on $\mathbb{R}$, we know that $\|1\|_1=1=\|-1\|_1$, so both $1$ and $-1$ are in the constraint set $C=\{x\in\mathbb{R}\,|\, \|x\|_1=1\}$. However, their convex combination $0.5(-1+1)=0$ is such that $\|0\|_1=0\neq 1$, so $0\not\in C$ and therefore the constraint $C$ is nonconvex.

Regarding your edit, every norm is a convex function. If you require, for instance, $\|x\|_1\leq 1$ then this becomes a convex constraint. The issue is with requiring an equality constraint, instead of an inequality constraint.

This can be visualized in $\mathbb{R}^2$ as well -- the equality constraint is the boundary of a sphere (lacking the interior), which is nonconvex. On the other hand, the inequality constraint is the ball (with interior) which is convex.

Zim
  • 4,318