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$
  • $\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 '18 at 14:02
  • $\begingroup$ for $n=1$ on the slice $y=1$, you will have $\sqrt{x}$, which is concave $\endgroup$ – Johan Löfberg May 30 '18 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 '18 at 14:25

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.