!+ Subroutine to perform scalar minimization in a fixed direction.
!
! Method:
!       The value of a parameter, S, giving the distance travelled
!       along a direction, H, is adjusted to minimize a function F.
!       The minimum is first bracketed and then Brent's method is
!       applied to find the minimum. This subroutine applies 
!	specifically to the fitting of cloud data.
!
!
! Current Owner of Code: J. M. Edwards
!
! History:
!       Version         Date                    Comment
!       1.0             12-04-95                First Version under RCS
!                                               (J. M. Edwards)
!
! Description of Code:
!   FORTRAN 77  with extensions listed in documentation.
!
!- ---------------------------------------------------------------------
      SUBROUTINE LINE_SEARCH_CLOUD(IERR
     &   , N_DATA, I_FIT_TYPE, N_PARAMETER
     &   , VOL_FRACTION, RADIUS_EFFECTIVE
     &   , DATA, PARM
     &   , H, H_L2_NORM, SEARCH_DISTANCE
     &   , RESIDUAL
     &   )
!
!
!
      IMPLICIT NONE
!
!
!     INCLUDE HEADER FILES.
      INCLUDE 'incl/def_std_io.icf'
      INCLUDE 'incl/dimensions_spec.ucf'
      INCLUDE 'incl/cloud_fit_parm.acf'
      INCLUDE 'incl/prec_machine.ucf'
      INCLUDE 'incl/precision.pcf'
      INCLUDE 'incl/error.pcf'
!
!     DUMMY ARGUMENTS
      INTEGER 	!, INTENT(OUT)
     &     IERR
!             ERROR FLAG
      INTEGER 	!, INTENT(IN)
     &     N_DATA
!             NUMBER OF DATA POINTS
     &   , I_FIT_TYPE
!             TYPE OF FIT REQUIRED
     &   , N_PARAMETER
!             NUMBER OF PARAMETERS
      REAL*8	!, INTENT(IN)
     &     VOL_FRACTION(N_DATA)
!             VOLUME FRACTION OF ABSORBER
     &   , RADIUS_EFFECTIVE(N_DATA)
!             EFFECTIVE RADII OF PARTICLES
     &   , DATA(N_DATA)
!             DATA TO BE FITTED
     &   , H(N_PARAMETER)
!             SEARCHING DIRECTION
     &   , H_L2_NORM
!             L2-NORM OF H
     &   , SEARCH_DISTANCE
!             SEARCHING DISTANCE
      REAL*8	!, INTENT(INOUT)
     &     PARM(N_PARAMETER)
!             FITTING PARAMETERS
      REAL*8	!, INTENT(IN)
     &     RESIDUAL
!             NAME OF RESIDUAL FUNCTION
      EXTERNAL
     &     RESIDUAL
!             NAME OF RESIDUAL FUNCTION
!
!     LOCAL ARGUMENTS.
      INTEGER
     &     I
!             LOOP VARIABLE
     &   , ITERATION
!             NUMBER OF ITERATION
      LOGICAL
     &     L_FIT
!             VARIABLE FOR FITTING
      REAL*8
     &     S_LOW
!             LOWER LIMIT OF ENCLOSING INTERVAL
     &   , S_HIGH
!             UPPER LIMIT OF ENCLOSING INTERVAL
     &   , S_MIDDLE
!             MID-POINT OF INTERVAL
     &   , S_FIRST
!             ABSCISSA OF LOWEST POINT SO FAR
     &   , S_SECOND
!             ABSCISSA OF SCEOND LOWEST POINT
     &   , S_THIRD
!             ABSICISSA OF THIRD LOWEST
     &   , S_NEW
!             ABSCISSA OF NEW POINT
     &   , S_INITIAL
!             INITIAL SEARCHING DISTANCE
     &   , F_FIRST
!             LOWEST POINT SO FAR
     &   , F_SECOND
!             SCEOND LOWEST POINT
     &   , F_THIRD
!             THIRD LOWEST
     &   , F_NEW
!             NEW POINT
     &   , STEP
!             STEP IN S
     &   , PENULT_STEP
!             PREVIOUS STEP
     &   , TOL_SCALED
!             SCALED TOLERANCE FOR MINIMUM
      REAL*8
     &     S0
!             POSITION OF MINIMUM OF QUADRATIC
     &   , X1(NPD_CLOUD_PARAMETER)
!             SEARCH POSITION
     &   , X2(NPD_CLOUD_PARAMETER)
