forked from m3g/packmol
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathgencan.f
6005 lines (5013 loc) · 198 KB
/
gencan.f
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
C *****************************************************************
C *****************************************************************
subroutine evalal(n,x,m,lambda,rho,f,flag)
C This subroutine computes the objective function when GENCAN is
C being used stand-alone to solve a unique bound-constrained problem.
C When GENCAN is being used in an Augmented Lagrangian framework,
C this subroutine must compute the Augmented Lagrangian function.
C
C On Entry:
C
C n integer,
C number of variables,
C
C x double precision x(n),
C current point,
C
C m integer,
C number of constraints (equalities plus inequalities),
C
C lambda double precision lambdae(m),
C current estimation of the Lagrange multipliers,
C
C rho double precision rho(m)
C penalty parameters,
C
C NOTE: arguments m, lambda and rho are useful when GENCAN is being used
C for solving the box-constrained subproblems of an Augmented Lagrangian
C framework. When GENCAN is being used stand-alone for solving a bound-
C constrained problem, these arguments are dummy arguments.
C
C On Return
C
C f double precision,
C objective function value at x,
C
C flag integer
C 0 means "no errors",
C 1 means "some error occurs in the objective funtion evaluation".
implicit none
C SCALAR ARGUMENTS
integer flag,m,n
double precision f
C ARRAY ARGUMENTS
double precision lambda(m),rho(m),x(n)
C LOCAL SCALARS
flag = 0
call computef(n,x,f)
end
C *****************************************************************
C *****************************************************************
subroutine evalnal(n,x,m,lambda,rho,g,flag)
C This subroutine computes the gradient of the objective function
C when GENCAN is being used stand-alone to solve a unique bound-
C constrained problem. When GENCAN is being used in an Augmented
C Lagrangian framework, this subroutine must compute the gradient of
C Augmented Lagrangian.
C
C On Entry:
C
C n integer,
C number of variables,
C
C x double precision x(n),
C current point,
C
C m integer,
C number of constraints (equalities plus inequalities),
C
C lambda double precision lambdae(m),
C current estimation of the Lagrange multipliers,
C
C rho double precision rho(m)
C penalty parameters,
C
C NOTE: arguments m, lambda and rho are useful when GENCAN is being used
C for solving the box-constrained subproblems of an Augmented Lagrangian
C framework. When GENCAN is being used stand-alone for solving a bound-
C constrained problem, these arguments are dummy arguments.
C
C On Return
C
C g double precision g(n),
C gradient of the objective function at x,
C
C flag integer
C 0 means "no errors",
C 1 means "some error occurs in the gradient evaluation".
implicit none
C SCALAR ARGUMENTS
integer flag,m,n
C ARRAY ARGUMENTS
double precision g(n),lambda(m),rho(m),x(n)
C LOCAL SCALARS
flag = 0
call computeg(n,x,g)
end
C *****************************************************************
C *****************************************************************
c Modified by L. Martinez (there was an error on the number of
c parameters when calling this subroutine). This subroutine does
c nothing.
c subroutine evalhd(nind,ind,n,x,m,lambda,rho,d,hd,flag)
subroutine evalhd(n)
C This subroutine computes the product of the Hessian matrix times
C the input vector argument d. If GENCAN is being used stand-alone
C to solve a bound-constrained problem, the ''Hessian matrix'' must
C be the Hessian matrix of the objective function. On the other hand,
C if GENCAN is being used to solve the bound-constrained subproblems
C in an Augmented Lagrangian framework, the Hessian matrix must be
C the Hessian of the Augmented Lagrangian function.
C
C IMPORTANT: This subroutine does not need to be coded if the user
C prefers to approximate the Hessian-vector product by incremental
C quotients. In this case, it is enough to set the GENCAN input
C argument htvtype equal to 1 and an internal GENCAN subroutine will
C be used to compute the approximation. In fact, this is the default
C GENCAN option. See the GENCAN and EASYGENCAN arguments descriptions
C for details.
C
C On Entry:
C
C nind integer
C number of component of the Hessian-vector product that
C must be computed,
C
C ind integer ind(nind)
C the component that must be computed are ind(1)-th ... ind(nind)-th,
C
C n integer,
C number of variables,
C
C x double precision x(n),
C current point,
C
C m integer,
C number of constraints (equalities plus inequalities),
C
C lambda double precision lambdae(m),
C current estimation of the Lagrange multipliers,
C
C rho double precision rho(m)
C penalty parameters,
C
C d double precision d(n)
C vector of the Hessian-vector product.
C
C NOTE: arguments m, lambda and rho are useful when GENCAN is being used
C for solving the box-constrained subproblems of an Augmented Lagrangian
C framework. When GENCAN is being used stand-alone for solving a bound-
C constrained problem, these arguments are dummy arguments.
C
C On Return
C
C hd double precision g(n),
C Hessian-vector product,
C
C flag integer
C 0 means "no errors",
C 1 means "some error occurs in the gradient evaluation".
implicit none
C SCALAR ARGUMENTS
c integer flag,m,n,nind
integer n
C ARRAY ARGUMENTS
c integer ind(nind)
c double precision d(n),hd(n),lambda(m),rho(m),x(n)
c flag = - 1
end
C**************************************************************************
C Last update of EASYGENCAN: February 18th, 2005.
subroutine easygencan(n,x,l,u,m,lambda,rho,epsgpsn,maxit,maxfc,
+trtype,iprint,ncomp,f,g,gpsupn,iter,fcnt,gcnt,cgcnt,inform,wi,wd,
+delmin)
implicit none
C SCALAR ARGUMENTS
integer cgcnt,fcnt,gcnt,m,maxfc,maxit,n,ncomp,inform,iprint,iter
double precision epsgpsn,f,gpsupn
C ARRAY ARGUMENTS
integer wi(n)
double precision g(n),l(n),lambda(m),rho(m),u(n),wd(8*n),x(n)
C This subroutine aims to simplify the use of GENCAN. For this
C purpose it gives values to most of the GENCAN arguments and
C leaves to the user those arguments which he/she may would like to
C set by him/herself.
C
C The arguments of EASYGENCAN are the input and output arguments of
C GENCAN that are supposed to be useful for a common user. The input
C arguments are mostly related to basic problem information, like
C dimension and bounds, and the initial point. There are also input
C arguments related to simple stopping criteria (like norm of the
C projected gradient, and maximum number of iterations and
C functional evaluations). There are also two input arguments
C related to control the amount of information written into the
C screen. The output arguments are related to information of the
C solution and some few performance measurements. Basically, on
C return, EASYGENCAN gives to the user the solution, the objective
C functional value and its gradient at the solution, Euclidian and
C sup-norm of the projected gradient at the solution, the number of
C iterations, functional and gradient evaluations, and Conjugate
C Gradient iterations used to reach the solution, and, finally, a
C flag that indicates the stopping criterion that was satisfied.
C
C All the other arguments of GENCAN are setted with its default
C values by EASYGENCAN. EASYGENCAN divides the arguments of GENCAN
C in two sets. Those that are related to the behaviour of GENCAN are
C declared as Fortran parameters (constants). The other arguments of
C GENCAN, most of them related to alternative stopping criteria, and
C that may depend of, for example, maxit, are declared as local
C variables of EASYGENCAN.
C
C GENCAN arguments that are defined as Fortran parameters in this
C subroutine are GENCAN arguments that should not be modified by a
C common user. They are arguments that modify the behaviour of
C GENCAN and whos values were selected because they are classical
C values in some cases or because some numerical experiments seemed
C to indicate that they are the best choices.
C
C GENCAN arguments that are declared as local variables in this
C subroutine are GENCAN arguments that may be modified if, with
C their suggested values, GENCAN does not give the desired result.
C Most of them are related to Conjugate Gradients or to disabled
C stopping criteria that may be useful in bad-scaled problems or
C problems with not trustable derivatives.
C
C Finally, this subroutine declares as local variables some
C arguments of GENCAN which in fact are output arguments. Most of
C them are related to quantities that can be used for statistics
C related to the GENCAN performance, like number Spectral Projected
C Gradient iterations, Truncated Newton iterations, Conjugate
C Gradient iterations, etc. As we assume that this values are not
C useful for the common user, this subroutine throw all of them
C away.
C
C We describe below the meaning of the arguments of the EASYGENCAN
C subroutine. More detailed descriptions as well as the descriptions
C of all the other GENCAN arguments that are not arguments of
C EASYGENCAN are also described at the begining of the GENCAN
C subroutine.
C
C On entry:
C
C n integer
C number of variables
C
C x double precision x(n)
C initial estimation of the solution
C
C l double precision l(n)
C lower bounds on the variables
C
C u double precision u(n)
C upper bounds on the variables
C
C m integer
C lambda double precision lambda(m)
C rho double precision rho(m)
C These three parameters are not used nor modified by
C GENCAN and they are passed as arguments to the user-
C defined subroutines evalal and evalnal to compute the
C objective function and its gradient, respectively.
C Clearly, in an Augmented Lagrangian context, if GENCAN is
C being used to solve the bound-constrainted subproblems, m
C would be the number of constraints, lambda the Lagrange
C multipliers approximation and rho the penalty parameters
C
C epsgpsn double precision
C GENCAN stops declaring convergence if it finds a point
C whos projected gradient sup-norm is smaller than or equal
C to epsgpsn
C
C maxit integer
C GENCAN stops declaring ''maximum number of iteration
C achieved'' if the number of iterations exceeds maxit
C
C maxfc integer
C the same as before but with the number of functional
C evaluations
C
C iprint integer
C indicates the degree of details of the output generated
C by GENCAN. Setting iprint to a value smaller than 2 will
C make GENCAN to generate no output at all. An iprint value
C greater than or equal to 2 will generate information of
C every GENCAN iteration. An iprint value greater than or
C equal to 3 will also show information of the Conjugate
C Gradient iterations (used to compute the Truncated Newton
C direction) and also information related to the line
C search procedures in the Spectral Projected Gradient
C direction and the Truncated Newton direction.
C
C ncomp integer
C Sometimes, vectors like the current point x, the gradient
C of the objective function g, or the search directions
C (Spectral Projected Gradient direction or Truncated
C Newton direction), among other vector, are showed in the
C screen. In such cases, if the problem dimension is large,
C to show just a few elements of these vectors may be
C preferable. Argument ncomp can be used to indicate how
C many array elements must be displayed.
C
C wi integer wi(n)
C integer working space
C
C wd double precision wd(8*n)
C double precision working space
C
C On return:
C
C x double precision x(n)
C estimation of the solution
C
C f double precision
C objective function value at the solution
C
C g double precision g(n)
C gradient of the objective function at the solution
C
C gpsupn double precision
C sup-norm of the continuous projected gradient
C
C iter integer
C number of iterations used to reach the solution
C
C fcnt integer
C number of functional evaluations
C
C gcnt integer
C number of gradient evaluations
C
C cgcnt integer
C number of Conjugate Gradient iterations
C
C inform integer
C termination criteria. inform equal to 1 means that
C GENCAN converged with the sup-norm of the continuous
C projected gradient stopping criterion (inform equal to 0
C means the same but with the Euclidian norm). Other
C positive values means that GENCAN stopped by a may be not
C successful stopping criteria. A negative value means that
C there was an error in the user-defined subroutines that
C computes the objective function (subroutine evalal), the
C gradient (subroutine evalnal), or the Hessian-vector
C product (subroutine evalhd). See the GENCAN description
C for more details.
C HERE STARTS THE DESCRIPTION OF SOME GENCAN ARGUMENTS THAT ARE
C BEING SETTED INSIDE EASYGENCAN. THE FIRST SET OF ARGUMENTS ARE
C THOSE ARGUMENTS THAT WE WILL CALL ''CONSTANTS'' AND THAT, AS THEIR
C VALUES ALTER THE BEHAVIOUR OF GENCAN, SHOULD NOT BE MODIFIED BY A
C COMMON USER.
C CONSTANTS FOR GENERAL USES
C Steps: h = max( steabs, sterel * abs( x ) ) should be a number
C such that h is small ( relatively to x ) and x + h is different
C from x. So, h is something that can be used a a step for a finite
C differences approximation of a partial derivative relative to x.
C Epsilons: something smaller than max( epsabs, epsrel * abs( x ) )
C should be considered as ``zero'' when compared with x. It is used,
C for example, to detect that a step taken during a line search is
C too small.
C Infinitys: infrel is a big number that may appear in the
C calculations. infabs is a number that should never be reached in
C the calculations and is used the represent ``infinite''. Detailed
C explanations of how are they used are rather cumbersome.
double precision steabs,sterel,epsabs,epsrel,infabs,infrel
parameter ( steabs = 1.0d-10 )
parameter ( sterel = 1.0d-07 )
parameter ( epsabs = 1.0d-20 )
parameter ( epsrel = 1.0d-10 )
parameter ( infabs = 1.0d+99 )
parameter ( infrel = 1.0d+20 )
C CONSTANTS FOR CLASSICAL LINE-SEARCH CONDITIONS
C beta is the constant for the ''beta condition''. We use this
C condition to test whether is promising to extrapolate or not.
C gamma is the constant for the sufficient decrease ''Armijo
C condition''.
C theta is the constant for the ''angle condition''.
C sigma1 and sigma2 are the constants for the safeguarding quadratic
C interpolations. We use them in a rather unusual way. Instead of
C discarding a new step anew if it does not belong to the interval
C [ sigma1 * aprev, sigma2 * aprev ], we discard it if it does not
C belong to the interval [ sigma1, sigma2 * aprev ]. In such a case
C we take something similar to ''anew = aprev / 2''.
double precision beta,gamma,theta,sigma1,sigma2
parameter ( beta = 0.5d0 )
parameter ( gamma = 1.0d-04 )
parameter ( theta = 1.0d-06 )
parameter ( sigma1 = 0.1d0 )
parameter ( sigma2 = 0.9d0 )
C CONSTANTS FOR SPECIFIC PROCEDURES (NOT SO CLASSICAL)
C In line searches, when interpolating, the step may become so
C small that we should declare a line search failure indicating that
C direction may not be a descent direction. This decision is never
C take before doing at least mininterp interpolations.
C In line searches, the beta condition (see above) may recommend to
C extrapolate. We never do more than maxextrap extrapolations.
C In the line searches, when we need to interpolate and the result
C of the quadratic interpolation is rejected, the new step is
C computed as anew = aprev / nint. When the beta condition
C recommends to extrapolate, we compute anew = aprev * next.
C When computing the Newton direction by Conjugate Gradients we
C never go further an artificial ''trust region''. This ''trust
C radius'' is never smaller than delmin.
C In active set strategies, constants eta is used to decide whether
C the current face should be abandoned or not. In particular, the
C current face is abandoned when the norm of the internal to face
C component of the continuous projected gradient is smaller than
C ( 1 - eta ) times the norm of the continuous projected gradient.
C In this way, values of eta near 1 makes the method to work hard
C inside the faces and values of eta near 0 makes the method to
C abandon the faces very quickly.
C We always use as a first step in a line search procedure along a
C first order direction the spectral steplength. This steplength
C must belong to the interval [lspgmi,lspgma].
integer maxextrap,mininterp
parameter ( maxextrap = 100 )
parameter ( mininterp = 4 )
double precision nint,next,delmin,eta,lspgma,lspgmi
parameter ( nint = 2.0d0 )
parameter ( next = 2.0d0 )
c parameter ( delmin = 1.d4 )
parameter ( eta = 0.9d0 )
parameter ( lspgma = 1.0d+10 )
parameter ( lspgmi = 1.0d-10 )
C DIMENSIONS FOR SOME WORKING SPACES
C In non-monotone line searches, given p, the last p objective
C functional values must be stored. For this reason we declare a
C vector with pmax double precision elements. So p must be less than
C or equal to pmax.
C Sometimes, is the problem is bad scaled, to request a small
C gradient norm at the solution may be inadequate. For this reason,
C a test to verify if this norm is not decreasing during maxitngp
C (MAXimum of ITerations with No Gradient Progress) consecutive
C iterations then we stop the method with a warning. As it is not
C expected a monotone decreasing of the gradient norm, again, the
C norm of the last maxitngp iterations must be saved. For this
C purpose, we declare a vector of tmax elements. So maxitngp must
C be less than or equal to tmax.
integer tmax
parameter ( tmax = 10000 )
C HERE STARTS THE DESCRIPTION OF THE OTHER ARGUMENTS OF GENCAN BEING
C SETTED BY EASYGENCAN. THESE ARGUMENTS MAY BE MODIFIED BY A COMMON
C USER IF, WITH THEIR SUGGESTED VALUES, GENCAN DOES NOT GIVE THE
C EXPECTED RESULT.
C GENCAN INPUT ARGUMENTS THAT WILL BE SETTED BELOW
logical nearlyq
integer cgmaxit,cgscre,gtype,htvtype,maxitnfp,maxitngp,maxitnqmp,
+ trtype
double precision cgepsf,cgepsi,cggpnf,delta0,epsgpen,epsnfp,
+ epsnqmp,fmin
C GENCAN OUTPUT ARGUMENTS THAT WILL BE DISCARDED
integer spgfcnt,spgiter,tnexbcnt,tnexgcnt,tnexbfe,tnexgfe,tnfcnt,
+ tnintcnt,tnintfe,tniter,tnstpcnt
double precision gpeucn2
C GENCAN WORKING VECTORS (WHICH DIMENSION IS NOT RELATED TO THE
C PROBLEM DIMENSION)
double precision lastgpns(tmax)
C ARGUMENTS RELATED TO DERIVATIVES CALCULATIONS
C gtype indicates in which way the gradient of the objective
C function will be computed. If the user have been implemented the
C user-supplied evalnal subroutine to compute the gradient of the
C objective function then gtype argument must be set to 0 (ZERO) and
C the user-supplied evalnal subroutine will be called by GENCAN any
C time the gradient would be required.
C
C The prototype of the evalnal subroutine must be:
C
C subroutine evalnal(n,x,m,lambda,rho,nal,flag)
C
C SCALAR ARGUMENTS
C integer n,m,flag
C
C ARRAY ARGUMENTS
C double precision x(n),lambda(m),rho(m),nal(n)
C
C ''Here must be written the subroutine body that calculates the
C n-dimensional gradient vector of the objective function
C evaluated at x and saves it in nal. It also must set flag to 0
C (ZERO) if the gradient was successfully computed and to any
C other value if the gradient vector is not well defined at the
C required point x. If GENCAN is been used stand-alone to solve
C a unique bound-constrained problem then m, lambda and rho are
C dummy arguments. On the other hand, if GENCAN is been used in
C an Augmented Lagrangian framework then these arguments should
C be used for the number of constraints, the Lagrange
C multipliers approximation and the penalty parameters,
C respectively.''
C
C end
C
C If, on the other hand, the user is not able to provide evalnal
C subroutine, gtype argument must be set to 1 (ONE). In this case,
C every time GENCAN needs to compute the gradient of the objective
C function, an internal subroutine that approximates it by finite-
C differences will be used (be aware that it maybe very time
C consuming). Moreover, note that the evalnal subroutine must still
C be present (with an empty body).
gtype = 0
C htvtype indicates in which way the product of the Hessian of the
C objective function times an arbitrary vector will be computed. If
C the user has not been implemented the user-supplied evalhd
C subroutine to do this task then htvtype argument must be set to 1
C (ONE). In this case an internal subroutine that approximates this
C product by incremental quotients will be used. Note that, even in
C this case, evalhd subroutine must be present (with an empty body).
C This is the default option and the empty-body subroutine follows:
C
C subroutine evalhd(nind,ind,n,x,m,lambda,rho,d,hd,flag)
C
C SCALAR ARGUMENTS
C integer nind,n,m,flag
C
C ARRAY ARGUMENTS
C integer ind(nind)
C double precision d(n),hd(n),lambda(m),rho(m),x(n)
C
C flag = - 1
C
C end
C
C If, on the other hand, the user prefers to implement his/her own
C evalhd subroutine then htvtype argument must be set to 0 (ZERO).
C In this case, the product of the Hessian times vector d (input
C argument of evalhd subroutine) must be saved in vector hd (output
C argument of evalhd subroutine). The other arguments description as
C well as some hints on how to implement your own evalhd subroutine
C can be found in the GENCAN arguments description.
C When ALGENCAN uses GENCAN to solve the subproblems in the classical
C Augmented Lagrangian framework, ALGENCAN uses its own evalhd
C subroutine to overcome the lack of continuity of the second
C derivatives. So, when GENCAN is being used toghether with ALGENCAN,
C htvtype must be equal to 0 (ZERO). On the other hand, if GENCAN is
C being used stand-alone, just set htvtype equal to 1 (ONE) and add
C the empty-body subroutine described above.
htvtype = 1
C ARGUMENTS RELATED TO STOPPING CRITERIA
C Besides the stopping criterion related to the sup-norm of the
C continuous projected gradient, there is another stopping criterion
C related to its Euclidian norm. So, GENCAN stops the process if it
C finds a point at which the Euclidian norm of the continuous
C projected gradient is smaller than epsgpen.
epsgpen = 0.0d0
C For an explanation of maxitngp see above the explanation of tmax
C in ''DIMENSIONS FOR SOME WORKING SPACES''. Just note that the
C value of maxitngp must be less than or equal to tmax.
maxitngp = tmax
C maxitnfp means MAXimum of allowed number of iterations with No
C Progress in the objective functional value. ''Progress'' from one
C iteration to the next one refers to ( fnew - fprev ). Since the
C begining of the algorithm we save the ''best progress'' and
C consider that there was no progress in an iteration if the
C progress of this iterations was smaller than epsnfp times the best
C progress. Finally, the algorithm stops if there was no progress
C during maxitnfp consecutive iterations.
maxitnfp = maxit
epsnfp = 0.0d0
C There is a stopping criterion that stops the method if a point
C with a functional value smaller than fmin is found. The idea
C behind this stopping criterion is to stop the method if the
C objective function is not bounded from below.
fmin = 1.0d-05
C ARGUMENTS RELATED TO CONJUGATE GRADIENTS
C When computing the Truncated Newton direction by Conjugate
C Gradients there is something similar to a ''trust-region radius''.
C This trust radius is updated from iteration to iteration depending
C on the agreement of the objective function and its quadratic
C model. But an initial value for the trust radius is required. If
C the user has a good guess for this initial value then it should be
C passed to GENCAN using the delta0 arguments. On the other hand, if
C delta0 is set to -1, a default value depending on the norm of the
C current point will be used.
delta0 = - 1.0d0
delmin = 1.d-2
c delta0 = delmin
C The ''trust-region'' can be like a ball (using Euclidian norm) or
C like a box (using sup-norm). This choice can be made using trtype
C (TRust region TYPE) argument. trtype equal to 0 means Euclidian
C norm and trtype equal to 1 means sup-norm.
trtype = 1
C When the method is far from the solution, it may be not useful to
C do a very large effort in computing the Truncated Newton direction
C precisely. To avoid it, a fixed maximum number of iterations for
C Conjugate Gradients can be given to GENCAN. If the user would like
C to choose this maximum number of iterations for Conjugate
C Gradient then it should use the cgmaxit arguments. On the other
C hand he/she prefers to leave this task to GENCAN then he/she
C should set cgmaxit to -1.
cgmaxit = -1
C If the task of deciding the accuracy for computing the Truncated
C Newton direction is leaved to GENCAN then a default strategy based
C on increasing accuracies will be used. The proximity to the
C solution is estimated observing the norm of the projected gradient
C at the current point and locating it between that norm at the
C initial point and the expected value of that norm at the solution.
C Then the accuracy for the Truncated Newton direction of the
C current iteration will be computed taking a precision located in
C the same relative position with respect to two given values for
C the accuracies for the first and the last Truncated Newton
C direction calculations. These two accuracies (cgepsi and cgepsf,
C respectively) must be given by the user. Moreover, the expected
C value of the projected gradient norm at the solution (cggpnf) must
C also be given by the user who must indicate setting argument
C cgscre to 1 or 2 if that norm is the Euclidian or the sup-norm.
cggpnf = max( 1.0d-04, max( epsgpen, epsgpsn ) )
cgscre = 2
cgepsi = 1.0d-01
cgepsf = 1.0d-05
C The next two arguments are used for an alternative stopping
C criterion for Conjugate Gradients. Conjugate Gradients method is
C stopped if the quadratic model makes no progress during maxitnqmp
C (MAXimum of ITerations with No Quadratic Model Progress)
C consecutive iterations. In this context, ''no progress'' means
C that the progress is smaller than epsnqmp (EPSilon to measure the
C No Quadratic Model Progress) times the best progress obtained
C during the previous iterations.
epsnqmp = 1.0d-04
maxitnqmp = 5
C Depending on how much the objective function seems to be a
C quadratic, function, Conjugate Gradients may take different
C decision. So, if the objective function is a quadratic function or
C is very similar to a quadratic function then the nearlyq argument
C should be set to TRUE, else, it should be set to FALSE. However,
C the option with nearlyq equal TRUE never showed good results.
C Regarding this unexpected no good performance, rather recently it
C was found a bug that affected the behaviour of GENCAN just in this
C case (See the April 1st, 2003 modifications report at the end of
C this file). So, new experiments setting nearlyq equal TRUE should
C be made.
nearlyq = .false.
C FINALLY, CALL GENCAN
call gencan(n,x,l,u,m,lambda,rho,epsgpen,epsgpsn,maxitnfp,epsnfp,
+maxitngp,fmin,maxit,maxfc,delta0,cgmaxit,cgscre,cggpnf,cgepsi,
+cgepsf,epsnqmp,maxitnqmp,nearlyq,nint,next,mininterp,maxextrap,
+gtype,htvtype,trtype,iprint,ncomp,f,g,gpeucn2,gpsupn,iter,fcnt,
+gcnt,cgcnt,spgiter,spgfcnt,tniter,tnfcnt,tnstpcnt,tnintcnt,
+tnexgcnt,tnexbcnt,tnintfe,tnexgfe,tnexbfe,inform,wd(1),wd(n+1),
+wd(2*n+1),wi,lastgpns,wd(3*n+1),eta,delmin,lspgma,lspgmi,theta,
+gamma,beta,sigma1,sigma2,sterel,steabs,epsrel,epsabs,infrel,
+infabs)
end
C ******************************************************************
C ******************************************************************
C Last update of GENCAN or any of its dependencies:
C
C February 18th, 2005.
C
C See report of modifications at the end of this file.
subroutine gencan(n,x,l,u,m,lambda,rho,epsgpen,epsgpsn,maxitnfp,
+epsnfp,maxitngp,fmin,maxit,maxfc,udelta0,ucgmaxit,cgscre,cggpnf,
+cgepsi,cgepsf,epsnqmp,maxitnqmp,nearlyq,nint,next,mininterp,
+maxextrap,gtype,htvtype,trtype,iprint,ncomp,f,g,gpeucn2,gpsupn,
+iter,fcnt,gcnt,cgcnt,spgiter,spgfcnt,tniter,tnfcnt,tnstpcnt,
+tnintcnt,tnexgcnt,tnexbcnt,tnintfe,tnexgfe,tnexbfe,inform,s,y,d,
+ind,lastgpns,w,eta,delmin,lspgma,lspgmi,theta,gamma,beta,sigma1,
+sigma2,sterel,steabs,epsrel,epsabs,infrel,infabs)
implicit none
C SCALAR ARGUMENTS
logical nearlyq
integer cgcnt,cgscre,fcnt,gcnt,gtype,htvtype,inform,iprint,iter,m,
+ maxextrap,maxfc,maxit,maxitnfp,maxitngp,maxitnqmp,
+ mininterp,n,ncomp,spgfcnt,spgiter,tnexbcnt,tnexbfe,
+ tnexgcnt,tnexgfe,tnfcnt,tnintcnt,tnintfe,tniter,tnstpcnt,
+ trtype,ucgmaxit
double precision beta,cgepsf,cgepsi,cggpnf,delmin,epsabs,epsgpen,
+ epsgpsn,epsnfp,epsnqmp,epsrel,eta,f,fmin,gamma,gpeucn2,
+ gpsupn,infabs,infrel,lspgma,lspgmi,next,nint,sigma1,
+ sigma2,steabs,sterel,theta,udelta0
C ARRAY ARGUMENTS
integer ind(n)
double precision d(n),g(n),l(n),lambda(m),lastgpns(0:maxitngp-1),
+ rho(m),s(n),u(n),w(5*n),x(n),y(n)
C Solves the box-constrained minimization problem
C
C Minimize f(x)
C
C subject to
C
C l <= x <= u
C
C using a method described in
C
C E. G. Birgin and J. M. Martinez, ''Large-scale active-set box-
C constrained optimization method with spectral projected
C gradients'', Computational Optimization and Applications 23, pp.
C 101-125, 2002.
C
C Subroutine evalal must be supplied by the user to evaluate the
C objective function. The prototype of evalal subroutine must be
C
C subroutine evalal(n,x,m,lambda,rho,f,flag)
C
C C On Entry:
C C
C C n integer
C C number of variables
C C
C C x double precision x(n)
C C current point
C C
C C m integer
C C number of constraints (equalities plus inequalities)
C C
C C lambda double precision lambda(m)
C C current estimation of the Lagrange multipliers
C C
C C rho double precision rho(m)
C C penalty parameters
C C
C C NOTE: arguments m, lambda and rho are useful when GENCAN is
C C being used for solving the box-constrained subproblems of an
C C Augmented Lagrangian framework. When GENCAN is being used
C C stand-alone for solving a bound-constrained problem, these
C C arguments are dummy arguments and must be ignored.
C C
C C On Return
C C
C C f double precision
C C objective function value at x
C C
C C flag integer
C C 0 means ''no errors''
C C any other value means ''there was an error in the
C C objective function calculation''.
C C
C C SCALAR ARGUMENTS
C integer flag,m,n
C double precision f
C
C C ARRAY ARGUMENTS
C double precision lambda(m),rho(m),x(n)
C
C C ''Here it should be the body of evalal subroutine that saves
C C in f the objective function value at x. Moreover, it sets
C C flag equal to 0 if the calculation was successfully done and
C C sets flag equal to any other value different from 0 if the
C C objective function is not well defined at the current point
C C x.''
C
C end
C
C Subroutine evalnal to calculate the gradient of the objective
C function may be supplied by the user or not, depending on the
C value of gtype argument (gtype equal to 0 means that the evalnal
C subroutine will be supplied by the user and gtype equal to 1 means
C that an internal GENCAN subroutine will be used to estimate the
C gradient vector by central finite differences). In any case, a
C subroutine named evalnal with the following prototype must
C present.
C
C subroutine evalnal(n,x,m,lambda,rho,g,flag)
C
C C On Entry:
C
C C n integer
C C number of variables
C C
C C x double precision x(n)
C C current point
C C
C C m integer
C C number of constraints (equalities plus inequalities)
C C
C C lambda double precision lambda(m)
C C current estimation of the Lagrange multipliers
C C
C C rho double precision rho(m)
C C penalty parameters
C C
C C NOTE: arguments m, lambda and rho are useful when GENCAN is
C C being used for solving the box-constrained subproblems of an
C C Augmented Lagrangian framework. When GENCAN is being used
C C stand-alone for solving a bound-constrained problem, these
C C arguments are dummy arguments and must be ignored.
C C
C C On Return
C C
C C g double precision g(n)
C C gradient of the objective function at x
C C
C C flag integer
C C 0 means ''no errors'',
C C any other value means ''there was an error in the
C C gradient calculation''.
C C
C C SCALAR ARGUMENTS
C integer flag,m,n
C
C C ARRAY ARGUMENTS
C double precision g(n),lambda(m),rho(m),x(n)
C
C C ''Here it should be the body of evalnal subroutine that
C C saves in g the gradient vector of the objective function at
C C x. Moreover, it sets flag equal to 0 if the calculation was
C C successfully done and sets flag equal to any other value
C C different from 0 if the gradient vector is not well defined
C C at the current point x. If GENCAN gtype argument was setted
C C to 1, i.e., the finite difference approximation provided by
C C GENCAN will be used, then this subroutine must even be
C C present for compilation purpose but it will never be
C C called.''
C
C end
C
C Subroutine evalhd to calculate of the Hessian of the objective
C function times a given vector may be supplied by the user or not,
C depending on the value of htvtype argument (htvtype equal to 0
C means that the evalhd subroutine will be supplied by the user and
C htvtype equal to 1 means tha an internal GENCAN subroutine will be
C used to estimate the product by incremental quotients). In any
C case, a subroutine named evalhd with the following prototype must
C present.
C
C subroutine evalhd(nind,ind,n,x,m,lambda,rho,d,hd,flag)
C
C C On Entry:
C C
C C nind integer
C C number of component of the Hessian-vector product that
C C must be computed
C C
C C ind integer ind(nind)
C C the component that must be computed are ind(1)-th ...
C C ind(nind)-th
C C
C C n integer
C C number of variables
C C
C C x double precision x(n)
C C current point
C C
C C m integer
C C number of constraints (equalities plus inequalities)
C C
C C lambda double precision lambda(m)
C C current estimation of the Lagrange multipliers
C C
C C rho double precision rho(m)
C C penalty parameters
C C
C C NOTE: arguments m, lambda and rho are useful when GENCAN is
C C being used for solving the box-constrained subproblems of an
C C Augmented Lagrangian framework. When GENCAN is being used
C C stand-alone for solving a bound-constrained problem, these
C C arguments are dummy arguments and must be ignored.
C C
C C d double precision d(n)
C C vector of the Hessian-vector product
C C
C C On Return
C C
C C hd double precision g(n)
C C Hessian-vector product
C C
C C flag integer
C C 0 means ''no errors'',
C C any other value means ''there was an error in the
C C product calculation''. Just as an example, as it has
C C no sense that an error occurs in a matrix-vector
C C product, the error could happen in the Hessian
C C calculation. But the possible errors will depend
C C on the way this Hessian-vector product is computed
C C or approximated.
C
C C SCALAR ARGUMENTS
C integer flag,m,n,nind
C
C C ARRAY ARGUMENTS
C integer ind(nind)
C double precision d(n),hd(n),lambda(m),rho(m),x(n)
C
C C ''Here it should be the body of evalhd subroutine that saves
C C in hd the product of the Hessian of the objective function
C C times vector d. Moreover, it sets flag equal to 0 if the
C C calculation was successfully done and sets flag equal to any
C C other value different from 0 if the Hessian matrix is not
C C well defined at the current point x. If GENCAN htvtype
C C argument was setted to 1, i.e., the incremental quotients
C C approximation provided by GENCAN will be used, then this
C C subroutine must even be present for compilation purposes
C C but it will never be called.''
C
C end
C
C In evalhd subroutine, the information about the matrix H must be
C passed by means of common declarations. This subroutine must be
C coded by the user, taking into account that only nind components
C of d are nonnull and that ind is the set of indices of those
C components. In other words, the user must write evalhd in such a
C way that hd is the vector whose i-th entry is
C
C hd(i) = \Sum_{j=1}^{nind} H_{i,ind(j)} d_ind(j)
C
C Moreover, the only components of hd that must be computed are
C those which correspond to the indices ind(1),...,ind(nind).