given vector a, how to find vector b such that inifinitive norm of $a -b$ is smallest I'd appreciate any hint for the following problem: Given a vector $a=(a_1, a_2,\ldots,a_n)$, how can I find a vector $b=(b_1, b_2,\ldots,b_n)$ such that $b_1 \leq b_2 \leq \cdots \leq b_n$ and the infinitive norm of the vector $a-b$ is smallest. Thank you.
 A: As @benmachine has pointed out, it is not entirely clear what the infinitive norm is; I'll assume you have been talking about the supremum norm.
A constructive proof
You can find such a function with induction. When $n=1$, take $b_1=a_1$. Suppose, as the induction hypothesis, that for all $k\leq n$ we can find such a sequence $(b_1,\ldots,b_k)$ for any vector $(a_1,\ldots,a_k)$ and let $(a_1,\ldots,a_{n+1})\in\mathbb{R}^{n+1}$. We construct $(b_1,\ldots,b_{n+1})$ in several steps (take pen and paper with you, because it will be easier to follow when you draw what's going on):


*

*First find $n_0$ such that $a_{n_0}$ is maximal among the $a_1,\ldots,a_{n+1}$. 

*
*

*If $n_0=n+1$, define $b_{n+1}:=a_{n_0}$ and construct $(b_1,\ldots, b_n)$ with the induction hypothesis.

*If $n_0<n+1$, find $n_0< n_1\leq n+1$ such that $a_{n_1}$ is minimal among $a_{n_0+1},\ldots,a_{n+1}$. Also, find $$n_2:=\min\{1\leq i\leq n_0:\forall j\geq i,\ a_{n_1}\leq a_j\},$$
Then define $b_{n_2},\ldots,b_{n+1}:=\frac{1}{2}(a_{n_0}+a_{n_1})$. This is clearly the best one can go for.
For the remaining part $1,\ldots,n_2-1$ apply the induction hypothesis to find $b_1,\ldots,b_{n_2-1}$. By the way of construction, it will follow easily that $b_{n_2-1}\leq b_{n_2}$.
You can test your understanding of the above construction by proving that this sequence indeed matches your requirements (that's a good homework too, I guess).

A non-constructive existence proof
To show only existence is easier. For $a\in\mathbb{R}^n$, define the set
$$
D:=\{\|a-b\|_{\infty}:\min\{a_i\}\leq b_1\leq\cdots\leq b_n\leq\max\{a_i\}\}.
$$
This is the image of a continuous function of a compact set, hence it is compact. In particular, it has a minimum. It is not so hard to verify that this minimum is also the infimum of the set
$$
\{\|a-b\|_{\infty}: b_1\leq\cdots\leq b_n\}.
$$

Note that the result can be extended: for every continuous function $a:[0,1]\to\mathbb{R}$ there exists an increasing continuous function $b:[0,1]\to\mathbb{R}$ with the property that $\|a-b\|_\infty$ is minimal.
