sci.op-research

?? wrote:
> On Feb 25, 7:55 pm, Johan Löfberg wrote:
>> Bess wrote:
>>> Hi, can anyone help me? I solve a semidefinite programming problem,
>>> and the solution matrix is actually full-rank cause the algorithm
>>> omits the rank-1 constraint. So my task is to reduce this full-rank
>>> solution matrix into rank-1 one.
>>> any reply would be appreciated. Thanks.
>>> Bess
>> I hope you are aware that this is in general an intractable problem
>> (i.e. finding a specified-rank solution to a semidefinite program)?
>>
>> /johan
>
> Thanks for your reply. I see that is an intractable problem indeed, so
> do you mean i am hopeless? do i have to give up?
>
> Bess

Depends on what you are looking for. A guaranteed globally optimal
solution, or are you OK with a local optimizer?

If you are OK with a locally optimal solution, you can go for some kind
of alternating projections strategy or similar. If you have a very
specific problem, better heuristics may exist though

As an example, the solver lmirank by Robert Orsi attempts to solve these
problems locally using a projection strategy. You can find examples here

http://control.ee.ethz.ch/~joloef/wiki/pmwiki.php?n=Tutorials.Rank

You are welcome to email me for more details regarding your problem, as
I have colleagues who are working on the topic, and they might be
interested in interesting examples.

cheers,
johan