How to find the maximal 2-norm $\|x\|$ when the point $x$ in a Polyhedron?

45 Views Asked by At

Let $A \in \mathbb{R}^{q\times n}$, $x \in \mathbb{R}^n$ and $b \in\mathbb{R} ^{q}$.
The set $H=\{x:Ax\leq b\}$ is a Polyhedral set. I got to determine the maximum $$S_{max}=\max\{x^Tx:Ax\leq b\}$$ Maybe I can rewrite the problem as $$L_{max}=\max\{x^Tx+\sum_i\lambda_i(A_ix-b_i)\}$$ by Langrangian approach. The maximum is caused by KKT conditions, i.e. $\frac{dL_{max}}{dx}=0$ with $\lambda_i\ge0$, $\lambda_i(A_ix-b_i)=0$ and $A_ix-b_i\le0$ for $i=1,2,\cdots,q$. Here, $A_i$ is the $i^{th}$ row of $A$ and $b_i$ is the $i^{th}$ ingredient of $b$.
$\frac{dL_{max}}{dx}=2x^T+\sum_i\lambda_iA_i=0$ implies $x=-\frac{1}{2}\sum_i\lambda_iA_i^T$. The maximum $x=-\frac{1}{2}\sum_i\lambda_iA_i^T$ is irrelevant to $b$. Is it wrong? I guess the maximum is obtained when $x$ is the some vertex of $H$.