Is there any closed-form solution for the following optimization problem? \begin{align} &\max_{\mathbf{u}_1,\ldots,\mathbf{u}_M}\min_{i}\mathbf{1}^{\mathrm{T}}\mathbf{u}_i\\ &\text{s.t.}\quad [\mathbf{A}_1,\ldots,\mathbf{A}_M] \begin{bmatrix} \mathbf{u}_1\\ \vdots\\ \mathbf{u}_M \end{bmatrix} \leq\mathbf{1}_{N\times 1}, \end{align} where $\mathbf{u}_i$'s are vectors of size $Q\times 1$, $\mathbf{A}_i$'s are matrices of size $N\times Q$ and $\mathbf{1}$ is all-one column vector.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Unfortunately, one can not find a closed form answer if no extra information of $A_1,...,A_M$ is provided.
Let $u_i^*$ be the optimal solition of problem $min\ 1^T u_i,\ s.t.\ A_i u\le 1$. You need to choose from $u_1^*,...,u_M^*$ the maximum, which clearly cannot be done without knowing $A_i,0\le i \le M$.
Moreover, the dual problem of $min\ 1^T u_i,\ s.t.\ A_i u\le 1$ is:
$\begin{array}{lll}
\max & & - 1^T \lambda_i\\
s.t. & & 1 + A_i^T \lambda_i = 0\\
& & \lambda_i \geqslant 0
\end{array}$
Strong duality holds since the original problem is linear. However the problem may be infeasible, and finding the optimal $\lambda_i^*$ also need to know $A_i$.
