Quadratic objective function and semidefinite programming

174 Views Asked by At

Given the following problem :

$$ \min. QGQ^T, ~\text{s.t.}~ Q.1_m = 1_n $$ where Q is the unkown matrix of size [n x m], G is a known positive matrix of size [m x m], and minimising with respect to the set of positive definite matrices, how should we proceed to solve it (or formulat it so that a solver can understand it) ?

I tried to use semidefinite programming solver, but the objective function is not in the expected format...

[Edit]

It appears that it is a multiobjective optimisation, in which case the solution could be obtained with scalarisation : $$ \min. tr(W.QGQ^T), ~\text{s.t.}~ tr(A_i^T.Q) = 1, i = 1, ..., n . $$

for any positive semidefinite matrix $W$ of size [n x n], and $A_i$ a matrix of size [n x m] which is filled with 0 and the i-th line with 1 (I reformulated the constraints in a standard format).

The gradient of the objective function is $(W+W^T).QG$, and therefore the KKT equation becomes $ (W+W^T)QG + \sum_j \nu_j.A_j = 0 $ and $tr(A_i^T.Q) = 1$.