!*****************************************************
!***Routine for Finding Minimum Along Search Vector***
!*****************************************************
	SUBROUTINE LINEAR
	USE SHAREDVARS
	REAL*8 FUNCCALC
	INTEGER IPT,ILINE,IOPTPARM
!***Use Current Best Point (Location #0) As Start of Line, Loading It Into the First Working Point 
	CALL SHIFT(0,1)
	STEP(1)=0.0
!***Generate Two More  Points Along Search Vector (Locations 2 and 3) Based on Step Size from Subroutine Newton and half that size
	STEP(2)=0.5*STEP(3)
	DO IPT=2,3
		DO IOPTPARM=1,NOPTPARM
			OPTPARMSEARCH(IOPTPARM,IPT)=OPTPARMSEARCH(IOPTPARM,1)+STEP(IPT)*VECTOR(IOPTPARM)
			OPTPARMSEARCH(IOPTPARM,IPT)=MAX(PARMMIN(OPTPARMID(IOPTPARM)),MIN(PARMMAX(OPTPARMID(IOPTPARM)),OPTPARMSEARCH(IOPTPARM,IPT)))
		END DO
		FUNC(IPT)=FUNCCALC(OPTPARMSEARCH(1,IPT))
		IF(ISNAN(FUNC(IPT))) FUNC(IPT)=FUNC(0)+2
	END DO
!***Determine Which Working Point is Best
	BEST=1
	DO IPT=2,3
		IF(FUNC(IPT).LT.FUNC(BEST)) BEST=IPT
	ENDDO
	IF(PRINTFLAG) TYPE *,'START OF LINEAR, BEST IS',BEST
	IF(PRINTFLAG) TYPE "('STEP',6F15.6)",STEP
	IF(PRINTFLAG) TYPE"('FUNC',6F15.6)",FUNC
!***Main Minimization Iteration Loop
	DO ILINE=1,MLINE
		IF(PRINTFLAG) TYPE *,'START OF LINEAR LOOP',ILINE,' BEST IS',BEST
		IF(PRINTFLAG) TYPE "('STEP',6F15.6)",STEP
		IF(PRINTFLAG) TYPE"('FUNC',6F15.6)",FUNC
!***If Third Working Point is Best, Drop First Point and Generate New Third Point Further Along Line
!***(This can only occur if working points don't yet reach minimum and results in longer steps until minimum is bracketed)
		IF(BEST.EQ.3) THEN
			CALL SHIFT(2,1)
			CALL SHIFT(3,2)
			STEP(3)=STEP(2)+2.0*(STEP(2)-STEP(1))
			DO IOPTPARM=1,NOPTPARM
				OPTPARMSEARCH(IOPTPARM,3)=OPTPARMSEARCH(IOPTPARM,0)+STEP(3)*VECTOR(IOPTPARM)
				OPTPARMSEARCH(IOPTPARM,3)=MAX(PARMMIN(OPTPARMID(IOPTPARM)),MIN(PARMMAX(OPTPARMID(IOPTPARM)),OPTPARMSEARCH(IOPTPARM,3)))
			END DO
			FUNC(3)=FUNCCALC(OPTPARMSEARCH(1,3))
			IF(ISNAN(FUNC(3))) FUNC(3)=FUNC(0)+2
			IF(FUNC(2).LT.FUNC(3)) BEST=2
!***If First Working Point is Best, Drop Third Point and Generate New Point Between First and Second Points 
!***(This can only occur if first point is at step=0 and results in shorter steps until working points bracket minimum)
		ELSEIF(BEST.EQ.1) THEN
			CALL SHIFT(2,3)
			STEP(2)=0.5*STEP(3)
			DO IOPTPARM=1,NOPTPARM
				OPTPARMSEARCH(IOPTPARM,2)=OPTPARMSEARCH(IOPTPARM,0)+STEP(2)*VECTOR(IOPTPARM)
				OPTPARMSEARCH(IOPTPARM,2)=MAX(PARMMIN(OPTPARMID(IOPTPARM)),MIN(PARMMAX(OPTPARMID(IOPTPARM)),OPTPARMSEARCH(IOPTPARM,2)))
			END DO
			FUNC(2)=FUNCCALC(OPTPARMSEARCH(1,2))
			IF(ISNAN(FUNC(2))) FUNC(2)=FUNC(0)+2
			IF(FUNC(2).LT.FUNC(1)) BEST=2
!***If Second Working Point is Best, Generate Fourth Point Between First And Second Points and Fifth Point Between Second and Third Points
!***Retain Best Point (Either 2, 4, or 5) and the Points on Either Side of Best Point 
!***(Once point 2 is best point, a minimum is bracketed and working points will compress around minimum until loop is done)
		ELSEIF(BEST.EQ.2) THEN
			STEP(4)=(STEP(1)+STEP(2))/2
			DO IOPTPARM=1,NOPTPARM
				OPTPARMSEARCH(IOPTPARM,4)=OPTPARMSEARCH(IOPTPARM,0)+STEP(4)*VECTOR(IOPTPARM)
				OPTPARMSEARCH(IOPTPARM,4)=MAX(PARMMIN(OPTPARMID(IOPTPARM)),MIN(PARMMAX(OPTPARMID(IOPTPARM)),OPTPARMSEARCH(IOPTPARM,4)))
			END DO
			FUNC(4)=FUNCCALC(OPTPARMSEARCH(1,4))
			IF(FUNC(4).LT.FUNC(2)) BEST=4
			STEP(5)=(STEP(2)+STEP(3))/2
			DO IOPTPARM=1,NOPTPARM
				OPTPARMSEARCH(IOPTPARM,5)=OPTPARMSEARCH(IOPTPARM,0)+STEP(5)*VECTOR(IOPTPARM)
				OPTPARMSEARCH(IOPTPARM,5)=MAX(PARMMIN(OPTPARMID(IOPTPARM)),MIN(PARMMAX(OPTPARMID(IOPTPARM)),OPTPARMSEARCH(IOPTPARM,5)))
			END DO
			FUNC(5)=FUNCCALC(OPTPARMSEARCH(1,5))
			IF(FUNC(5).LT.FUNC(BEST)) BEST=5
			IF(PRINTFLAG) TYPE *,'MIDDLE OF LINE LOOP, BEST IS NOW',BEST,STEP(BEST)
			IF(BEST.EQ.2) THEN
				CALL SHIFT(4,1)
				CALL SHIFT(5,3)
			ELSEIF(BEST.EQ.4) THEN
				CALL SHIFT(2,3)
				CALL SHIFT(4,2)
			ELSEIF(BEST.EQ.5) THEN
				CALL SHIFT(2,1)
				CALL SHIFT(5,2)
			ENDIF
			BEST=2
		ENDIF
		IF(PRINTFLAG) TYPE *,'END OF LINEAR LOOP',ILINE,' BEST IS',BEST
		IF(PRINTFLAG) TYPE "('STEP',6F15.6)",STEP
		IF(PRINTFLAG) TYPE "('FUNC',6F15.6)",(FUNC(IPOS),IPOS=0,5)
		IF(ABS((FUNC(BEST)-FUNC(1))/FUNC(BEST)).LT.CONVRGREQ.AND.ABS((FUNC(BEST)-FUNC(3))/FUNC(BEST)).LT.CONVRGREQ) EXIT
	ENDDO
	RETURN
	END SUBROUTINE LINEAR

!********************************************************
!***Routine for Shifting Working Points in Line Search***
!********************************************************
	SUBROUTINE SHIFT(PT1,PT2)
	USE SHAREDVARS
	INTEGER PT1,PT2,IOPTPARM
	FUNC(PT2)=FUNC(PT1)
	STEP(PT2)=STEP(PT1)
	DO IOPTPARM=1,NOPTPARM
		OPTPARMSEARCH(IOPTPARM,PT2)=OPTPARMSEARCH(IOPTPARM,PT1)
	END DO
	RETURN
	END SUBROUTINE SHIFT
