Matrix decomposition minimizing infinity norm I have the following minimization problem in diagonal matrix $D$ and matrix $V$
$$\text{minimize} \quad \| A - V D V^T \|_{\infty}$$ 
where square matrix $A$ is given. What approach should I take?
 A: I'm assuming that you're interested in real matrices $A$ because of the use of transpose (rather than the Hermitian conjugate) in your statement of the problem. 
This problem can be reduced to solving a linear programming problem and diagonalizing an $n$ by $n$ matrix.   
If $A$ is symmetric, then $A$ can be diagonalized as 
$A=VDV^{T}$
where $D$ is the diagonal matrix of eigenvalues of $V$ and $V$ is an orthogonal matrix of eigenvectors.  So, you can reduce $\| A -VDV^{T} \|_{\infty}$ to 0 in this case.
If $A$ is not symmetric, then your problem can be written as 
$\min_{B \in S^{n}} \| A - B \|_{\infty}$
where $S^{n}$ is the space of symmetric matrices.  To get $V$ and $D$ from $B$, simply diagonalize $B$. Since the infinity norm of a matrix is the maximum of the row-wise sums of absolute values, this problem can be written as 
$\min_{B \in S^{n}} \max_{i} \sum_{j=1}^{n} | A_{i,j}-B_{i,j} |$
Using standard techniques, we can reformulate this as a linear programming problem.  First, we reduce the inner $\max$:
$\min_{B \in S^{n}} t_{0}$
subject to 
$t_{0} \geq \sum_{j=1}^{n} | A_{i,j}-B_{i,j} |,\;\; i=1, 2, \ldots, n$
Next, we deal with the absolute value of $A_{i,j}-B_{i,j}$ by writing the problem as 
$\min_{B \in S^{n}} t_{0}$
subject to 
$t_{0} \geq \sum_{j=1}^{n} t_{i,j},\;\; i=1, 2, \ldots, n$
$t_{i,j} \geq A_{i,j}-B_{i,j},\;\; i=1, 2, \ldots, n, \; j=1, 2, \ldots, n.$
$t_{i,j} \geq -(A_{i,j}-B_{i,j}),\;\; i=1, 2, \ldots, n, \; j=1, 2, \ldots, n.$
Finally, we can rewrite the $B \in S^{n}$ constraints to get:
$\min_{B,t} t_{0}$
subject to 
$t_{0} \geq \sum_{j=1}^{n} t_{i,j},\;\; i=1, 2, \ldots, n$
$t_{i,j} \geq A_{i,j}-B_{i,j},\;\; i=1, 2, \ldots, n, \; j=1, 2, \ldots, n.$
$t_{i,j} \geq -(A_{i,j}-B_{i,j}),\;\; i=1, 2, \ldots, n, \; j=1, 2, \ldots, n.$
$B_{i,j}=B_{j,i},\;\; i \neq j$.
This is an LP with $n^{2}+n+1$ variables and $n(n=1)/2+2n^{2}+n$ constraints.
You can also use the fact that $B_{i,j}=B_{j,i}$ to reduce the number of variables to $n(n+1)/2+n+1$ and eliminate $n(n-1)/2$ of the constraints.  
Once you've found an optimal $B$, diagonalize $B$ to obtain $D$.  
