1
$\begingroup$

I have an optimization problem where all the constraints are linear but some of the type: $$ y_i = \frac{x_i}{\sum_k x_k} $$

It seems that the equality can be relaxed to an inequality adding the linear constraint: $$ \sum_k y_k =1. $$

I further have the constraints: $$x_i\geq0$$ $$0\leq y_i \leq 1$$

The question is if the relaxed inequality is (or can be recasted as) a convex constraint? $$ y_i \leq \frac{x_i}{\sum_k x_k} $$

If I analyze it as a quadratic constraint $$\mathbf{x}^T A \mathbf{x} - b \mathbf{y} \leq 0,$$ the corresponding matrix $A$ has all zeros in the main diagonal (since there are no squared variables) and shows a negative eigenvalue, so the matrix is not positive semidefinite, and thus, the constraint is not convex.

I have also looked into the possibility of recasting the constraint as a Geometric Programming one: $$ y_i\, x_i^{-1} \,\sum_k x_k \leq 1 $$ but then I face that I don't know if a geometric programming problem can mix constraints in the transformed variables and the original ones.

Any hint towards where to look would be very appreciated!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.