[Csdp] Csdp Digest, Vol 27, Issue 4

Hui Wu wuhuing at gmail.com
Fri Nov 15 12:35:10 EST 2013 

 Thank Imre. Will try this solution.

Hui


On Fri, Nov 15, 2013 at 9:30 AM, Imre Pólik <imre.polik at gmail.com> wrote:

> 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/f03d1377/attachment-0001.html>

More information about the Csdp mailing list