In general, there is no single linear program (LP) that exactly computes $\lambda_{\max}(A)$ for every symmetric matrix $A$.
Suppose, for contradiction, that there exists a polytope $P\subseteq\mathbb S^n$ (independent of $A$) such that for all symmetric $A$,
$$
\lambda_{\max}(A)=\max_{X\in P}\,\langle A,X\rangle
=\max_{X\in P}\operatorname{Tr}(AX). \tag{\(\star\)}
$$
The right-hand side is exactly the support function $h_P(A)$ of the polytope $P$. If $V^1,\ldots,V^m$ are the (finitely many) extreme points of (P), then
$$
h_P(A)=\max_{k=1,\dots,m}\,\langle A, V^k\rangle .
$$
Hence $A\mapsto h_P(A)$ is the maximum of finitely many affine functions—i.e., a piecewise-linear function of $A$. Along any line $A(t)=A_0+tH$, this has the form $t\mapsto \max_k\{\alpha_k t + \beta_k\}$.
However, $\lambda_{\max}(A)$ is not piecewise linear. Consider
$$
A(t)=\begin{bmatrix} t & 1\\ 1 & -t\end{bmatrix},\qquad t\in\mathbb R .
$$
Its eigenvalues are $\lambda_\pm(t)=\pm\sqrt{t^2+1}$, so
$$
\lambda_{\max}\big(A(t)\big)=\sqrt{t^2+1},\qquad
\frac{d^2}{dt^2}\sqrt{t^2+1}=\frac{1}{(t^2+1)^{3/2}}>0,
$$
which is strictly curved on every interval—impossible for a piecewise-linear function. This contradicts $(\star)$. Therefore no fixed polytope $P$ (hence no single LP) can exactly represent $\lambda_{\max}(A)$.
