2
$\begingroup$

Let $f(X)$ be convex and continuous function , with $X$ a PSD matrix.

Assume that under the affine set of constraints $\mathcal{A}(X)=b$ and the convex constraint $f(X)\le1$ there is an optimal, unique solution $X^*$ for which $f(X^*)$ is maximal.

How can I maximize $f(X)$ under the constraints $\mathcal{A}(X)=b$, $f(X)\le1$ and $X\ge0$?

$\endgroup$
5
  • $\begingroup$ You are maximizing a convex function subject to convex constraints, i.e., you are minimizing a concave function subject to convex constraints. So this is a concave programming problem, not a convex programming problem, if this is what you really mean. I don't think that knowledge of there being a unique (global) maximum of the problem without the PSD constraint tells you anything about the uniqueness of globala maximum with PSD constraint. If the constraint set is compact, then there will be a global maximum, not necessarily unique, at an extreme of the constraints. $\endgroup$ Oct 6, 2015 at 13:17
  • $\begingroup$ In general, if the problem is as you have stated it (see my above comment to confirm that is your problem), it is a potentially difficult global optimization problem, which perhaps can be solved using a branch and bound and/or interval analysis rigorous global optimizer, although there don't seem to be any at the moment which accept PSD constraints, so you have to reformulate, thereby making the problem even more difficult potentially. But the difficulty depends on your specific objective function and constraints. Do you have a concrete specific problem to solve? If so, tell us what it is. $\endgroup$ Oct 6, 2015 at 13:20
  • $\begingroup$ Thanks for the reply. I'm not sure I undestood, if the set of constraints is compact then the function might be maximized? A particular case I'm interested in is $f(X)$=$\lambda_{max}(X)$, that is, the largest eigenvalue. $\endgroup$ Oct 6, 2015 at 19:00
  • $\begingroup$ So you want to maximize the largest eigenvalue, subject to the minimum eigenvalue being >= 0? What are your other constraints? $\endgroup$ Oct 7, 2015 at 0:04
  • $\begingroup$ As for maximization vs. minimization, you have to tell me (the board) what you want to do. I was just quoting a standard result that when minimizing a concave function (i.e., maximizing a convex function) subject to compact convex constraints, there is a global optimum at an extreme of the constraints, which is not to rule out that there could be other global opitma, at an extreme of the constraints or otherwise. $\endgroup$ Oct 7, 2015 at 0:08

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.