endless local search
36 views
Skip to first unread message
Andrea Cassioli
May 4, 2012, 10:57:33 AM5/4/12
to TANGO Project - ALGENCAN
Hi,
I am having quite and hard time trying to figured out what's wrong
with the solution of a quite easy problem. The setting is:
- ALGENCAN 2.3.7 running on Linux and compiled with g++/gfortran
- a convex box constrained problem with a piecewise quadratic
objective function
- variables are bounded in [0,1]
- other solvers can find a solution in some 20-30 function evaluations
Now ALGENCAN performs a couple of major iterations and the it gets
stuck in an infinite inner loop calling evalf forever....the only
output I get is like follows:
Alpha = 3.0D-95 F = 1.8971800123133085D+03 FE = 321
Alpha = 1.5D-95 F = 1.8971800142932461D+03 FE = 322
Alpha = 7.5D-96 F = 1.8971800163072364D+03 FE = 323
Alpha = 3.7D-96 F = 1.8971800183027008D+03 FE = 324
Alpha = 1.9D-96 F = 1.8971800203184591D+03 FE = 325
Alpha = 9.4D-97 F = 1.8971800223244027D+03 FE = 326
Alpha = 4.7D-97 F = 1.8971800243003756D+03 FE = 327
Alpha = 2.3D-97 F = 1.8971800263086134D+03 FE = 328
Alpha = 1.2D-97 F = 1.8971800283148546D+03 FE = 329
Alpha = 5.9D-98 F = 1.8971800303257412D+03 FE = 330
Alpha = 2.9D-98 F = 1.8971800323363229D+03 FE = 331
Alpha = 1.5D-98 F = 1.8971800343208315D+03 FE = 332
Alpha = 7.3D-99 F = 1.8971800364308531D+03 FE = 333
and it continues forever....
Any clues? I have double-checked the gradient but seems to me
correct....
Best Andrea
I am having quite and hard time trying to figured out what's wrong
with the solution of a quite easy problem. The setting is:
- ALGENCAN 2.3.7 running on Linux and compiled with g++/gfortran
- a convex box constrained problem with a piecewise quadratic
objective function
- variables are bounded in [0,1]
- other solvers can find a solution in some 20-30 function evaluations
Now ALGENCAN performs a couple of major iterations and the it gets
stuck in an infinite inner loop calling evalf forever....the only
output I get is like follows:
Alpha = 3.0D-95 F = 1.8971800123133085D+03 FE = 321
Alpha = 1.5D-95 F = 1.8971800142932461D+03 FE = 322
Alpha = 7.5D-96 F = 1.8971800163072364D+03 FE = 323
Alpha = 3.7D-96 F = 1.8971800183027008D+03 FE = 324
Alpha = 1.9D-96 F = 1.8971800203184591D+03 FE = 325
Alpha = 9.4D-97 F = 1.8971800223244027D+03 FE = 326
Alpha = 4.7D-97 F = 1.8971800243003756D+03 FE = 327
Alpha = 2.3D-97 F = 1.8971800263086134D+03 FE = 328
Alpha = 1.2D-97 F = 1.8971800283148546D+03 FE = 329
Alpha = 5.9D-98 F = 1.8971800303257412D+03 FE = 330
Alpha = 2.9D-98 F = 1.8971800323363229D+03 FE = 331
Alpha = 1.5D-98 F = 1.8971800343208315D+03 FE = 332
Alpha = 7.3D-99 F = 1.8971800364308531D+03 FE = 333
and it continues forever....
Any clues? I have double-checked the gradient but seems to me
correct....
Best Andrea
Jose Mario Martinez
May 5, 2012, 9:22:15 AM5/5/12
to Andrea Cassioli, TANGO Project - ALGENCAN
Good morning:
Can you give use the description of that problem. I would like to run it in the straight fortran platform.
Regards,
Mario
Can you give use the description of that problem. I would like to run it in the straight fortran platform.
Regards,
Mario
--
You received this message because you are subscribed to the Google Groups "TANGO Project - ALGENCAN" group.
To post to this group, send email to tango-...@googlegroups.com.
To unsubscribe from this group, send email to tango-projec...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/tango-project?hl=en.
Ernesto G. Birgin
May 5, 2012, 6:37:50 PM5/5/12
to tango-...@googlegroups.com
Hi!
An endless local search may be the reflect of a nondescent direction computed using a wrong coded gradient. Did you check the derivatives of your problem? Set parameter checkder equal to true within inip subroutine and see the output of the comparison made by Algencan between your coded derivatives and finite differences aproximations.
Independently of that, seeing a partial output is not very useful to detect problems. Next time you may would like to post the complete output.
Regards,
Ernesto.
An endless local search may be the reflect of a nondescent direction computed using a wrong coded gradient. Did you check the derivatives of your problem? Set parameter checkder equal to true within inip subroutine and see the output of the comparison made by Algencan between your coded derivatives and finite differences aproximations.
Independently of that, seeing a partial output is not very useful to detect problems. Next time you may would like to post the complete output.
Regards,
Ernesto.
Jose Mario Martinez
May 5, 2012, 7:00:02 PM5/5/12
to Andrea Cassioli, TANGO Project - ALGENCAN
Andrea: I followed your instructions and I generated the matrix A (1000000, 40) randomly in (0, 1).
Then I generated a random (0, 1) x, and I computed z = A x. Then I generated b = 0.99 z and c = 1.01 z, so that I know
that there exists a global solution of the problem with functional value 0.
The output of Algencan was below.
Observe that iteration 20 one gets f = 1.e-10 revealing that we are very close to a solution but the projected gradient is still
4.3 e- 5. This situation states more or less in the same way until iteration 39. At iteration 40 suddenly the projected gradient
norm falls to 1.e-14 and convergence was declared.
I ran Algencan without computation of the Hessian.
In your problem, do you expect to have a null objective function value?
Could it be possible that you are close to the solution but in a situation in which it is impossible to obtain a sufficiently small
projected gradient due to cancelation errors?
Entry to GENCAN.
Number of variables: 40
Required optimality tolerance: 1.0D-08
It f gpsupn xsupn ssupn nind lvfit innit fcnt
0 1.38723410D+08 1.0D+00 1.0D+00
1 1.84974150D+05 4.2D-01 4.2D-01 5.9D-01 40 1 0 2
2 3.67908364D+02 8.5D-01 8.5D-01 4.3D-01 40 1 1 3
3 4.08454108D+01 8.7D-01 8.7D-01 2.0D-02 40 1 2 4
4 7.19433881D+00 8.8D-01 8.8D-01 8.8D-03 40 1 3 5
5 1.53368489D+00 8.9D-01 8.9D-01 4.8D-03 40 1 4 6
6 3.72249447D-01 8.9D-01 8.9D-01 3.5D-03 40 1 5 7
7 9.54097499D-02 8.9D-01 8.9D-01 3.2D-03 40 1 6 8
8 2.55574664D-02 8.1D-01 8.9D-01 3.9D-03 40 1 7 9
9 6.01525440D-03 5.0D-01 8.9D-01 4.5D-03 40 1 8 10
It f gpsupn xsupn ssupn nind lvfit innit fcnt
10 1.33055314D-03 2.3D-01 8.9D-01 3.5D-03 40 1 9 11
11 3.42689730D-04 1.2D-01 8.9D-01 7.0D-03 40 1 10 12
12 6.49807031D-05 4.2D-02 8.9D-01 5.3D-03 40 1 11 13
13 4.92321025D-05 3.9D-02 8.9D-01 1.0D-03 40 1 12 16
14 1.83078502D-05 2.8D-02 8.9D-01 2.4D-03 40 1 13 17
15 9.12611405D-07 2.7D-03 8.9D-01 1.6D-03 40 1 14 18
16 3.72772682D-07 1.9D-03 8.9D-01 5.0D-04 40 1 15 19
17 3.69353460D-07 1.9D-03 8.9D-01 1.2D-04 40 1 16 25
18 3.60689297D-07 2.0D-03 8.9D-01 1.5D-04 40 1 17 31
19 3.17582349D-09 1.1D-04 8.9D-01 1.4D-04 40 1 18 32
It f gpsupn xsupn ssupn nind lvfit innit fcnt
20 4.89033744D-10 4.3D-05 8.9D-01 4.4D-04 40 1 19 33
21 4.73870823D-10 4.3D-05 8.9D-01 2.9D-04 40 1 20 40
22 4.70175926D-10 4.3D-05 8.9D-01 7.2D-05 40 1 21 49
23 4.68341093D-10 4.2D-05 8.9D-01 3.6D-05 40 1 22 59
24 4.67426821D-10 4.2D-05 8.9D-01 1.8D-05 40 1 23 70
25 4.66970462D-10 4.2D-05 8.9D-01 8.9D-06 40 1 24 82
26 4.66856462D-10 4.2D-05 8.9D-01 2.3D-06 40 1 25 96
27 4.66799474D-10 4.2D-05 8.9D-01 1.1D-06 40 1 26 111
28 4.66770983D-10 4.2D-05 8.9D-01 6.1D-07 40 1 27 127
29 4.66768228D-10 4.2D-05 8.9D-01 3.2D-08 40 1 28 146
It f gpsupn xsupn ssupn nind lvfit innit fcnt
30 4.66766954D-10 4.2D-05 8.9D-01 1.1D-08 40 1 29 165
31 4.66766170D-10 4.2D-05 8.9D-01 8.2D-09 40 1 30 185
32 3.61456627D-10 3.7D-05 8.9D-01 5.1D-03 40 1 31 189
33 3.25433891D-10 3.5D-05 9.0D-01 1.9D-03 40 1 32 194
34 3.10282418D-10 3.5D-05 9.0D-01 8.4D-04 40 1 33 200
35 3.03293737D-10 3.4D-05 9.0D-01 3.9D-04 40 1 34 207
36 3.01581468D-10 3.4D-05 9.0D-01 9.5D-05 40 1 35 216
37 3.01168745D-10 3.4D-05 9.0D-01 2.4D-05 40 1 36 227
38 3.01164264D-10 3.4D-05 9.0D-01 3.0D-07 40 1 37 243
39 2.95085614D-10 3.4D-05 8.9D-01 5.5D-03 40 1 38 250
It f gpsupn xsupn ssupn nind lvfit innit fcnt
40 6.52428752D-29 1.6D-14 8.9D-01 1.3D-06 40 1 39 251
Flag of GENCAN: Solution was found.
inform = 0
Solution found by Algencanadap:
0.51272637742798410 0.51283250078163622 0.40812666485588328 0.19120303576075617 0.36763057821730361 0.71769566819851116 0.44691660002956018 0.80941312855909486 0.74744510812148612 3.36504286352328555E-002 7.49471247432815374E-002 0.53575555701503519 0.16356527217814035 0.89406003257219790 0.23199911334982720 0.81159502909279058 0.30587290212274726 0.48488145187245402 1.22595838570735537E-002 0.75489636284845230 0.23356081701651721 0.17090473545375481 0.86681492695852513 0.51865216745990073 0.80450951406820681 0.73163562970040308 3.17258029137294645E-002 0.31036485500283062 0.48861828487507381 0.58481593118902109 3.81143717775381877E-002 0.13994798534172684 0.24716499885709398 0.17146952543097385 0.35712101028686166 0.44757994810785307 0.25074974630681968 0.58195621184274759 0.12993602787873931 0.25707048717921199
Functional value: 6.52428752065140124E-029
Then I generated a random (0, 1) x, and I computed z = A x. Then I generated b = 0.99 z and c = 1.01 z, so that I know
that there exists a global solution of the problem with functional value 0.
The output of Algencan was below.
Observe that iteration 20 one gets f = 1.e-10 revealing that we are very close to a solution but the projected gradient is still
4.3 e- 5. This situation states more or less in the same way until iteration 39. At iteration 40 suddenly the projected gradient
norm falls to 1.e-14 and convergence was declared.
I ran Algencan without computation of the Hessian.
In your problem, do you expect to have a null objective function value?
Could it be possible that you are close to the solution but in a situation in which it is impossible to obtain a sufficiently small
projected gradient due to cancelation errors?
Entry to GENCAN.
Number of variables: 40
Required optimality tolerance: 1.0D-08
It f gpsupn xsupn ssupn nind lvfit innit fcnt
0 1.38723410D+08 1.0D+00 1.0D+00
1 1.84974150D+05 4.2D-01 4.2D-01 5.9D-01 40 1 0 2
2 3.67908364D+02 8.5D-01 8.5D-01 4.3D-01 40 1 1 3
3 4.08454108D+01 8.7D-01 8.7D-01 2.0D-02 40 1 2 4
4 7.19433881D+00 8.8D-01 8.8D-01 8.8D-03 40 1 3 5
5 1.53368489D+00 8.9D-01 8.9D-01 4.8D-03 40 1 4 6
6 3.72249447D-01 8.9D-01 8.9D-01 3.5D-03 40 1 5 7
7 9.54097499D-02 8.9D-01 8.9D-01 3.2D-03 40 1 6 8
8 2.55574664D-02 8.1D-01 8.9D-01 3.9D-03 40 1 7 9
9 6.01525440D-03 5.0D-01 8.9D-01 4.5D-03 40 1 8 10
It f gpsupn xsupn ssupn nind lvfit innit fcnt
10 1.33055314D-03 2.3D-01 8.9D-01 3.5D-03 40 1 9 11
11 3.42689730D-04 1.2D-01 8.9D-01 7.0D-03 40 1 10 12
12 6.49807031D-05 4.2D-02 8.9D-01 5.3D-03 40 1 11 13
13 4.92321025D-05 3.9D-02 8.9D-01 1.0D-03 40 1 12 16
14 1.83078502D-05 2.8D-02 8.9D-01 2.4D-03 40 1 13 17
15 9.12611405D-07 2.7D-03 8.9D-01 1.6D-03 40 1 14 18
16 3.72772682D-07 1.9D-03 8.9D-01 5.0D-04 40 1 15 19
17 3.69353460D-07 1.9D-03 8.9D-01 1.2D-04 40 1 16 25
18 3.60689297D-07 2.0D-03 8.9D-01 1.5D-04 40 1 17 31
19 3.17582349D-09 1.1D-04 8.9D-01 1.4D-04 40 1 18 32
It f gpsupn xsupn ssupn nind lvfit innit fcnt
20 4.89033744D-10 4.3D-05 8.9D-01 4.4D-04 40 1 19 33
21 4.73870823D-10 4.3D-05 8.9D-01 2.9D-04 40 1 20 40
22 4.70175926D-10 4.3D-05 8.9D-01 7.2D-05 40 1 21 49
23 4.68341093D-10 4.2D-05 8.9D-01 3.6D-05 40 1 22 59
24 4.67426821D-10 4.2D-05 8.9D-01 1.8D-05 40 1 23 70
25 4.66970462D-10 4.2D-05 8.9D-01 8.9D-06 40 1 24 82
26 4.66856462D-10 4.2D-05 8.9D-01 2.3D-06 40 1 25 96
27 4.66799474D-10 4.2D-05 8.9D-01 1.1D-06 40 1 26 111
28 4.66770983D-10 4.2D-05 8.9D-01 6.1D-07 40 1 27 127
29 4.66768228D-10 4.2D-05 8.9D-01 3.2D-08 40 1 28 146
It f gpsupn xsupn ssupn nind lvfit innit fcnt
30 4.66766954D-10 4.2D-05 8.9D-01 1.1D-08 40 1 29 165
31 4.66766170D-10 4.2D-05 8.9D-01 8.2D-09 40 1 30 185
32 3.61456627D-10 3.7D-05 8.9D-01 5.1D-03 40 1 31 189
33 3.25433891D-10 3.5D-05 9.0D-01 1.9D-03 40 1 32 194
34 3.10282418D-10 3.5D-05 9.0D-01 8.4D-04 40 1 33 200
35 3.03293737D-10 3.4D-05 9.0D-01 3.9D-04 40 1 34 207
36 3.01581468D-10 3.4D-05 9.0D-01 9.5D-05 40 1 35 216
37 3.01168745D-10 3.4D-05 9.0D-01 2.4D-05 40 1 36 227
38 3.01164264D-10 3.4D-05 9.0D-01 3.0D-07 40 1 37 243
39 2.95085614D-10 3.4D-05 8.9D-01 5.5D-03 40 1 38 250
It f gpsupn xsupn ssupn nind lvfit innit fcnt
40 6.52428752D-29 1.6D-14 8.9D-01 1.3D-06 40 1 39 251
Flag of GENCAN: Solution was found.
inform = 0
Solution found by Algencanadap:
0.51272637742798410 0.51283250078163622 0.40812666485588328 0.19120303576075617 0.36763057821730361 0.71769566819851116 0.44691660002956018 0.80941312855909486 0.74744510812148612 3.36504286352328555E-002 7.49471247432815374E-002 0.53575555701503519 0.16356527217814035 0.89406003257219790 0.23199911334982720 0.81159502909279058 0.30587290212274726 0.48488145187245402 1.22595838570735537E-002 0.75489636284845230 0.23356081701651721 0.17090473545375481 0.86681492695852513 0.51865216745990073 0.80450951406820681 0.73163562970040308 3.17258029137294645E-002 0.31036485500283062 0.48861828487507381 0.58481593118902109 3.81143717775381877E-002 0.13994798534172684 0.24716499885709398 0.17146952543097385 0.35712101028686166 0.44757994810785307 0.25074974630681968 0.58195621184274759 0.12993602787873931 0.25707048717921199
Functional value: 6.52428752065140124E-029
On Fri, May 4, 2012 at 11:57 AM, Andrea Cassioli <cassio...@gmail.com> wrote:
Jose Mario Martinez
May 6, 2012, 8:19:46 AM5/6/12
to Andrea Cassioli, TANGO Project - ALGENCAN
Andrea: I ran the similar problem that we talked yesterday, this time using the option of coding the Hessian. (The Hessian is
discontinuous in this problem but it doesn't matter). The results were:
Entry to GENCAN.
Number of variables: 40
Required optimality tolerance: 1.0D-08
It f gpsupn xsupn ssupn nind lvfit innit fcnt
0 1.38723410D+08 1.0D+00 1.0D+00
1 1.84974150D+05 4.2D-01 4.2D-01 5.9D-01 40 1 0 2
2 3.83754601D+02 8.5D-01 8.5D-01 4.3D-01 40 1 1 3
3 1.08347770D+02 8.7D-01 8.7D-01 1.4D-02 40 1 2 4
4 0.00000000D+00 0.0D+00 9.1D-01 4.7D-02 40 1 3 9
Flag of GENCAN: Solution was found.
Regards,
Mario
discontinuous in this problem but it doesn't matter). The results were:
Entry to GENCAN.
Number of variables: 40
Required optimality tolerance: 1.0D-08
It f gpsupn xsupn ssupn nind lvfit innit fcnt
0 1.38723410D+08 1.0D+00 1.0D+00
1 1.84974150D+05 4.2D-01 4.2D-01 5.9D-01 40 1 0 2
3 1.08347770D+02 8.7D-01 8.7D-01 1.4D-02 40 1 2 4
4 0.00000000D+00 0.0D+00 9.1D-01 4.7D-02 40 1 3 9
Flag of GENCAN: Solution was found.
Mario
On Fri, May 4, 2012 at 11:57 AM, Andrea Cassioli <cassio...@gmail.com> wrote:
Reply all
Reply to author
Forward
0 new messages