1
$\begingroup$

Given a $n \times n$ symmetric matrix $\rm S$, solve the optimization problem in $n \times k$ (where $n \geq k$) matrix $\rm X$

$$\begin{array}{ll} \text{maximize} & \mbox{tr} \left( \mathrm X^\top \mathrm S \,\mathrm X \right)\\ \text{subject to} & \mathrm X \in [0,1]^{n \times k}\end{array}$$

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

This can be formulated and solved as a Quadratic Programming (QP) problem, by minimizing -trace($X^TSX)$ subject to the element-wise bounds $0 \le X \le 1$. If the objective is not convex, then a global (non-convex) QP solver, such as CPLEX, can be used to find the globally optimal solution.

Using YALMIP under MATLAB, and presuming a global QP solver is installed (convex QP solver is sufficient if the objective is convex), this can be formulated and solved with the YALMIP code (portion of line after % is comment):

X = sdpvar(n,k,'full'); declare an n by k matrix variable X
optimize(0 <= X < = 1,-trace(X'*S*X)) % minimize 2nd argument subject to constraints in 1st argument
disp(value(X)) % display optimal value of X (presuming solver reports problem has been solved
Improve this answer
$\endgroup$
2
  • $\begingroup$ @ Mark, Thanks . And I wonder whether can this problem be solved in a eigenvectors way, just like math.stackexchange.com/questions/728037/… $\endgroup$
    – Gehen
    Commented Mar 4, 2018 at 7:00
  • $\begingroup$ @Gehen I don;t believe there's any such simple solution for a general symmetric S as you have. In general, your problem is a non-convex QP not admitting any such simple solution. For special classes of S, it could be a different story. $\endgroup$
    – Mark L. Stone
    Commented Mar 4, 2018 at 13:18

Not the answer you're looking for? Browse other questions tagged .