    // @(#)root/quadp:$Name:  $:$Id: TMehrotraSolver.cxx,v 1.3 2004/06/09 12:23:16 brun Exp $
    // Author: Eddy Offermann   May 2004

    /*************************************************************************
     * Copyright (C) 1995-2000, Rene Brun and Fons Rademakers.               *
     * All rights reserved.                                                  *
     *                                                                       *
     * For the licensing terms see $ROOTSYS/LICENSE.                         *
     * For the list of contributors see $ROOTSYS/README/CREDITS.             *
     *************************************************************************/

    /*************************************************************************
     * Parts of this file are copied from the OOQP distribution and          *
     * are subject to the following license:                                 *
     *                                                                       *
     * COPYRIGHT 2001 UNIVERSITY OF CHICAGO                                  *
     *                                                                       *
     * The copyright holder hereby grants you royalty-free rights to use,    *
     * reproduce, prepare derivative works, and to redistribute this software*
     * to others, provided that any changes are clearly documented. This     *
     * software was authored by:                                             *
     *                                                                       *
     *   E. MICHAEL GERTZ      gertz@mcs.anl.gov                             *
     *   Mathematics and Computer Science Division                           *
     *   Argonne National Laboratory                                         *
     *   9700 S. Cass Avenue                                                 *
     *   Argonne, IL 60439-4844                                              *
     *                                                                       *
     *   STEPHEN J. WRIGHT     swright@cs.wisc.edu                           *
     *   Computer Sciences Department                                        *
     *   University of Wisconsin                                             *
     *   1210 West Dayton Street                                             *
     *   Madison, WI 53706   FAX: (608)262-9777                              *
     *                                                                       *
     * Any questions or comments may be directed to one of the authors.      *
     *                                                                       *
     * ARGONNE NATIONAL LABORATORY (ANL), WITH FACILITIES IN THE STATES OF   *
     * ILLINOIS AND IDAHO, IS OWNED BY THE UNITED STATES GOVERNMENT, AND     *
     * OPERATED BY THE UNIVERSITY OF CHICAGO UNDER PROVISION OF A CONTRACT   *
     * WITH THE DEPARTMENT OF ENERGY.                                        *
     *************************************************************************/

    //////////////////////////////////////////////////////////////////////////
    //                                                                      //
    // TMehrotraSolver                                                      //
    //                                                                      //
    //////////////////////////////////////////////////////////////////////////

    #include "Riostream.h"
    #include "TMehrotraSolver.h"

    ClassImp(TMehrotraSolver)

    //______________________________________________________________________________
     TMehrotraSolver::TMehrotraSolver()
    {
      fPrintlevel = 0;
      fTsig       = 0.0;
      fStep       = 0;
      fFactory    = 0;
    }

    //______________________________________________________________________________
     TMehrotraSolver::TMehrotraSolver(TQpProbBase *of,TQpDataBase *prob,Int_t verbose)
    {
      fFactory = of;
      fStep = fFactory->MakeVariables(prob);

      fPrintlevel = verbose;
      fTsig       = 3.0; // the usual value for the centering exponent (tau)
    }

    //______________________________________________________________________________
     TMehrotraSolver::TMehrotraSolver(const TMehrotraSolver &another) : TQpSolverBase(another)
    {
      *this = another;
    }

    //______________________________________________________________________________
     Int_t TMehrotraSolver::Solve(TQpDataBase *prob,TQpVar *iterate,TQpResidual *resid)
    {
      Int_t status_code;
      Double_t alpha = 1;
      Double_t sigma = 1;

      fDnorm = prob->DataNorm();

      // initialization of (x,y,z) and factorization routine.
      fSys = fFactory->MakeLinSys(prob);
      this->Start(fFactory,iterate,prob,resid,fStep);

      fIter = 0;
      Double_t mu = iterate->GetMu();

      Int_t done = 0;
      do
        {
          fIter++;

          // evaluate residuals and update algorithm status:
          resid->CalcResids(prob,iterate);

          //  termination test:
          status_code = this->DoStatus(prob,iterate,resid,fIter,mu,0);
          if (status_code != kNOT_FINISHED ) break;
          if (fPrintlevel >= 10)
            this->DoMonitor(prob,iterate,resid,alpha,sigma,fIter,mu,status_code,0);

          // *** Predictor step ***

          resid->Set_r3_xz_alpha(iterate,0.0);

          fSys->Factor(prob,iterate);
          fSys->Solve(prob,iterate,resid,fStep);
          fStep->Negate();

          alpha = iterate->StepBound(fStep);

          // calculate centering parameter
          Double_t muaff = iterate->MuStep(fStep,alpha);
          sigma = TMath::Power(muaff/mu,fTsig);

          // *** Corrector step ***

          // form right hand side of linear system:
          resid->Add_r3_xz_alpha(fStep,-sigma*mu );

          fSys->Solve(prob,iterate,resid,fStep);
          fStep->Negate();

          // We've finally decided on a step direction, now calculate the
          // length using Mehrotra's heuristic.
          alpha = this->FinalStepLength(iterate,fStep);

          // alternatively, just use a crude step scaling factor.
          //alpha = 0.995 * iterate->StepBound(fStep);

          // actually take the step and calculate the new mu
          iterate->Saxpy(fStep,alpha);
          mu = iterate->GetMu();
        } while(!done);

      resid->CalcResids(prob,iterate);
      if (fPrintlevel >= 10)
        this->DoMonitor(prob,iterate,resid,alpha,sigma,fIter,mu,status_code,1);

      return status_code;
    }

    //______________________________________________________________________________
     void TMehrotraSolver::DefMonitor(TQpDataBase * /* data */,TQpVar * /* vars */,
                                      TQpResidual *resids,
                                      Double_t alpha,Double_t /* sigma */,Int_t i,Double_t mu,
                                      Int_t status_code,Int_t level)
    {
      switch (level) {
        case 0 : case 1: {
          cout << endl << "Duality Gap: " << resids->GetDualityGap() << endl;
          if (i > 1) {
            cout << " alpha = " << alpha << endl;
          }
          cout << " *** Iteration " << i << " *** " << endl;
          cout << " mu = " << mu << " relative residual norm = "
      	 << resids->GetResidualNorm()/fDnorm << endl;

          if (level == 1) {
            // Termination has been detected by the status check; print
            // appropriate message
            switch (status_code) {
              case kSUCCESSFUL_TERMINATION:
              cout << endl << " *** SUCCESSFUL TERMINATION ***" << endl;
              break;
            case kMAX_ITS_EXCEEDED:
              cout << endl << " *** MAXIMUM ITERATIONS REACHED *** " << endl;
              break;
            case kINFEASIBLE:
              cout << endl << " *** TERMINATION: PROBABLY INFEASIBLE *** " << endl;
              break;
            case kUNKNOWN:
              cout << endl << " *** TERMINATION: STATUS UNKNOWN *** " << endl;
              break;
            }
          }
        } break; // end case 0: case 1:
      } // end switch(level)
    }

    //______________________________________________________________________________
     TMehrotraSolver::~TMehrotraSolver()
    {
      delete fStep;
    }

    //______________________________________________________________________________
    TMehrotraSolver &TMehrotraSolver::operator=(const TMehrotraSolver &source)
    {
      if (this != &source) {
        TQpSolverBase::operator=(source);

        fPrintlevel = source.fPrintlevel;
        fTsig       = source.fTsig;

        if (fStep) delete fStep;

        fStep    = new TQpVar(*source.fStep);
        fFactory = source.fFactory;
      }
      return *this;
    }