0
$\begingroup$

Suppose you have a concave function defined over a non-polyhedral convex cone and you are interested in the infimum. What would be standard approaches to tackle the question? (The cone is actually PSD but I am having some difficulty expressing the function as a semidefinite program, so I thought maybe casting a wider net would be beneficial).

UPDT: The specific function I have in mind goes like this. Take a fixed real matrix $A$ and let $f(X)=\min{diag(AX)}$ for all $X \in PSD$, excluding $X=0$. So actually, I'm looking at the cone without it's vertex, possibly complicating matters further.

UPDT2: Let's also assume we are taking a compact subset of the cone (in the PSD case, we can take all the diagonal entries to be $1$).

Improve this question
$\endgroup$
6
  • $\begingroup$ it would be beneficial to see the explicit formulation. But since you are trying to minimize a concave function it won't be that easy.... $\endgroup$
    – Suvrit
    Commented Aug 28, 2012 at 11:28
  • $\begingroup$ Yes, I understand it'd be hard:) That's why i want to know if there are some approaches people have developed to this kind of problem. Thanks! $\endgroup$
    – Felix Goldberg
    Commented Aug 28, 2012 at 11:33
  • $\begingroup$ Since it is in general NP-hard, it is of value to look at the specific case that you might have; perhaps that may be amenable to a global solution, or at least a good approximation algorithm....(if the solution exists at all) $\endgroup$
    – Suvrit
    Commented Aug 28, 2012 at 11:37
  • $\begingroup$ If I understand the problem correctly, can't you minimize $(AX)_{ii}$ over the psd cone for each $i$ individually and then take the $i$ which makes this smallest? Of course, since the set of psd matrices is a cone and scaling $X$ scales your objective, you will either get an optimal value of $0$ achieved at $0$ (or as you approach $0$ if you are interested in the infimum and not including zero) or else the infimum will be $-\infty$. $\endgroup$
    – Noah Stein
    Commented Aug 28, 2012 at 12:26
  • $\begingroup$ Yep: suppose $A$ is a diagonal matrix with $-1$ as its 1st entry, and all other entries zero. Then, clearly let $X=tI$, with $t\to \infty$ makes the problem unbounded below, and there is no minimum. The infimum is $-\infty$. So the problem needs either a compact set or some other modifications before it is well-posed. $\endgroup$
    – Suvrit
    Commented Aug 28, 2012 at 14:00

1 Answer 1

Reset to default
-1
$\begingroup$

http://en.wikipedia.org/wiki/Convex_optimization#Convex_maximization

Improve this answer
$\endgroup$

You must log in to answer this question.

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