7
$\begingroup$

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}$.

Any comments would be appreciated!

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?

$\endgroup$
  • 4
    $\begingroup$ 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)$) $\endgroup$ – Gae. S. Mar 25 at 16:47
  • $\begingroup$ If you are looking for a numerical solution, cplex/gurobi can solve this. $\endgroup$ – LinAlg Mar 26 at 1:08
  • $\begingroup$ Thanks for your kind comment. I still want to figure it out analytically. $\endgroup$ – Kris Prokins Mar 26 at 1:13
  • $\begingroup$ Thanks for you comment, but when $x_i \geq 0$, it seems the question have a maximum at the boundary. $\endgroup$ – Kris Prokins Mar 26 at 2:58
  • 2
    $\begingroup$ With the constraint $x_i>0$, I don't think there is any closed-form solution. $\endgroup$ – user1551 Mar 26 at 7:25
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nice solution. The maximum of a convex function over the polyhedron is achieved at one of its vertices. $\endgroup$ – River Li Mar 27 at 0:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.