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$

5,544

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.

Share:
5,544

Related videos on Youtube

tam
Author by

tam

Updated on May 30, 2020

Comments

  • tam
    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
      AndreaCassioli over 7 years
      Isn't it just a linear program?
    • tam
      tam over 7 years
      I don't think so, because the constraints are not linear.
    • Luca Citi
      Luca Citi over 7 years
      It 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
      tam over 7 years
      Oh yes, you are right. Could one of you extend his comment to an answer (in order to accept it)?
  • AndreaCassioli
    AndreaCassioli over 7 years
    Exactly. But also notice that also in the original formulation you need a constraint that remove the case q=0.