On the use of the Triangle Inequality in Optimization

204 Views Asked by At

Can the Triangle Inequality be used as follows?

$$\max_{x\in\mathcal{R}^m,\ x\neq 0} \ \frac{\| Ax + Bx\|_2}{\|x\|_2} \leq \max_{x\in\mathcal{R}^m,\ x\neq 0} \ \frac{\| Ax \|_2}{\|x\|_2}+ \frac{\|Bx\|_2}{\|x\|_2}$$ $$ = \max_{x\in\mathcal{R}^m,\ x\neq 0} \ \frac{\| Ax \|_2}{\|x\|_2}+ \max_{x\in\mathcal{R}^m,\ x\neq 0} \frac{\|Bx\|_2}{\|x\|_2}$$ where $A,B\in\mathcal{R}^{n\times m}$.

When does the Triangle Inequality not hold in optimization?

1

There are 1 best solutions below

0
On BEST ANSWER

The first inequality is a correct application of the Triangle Inequality. However, the equality in the next line is not valid; it should be $\leq$ in general. The reason is that compared to the line above it, one can choose different $x$ values for each maximum, while the line above it requires you to use the same $x$. This extra flexibility leads to the inequality.