1
$\begingroup$

I searched for some results online but it seems that the objective functions considered there depend on continuous variables. I am not sure if it will be different when the variables are restricted to be integers.

So, for example, we have the following objective function $$\frac{\sum_{i=1}^n (x_iy_i)}{\sqrt{\sum_{i=1}^n x_i} \sqrt{\sum_{i=1}^n y_i}},$$ where $x_i, y_i \in \{0,1\}$.

Clearly, this function is non-linear. How can we determine if it is convex or not? I appreciate it if you can provide some general guidance.

Also, I guess this optimization problem falls into (non-linear) Binary-Integer-Programming. Can you provide some references on how to start solving such a class of problems?

$\endgroup$
3
  • $\begingroup$ I have read some references. The typical way is to treat the discrete variables as continuous for the moment and analyze the convexity of the objective function. And then use the branch and bound method to solve the discrete case. Is my understanding right? $\endgroup$
    – Paradox
    May 30, 2018 at 14:02
  • $\begingroup$ for $n=1$ on the slice $y=1$, you will have $\sqrt{x}$, which is concave $\endgroup$ May 30, 2018 at 14:09
  • $\begingroup$ @Rodrigo de Azevedo: Why not give an ad hoc definition for integer variables saying that such a function is convex when the line segment between any two points on the graph of the function lies "above" of the graph? In this sense a "convex" function would always be susceptible to being prolonged (in theory) to a proper convex function. Regards. $\endgroup$
    – Piquito
    Jun 6, 2018 at 14:25

0

You must log in to answer this question.