[Csdp] Csdp Digest, Vol 27, Issue 4

Imre Pólik imre.polik at gmail.com
Fri Nov 15 12:30:02 EST 2013 

If your matrix X is actually rank 1, then it has a decomposition into z*z'.
In this case only one eigenvalue is nonzero, and the others are zero.

The full eigenvalue decomposition is the sum of such rank-1 terms.

The basic fact is that the rank of X is the number of its nonzero
eigenvalues (counted with multiplicities).
Imre


On Fri, Nov 15, 2013 at 12:26 PM, Hui Wu <wuhuing at gmail.com> wrote:

>
> Hi Imre, thanks for your solution. Can you give me some references for
> explaining why that works ?
>
> Hui
>
>
> On Fri, Nov 15, 2013 at 9:07 AM, Imre Pólik <imre.polik at gmail.com> wrote:
>
>> This means that you want a rank-1 solution for your problem. This in
>> general is much harder than just solving an SDP. Your best bet is to
>> perform an engeivalue decomposition and choose the eigenvector that blongs
>> to the largest eigenvalue. If all the other eigenvalues are small, then you
>> are fine.
>>
>> Best,
>> Imre
>>
>>
>> On Fri, Nov 15, 2013 at 12:00 PM, <csdp-request at list.coin-or.org> wrote:
>>
>>> Send Csdp mailing list submissions to
>>>         csdp at list.coin-or.org
>>>
>>> To subscribe or unsubscribe via the World Wide Web, visit
>>>         http://list.coin-or.org/mailman/listinfo/csdp
>>> or, via email, send a message with subject or body 'help' to
>>>         csdp-request at list.coin-or.org
>>>
>>> You can reach the person managing the list at
>>>         csdp-owner at list.coin-or.org
>>>
>>> When replying, please edit your Subject line so it is more specific
>>> than "Re: Contents of Csdp digest..."
>>>
>>>
>>> Today's Topics:
>>>
>>>    1. Re: SDP is dual infeasible (Wendel Melo)
>>>
>>>
>>> ----------------------------------------------------------------------
>>>
>>> Message: 1
>>> Date: Fri, 15 Nov 2013 04:23:59 -0500
>>> From: Wendel Melo <wendelalexandre at gmail.com>
>>> To: Hui Wu <wuhuing at gmail.com>
>>> Cc: Brian Borchers <borchers.brian at gmail.com>,  "csdp at list.coin-or.org"
>>>         <csdp at list.coin-or.org>
>>> Subject: Re: [Csdp] SDP is dual infeasible
>>> Message-ID:
>>>         <CAATj=
>>> 87UBTuRDhGNSbhLeW2tZFZ48a4uZMY_T5FzOKN9RkygPw at mail.gmail.com>
>>> Content-Type: text/plain; charset="iso-8859-1"
>>>
>>> Hi guys, one more question. After I get X, how can I get the vector of z,
>>> which satisfies z' * z = X. I tried Cholesky Decomposition in Matlab, it
>>> can only get an upper/lower triangular matrix. Any pkg to decompose X to
>>> a
>>> vector z ? Thanks
>>>
>>> I suppose that decomposition is not possible for all matrix X
>>>
>>>
>>> 2013/11/15 Hui Wu <wuhuing at gmail.com>
>>>
>>> > Hi guys, one more question. After I get X, how can I get the vector of
>>> z,
>>> > which satisfies z' * z = X. I tried Cholesky Decomposition in Matlab,
>>> it
>>> > can only get an upper/lower triangular matrix. Any pkg to decompose X
>>> to a
>>> > vector z ? Thanks
>>> >
>>> >
>>> > Hui
>>> >
>>> >
>>> >
>>> > On Thu, Nov 14, 2013 at 10:20 PM, Hui Wu <wuhuing at gmail.com> wrote:
>>> >
>>> >> Hi All, after adding one constraint, the SDP is successfully solved.
>>> >> Really appreciate all of you guys' analysis !
>>> >>
>>> >> Hui
>>> >>
>>> >>
>>> >>
>>> >> On Thu, Nov 14, 2013 at 5:24 PM, Hui Wu <wuhuing at gmail.com> wrote:
>>> >>
>>> >>> yeah good analysis.
>>> >>>
>>> >>> If primal is feasible, as my input is primal form, does it mean that
>>> the
>>> >>> output solution is feasible ? Thanks
>>> >>>
>>> >>> Hui
>>> >>>
>>> >>>
>>> >>> On Thu, Nov 14, 2013 at 5:22 PM, Brian Borchers <
>>> >>> borchers.brian at gmail.com> wrote:
>>> >>>
>>> >>>>
>>> >>>>
>>> >>>>
>>> >>>> On Thu, Nov 14, 2013 at 6:17 PM, Hui Wu <wuhuing at gmail.com> wrote:
>>> >>>>
>>> >>>>> One potential issue I can think about is the constraints are not
>>> >>>>> enough to make it bounded. I will add more constraints to see if
>>> it can be
>>> >>>>> feasible. Thanks again
>>> >>>>>
>>> >>>>
>>> >>>> It appears from the output that this problem is primal feasible and
>>> >>>> dual unbounded.  Additional constrains could result in a problem
>>> with an
>>> >>>> optimal solution.
>>> >>>>
>>> >>>>>
>>> >>>>> Hui
>>> >>>>>
>>> >>>>>
>>> >>>>> On Thu, Nov 14, 2013 at 5:11 PM, Wendel Melo <
>>> >>>>> wendelalexandre at gmail.com> wrote:
>>> >>>>>
>>> >>>>>> Yes. But CSDP is declaring dual infeasibility. If the dual is
>>> >>>>>> infeasible, your (primal) problem can be unbounded or infeasible
>>> also.
>>> >>>>>>
>>> >>>>>>
>>> >>>>>> > If it is unbounded, then it needs more constraints, right ?
>>> >>>>>>
>>> >>>>>> More or less. Maybe yes, but maybe you have a mistake on your
>>> >>>>>> objective function or in some constraint...
>>> >>>>>>
>>> >>>>>>
>>> >>>>>> 2013/11/14 Hui Wu <wuhuing at gmail.com>
>>> >>>>>>
>>> >>>>>>>
>>> >>>>>>> Hi Wendel, if it is unbounded, it means there is no optimal
>>> >>>>>>> solution, but there should have feasible solutions, right ?
>>> >>>>>>>
>>> >>>>>>> Hui
>>> >>>>>>>
>>> >>>>>>>
>>> >>>>>>> On Thu, Nov 14, 2013 at 4:58 PM, Hui Wu <wuhuing at gmail.com>
>>> wrote:
>>> >>>>>>>
>>> >>>>>>>> I am not too sure ...
>>> >>>>>>>> If it is unbounded, then it needs more constraints, right ?
>>> >>>>>>>>
>>> >>>>>>>> Appreciate your analysis !
>>> >>>>>>>>
>>> >>>>>>>> Hui
>>> >>>>>>>>
>>> >>>>>>>>
>>> >>>>>>>> On Thu, Nov 14, 2013 at 4:56 PM, Wendel Melo <
>>> >>>>>>>> wendelalexandre at gmail.com> wrote:
>>> >>>>>>>>
>>> >>>>>>>>> Maybe your problem is unbounded and so, CSDP is declaring
>>> >>>>>>>>> infeasibility. (We can say primal objective function getting
>>> huge vaules
>>> >>>>>>>>> before CSDP stop).
>>> >>>>>>>>>
>>> >>>>>>>>> Can you be sure your problem is not unbounded?
>>> >>>>>>>>>
>>> >>>>>>>>>
>>> >>>>>>>>> 2013/11/14 Hui Wu <wuhuing at gmail.com>
>>> >>>>>>>>>
>>> >>>>>>>>>>  resend after joining the mail list :)
>>> >>>>>>>>>> On Nov 13, 2013 9:51 PM, "Hui Wu" <wuhuing at gmail.com> wrote:
>>> >>>>>>>>>>
>>> >>>>>>>>>>> Hi Guys, I am using csdp's matlab interface for the following
>>> >>>>>>>>>>> sdp problem, which is described in the attachment. While I
>>> run the script,
>>> >>>>>>>>>>> I get
>>> >>>>>>>>>>>
>>> >>>>>>>>>>> *>>[x, y, z] = genSample();*
>>> >>>>>>>>>>> *Number of constraints: 6 *
>>> >>>>>>>>>>> *Number of SDP blocks: 1 *
>>> >>>>>>>>>>> *Number of LP vars: 0 *
>>> >>>>>>>>>>> *C block 1, blocksize, 6*
>>> >>>>>>>>>>> *Checking constraint 1 *
>>> >>>>>>>>>>> *Checking constraint 2 *
>>> >>>>>>>>>>> *Checking constraint 3 *
>>> >>>>>>>>>>> *Checking constraint 4 *
>>> >>>>>>>>>>> *Checking constraint 5 *
>>> >>>>>>>>>>> *Checking constraint 6 *
>>> >>>>>>>>>>> *Iter:  0 Ap: 0.00e+00 Pobj:  0.0000000e+00 Ad: 0.00e+00
>>> Dobj:
>>> >>>>>>>>>>>  0.0000000e+00 *
>>> >>>>>>>>>>> *Iter:  1 Ap: 1.00e+00 Pobj:  2.4901133e+04 Ad: 6.77e-01
>>> Dobj:
>>> >>>>>>>>>>>  3.0972415e+03 *
>>> >>>>>>>>>>> *Iter:  2 Ap: 1.00e+00 Pobj:  1.7734229e+05 Ad: 5.18e-01
>>> Dobj:
>>> >>>>>>>>>>>  1.6715331e+02 *
>>> >>>>>>>>>>> *Iter:  3 Ap: 2.10e-02 Pobj:  9.3394935e+05 Ad: 2.66e-02
>>> Dobj:
>>> >>>>>>>>>>>  1.2916856e+03 *
>>> >>>>>>>>>>> *Iter:  4 Ap: 1.00e+00 Pobj:  5.7585163e+07 Ad: 1.05e-01
>>> Dobj:
>>> >>>>>>>>>>>  1.0092369e+03 *
>>> >>>>>>>>>>> *Iter:  5 Ap: 2.82e-03 Pobj:  5.3050644e+08 Ad: 2.97e-03
>>> Dobj:
>>> >>>>>>>>>>>  8.2813968e+02 *
>>> >>>>>>>>>>> *Iter:  6 Ap: 1.29e-03 Pobj:  2.8396651e+09 Ad: 2.90e-03
>>> Dobj:
>>> >>>>>>>>>>>  9.6682104e+02 *
>>> >>>>>>>>>>> *Declaring dual infeasibility.*
>>> >>>>>>>>>>> *Success: SDP is dual infeasible*
>>> >>>>>>>>>>> *Certificate of dual infeasibility: tr(CX)=1.00000e+00,
>>> >>>>>>>>>>> ||A(X)||=4.91757e-09*
>>> >>>>>>>>>>> *Elements time: 0.000010 *
>>> >>>>>>>>>>> *Factor time: 0.000045 *
>>> >>>>>>>>>>> *Other time: 0.000882 *
>>> >>>>>>>>>>> *Total time: 0.000937 *
>>> >>>>>>>>>>>
>>> >>>>>>>>>>> Can some body help tell me why my SDP is dual infeasible ?
>>> Is it
>>> >>>>>>>>>>> because there is something wrong with my problem setting or
>>> it is normal to
>>> >>>>>>>>>>> my SDP? Thanks
>>> >>>>>>>>>>>
>>> >>>>>>>>>>> Hui
>>> >>>>>>>>>>>
>>> >>>>>>>>>>>
>>> >>>>>>>>>> _______________________________________________
>>> >>>>>>>>>> Csdp mailing list
>>> >>>>>>>>>> Csdp at list.coin-or.org
>>> >>>>>>>>>> http://list.coin-or.org/mailman/listinfo/csdp
>>> >>>>>>>>>>
>>> >>>>>>>>>>
>>> >>>>>>>>>
>>> >>>>>>>>>
>>> >>>>>>>>> --
>>> >>>>>>>>> Wendel
>>> >>>>>>>>>
>>> >>>>>>>>
>>> >>>>>>>>
>>> >>>>>>>
>>> >>>>>>
>>> >>>>>>
>>> >>>>>> --
>>> >>>>>> Wendel
>>> >>>>>>
>>> >>>>>
>>> >>>>>
>>> >>>>> _______________________________________________
>>> >>>>> Csdp mailing list
>>> >>>>> Csdp at list.coin-or.org
>>> >>>>> http://list.coin-or.org/mailman/listinfo/csdp
>>> >>>>>
>>> >>>>>
>>> >>>>
>>> >>>
>>> >>
>>> >
>>>
>>>
>>> --
>>> Wendel
>>> -------------- next part --------------
>>> An HTML attachment was scrubbed...
>>> URL: <
>>> http://list.coin-or.org/pipermail/csdp/attachments/20131115/1e6248b0/attachment-0001.html
>>> >
>>>
>>> ------------------------------
>>>
>>> _______________________________________________
>>> Csdp mailing list
>>> Csdp at list.coin-or.org
>>> http://list.coin-or.org/mailman/listinfo/csdp
>>>
>>>
>>> End of Csdp Digest, Vol 27, Issue 4
>>> ***********************************
>>>
>>
>>
>>
>> --
>> http://imre.polik.net
>>
>> _______________________________________________
>> Csdp mailing list
>> Csdp at list.coin-or.org
>> http://list.coin-or.org/mailman/listinfo/csdp
>>
>>
>


-- 
http://imre.polik.net
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/csdp/attachments/20131115/679196b5/attachment.html>

More information about the Csdp mailing list