Optimization problem: $\min \limits_{\mathbf{q}} \sum_{n=1}^N q_n$, s.t. $\frac{c_{nn} q_n }{\sum_{m \ne n} c_{nm} q_m } \ge a$
As pointed out by @AC_MOSEK, this is a linear program. The cost function is linear and the constraints can be rewritten as $\mathbf{q}\ge\mathbf{0}$ and: $$c_{nn} q_n - a \sum_{m \ne n} c_{nm} q_m \ge 0, \forall n \in \{1,\ldots,N\}.$$ Careful: you may introduce some valid solutions that weren't valid in your original problem due to the denominator in the constraint. For example $N=2$, $a=2$, $c_{mn} = 1 \,\forall m,n$ has no valid solution for your original problem but has solution $\mathbf{q}=\mathbf{0}$ in the (almost) equivalent linear problem.
Related videos on Youtube
tam
Updated on May 30, 2020Comments
-
tam over 3 years
\begin{array}{rl} \min \limits_{\mathbf{q}} & \sum_{n=1}^N q_n \\ \mbox{s.t.} & \frac{c_{nn} q_n }{\sum_{m \ne n} c_{nm} q_m } \ge a, \forall n \in \{1,\ldots,N\} \end{array}
For this optimization problem, we have: $\mathbf{q}=[q_1,\ldots,q_N ]$, with $q_n \ge 0$, and $c_{nm}$ and $a$ are some positive constants.
How can I solve such a problem ?-
AndreaCassioli over 7 yearsIsn't it just a linear program?
-
tam over 7 yearsI don't think so, because the constraints are not linear.
-
Luca Citi over 7 yearsIt should be if you rewrite the constraints as $c_{nn} q_n - a \sum_{m \ne n} c_{nm} q_m } \ge 0, \forall n \in \{1,\ldots,N\}$.
-
tam over 7 yearsOh yes, you are right. Could one of you extend his comment to an answer (in order to accept it)?
-
-
AndreaCassioli over 7 yearsExactly. But also notice that also in the original formulation you need a constraint that remove the case q=0.