Formal Proof of Minimum of maximum between two values

Question

Consider the following minimization problem:

$\min_{X} \left[ \max \left( \left| X \right|, \left| X -T^2 \right| \right) \right]$

I know the answer is $X = 0.5 T^2$ but I am looking for a formal proof of that.

Thanks in advance

Answer 1

You can solve the problem via linear programming by introducing a variable $Z$ and linear constraints. The problem is to minimize $Z$ subject to \begin{align} Z &\ge X \tag1\label1\\ Z &\ge -X \tag2\label2\\ Z &\ge X-T^2 \tag3\label3\\ Z &\ge -(X-T^2) \tag4\label4 \end{align} As you noted, $X=Z=T^2/2$ is optimal. The optimal dual variables $\pi=(1/2,0,0,1/2)$ provide a short certificate of optimality. Explicitly, multiplying \eqref{1} through \eqref{4} by $\pi$ yields $$(1/2)Z+0Z+0Z+(1/2)Z \ge (1/2)X+0(-X)+0(X-T^2)+(1/2)(-X+T^2),$$ which simplifies to $$Z \ge T^2/2,$$ as claimed.

Answer 2

Here's a shorter proof (without linear programming), motivated by plotting the graphs of $Y=|X|$ and $Y=|X-T^2|$: $$\max(|X|,|X-T^2|) = |X-T^2/2| + T^2/2 \ge T^2/2$$