Patatiniuh

Answered

2022-07-08

I'm facing this problem:

$\underset{x\in {\mathbb{R}}_{+}^{3}}{min}max\{\frac{\sum _{i=1}^{3}{x}_{i}^{2}-2{x}_{1}{x}_{3}}{{\left(\sum _{i=1}^{3}{x}_{i}\right)}^{2}},\frac{\sum _{i=1}^{3}{x}_{i}^{2}+2({x}_{1}{x}_{3}-{x}_{1}{x}_{2}+{x}_{2}{x}_{3})}{{\left(\sum _{i=1}^{3}{x}_{i}\right)}^{2}}\}$

I don't know how to deal with inner max and choose one of two!

I'm trying to use $max(A,B)\ge \frac{1}{2}(A+B)$! Do you have any idea?

$\underset{x\in {\mathbb{R}}_{+}^{3}}{min}max\{\frac{\sum _{i=1}^{3}{x}_{i}^{2}-2{x}_{1}{x}_{3}}{{\left(\sum _{i=1}^{3}{x}_{i}\right)}^{2}},\frac{\sum _{i=1}^{3}{x}_{i}^{2}+2({x}_{1}{x}_{3}-{x}_{1}{x}_{2}+{x}_{2}{x}_{3})}{{\left(\sum _{i=1}^{3}{x}_{i}\right)}^{2}}\}$

I don't know how to deal with inner max and choose one of two!

I'm trying to use $max(A,B)\ge \frac{1}{2}(A+B)$! Do you have any idea?

Answer & Explanation

Tristin Case

Expert

2022-07-09Added 15 answers

A standard trick when dealing with max-min or min-max problem is to introduce a new decision variable, call it $z$, which models the inner optimization. Hence, your objective function becomes

$\underset{z\in \mathbb{R},\mathbf{x}\in {\mathbb{R}}_{\mathbf{+}}^{\mathbf{3}}}{min}z$

with the following constraints

$\begin{array}{rl}z& \ge {\displaystyle \frac{\sum _{i=1}^{3}{x}_{i}^{2}-2{x}_{1}{x}_{3}}{{\left(\sum _{i=1}^{3}{x}_{i}\right)}^{2}}}\\ z& \ge {\displaystyle \frac{\sum _{i=1}^{3}{x}_{i}^{2}+2({x}_{1}{x}_{3}-{x}_{1}{x}_{2}+{x}_{2}{x}_{3})}{{\left(\sum _{i=1}^{3}{x}_{i}\right)}^{2}}}\\ \sum _{i=1}^{3}{x}_{i}& =1\end{array}$

The first two inequalities model the max expression, i.e. they state that whatever $z$ comes out to be, it has to be larger than either of the two terms. The last one captures the homogeneity, as it has been pointed out in the comments. From here, you can apply the KKT conditions.

$\underset{z\in \mathbb{R},\mathbf{x}\in {\mathbb{R}}_{\mathbf{+}}^{\mathbf{3}}}{min}z$

with the following constraints

$\begin{array}{rl}z& \ge {\displaystyle \frac{\sum _{i=1}^{3}{x}_{i}^{2}-2{x}_{1}{x}_{3}}{{\left(\sum _{i=1}^{3}{x}_{i}\right)}^{2}}}\\ z& \ge {\displaystyle \frac{\sum _{i=1}^{3}{x}_{i}^{2}+2({x}_{1}{x}_{3}-{x}_{1}{x}_{2}+{x}_{2}{x}_{3})}{{\left(\sum _{i=1}^{3}{x}_{i}\right)}^{2}}}\\ \sum _{i=1}^{3}{x}_{i}& =1\end{array}$

The first two inequalities model the max expression, i.e. they state that whatever $z$ comes out to be, it has to be larger than either of the two terms. The last one captures the homogeneity, as it has been pointed out in the comments. From here, you can apply the KKT conditions.

Most Popular Questions