Maximizing the trace of a matrix

1,229

Let $x_1, x_2, \dots, x_n$ be the entries on the main diagonal of (symmetric) matrix $\mathrm X$. The entries off the main diagonal are bilinear in the entries on the main diagonal

$$x_{ij} = \rho_{ij} \, x_i x_j$$

where $\rho_{ij} = \rho_{ji} \in [-1,1]$. Let $\rm C := W^{\top} W$. Thus, the objective function is given by

$$\sum_{i=1}^n c_{ii} x_i + 2\sum_{i=1}^n \sum_{j=i+1}^n c_{ij} \, \rho_{ij} \, x_i x_j = \begin{bmatrix} c_{11}\\ c_{22}\\ \vdots\\ c_{nn}\end{bmatrix}^{\top} \begin{bmatrix} x_{1}\\ x_{2}\\ \vdots\\ x_{n}\end{bmatrix} + \begin{bmatrix} x_{1}\\ x_{2}\\ \vdots\\ x_{n}\end{bmatrix}^{\top} \underbrace{\begin{bmatrix} 0 & c_{12} \, \rho_{12} & \dots & c_{1n} \, \rho_{1n}\\ c_{12} \, \rho_{12} & 0 & \dots & c_{2n} \, \rho_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ c_{1n} \, \rho_{1n} & c_{2n} \, \rho_{2n} & \dots & 0\end{bmatrix}}_{=: \mathrm M} \begin{bmatrix} x_{1}\\ x_{2}\\ \vdots\\ x_{n}\end{bmatrix}$$

Let $b := a^2$. We have the following inequality-constrained quadratic program (QP)

$$\begin{array}{ll} \text{maximize} & \mathrm c^{\top} \mathrm x + \mathrm x^{\top} \mathrm M \, \mathrm x\\ \text{subject to} & 1_n^{\top} \mathrm x \leq b\end{array}$$

which can be rewritten as follows

$$\begin{array}{ll} \text{minimize} & \frac 12 \mathrm x^{\top} \mathrm Q \, \mathrm x - \mathrm c^{\top} \mathrm x\\ \text{subject to} & 1_n^{\top} \mathrm x \leq b\end{array}$$

where $\mathrm Q := - 2 \mathrm M$. If $\mathrm Q \succ \mathrm O_n$ (i.e., if $\mathrm M \prec \mathrm O_n$), then the latter QP is convex.

Introducing slack variable $s \in \mathbb R$, the inequality constraint $1_n^{\top} \mathrm x \leq b$ is rewritten as the equality constraint $1_n^{\top} \mathrm x + s^2 = b$. Let the Lagrangian be

$$\mathcal L (\mathrm x, s, \lambda) := \frac 12 \mathrm x^{\top} \mathrm Q \, \mathrm x - \mathrm c^{\top} \mathrm x + \lambda \left( 1_n^{\top} \mathrm x + s^2 - b \right)$$

Taking the partial derivatives and finding where they vanish, we obtain

$$\begin{array}{rl} \mathrm Q \mathrm x + \lambda 1_n &= \mathrm c\\ \lambda s &= 0\\ 1_n^{\top} \mathrm x + s^2 &= b\end{array}$$

From the 2nd equation, we conclude that $\lambda = 0$ or $s = 0$.

  • Suppose $\lambda = 0$. We solve the linear system $\mathrm Q \mathrm x = \mathrm c$ and check if $s^2 = b - 1_n^{\top} \mathrm x$ is nonnegative. If it is not, then the solution is not admissible.

  • Suppose $s = 0$. We solve the linear system $$\begin{bmatrix} \mathrm Q & 1_n\\ \mathrm 1_n^{\top} & 0\end{bmatrix} \begin{bmatrix} \mathrm x\\ \lambda\end{bmatrix} = \begin{bmatrix} \mathrm c\\ b\end{bmatrix}$$

Share:
1,229
Mike
Author by

Mike

Updated on April 07, 2020

Comments

  • Mike
    Mike over 3 years

    $$\begin{array}{ll} \text{maximize} & \mbox{tr} (WXW^T)\\ \text{subject to} & \mbox{tr} (X) \leq a^2\end{array}$$

    where the off-diagonal entries of $X$ are $x_{i,j}=\rho_{i,j} x_{i,i}x_{j,j} $, where $-1 \le \rho_{i,j} \le1$ and $\rho_{i,j} = \rho_{j,i}$, and $W$ is full column matrix.

    I just did the derivative with respect to $X$, it is $W^TW$, which is a positive semidefinite matrix. What property can I use in order to maximize the objective function?

    • Aaron
      Aaron over 6 years
      The max over what? Is $X$ fixed? is $W$ fixed? Does $W$ satisfy any properties? You have given properties of $X$, but you haven't fully specified your problem.
    • Mike
      Mike over 6 years
      Sorry for the misleading. W is fixed. X is the variable, which is a matrix.
    • user1551
      user1551 over 6 years
      Linear objective function with multiple linear or quadratic constraints. I think it takes an optimisation package to solve it.
    • Mike
      Mike over 6 years
      Any clue to get a closed form solution.