0
$\begingroup$

I need to minimize a complicated loss function, $f\left(\Lambda\right)$ over a set of symmetric matrices, $S_{p}$ of dimension p, such that all the eigenvalues of $\Lambda \in \left[0,1\right]$. I want to set this up as univariate optimization problem. Using spectral decomposition, I can write $\Lambda=Q \Sigma Q^\top$. Where $\Sigma$ is p-dimensional diagonal matrix with eigenvalues along the diagonal. I have freedom to choose the orthogonal matrix Q. Are there any strategies/characterizations to select Q. What kind of restrictions can I impose on Q? Is there a better way to solve this problem?

I also know that, $$\lim_{k \to \infty }\left(\Lambda-I_p\right)^k = 0$$

$\endgroup$
1
$\begingroup$

You haven't told us what your objective function is, so it's not possible to answer the question completely. However, problems like this are commonly solved by semidefinite programming techniques.

The constraint that the eigenvalues of $\Lambda$ all lie in the interval $[0,1]$ can be written as

$\Lambda \succeq 0$

(This notation just means that $\Lambda$ is symmetric and positive semidefinite) and

$I-\Lambda \succeq 0$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I edited the description. I cannot use semi definite programming here for the reason that I must objective (loss function) is more complicated and it may not be possible to represent it in standard form $\endgroup$ – Kumar Jul 8 '15 at 4:22
1
$\begingroup$

As Brian Borchers wrote, we need to know what your objective function is. We also need to know what additional constraints, if any, there are.

Minimum eigenvalue >= 0 is a convex senidefinite constraint, as is maximum eigenvalue <= 1. Therefore, your optimization problem is a convex SDP (SemiDefinite Program, meaning convertible into standard form) if your objective function is convex, and presuming that if there are any additional constraints, they are convex.

I don't see why you would or should want to set this up as a one-dimensional optimization problem. There probably is no point or value for you to do the spectral decomposition. You can make the whole matrix an optimization variable, and then impose whatever constraints there are, including constraining any matrix elements to fixed values if they are off limits to the optimization.

If your objective function and any other constraints are convex, you should be able to formulate the optimization problem in YALMIP and have YALMIP solve it with a convex SDP solver (SeDuMi and SDPT3, among others, are free for everyone). If your objective function and any other constraints also happen to comply with CVX's Disciplined Convex Programming (DCP) rules, you could also use CVX, which has a lesser learning curve than YALMIP, and includes SeDuMi and SDPT3 with the CVX installation. YALMIP and CVX take care of converting your problem into a standard form required by solvers - you don't need to do that.

If the objective function or any other constraints are not convex, you should be able to have YALMIP use the local non-convex SDP solver PENLAB to solve the problem, but there will be no guarantee that any local optimum which is found by PENLAB (or PENBMI per next paragraph) is globally optimal.

All the software and solvers mentioned above run under MATLAB and are free for all users. There is a non-free solver, PENBMI, from the same developers as PENLAB, which may or may not work better, and can also be invoked by YALMIP to solve your problem. You have to install solvers under MATLAB to use with YALMIP. Convex SDP solvers SeDuMi and SDPT 3 come ready to go when you install CVX, and you can actually use the CVX SeDuMi and SDPT3 installations for use under YALMIP.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Apparently the OP has no interest in providing additional information, such as the objective function and any addtiional constraints. $\endgroup$ – Mark L. Stone Jul 14 '15 at 0: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.