# How to find the maximum of $\boldsymbol{x}^T \boldsymbol{A} \boldsymbol{x}$ subject to $\boldsymbol{q}^T \boldsymbol{x}=1$?

I want to solve the following problem in $$\boldsymbol{x} \in \mathbb R^{n}$$

$$\begin{array}{ll} \text{maximize} & \boldsymbol{x}^T \boldsymbol{A} \boldsymbol{x}\\ \text{subject to} & \boldsymbol{q}^T \boldsymbol{x} = 1\\ & x_i \geq 0\end{array}$$

where matrix $$\boldsymbol{A}$$ is positive definite matrix and $$x_i$$ denotes the $$i$$-th entry of $$\boldsymbol{x}$$.

Actually, I have tried to use Lagrangian multiplier. I directly transformed the objective function to $$-\boldsymbol{x}^T \boldsymbol{A} \boldsymbol{x} + \lambda ( \boldsymbol{q}^T \boldsymbol{x} - 1 )$$ and take its first derivative and set that to zero.

However, the solution obtained did not maximize the objective function, it just makes $$\boldsymbol{x}^T\boldsymbol{A} \boldsymbol{x}$$ smaller and smaller. Then I found that the solution of $$\min_{\boldsymbol{x}} \boldsymbol{x}^T \boldsymbol{A} \boldsymbol{x}$$ with the same constraints is the same with that of $$\max_{\boldsymbol{x}} \boldsymbol{x}^T \boldsymbol{A} \boldsymbol{x}$$.

Update As comments suggested, I changed the situation to $$x_i \geq 0, \forall i$$. Thus for example, when $$\boldsymbol{A}= \left[\begin{matrix} {2 \; 0\\ 0 \;1 }\end{matrix} \right]$$ and $$\boldsymbol{q} = [1,1]^T$$. The problem has a solution $$\boldsymbol{x} = [1 ,0]^T$$ that maximize the objective function. Can this extend to more general case?

• Geometric intuition should suggest that in a noticeable number of cases $\sup\{x^TAx\,:\, q^Tx=1\land \forall i, x_i> 0\}=\infty$ (specifically, cases where $\neg(q>0)$) – Gae. S. Mar 25 at 16:47
• If you are looking for a numerical solution, cplex/gurobi can solve this. – LinAlg Mar 26 at 1:08
• Thanks for your kind comment. I still want to figure it out analytically. – Kris Prokins Mar 26 at 1:13
• Thanks for you comment, but when $x_i \geq 0$, it seems the question have a maximum at the boundary. – Kris Prokins Mar 26 at 2:58
• With the constraint $x_i>0$, I don't think there is any closed-form solution. – user1551 Mar 26 at 7:25

Since $$\mathbf q > \mathbf 0$$, the feasible region $$\{\mathbf x \in \mathbb R^n : \mathbf q^{\mathsf T} \mathbf x = 1, \mathbf x \ge \mathbf 0\}$$ is bounded (we have $$x_i \in [0, \frac1{q_i}]$$ for each $$i$$). It's also closed, so the maximum of $$f(\mathbf x) = \mathbf x^{\mathsf T} \!A \mathbf x$$ must be achieved somewhere in the feasible region.
Because $$f(\mathbf x)$$ is convex, this maximum must be at an extreme point, and this feasible region has only $$n$$ extreme points: for each $$i$$, we can get one of them by setting $$x_i = \frac1{q_i}$$ and all other entries to $$0$$. This point has objective value $$f(\mathbf x) = \frac{A_{ii}}{q_i^2}$$. Now just compare the values $$\frac{A_{11}}{q_1^2}, \dots, \frac{A_{nn}}{q_n^2}$$ and pick the largest.