!+ 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 routine is specific to the
!       minimization of errors in fitting gaseous transmissions and
!	is applicable when each ESFT term is allowed a separate
!	scaling.
!
! 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 M_LINE_SEARCH(IERR
     &   , N_SET, LENGTH_SET
     &   , U_SET, TRANS_SET, WEIGHT_POINT
     &   , N_TERM, W_ESFT, K_ESFT
     &   , I_SCALE_FUNCTION, SCALE_VECTOR, P_ARRAY, T_ARRAY
     &   , H, H_L2_NORM, SEARCH_DISTANCE
     &   )
!
!
!
      IMPLICIT NONE
!
!
!     INCLUSION OF HEADER FILES.
      INCLUDE 'incl/def_std_io.icf'
      INCLUDE 'incl/dimensions_pp.ucf'
      INCLUDE 'incl/dimensions_spec.ucf'
      INCLUDE 'incl/scale_parameters.acf'
      INCLUDE 'incl/scale_fnc.pcf'
      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_SET
!             NUMBER OF SETS
     &   , LENGTH_SET(NPD_SET_SCALE)
!             LENGTHS OF SETS
     &   , N_TERM
!             NUMBER OF ESFT TERMS
     &   , I_SCALE_FUNCTION
!             TYPE OF SCALING FUNCTION
      REAL*8	!, INTENT(IN)
     &     U_SET(NPD_AMOUNT, NPD_SET_SCALE)
!             AMOUNTS OF ABSORBER
     &   , TRANS_SET(NPD_AMOUNT, NPD_SET_SCALE)
!             TRANSMISSIVITIES
     &   , WEIGHT_POINT(NPD_SET_SCALE, NPD_AMOUNT)
!             WEIGHTS FOR DATA POINTS
     &   , W_ESFT(NPD_ESFT_TERM)
!             ESFT WEIGHTS
     &   , K_ESFT(NPD_ESFT_TERM)
!             ESFT EXPONENTS
     &   , SCALE_VECTOR(NPD_SCALE_VARIABLE, NPD_ESFT_TERM)
!             PARAMETERS FOR SCALE FUNCTION
     &   , P_ARRAY(NPD_SET_SCALE)
!             PRESSURE ARRAY
     &   , T_ARRAY(NPD_SET_SCALE)
!             TEMPERATURE ARRAY
     &   , H(NPD_SCALE_VARIABLE, NPD_ESFT_TERM)
!             DIRECTION OF SEARCHING
     &   , H_L2_NORM
!             L2 NORM OF H.
      REAL*8	!, INTENT(INOUT)
     &     SEARCH_DISTANCE
!             ESITMATED SEARCHING DISTANCE
!
!     LOCAL VARIABLES.
      INTEGER
     &     I
!             LOOP VARIABLE
     &   , K
!             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_SCALE_VARIABLE, NPD_ESFT_TERM)
!             SEARCH POSITION
     &   , X2(NPD_SCALE_VARIABLE, NPD_ESFT_TERM)
!             SEARCH POSITION
     &   , X3(NPD_SCALE_VARIABLE, NPD_ESFT_TERM)
!             SEARCH POSITION
     &   , X_NEW(NPD_SCALE_VARIABLE, NPD_ESFT_TERM)
!             NEW SEARCH POSITION
      REAL*8
     &     GOLDEN_RATIO
!             GOLDEN RATIO FOR SEARCH
      PARAMETER(
     &     GOLDEN_RATIO=.61803399
     &   )
!
!     FUNCTIONS CALLED:
      REAL*8
     &     M_RESIDUAL_TRANS
!             RESIDUAL FUNCTION
      EXTERNAL
     &     M_RESIDUAL_TRANS
!
!     SUBROUTINES CALLED:
      EXTERNAL
     &     FIT_PARABOLA
!
      INCLUDE 'incl/scale_fnc.dcf'
!
!
!
!     RECORD THE INITAIL SEARCHING DISTANCE.
      S_INITIAL=SEARCH_DISTANCE/H_L2_NORM
      S_NEW=S_INITIAL
