9
$\begingroup$

My problem is: \begin{align}\min\limits_{x_{ij}}\qquad&{\sum_{i\in N}\sum_{j\in M}\frac{x_{ij}}{C_j-\sum\limits_{i\in N} x_{ij}a_i}}\\\text{s.t.}\qquad&0<C_j-\sum_{i\in N} x_{ij}a_i\\\qquad&\sum_{j\in M} x_{ij}=1\\\qquad&x_{ij}\in[0,1]\\\quad&{\sum_{j\in M}\frac{x_{ij}}{C_j-\sum\limits_{i\in N} x_{ij}a_i}} \le d_i,\forall i\in N\end{align}

It is worth mentioning that the third constraint indicates the range and $x_{ij}$ isn't binary. As I calculated the Hessian of my objective function, I understood that the sign of matrix elements is dependent on $x_{ij}$ and $C_j-\sum\limits_{i\in N} x_{ij}a_i$ which are always positive or zero.

  • Due to this, can I conclude that my problem is convex?
  • If the answer is yes, what class of convex problems does it belong to? (conic, geometric, etc.) and if no what is the type of problem?
Improve this question
$\endgroup$
4
  • 5
    $\begingroup$ You are using $i$ in three different and conflicting ways: as an outer summation index, an inner summation index, and a constraint index. $\endgroup$
    – RobPratt
    Aug 29, 2019 at 15:10
  • $\begingroup$ Your last constraint sums over $i$ on the left but has a RHS indexed by $i$. This cannot be parsed. $\endgroup$
    – prubin ♦
    Aug 29, 2019 at 20:59
  • $\begingroup$ @prubin Thanks, I corrected it. $\endgroup$
    – Ben
    Aug 29, 2019 at 22:06
  • $\begingroup$ That change eliminates one of the conflicts, but you still have $i$ pulling double-duty in the summations. Maybe change $i$ to $k$ in the denominator in both the objective and the last constraint? $\endgroup$
    – RobPratt
    Aug 29, 2019 at 23:17

2 Answers 2

Reset to default
9
$\begingroup$

This is a Linear-Fractional Programming problem.

It can be transformed to a Linear Programming problem as shown in section 4.3.2 "Linear-fractional programming" of "Convex Optimization" by Boyd and Vandenberghe

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ Just to be clear, the stated problem is actually a generalization of the linear-fractional problem in which there is a linear sun of fractions (sum wiith respect to j). So the transformation in the linked section will have to be applied using new variables, and applied separately, for each fraction (each value of j) in the sum. Everything still works out. $\endgroup$
    – Mark L. Stone
    Aug 29, 2019 at 15:44
  • $\begingroup$ @MarkL.Stone I am not sure repeatedly applying the Charnes-Cooper transformation results in a linear program. That seems to contradict this answer on the Mathematics StackExchange. $\endgroup$
    – Kevin Dalmeijer
    Aug 30, 2019 at 0:15
  • $\begingroup$ @KevinDalmeijer The sign of the decision variable in the denominator of my problem is negative and I think this is the difference that makes it convex. $\endgroup$
    – Ben
    Aug 30, 2019 at 0:40
  • $\begingroup$ @MarkL.Stone Thanks for your helpful answer. If the problem is large-scale, is it possible to attain the solution as the one-by-one transformation wouldn't be practical? Moreover, is there any way to implement it by toolboxes such as CVX or YALMIP? $\endgroup$
    – Ben
    Aug 30, 2019 at 0:57
  • $\begingroup$ CVX and YALMIP won't do the transformations for you. But once you have done them, you should be able to enter the problem in either.Rather large (non-integer) LPs are not much of a problem nowadays. $\endgroup$
    – Mark L. Stone
    Aug 30, 2019 at 1:28
4
$\begingroup$

If the feasible region would be convex, then you have a sum-of-ratios problem. In general, sum-of-ratios problems are $\mathcal{NP}$-hard, although your specific problem could be easier to solve.

My intuition says that the function $$\sum_{j\in M}\frac{x_{ij}}{C_j-\sum\limits_{i\in N} x_{ij}a_i}$$ is not convex, such that the feasible region is probably non-convex. Note that for proving convexity you need that the Hessian is positive semi-definite. It is not sufficient for all elements to be non-negative.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Numerator and denominator both being linear (affine) is a special case which is easier than what is addressed in the paper you linked. $\endgroup$
    – Mark L. Stone
    Aug 30, 2019 at 1:19
  • 2
    $\begingroup$ Minimizing the ratio $f(x)/g(x)$ with $f$ convex and $g$ concave can be replaced by minimizing the ratio $y/z$ if the constraints $f(x) \le y$ and $g(x) \ge z$ are added, which are convex. This trick is used in this paper. It would then follow that the linear case is not easier (in the complexity sense). $\endgroup$
    – Kevin Dalmeijer
    Aug 30, 2019 at 1:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.