0
$\begingroup$

Consider the following optimization problem:

$\max\limits_\mathbf{w} \frac{\frac{\sum_i w_i}{2} - \sum_i w_ip_{i}}{(\sum_i w_i(1 - p_{i})p_{i})^\frac{1}{2}}$ s.t. $\mathbf{w} = [w_1, w_2,..., w_M ]^T \in \{0,1\}^M, \mathbf{p} = [p_1, p_2,..., p_M ]^T, 0.5 \leq p_i \leq 1$

I was initially trying to find out whether the objective function is convex or concave after removing the integer constraint and no luck.

So is the objective function convex without the integer constraint? If not, how can we optimize the objective?

$\endgroup$
2
  • $\begingroup$ The $p_i$ are given fixed numbers? $\endgroup$ Mar 25, 2019 at 22:04
  • $\begingroup$ Yes. The $p_i$ are given fixed numbers ranging from $0.5$ to $1$ $\endgroup$
    – J.Sun
    Mar 26, 2019 at 6:12

1 Answer 1

0
$\begingroup$

The objective function is not convex nor concave. However, since you mentioned that $p_i\geq 0.5$, the numerator is non-positive and the denominator is non-negative.

Thus, the objective can be replaced by minus its square, namely, $$ -\frac{(\tfrac{1}{2} \sum_i w_i - \sum_i w_i p_i)^2}{\sum_i w_i(1-p_i)p_i} $$

Fortunately, what you obtain is the negative of the well-known 'quadratic over linear' function which is concave.

Moreover, in your case you might have a zero denominator. So I believe you need a constraint on $\mathbf{w}$ to ensure that it cannot happen.

$\endgroup$
2
  • $\begingroup$ Does all general 'quadratic over linear' function convex regardless of the details in the denominator and the numerator? $\endgroup$
    – J.Sun
    Mar 26, 2019 at 14:13
  • $\begingroup$ @J.Sun no. They are convex when the denominator is positive, and concave when the denominator is negative. $\endgroup$ Mar 26, 2019 at 14:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .