spectrum fails to find isolated zeros

[vasdommes]

Repro

The problem

Consider the problem: maximize -y s.t. 1+x^4 + y(x^4/12 + x^2) >= 0 for all x>=2, and for x=2/3, x=4/3

It has solution y = -2.038. With this value, the polynomial has two zeros, x = 0.823 and x = 4/3. Zero at 4/3 corresponds to a saturated positivity constraint, so spectrum should find it, but fails.

Generate SDP

This Mathematica code generates PVM input for the above problem (you may replace test/data/end-to-end_tests/1d-isolated-zeros/bin and test/out/end-to-end_tests/1d-isolated-zeros/bin/ with your folder):

SetDirectory@NotebookDirectory[];
<<"mathematica/SDPB.m";
Module[
 {
  pols = {
    PositiveMatrixWithPrefactor[
     DampedRational[1, {}, 1/E, x],
     {{{1 + x^4, x^4/12 + x^2}}} /. x -> x + 2
     ],
    PositiveMatrixWithPrefactor[
     DampedRational[1, {}, 1/E, x],
     {{{1 + x^4, x^4/12 + x^2}}} /. x -> 2/3
     ],
    PositiveMatrixWithPrefactor[
     DampedRational[1, {}, 1/E, x],
     {{{1 + x^4, x^4/12 + x^2}}} /. x -> 4/3
     ]
    },
  norm = {1, 0},
  obj = {0, -1}
  },
 WriteBootstrapSDP["test/data/end-to-end_tests/1d-isolated-zeros/pvm.xml", SDP[obj, norm, pols]]
 ]

Run spectrum

Run pvm2sdp, spdb and spectrum:

mpirun -n 1  build/pvm2sdp bin 768 test/data/end-to-end_tests/1d-isolated-zeros/pvm.xml test/out/end-to-end_tests/1d-isolated-zeros/bin/sdp.zip

mpirun -n 1  build/sdpb --checkpointInterval 3600 --maxRuntime 1340 --dualityGapThreshold 1.0e-30 --primalErrorThreshold 1.0e-30 --dualErrorThreshold 1.0e-30 --initialMatrixScalePrimal 1.0e20 --initialMatrixScaleDual 1.0e20 --feasibleCenteringParameter 0.1 --infeasibleCenteringParameter 0.3 --stepLengthReduction 0.7 --maxComplementarity 1.0e100 --maxIterations 1000 --verbosity 1 --procGranularity 1 --writeSolution x,y  --checkpointDir=test/out/end-to-end_tests/1d-isolated-zeros/bin/ck --outDir=test/out/end-to-end_tests/1d-isolated-zeros/bin/out --precision=768 --procsPerNode=1 --sdpDir=test/out/end-to-end_tests/1d-isolated-zeros/bin/sdp.zip

mpirun -n 1  build/spectrum  --format=PVM --input=test/data/end-to-end_tests/1d-isolated-zeros/pvm.xml --output=test/out/end-to-end_tests/1d-isolated-zeros/bin/spectrum.json --precision=768 --solution=test/out/end-to-end_tests/1d-isolated-zeros/bin/out --threshold=1e-10

Output spectrum.json should contain a zero at 4/3 for the third block, but it doesn't:

[
  {
    "zeros":
      [
      ],
    "error": "1.0562524597360583337573069506108746335315451887655830574165928895340864631033674112019596635496141058212641250675937499562542133584960258556025956504667784309160337632078674204256901869415481801704638694677768425245544266979804121507e-30"
  },
  {
    "zeros":
      [
      ],
    "error": "2.095731219614796108403644916691961569628769586161190798909263556734475250735374092554378010868024452879644779179134897687101936373532115722952718724068957113539240939763253896007982570257798949218397185511285978606975217990023424953e-30"
  },
  {
    "zeros":
      [
      ],
    "error": "0.48991935483870967741935483870873239717071607179703074516625492115066921878322723123658867648246469430121912667532024803889317061789256294639626253051508541414819586805959820018744516901258235728395112924931889854904825444993731832109"
  }
]

[davidsd]

Only the zero at 4/3 corresponds to a saturated positivity constraint, so spectrum should only find that one.

On Mon, Nov 20, 2023 at 5:38 PM Vasiliy Dommes @.***> wrote:

Repro The problem

Consider the problem: maximize -y s.t. 1+x^4 + y(x^4/12 + x^2) >= 0 for all x>=2, and for x=2/3, x=4/3

It has solution y = -2.038. With this value, the polynomial has two zeros, x = 0.823 and x = 1.333. Spectrum fails to find them.

[image: image] https://user-images.githubusercontent.com/8809142/284402941-1fd31dd6-2030-4e44-8c22-be4a1c9ac3d6.png Generate SDP

This Mathematica code generates PVM input for the above problem (you may replace test/data/end-to-end_tests/1d-isolated-zeros/bin and test/out/end-to-end_tests/1d-isolated-zeros/bin/ with your folder):

@.***[]; <<"mathematica/SDPB.m"; Module[ { pols = { PositiveMatrixWithPrefactor[ DampedRational[1, {}, 1/E, x], {{{1 + x^4, x^4/12 + x^2}}} /. x -> x + 2 ], PositiveMatrixWithPrefactor[ DampedRational[1, {}, 1/E, x], {{{1 + x^4, x^4/12 + x^2}}} /. x -> 2/3 ], PositiveMatrixWithPrefactor[ DampedRational[1, {}, 1/E, x], {{{1 + x^4, x^4/12 + x^2}}} /. x -> 4/3 ] }, norm = {1, 0}, obj = {0, -1} }, WriteBootstrapSDP["test/data/end-to-end_tests/1d-isolated-zeros/pvm.xml", SDP[obj, norm, pols]] ]

Run spectrum

Run pvm2sdp, spdb and spectrum:

mpirun -n 1 build/pvm2sdp bin 768 test/data/end-to-end_tests/1d-isolated-zeros/pvm.xml test/out/end-to-end_tests/1d-isolated-zeros/bin/sdp.zip

mpirun -n 1 build/sdpb --checkpointInterval 3600 --maxRuntime 1340 --dualityGapThreshold 1.0e-30 --primalErrorThreshold 1.0e-30 --dualErrorThreshold 1.0e-30 --initialMatrixScalePrimal 1.0e20 --initialMatrixScaleDual 1.0e20 --feasibleCenteringParameter 0.1 --infeasibleCenteringParameter 0.3 --stepLengthReduction 0.7 --maxComplementarity 1.0e100 --maxIterations 1000 --verbosity 1 --procGranularity 1 --writeSolution x,y --checkpointDir=test/out/end-to-end_tests/1d-isolated-zeros/bin/ck --outDir=test/out/end-to-end_tests/1d-isolated-zeros/bin/out --precision=768 --procsPerNode=1 --sdpDir=test/out/end-to-end_tests/1d-isolated-zeros/bin/sdp.zip

mpirun -n 1 build/spectrum --format=PVM --input=test/data/end-to-end_tests/1d-isolated-zeros/pvm.xml --output=test/out/end-to-end_tests/1d-isolated-zeros/bin/spectrum.json --precision=768 --solution=test/out/end-to-end_tests/1d-isolated-zeros/bin/out --threshold=1e-10

Output spectrum.json should contain two zeros (0.823 for the second block and 1.333 for the third one), but it doesn't:

[ { "zeros": [ ], "error": "1.0562524597360583337573069506108746335315451887655830574165928895340864631033674112019596635496141058212641250675937499562542133584960258556025956504667784309160337632078674204256901869415481801704638694677768425245544266979804121507e-30" }, { "zeros": [ ], "error": "2.095731219614796108403644916691961569628769586161190798909263556734475250735374092554378010868024452879644779179134897687101936373532115722952718724068957113539240939763253896007982570257798949218397185511285978606975217990023424953e-30" }, { "zeros": [ ], "error": "0.48991935483870967741935483870873239717071607179703074516625492115066921878322723123658867648246469430121912667532024803889317061789256294639626253051508541414819586805959820018744516901258235728395112924931889854904825444993731832109" } ]

— Reply to this email directly, view it on GitHub https://github.com/davidsd/sdpb/issues/153, or unsubscribe https://github.com/notifications/unsubscribe-auth/AABZCILQ5OL7UG6F5ZPW26DYFQAXZAVCNFSM6AAAAAA7TZBSPKVHI2DSMVQWIX3LMV43ASLTON2WKOZSGAYDGMRZGA3TEMA . You are receiving this because you are subscribed to this thread.Message ID: @.***>

[vasdommes]

Only the zero at 4/3 corresponds to a saturated positivity constraint, so spectrum should only find that one.

Thanks, updated issue description