Matrix norm in the objective of an optimization problem

Question

I am stuck with the following optimization problem from research. The optimization problem have the following objective function: $\|Q-H\|_\infty$. Here $Q$ is a PSD matrix and $H$ is a symmetric constant matrix.

The objective function looks to be non-linear. Is there any way to linearize the objective function? Any pointers greatly appreciated.

Answer 1

You can rephrase $\| Q - H \|_\infty$ using additional dummy variables and constraints, and turn the problem into a linear semidefinite program.

Just use following the tricks

1. For $x\in\mathbb R, u, v \ge 0$ with $x = u - v$ it follows $|x| \le u+v$. The equality holds if $u$ or $v$ is zero.

2. Instead of minimize $\max\{x,y\}$, minimize $z$ with $x \le z$ and $y \le z$.