How to prove: $\max_{\left \| x \right \|=1}x^*(\frac{A+A^*}{2})x\geq \max_{\left \| x \right \|=1}(x^*A^*Ax)^{\frac{1}{2}}$? Problem:
A is an $n\times n$ complex matrix. Let $\lambda _\max(Y)$ and $\sigma _\max(Y)$ denote respectively the largest eigenvalue and the largest singular value of a square matrix $Y$. The question is to prove that: $$\lambda _\max\left(\frac{A+A^*}{2}\right)\leq \sigma _\max (A)$$ 
I started as follows: Since $A$ is Hermitian, then $(A+A^*)$ is Hermitian as well. Then:
$$\lambda_\max\left(\frac{A+A^*}{2}\right)=\max_{\left \| x \right \|=1}x^*\left(\frac{A+A^*}{2}\right)x$$ where $x\in \mathbb{C}^n$
I need to prove the following to finish my proof: $$\max_{\left \| x \right \|=1}x^*\left(\frac{A+A^*}{2}\right)x\geq \max_{\left \| x \right \|=1}(x^*A^*Ax)^{\frac{1}{2}}\tag{1}$$
From the first sight, it looks like I have to use the fact that: $\sqrt{ab}\geq \frac{a+b}{2}$ for $a$ and $b$ positive, but this works only for numbers and not matrices. 
I appreciate if someone can prove the inequality $(1)$.
 A: Your inequality is actually a well-known equality (in the case where $A$ is hermitian).
The right-hand side of your inequality is the operator norm of $A$, i.e.
$$
\max_{\left \| x \right \|=1}(x^*A^*Ax)^{\frac{1}{2}}=\|A\|.
$$
For the left-hand side we get, using the Cauchy-Schwarz inequality,
$$
\max_{\left \| x \right \|=1}\left|x^*(\frac{A+A^*}{2})x\right|\leq\max_{\left \| x \right \|=1}\|x\|\,\left\|\frac{A+A^*}2\right\|\,\|x\|=\left\|\frac{A+A^*}2\right\|\\ \leq\frac{\|A\|+\|A^*\|}2=\frac{\|A\|+\|A\|}2=\|A\|.
$$
Note that so far we don't use that $A$ is hermitian. When $A$ is hermitian, however, we can prove the reverse inequality, which requires a little more work. 
Let
$$
s=\max\{|x^*Ax|:\ \|x\|=1\}
$$
Now take vectors $x,y$ with  $\|x\|=\|y\|=1$. Then
$$
(x\pm y)^*A(x\pm y)=x^*Ax+y^*Ay\pm2\text{Re}\,y^*Ax.
$$
Subtracting one equation from the other we get
$$
4\text{Re}\,y^*Ax=(x+y)^*A(x+y)-(x-y)^*A(x-y)
$$
(this is the real part of what is usually called the polarization identity). Now we get
$$
4\text{Re}\,y^*Ax\leq s\,\|x+y\|^2+s\,\|x-y\|^2=2s\,(\|x\|^2+\|y\|^2)=2s.
$$
Fix $t$ such that $y^*Ax=e^{it}\,|y^*Ax|$. Note that we can do the above process for the vector $e^{-it}x$, and so this shows that 
$$
|y^*Ax|\leq s\ \ \ \ \text{ for any }x,y\text{ with }\|x\|=\|y\|=1.
$$
Taking max over $y$ with $\|y\|=1$, we obtain
$$
\|Ax\|\leq s \ \ \ \text{ for all } x \text{ with } \|x\|=1,
$$
and thus
$$
\|A\|\leq s.
$$
