1
$\begingroup$

Consider the optimization problem

\begin{align} \max ~~ &x && \label{f}\\ \text{subject to}\ & \sum_{i=1}^{x} y_{i} = a && \label{s}\\ & y_{i} + y_{j} > b && \forall i,j \in \{1,\dots,x\} \text{ and } i \ne j \label{fd}\\ & 0 < y_{i} \le b && \forall i \in \{1,\dots,x\} \label{ad}\\ & x \in\{0,1,\dots\}, && \label{d} \end{align} where $a\ge 0$ and $b>0$ are real numbers. The decision variable $x$ can only take integer values, while the decision variable $y_i$ can take a positive real value. In this problem, $x=0$ iff $a=0$ and $x=1$ iff $0<a\le b$.

Although there are some strict inequalities, I think we can find an optimal solution for this optimization problem for any $a\ge 0$ and $b>0$. To approach this problem, we can find a supremum for the problem, that is, the supremum of the set of all possible objective values, $X \subset \{0,1,\dots\}$. If we can find a feasible solution for the problem whose objective value is equal to the supremum, then we have proved that the solution is optimal. For example, if $a=2$ and $b=1$ then $x=4$ is infeasible and therefore $x^*=3$ is the supremum which is also an upper bound (i.e., the optimal value) since the feasible solution $y=(0.5,0.7,0.8)$ exists.

My problem is that I don't know how to find such a supremum and mathematically prove it. How can you find the supremum in this problem (or other optimization problems with strict inequalities)?

Edit

This optimization problem (with $0 < b < a$) is equivalent to this problem and therefore they have the same solution.

$\endgroup$
1
$\begingroup$

Here is why there is always a feasible $x$. Let $2a/b = k+\epsilon$ with $0\le\epsilon<1$, that is, with $k=\lfloor 2a/b\rfloor.$ Then if $k\ge 1$, and $\epsilon>0$, the choice $x=k$, $y_i = (k+\epsilon)b/2k$ for all $i$ is feasible. If $k= 1$ and $\epsilon=0$ (so $a=b/2$) the choice $x=1$ and $y_1=a$ is feasible. If $k>1$ and $\epsilon=0$ (so $a=kb/2$) the choice $x=k-1$ and $y_i=kb/(2(k-1))$ for all $i$ is feasible. Finally, if $k=0$, which is to say $2a/b\lt 1$, then $x=1$, $y_1=a$ is feasible.

Here is why there is a maximal feasible $x$. If $x$ is even we have $$a = (y_1+y_2)+\cdots +(y_{x-1}+y_x) \ge \frac x 2 b$$ and if $x$ is odd we have $$a = (y_1+y+2)+\cdots +(y_{x-2}+y_{x-1}) + y_x\ge \frac {x-1} 2 b.$$ Either way,we have $x\le 1+2a/b$.

From here you should be able to fill in the missing pieces to find optimal $x$ values: the $y_i$ should be approximately $b/2$ each, with little perturbations to make them feasible.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy