Infinity norm of matrix as inequality constraint in optimization

668 Views Asked by At

Imagine the optimization problem below, where the matrix $\ell_\infty$ norm appears as an inequality constraint:

\begin{equation} \min_{X} \| XB - C\|_F^2 \\ \text{s.t. } \|AXB - B\|_\infty \leqslant t, \end{equation}

where $A_{L \times N}$, $B_{L \times M}$, $C_{N \times M}$ with $L > N$ are given, $t$ is a given threshold, and $X_{N \times L}$ is the optimization variable. We also define the $\ell_{\infty}$ of the matrix as maximum of the absolute values of the matrix elements.

Defining $T_{L \times M}$ as a matrix whose all elements equal $t$, one can write the $\ell_{\infty}$ constraint in matrix inequality constraint as $-T \leqslant AXB - B \leqslant +T$, where the inequality is element-wise. However, since the matrices are non-square, I am not sure how to get rid of $A$ and $B$. Furthermore, the matrix multiplication in $AXB$ is performed from both sides.

Can this $\ell_{\infty}$ inequality constraint, or equivalently the matrix linear inequality constraint be written in some standard form? I have seen similar forms in control theory but they were talking about square matrices.

Does it help to have some structure in the matrices? For example, I know that $B$ is additionally sparse.