Simplification of a min-max problem

163 Views Asked by At

I have an optimisation problem to solve. The book I'm following says that the original problem can be rewritten in a simpler way by observing that one of the unknowns is a subset of the $Y-1$ dimensional simplex. I'm struggling to write down this equivalent way.


Original problem

Let me first introduce some notation. $B,L,Q$ are $Y\times 1$ vector. $Q_y\equiv Q(y)$ is the $y$-th element of $Q$. $R$ is a 3d matrix of size $Y\times V \times E$. $R_{y,v,e}\equiv R(Y,V,E)$ is the $(y,v,e)$-th element of $R$. $P$ is an $E\times 1$ vector. $P_e\equiv P(e)$ is the $e$-th element of $P$.

The original problem is:

$$ \text{max}_{B}\text{ min}_{Q,R}\text{ } B^T (L-Q)\\ \text{s.t.} \\ Q_y - \sum_{e=1,..,E,v=1,...,V} R_{y,v,e} \times P_e=0 \text{ }\forall y=1,...,Y\\ R\in [0,1]^{Y\times V\times E}\\ \sum_{y=1,...,Y,v=1,...,V}R_{y,v,e}-1=0 \text{ }\forall e=1,...,E\\ \sum_{y=1,...,Y} R_{y,v,e}-1=0 \text{ }\forall e=1,...,E,v=1,...,V\\ \sum_{v=1,...,V} R_{y,v,e}-1=0 \text{ }\forall e=1,...,E,y=1,...,Y\\ Q\in [0,1]^Y\\ \sum_{y=1,...,Y}Q_y-1=0\\ B^TB\leq 1\\ $$


Transformed problem

The exercise says: given that $Q$ belongs to the $Y-1$ dimensional simplex, the problem above can be rewritten in a simpler way. Could you check whether my attempt is correct? If not, could you fix it? Are some constraints superfluous?

Let $Z\equiv L-Q$. Let $\tilde{B}$ be the $Y\times 1$ vector collecting the first $Y-1$ elements of $B$ and having as last element a zero.

$$ \text{max}_{\tilde{B}}\text{ min}_{Z,R}\text{ } \tilde{B}^T Z\\ \text{s.t.} \\ (L_y-Z_y) - \sum_{e=1,..,E,v=1,...,V} R_{y,v,e} \times P_e=0 \text{ }\forall y=1,...,Y\\ R\in [0,1]^{Y\times V\times E}\\ \sum_{y=1,...,Y,v=1,...,V}R_{y,v,e}-1=0 \text{ }\forall e=1,...,E\\ \sum_{y=1,...,Y} R_{y,v,e}-1=0 \text{ }\forall e=1,...,E,v=1,...,V\\ \sum_{v=1,...,V} R_{y,v,e}-1=0 \text{ }\forall e=1,...,E,y=1,...,Y\\ L-Z\in [0,1]^Y\\ \sum_{y=1,...,Y}(L_y-Z_y)-1=0\\ \tilde{B}^T\tilde{B}\leq 1\\ $$

Also, what is the technical name of this optimisation problem? It looks to me "a constrained optimisation problem with linear objective function and linear and quadratic constraints". Is there a shorter way to call it?