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!


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.