Is there a general solution to this problem?

59 Views Asked by At

Assuming $\alpha_1,\alpha_2,\beta_1, \beta_2$ are both boundary parameters and variables.

For all $x_1, x_2$, we have $x_1 \in [\alpha_1, \beta_1]$ and $x_2 \in [\alpha_2, \beta_2]$.

Also, $x_1, x_2$ are constrained by additional inequalities like $0.5 \leq x_1 + x_2 \leq 1$.

How to get the maximum intervals between $\alpha$ and $\beta$

$$max \ \ (\beta_1 - \alpha_1) + (\beta_2 - \alpha_2)\\ s.t. \forall x_1 \in [\alpha_1, \beta_1]\\ \ \ \ \ \ \ \ \forall x_2 \in [\alpha_2, \beta_2] \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0.5 \leq x_1 + x_2 \leq 1 \\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0 \leq \alpha_1, \alpha_2, \beta_1, \beta_2 \leq 1$$

I'm not sure if the problem can be transfer a general robust optimization problem

1

There are 1 best solutions below

3
On BEST ANSWER

Define square $S=[0,1]\times[0,1]$, quadrilateral $Q=\{(x_1,x_2)\in S: 0.5 \le x_1 + x_2 \le 1\}$, and rectangle $R=[\alpha_1,\beta_1]\times[\alpha_2,\beta_2]$. You want to find $\alpha_i,\beta_i \in S$ to maximize the semiperimeter $\sum_{i=1}^2 (\beta_i-\alpha_i)$ of $R$ subject to $R \subset Q$. By convexity, $R \subset Q$ if and only if all four corners of $R$ are in $Q$. You can solve the problem via linear programming: maximize the linear function $\sum_{i=1}^2 (\beta_i-\alpha_i)$ subject to linear constraints \begin{align} 0.5 \le \alpha_1 + \alpha_2 &\le 1 \\ 0.5 \le \alpha_1 + \beta_2 &\le 1 \\ 0.5 \le \beta_1 + \alpha_2 &\le 1 \\ 0.5 \le \beta_1 + \beta_2 &\le 1 \\ \alpha_i &\ge 0 \\ \beta_i &\ge 0 \end{align}

But there is also a simple geometric argument. From a plot of $Q$, it is clear that you want the lower left corner $(\alpha_1,\alpha_2)$ to be on the bottom border and the upper right corner $(\beta_1,\beta_2)$ to be on the top border: \begin{align} \alpha_1 + \alpha_2 &= 0.5 \tag1\label1\\ \beta_1 + \beta_2 &= 1 \tag2\label2 \end{align} Now subtracting \eqref{1} from \eqref{2} yields maximum semiperimeter $0.5$.