MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$).

share|cite|improve this question
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.... – Suvrit Aug 28 '12 at 11:28
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! – Felix Goldberg Aug 28 '12 at 11:33
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) – Suvrit Aug 28 '12 at 11:37
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$. – Noah Stein Aug 28 '12 at 12:26
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. – Suvrit Aug 28 '12 at 14:00

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.