!             SEARCH POSITION
     &   , X3(NPD_CLOUD_PARAMETER)
!             SEARCH POSITION
     &   , X_NEW(NPD_CLOUD_PARAMETER)
!             NEW SEARCH POSITION
      REAL*8
     &     GOLDEN_RATIO
!             GOLDEN RATIO FOR SEARCH
      PARAMETER(
     &     GOLDEN_RATIO=6.1803399D-01
     &   )
!
!     SUBROUTINES CALLED:
      EXTERNAL
     &     FIT_PARABOLA
!
!
!
!     RECORD THE INITIAL SEARCHING DISTANCE.
      S_INITIAL=SEARCH_DISTANCE/H_L2_NORM
      S_NEW=S_INITIAL
!
!     FIND THREE POINTS ENCLOSING THE MINIMUM.
10    DO I=1, N_PARAMETER
         X1(I)=PARM(I)
         X2(I)=PARM(I)-S_NEW*H(I)
         X3(I)=PARM(I)+S_NEW*H(I)
      ENDDO
!
!     FIND THE RESIDUALS AT THESE POINTS.
      F_FIRST=RESIDUAL(N_DATA, I_FIT_TYPE, N_PARAMETER
     &   , VOL_FRACTION, RADIUS_EFFECTIVE
     &   , DATA, X1
     &   )
      F_SECOND=RESIDUAL(N_DATA, I_FIT_TYPE, N_PARAMETER
     &   , VOL_FRACTION, RADIUS_EFFECTIVE
     &   , DATA, X2
     &   )
      F_THIRD=RESIDUAL(N_DATA, I_FIT_TYPE, N_PARAMETER
     &   , VOL_FRACTION, RADIUS_EFFECTIVE
     &   , DATA, X3
     &   )
!
!     INCREASE S_NEW IF MINIMUM IS NOT ENCLOSED.
      IF ( (F_FIRST.GE.F_SECOND).OR.(F_FIRST.GE.F_THIRD) ) THEN
         IF ( (F_SECOND.LT.F_THIRD).AND.(F_FIRST.GE.F_SECOND) ) THEN
            DO I=1, N_PARAMETER
               PARM(I)=X1(I)
            ENDDO
         ELSE IF (F_FIRST.GE.F_THIRD) THEN
            DO I=1, N_PARAMETER
               PARM(I)=X3(I)
            ENDDO
         ENDIF
         IF (ABS(S_NEW/S_INITIAL).LT.S_MAX_RATIO) THEN
            S_NEW=1.5D+00*S_NEW
            GOTO 10
         ELSE
            WRITE(IU_MONITOR, '(/A)')
     &         '*** ERROR: SEARCH RANGE HAS BEEN EXCEEDED.'
            IERR=I_ABORT_CALCULATION
            RETURN
         ENDIF
      ENDIF
!
!     THE MINIMUM IS BRACKETED BETWEEN -S AND +S. LOCATE IT 
!     USING BRENT'S METHOD.
!
!     INITIALIZE.
      S_HIGH=S_NEW
      S_LOW=-S_NEW
      S_FIRST=0.0D+00
      S_SECOND=S_FIRST
      S_THIRD=S_FIRST
      S_NEW=0.0D+00
      F_SECOND=F_FIRST
      F_THIRD=F_FIRST
!
!     SET THE ITERATION COUNT TO 0.
      ITERATION=0
!
!     TEST FOR CONVERGENCE.
100   TOL_SCALED=(1.0D+00/H_L2_NORM+ABS(S_FIRST))*SQRT(TOL_TEST)
      IF ( (S_FIRST.LT.S_LOW+TOL_SCALED).AND.
     &     (S_FIRST.GT.S_HIGH-TOL_SCALED) ) THEN
         IF (ITERATION.GE.1) THEN
!           SET THE NEW VALUES OF THE PARAMETERS.
            DO I=1, N_PARAMETER
               PARM(I)=X_NEW(I)
            ENDDO
!           RETURN THE NEW STEP AS THE SEARCHING DISTANCE.
            SEARCH_DISTANCE=ABS(S_NEW*H_L2_NORM)
         ENDIF
         RETURN
      ENDIF
!
!        ANOTHER ITERATION IF CONVERGENCE HAS NOT OCCURRED.
         ITERATION=ITERATION+1
         IF (ITERATION.EQ.1) THEN
