No subject
Fri Oct 7 20:10:04 EDT 2011
rather than four constraints. To fix this, you'll have to supply the right
hand side of the 5th constraint in line 4, and you'll have to give the
entries in the A5 constraint matrix.
On Tue, Oct 18, 2011 at 11:43 AM, Marcus P S <marcus.ps at gmail.com> wrote:
> Hello all,
>
> I am using SDP to perform maximum likelihood estimation of data for
> some physical problems, but I am running into some strange behaviour
> when the SDP problem becomes larger.
>
> Given an integer parameter N, the SD matrix has 2 blocks, one of
> size 4^N and the other 2^(N+1), while there are 4^N+1 constraints. The
> problem runs fine for randomly generated instance of size N=1,2,3,4.
> However, when I run random instances for N=5, I always end up with the
> dual objective function "running away" (quickly running up to >1E14),
> finally giving up with the message
>
> Stuck at edge of dual feasibility, giving up.
> Failure: return code is 6
> Primal objective value: -1.0208180e+14
> Dual objective value: 4.1157109e+14
> Relative primal infeasibility: 4.99e-01
> Relative dual infeasibility: 8.87e-07
> Real Relative Gap: 1.00e+00
> XZ Relative Gap: 2.00e-01
> DIMACS error measures: 4.99e-01 0.00e+00 6.46e-06 0.00e+00 1.00e+00
> 2.00e-01
> Elements time: 15.671315
> Factor time: 3.575801
> Other time: 275.737643
> Total time: 294.984759
>
> and the resulting answer being very far from the correct solution. I
> assume that this is an issue that can be addressed by tweaking the
> parameters of the numerical algorithm, but I am not sure how to do it.
> I tried changing "minstepfrac" and "maxstepfrac" but if anything that
> only made things worse.
>
> If anyone has run into similar problem or has some useful pointers, I
> would greatly appreciate it.
>
> Below you can find instances of the SDP problems I have been running.
>
> https://gist.github.com/1295649 (N=1)
> https://gist.github.com/1295650 (N=2)
> https://gist.github.com/1295782 (N=3)
> https://gist.github.com/2957fede27de2f8d08ee (N=4)
> https://gist.github.com/1296077 (N=5)
>
> (The last file was too large for gist, so I gzipped and then uuencoded)
>
> Best,
> Marcus
> _______________________________________________
> Csdp mailing list
> Csdp at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/csdp
>
>
--
Brian Borchers borchers at nmt.edu
Department of Mathematics http://www.nmt.edu/~borchers/
New Mexico Tech Phone: (575) 322-2592
Socorro, NM 87801 FAX: (575) 835-5366
--20cf307f34eeaf7bea04af9b9bb8
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Unfortunately, all of your SDPA files are incorrect.=A0 Although CSDP would=
ideally be able to detect this, it doesn't do so, and then the solutio=
n process fails.=A0 Anyway, here's an explanation of what's wrong w=
ith the file for N=3D1.=A0 The other files all appear to have the same defe=
ct:<br>
=A0<br>Here's the file:<br><pre><div class=3D"line" id=3D"LC1">5</div><=
div class=3D"line" id=3D"LC2">2</div><div class=3D"line" id=3D"LC3">4 4</di=
v><div class=3D"line" id=3D"LC4">1 0 0 0 </div><div class=3D"line" id=3D"LC=
5">0 1 2 2 -1.000000e-02</div>
<div class=3D"line" id=3D"LC6">0 1 1 2 -5.027783e-01</div><div class=3D"lin=
e" id=3D"LC7">0 1 3 3 -1.000000e-02</div><div class=3D"line" id=3D"LC8">0 1=
1 3 4.534177e-01</div><div class=3D"line" id=3D"LC9">0 1 4 4 -1.000000e-02=
</div><div class=3D"line" id=3D"LC10">
0 1 1 4 7.358455e-01</div><div class=3D"line" id=3D"LC11">0 2 1 1 -5.000000=
e-01</div><div class=3D"line" id=3D"LC12">0 2 2 2 -5.000000e-01</div><div c=
lass=3D"line" id=3D"LC13">0 2 3 3 -5.000000e-01</div><div class=3D"line" id=
=3D"LC14">0 2 4 4 -5.000000e-01</div>
<div class=3D"line" id=3D"LC15">1 1 1 1 1</div><div class=3D"line" id=3D"LC=
16">2 1 1 2 -1</div><div class=3D"line" id=3D"LC17">2 2 1 2 5.000000e-01</d=
iv><div class=3D"line" id=3D"LC18">2 2 3 4 5.000000e-01</div><div class=3D"=
line" id=3D"LC19">
3 1 1 3 -1</div><div class=3D"line" id=3D"LC20">3 2 2 3 5.000000e-01</div><=
div class=3D"line" id=3D"LC21">3 2 1 4 -5.000000e-01</div><div class=3D"lin=
e" id=3D"LC22">4 1 1 4 -1</div><div class=3D"line" id=3D"LC23">4 2 1 1 5.00=
0000e-01</div>
<div class=3D"line" id=3D"LC24">4 2 2 2 -5.000000e-01</div><div class=3D"li=
ne" id=3D"LC25">4 2 3 3 5.000000e-01</div><div class=3D"line" id=3D"LC26">4=
2 4 4 -5.000000e-01</div></pre>In the first line of the file, you say that=
the problem has five constraints matrices (A1, A2, A3, A4, and A5), plus a=
n objective matrix C.=A0 In line 2, you say that there are two SDP blocks i=
n each matrix, of sizes 4x4 and 4x4 (line 3.)=A0 In line 4, you provide the=
right hand sides for four constraints.=A0 This is incorrect, since you sai=
d that there were five constraints.=A0 In the following lines you give the =
entries for C and the constraint matrices A1, A2, A3, and A4, but not A5.=
=A0 <br>
=A0<br>From what you've said, this problem should actually have five co=
nstraints rather than four constraints.=A0 To fix this, you'll have to =
supply the right hand side of the 5th constraint in line 4, and you'll =
have to give the entries in the A5 constraint matrix.=A0 <br>
<br><br><div class=3D"gmail_quote">On Tue, Oct 18, 2011 at 11:43 AM, Marcus=
P S <span dir=3D"ltr"><<a href=3D"mailto:marcus.ps at gmail.com">marcus.ps=
@gmail.com</a>></span> wrote:<br><blockquote class=3D"gmail_quote" style=
=3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); p=
adding-left: 1ex;">
Hello all,<br>
<br>
=A0I am using SDP to perform maximum likelihood estimation of data for<br>
some physical problems, but I am running into some strange behaviour<br>
when the SDP problem becomes larger.<br>
<br>
=A0Given an integer parameter N, the SD matrix has 2 blocks, one of<br>
size 4^N and the other 2^(N+1), while there are 4^N+1 constraints. The<br>
problem runs fine for randomly generated instance of size N=3D1,2,3,4.<br>
However, when I run random instances for N=3D5, I always end up with the<br=
>
dual objective function "running away" (quickly running up to >=
;1E14),<br>
finally giving up with the message<br>
<br>
Stuck at edge of dual feasibility, giving up.<br>
Failure: return code is 6<br>
Primal objective value: -1.0208180e+14<br>
Dual objective value: 4.1157109e+14<br>
Relative primal infeasibility: 4.99e-01<br>
Relative dual infeasibility: 8.87e-07<br>
Real Relative Gap: 1.00e+00<br>
XZ Relative Gap: 2.00e-01<br>
DIMACS error measures: 4.99e-01 0.00e+00 6.46e-06 0.00e+00 1.00e+00 2.00e-0=
1<br>
Elements time: 15.671315<br>
Factor time: 3.575801<br>
Other time: 275.737643<br>
Total time: 294.984759<br>
<br>
and the resulting answer being very far from the correct solution. =A0I<br>
assume that this is an issue that can be addressed by tweaking the<br>
parameters of the numerical algorithm, but I am not sure how to do it.<br>
I tried changing "minstepfrac" and "maxstepfrac" but if=
anything that<br>
only made things worse.<br>
<br>
If anyone has run into similar problem or has some useful pointers, I<br>
would greatly appreciate it.<br>
<br>
Below you can find instances of the SDP problems I have been running.<br>
<br>
<a href=3D"https://gist.github.com/1295649" target=3D"_blank">https://gist.=
github.com/1295649</a> (N=3D1)<br>
<a href=3D"https://gist.github.com/1295650" target=3D"_blank">https://gist.=
github.com/1295650</a> (N=3D2)<br>
<a href=3D"https://gist.github.com/1295782" target=3D"_blank">https://gist.=
github.com/1295782</a> (N=3D3)<br>
<a href=3D"https://gist.github.com/2957fede27de2f8d08ee" target=3D"_blank">=
https://gist.github.com/2957fede27de2f8d08ee</a> (N=3D4)<br>
<a href=3D"https://gist.github.com/1296077" target=3D"_blank">https://gist.=
github.com/1296077</a> (N=3D5)<br>
<br>
(The last file was too large for gist, so I gzipped and then uuencoded)<br>
<br>
Best,<br>
Marcus<br>
_______________________________________________<br>
Csdp mailing list<br>
<a href=3D"mailto:Csdp at list.coin-or.org">Csdp at list.coin-or.org</a><br>
<a href=3D"http://list.coin-or.org/mailman/listinfo/csdp" target=3D"_blank"=
>http://list.coin-or.org/mailman/listinfo/csdp</a><br>
<br>
</blockquote></div><br><br clear=3D"all"><br>-- <br>Brian Borchers =A0 =A0 =
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0<a href=3D"mailto:borchers at nmt.e=
du" target=3D"_blank">borchers at nmt.edu</a><br>Department of Mathematics =A0=
=A0 =A0<a href=3D"http://www.nmt.edu/%7Eborchers/" target=3D"_blank">http:=
//www.nmt.edu/~borchers/</a><br>
New Mexico Tech =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 Phone: (575) 32=
2-2592<br>Socorro, NM 87801 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 FAX: (575) =
835-5366<br>
--20cf307f34eeaf7bea04af9b9bb8--
More information about the Csdp
mailing list