!
!     FIND THREE POINTS ENCLOSING THE MINIMUM.
10    DO K=1, N_TERM
         DO I=1, N_SCALE_VARIABLE(I_SCALE_FUNCTION)
            X1(I, K)=SCALE_VECTOR(I, K)
            X2(I, K)=SCALE_VECTOR(I, K)-S_NEW*H(I, K)
            X3(I, K)=SCALE_VECTOR(I, K)+S_NEW*H(I, K)
         ENDDO
      ENDDO
!
!     FIND THE RESIDUALS AT THESE POINTS.
      F_FIRST=M_RESIDUAL_TRANS(N_SET, LENGTH_SET
     &   , U_SET, TRANS_SET, WEIGHT_POINT
     &   , N_TERM, W_ESFT, K_ESFT
     &   , I_SCALE_FUNCTION, X1, P_ARRAY, T_ARRAY)
      F_SECOND=M_RESIDUAL_TRANS(N_SET, LENGTH_SET
     &   , U_SET, TRANS_SET, WEIGHT_POINT
     &   , N_TERM, W_ESFT, K_ESFT
     &   , I_SCALE_FUNCTION, X2, P_ARRAY, T_ARRAY)
      F_THIRD=M_RESIDUAL_TRANS(N_SET, LENGTH_SET
     &   , U_SET, TRANS_SET, WEIGHT_POINT
     &   , N_TERM, W_ESFT, K_ESFT
     &   , I_SCALE_FUNCTION, X3, P_ARRAY, T_ARRAY)
!
!     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 K=1, N_TERM
               DO I=1, N_SCALE_VARIABLE(I_SCALE_FUNCTION)
                  SCALE_VECTOR(I, K)=X1(I, K)
               ENDDO
            ENDDO
         ELSE IF (F_FIRST.GE.F_THIRD) THEN
            DO K=1, N_TERM
               DO I=1, N_SCALE_VARIABLE(I_SCALE_FUNCTION)
                  SCALE_VECTOR(I, K)=X3(I, K)
               ENDDO
            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)')
     &         'LINE 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 VALUE OF SCALE_VECTOR.
            DO K=1, N_TERM
               DO I=1, N_SCALE_VARIABLE(I_SCALE_FUNCTION)
                  SCALE_VECTOR(I, K)=X_NEW(I, K)
               ENDDO
            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
!           SET THIS TO A LARGE VALUE TO AVOID UNFAIR REJECTION OF
!           PARABOLIC FITTING LATER.
            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 K=1, N_TERM
            DO I=1, N_SCALE_VARIABLE(I_SCALE_FUNCTION)
               X_NEW(I, K)=SCALE_VECTOR(I, K)+S_NEW*H(I, K)
            ENDDO
         ENDDO
         F_NEW=M_RESIDUAL_TRANS(N_SET, LENGTH_SET
     &      , U_SET, TRANS_SET, WEIGHT_POINT
     &      , N_TERM, W_ESFT, K_ESFT
     &      , I_SCALE_FUNCTION, X_NEW, P_ARRAY, T_ARRAY)
!
!        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_TEST) ) 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_TEST).OR.
     &                (ABS(S_THIRD-S_SECOND).LT.TOL_TEST) ) 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.'
         WRITE(IU_MONITOR, '(A)') 'TOO MANY ITERATIONS HAVE OCCURRED.'
         IERR=I_ABORT_CALCULATION
!        SET THE NEW VALUE OF SCALE_VECTOR.
         DO K=1, N_TERM
            DO I=1, N_SCALE_VARIABLE(I_SCALE_FUNCTION)
               SCALE_VECTOR(I, K)=X_NEW(I, K)
            ENDDO
         ENDDO
!        RETURN THE NEW STEP AS THE SEARCHING DISTANCE.
         SEARCH_DISTANCE=ABS(S_NEW*H_L2_NORM)
         RETURN
      ENDIF
!
!
      END