!           ON THE FIRST STEP SET A LARGE VALUE SO AS NOT TO REJECT
!           PARABOLIC INTERPOLATION UNFAIRLY.
            PENULT_STEP=S_HIGH-S_LOW
         ELSE
            PENULT_STEP=STEP
         ENDIF
!
!        FIND MID-POINT
         S_MIDDLE=0.5D+00*(S_LOW+S_HIGH)
!
!        FIT A PARABOLA TO THE LOWEST THREE POINTS.
         CALL FIT_PARABOLA(S_FIRST, S_SECOND, S_THIRD
     &      , F_FIRST, F_SECOND, F_THIRD
     &      , S0, L_FIT)
!
!        IF THE FIT SUCCEEDED TEST THAT IT SATISFIES THE CONDITIONS.
         IF ( (L_FIT).AND.
     &        (S_LOW.LT.S0).AND.
     &        (S_HIGH.GT.S0).AND.
     &        (ABS(S0-S_FIRST).LT.0.5D+00*ABS(PENULT_STEP)) ) THEN
!           THE STEP IS ACCEPTABLE.
            S_NEW=S0
            STEP=S_NEW-S_FIRST
         ELSE
!           A GOLDEN SECTION SEARCH IS USED.
            IF (S_FIRST.GE.S_MIDDLE) THEN
               STEP=S_LOW-S_FIRST
            ELSE
               STEP=S_HIGH-S_FIRST
            ENDIF
            STEP=GOLDEN_RATIO*STEP
            S_NEW=S_FIRST+STEP
         ENDIF
!
!        FUNCTIONAL EVALUATION AT THE NEW POINT.
         DO I=1, N_PARAMETER
            X_NEW(I)=PARM(I)+S_NEW*H(I)
         ENDDO
         F_NEW=RESIDUAL(N_DATA, I_FIT_TYPE, N_PARAMETER
     &      , VOL_FRACTION, RADIUS_EFFECTIVE
     &      , DATA, X_NEW
     &      )
!
!        REARRANGE THE POINTS DEPENDING ON THE VALUE OF F_NEW.
         IF (F_NEW.LE.F_FIRST) THEN
!           THERE IS A NEW SEQUENCE OF THE LOWEST POINTS, AND THE
!           SIZE OF THE ENCLOSING INTERVAL CAN BE REDUCED.
            IF (S_NEW.GE.S_FIRST) THEN
               S_LOW=S_FIRST
            ELSE
               S_HIGH=S_FIRST
            ENDIF
            S_THIRD=S_SECOND
            F_THIRD=F_SECOND
            S_SECOND=S_FIRST
            F_SECOND=F_FIRST
            S_FIRST=S_NEW
            F_FIRST=F_NEW
!
         ELSE
!           THE INTERVAL CAN AT LEAST BE REFINED.
            IF (S_NEW.LT.S_FIRST) THEN
               S_LOW=S_NEW
            ELSE
               S_HIGH=S_NEW
            ENDIF
            IF ( (F_NEW.LE.F_SECOND).OR.
     &           (ABS(S_SECOND-S_FIRST).LT.TOL_MACHINE) ) THEN
               S_THIRD=S_SECOND
               F_THIRD=F_SECOND
               S_SECOND=S_NEW
               F_SECOND=F_NEW
            ELSE IF ( (F_NEW.LE.F_THIRD).OR.
     &                (ABS(S_THIRD-S_FIRST).LT.TOL_MACHINE).OR.
     &                (ABS(S_THIRD-S_SECOND).LT.TOL_MACHINE) ) THEN
               S_THIRD=S_NEW
               F_THIRD=F_NEW
            ENDIF
         ENDIF

!
      IF (ITERATION.LE.NP_MAX_LINE_SEARCH) THEN
         GOTO 100
      ELSE
         WRITE(IU_MONITOR, '(/A)')
     &      '*** WARNING IN SUBROUTINE LINE_SEARCH_CLOUD.'
         WRITE(IU_MONITOR, '(A)') 'TOO MANY ITERATIONS HAVE OCCURRED.'
         IERR=I_ABORT_CALCULATION
!        SET THE NEW VALUE OF MINIMUM.
         DO I=1, N_PARAMETER
            PARM(I)=X_NEW(I)
         ENDDO
!        RETURN THE NEW STEP AS THE SEARCHING DISTANCE.
         SEARCH_DISTANCE=ABS(S_NEW*H_L2_NORM)
         RETURN
      ENDIF
!
!
      END
