2
$\begingroup$

Given $P_1,P_2,\cdots,P_N$.

\begin{array}{ll} \text{maximize} & \det X\\ \text{subject to} & \mathrm X_{ii}\leq P_i \\\forall i=1,2,\cdots,n\end{array}

$X\in\mathbb{R}^{n\times n}$, $X>0$ (i.e. positive definite).

For $n=2$, maximum is achieved when $X_{ii}=P_i$ and $X$ is diagonal matrix.

Then for $n=3$, Let $X=\begin{bmatrix}X_1 & X_2\\X_2^T &x_3\end{bmatrix}$, where $X_1\in\mathbb{R}^{2\times2}$.

$\det(X)=\det(X_1)\times \det(x_3-X_2^TX_1^{-1}X_2)\leq \det(X_1)\times x_3\leq P_1P_2P_3$.

Then following same logic my conjecture is $\max\{ \det X\}=P_1\cdots P_n$, when $X_{ii}=P_i$.

Is it correct? If not, can you please point my mistake or give me counter example? Thanks

$\endgroup$
2
$\begingroup$

Your problem is equivalent to maximizing $\log \det X$ such that $X_{ii} \leq P_i$ and $X$ is positive definite. That is convenient, because now you have a convex optimization problem that satisfies the Slater condition, so the KKT conditions are necessary and sufficient. The Lagrangian is $$L(X,\lambda) = \log\det X - \sum_i \lambda_i (X_{ii} - P_i)$$ The derivative of $\log\det X$ is $(X^{-1})^T$, so the KKT conditions are: $$(X^{-1})_{ii} - \lambda_i = 0$$ $$(X^{-1})_{ij} = 0 \quad (i \neq j)$$ $$\lambda_i (X_{ii} - P_i)=0$$ $$X_{ii} \leq P_i$$ $$\lambda \geq 0.$$ The point you found satisfies these conditions and is therefore optimal.

$\endgroup$
  • $\begingroup$ what if rank$ X< n$? I think in this case these points are not optimal $\endgroup$ – Lee Dec 18 '18 at 9:24
  • 1
    $\begingroup$ @Lee a positive definite matrix has full rank. $\endgroup$ – LinAlg Dec 18 '18 at 15:13

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.