ROOT logo
// @(#)root/quadp:$Id: TMehrotraSolver.cxx 20882 2007-11-19 11:31:26Z rdm $
// 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                                                      //
//                                                                      //
// Derived class of TQpSolverBase implementing the original Mehrotra    //
// predictor-corrector algorithm                                        //
//                                                                      //
//////////////////////////////////////////////////////////////////////////

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

ClassImp(TMehrotraSolver)

//______________________________________________________________________________
TMehrotraSolver::TMehrotraSolver()
{
// Default constructor

   fPrintlevel = 0;
   fTsig       = 0.0;
   fStep       = 0;
   fFactory    = 0;
}


//______________________________________________________________________________
TMehrotraSolver::TMehrotraSolver(TQpProbBase *of,TQpDataBase *prob,Int_t verbose)
{
// Constructor

   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)
{
// Copy constructor

   *this = another;
}


//______________________________________________________________________________
Int_t TMehrotraSolver::Solve(TQpDataBase *prob,TQpVar *iterate,TQpResidual *resid)
{
// Solve the quadratic programming problem as formulated through prob, store
// the final solution in iterate->fX . Monitor the residuals during the iterations
// through resid . The status is returned as defined in TQpSolverBase::ETerminationCode .

   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)
{
// Print information about the optimization process and monitor the convergence
// status of thye algorithm

   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()
{
// Deconstructor

   delete fStep;
}


//______________________________________________________________________________
TMehrotraSolver &TMehrotraSolver::operator=(const TMehrotraSolver &source)
{
// Assignment operator

   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;
}
 TMehrotraSolver.cxx:1
 TMehrotraSolver.cxx:2
 TMehrotraSolver.cxx:3
 TMehrotraSolver.cxx:4
 TMehrotraSolver.cxx:5
 TMehrotraSolver.cxx:6
 TMehrotraSolver.cxx:7
 TMehrotraSolver.cxx:8
 TMehrotraSolver.cxx:9
 TMehrotraSolver.cxx:10
 TMehrotraSolver.cxx:11
 TMehrotraSolver.cxx:12
 TMehrotraSolver.cxx:13
 TMehrotraSolver.cxx:14
 TMehrotraSolver.cxx:15
 TMehrotraSolver.cxx:16
 TMehrotraSolver.cxx:17
 TMehrotraSolver.cxx:18
 TMehrotraSolver.cxx:19
 TMehrotraSolver.cxx:20
 TMehrotraSolver.cxx:21
 TMehrotraSolver.cxx:22
 TMehrotraSolver.cxx:23
 TMehrotraSolver.cxx:24
 TMehrotraSolver.cxx:25
 TMehrotraSolver.cxx:26
 TMehrotraSolver.cxx:27
 TMehrotraSolver.cxx:28
 TMehrotraSolver.cxx:29
 TMehrotraSolver.cxx:30
 TMehrotraSolver.cxx:31
 TMehrotraSolver.cxx:32
 TMehrotraSolver.cxx:33
 TMehrotraSolver.cxx:34
 TMehrotraSolver.cxx:35
 TMehrotraSolver.cxx:36
 TMehrotraSolver.cxx:37
 TMehrotraSolver.cxx:38
 TMehrotraSolver.cxx:39
 TMehrotraSolver.cxx:40
 TMehrotraSolver.cxx:41
 TMehrotraSolver.cxx:42
 TMehrotraSolver.cxx:43
 TMehrotraSolver.cxx:44
 TMehrotraSolver.cxx:45
 TMehrotraSolver.cxx:46
 TMehrotraSolver.cxx:47
 TMehrotraSolver.cxx:48
 TMehrotraSolver.cxx:49
 TMehrotraSolver.cxx:50
 TMehrotraSolver.cxx:51
 TMehrotraSolver.cxx:52
 TMehrotraSolver.cxx:53
 TMehrotraSolver.cxx:54
 TMehrotraSolver.cxx:55
 TMehrotraSolver.cxx:56
 TMehrotraSolver.cxx:57
 TMehrotraSolver.cxx:58
 TMehrotraSolver.cxx:59
 TMehrotraSolver.cxx:60
 TMehrotraSolver.cxx:61
 TMehrotraSolver.cxx:62
 TMehrotraSolver.cxx:63
 TMehrotraSolver.cxx:64
 TMehrotraSolver.cxx:65
 TMehrotraSolver.cxx:66
 TMehrotraSolver.cxx:67
 TMehrotraSolver.cxx:68
 TMehrotraSolver.cxx:69
 TMehrotraSolver.cxx:70
 TMehrotraSolver.cxx:71
 TMehrotraSolver.cxx:72
 TMehrotraSolver.cxx:73
 TMehrotraSolver.cxx:74
 TMehrotraSolver.cxx:75
 TMehrotraSolver.cxx:76
 TMehrotraSolver.cxx:77
 TMehrotraSolver.cxx:78
 TMehrotraSolver.cxx:79
 TMehrotraSolver.cxx:80
 TMehrotraSolver.cxx:81
 TMehrotraSolver.cxx:82
 TMehrotraSolver.cxx:83
 TMehrotraSolver.cxx:84
 TMehrotraSolver.cxx:85
 TMehrotraSolver.cxx:86
 TMehrotraSolver.cxx:87
 TMehrotraSolver.cxx:88
 TMehrotraSolver.cxx:89
 TMehrotraSolver.cxx:90
 TMehrotraSolver.cxx:91
 TMehrotraSolver.cxx:92
 TMehrotraSolver.cxx:93
 TMehrotraSolver.cxx:94
 TMehrotraSolver.cxx:95
 TMehrotraSolver.cxx:96
 TMehrotraSolver.cxx:97
 TMehrotraSolver.cxx:98
 TMehrotraSolver.cxx:99
 TMehrotraSolver.cxx:100
 TMehrotraSolver.cxx:101
 TMehrotraSolver.cxx:102
 TMehrotraSolver.cxx:103
 TMehrotraSolver.cxx:104
 TMehrotraSolver.cxx:105
 TMehrotraSolver.cxx:106
 TMehrotraSolver.cxx:107
 TMehrotraSolver.cxx:108
 TMehrotraSolver.cxx:109
 TMehrotraSolver.cxx:110
 TMehrotraSolver.cxx:111
 TMehrotraSolver.cxx:112
 TMehrotraSolver.cxx:113
 TMehrotraSolver.cxx:114
 TMehrotraSolver.cxx:115
 TMehrotraSolver.cxx:116
 TMehrotraSolver.cxx:117
 TMehrotraSolver.cxx:118
 TMehrotraSolver.cxx:119
 TMehrotraSolver.cxx:120
 TMehrotraSolver.cxx:121
 TMehrotraSolver.cxx:122
 TMehrotraSolver.cxx:123
 TMehrotraSolver.cxx:124
 TMehrotraSolver.cxx:125
 TMehrotraSolver.cxx:126
 TMehrotraSolver.cxx:127
 TMehrotraSolver.cxx:128
 TMehrotraSolver.cxx:129
 TMehrotraSolver.cxx:130
 TMehrotraSolver.cxx:131
 TMehrotraSolver.cxx:132
 TMehrotraSolver.cxx:133
 TMehrotraSolver.cxx:134
 TMehrotraSolver.cxx:135
 TMehrotraSolver.cxx:136
 TMehrotraSolver.cxx:137
 TMehrotraSolver.cxx:138
 TMehrotraSolver.cxx:139
 TMehrotraSolver.cxx:140
 TMehrotraSolver.cxx:141
 TMehrotraSolver.cxx:142
 TMehrotraSolver.cxx:143
 TMehrotraSolver.cxx:144
 TMehrotraSolver.cxx:145
 TMehrotraSolver.cxx:146
 TMehrotraSolver.cxx:147
 TMehrotraSolver.cxx:148
 TMehrotraSolver.cxx:149
 TMehrotraSolver.cxx:150
 TMehrotraSolver.cxx:151
 TMehrotraSolver.cxx:152
 TMehrotraSolver.cxx:153
 TMehrotraSolver.cxx:154
 TMehrotraSolver.cxx:155
 TMehrotraSolver.cxx:156
 TMehrotraSolver.cxx:157
 TMehrotraSolver.cxx:158
 TMehrotraSolver.cxx:159
 TMehrotraSolver.cxx:160
 TMehrotraSolver.cxx:161
 TMehrotraSolver.cxx:162
 TMehrotraSolver.cxx:163
 TMehrotraSolver.cxx:164
 TMehrotraSolver.cxx:165
 TMehrotraSolver.cxx:166
 TMehrotraSolver.cxx:167
 TMehrotraSolver.cxx:168
 TMehrotraSolver.cxx:169
 TMehrotraSolver.cxx:170
 TMehrotraSolver.cxx:171
 TMehrotraSolver.cxx:172
 TMehrotraSolver.cxx:173
 TMehrotraSolver.cxx:174
 TMehrotraSolver.cxx:175
 TMehrotraSolver.cxx:176
 TMehrotraSolver.cxx:177
 TMehrotraSolver.cxx:178
 TMehrotraSolver.cxx:179
 TMehrotraSolver.cxx:180
 TMehrotraSolver.cxx:181
 TMehrotraSolver.cxx:182
 TMehrotraSolver.cxx:183
 TMehrotraSolver.cxx:184
 TMehrotraSolver.cxx:185
 TMehrotraSolver.cxx:186
 TMehrotraSolver.cxx:187
 TMehrotraSolver.cxx:188
 TMehrotraSolver.cxx:189
 TMehrotraSolver.cxx:190
 TMehrotraSolver.cxx:191
 TMehrotraSolver.cxx:192
 TMehrotraSolver.cxx:193
 TMehrotraSolver.cxx:194
 TMehrotraSolver.cxx:195
 TMehrotraSolver.cxx:196
 TMehrotraSolver.cxx:197
 TMehrotraSolver.cxx:198
 TMehrotraSolver.cxx:199
 TMehrotraSolver.cxx:200
 TMehrotraSolver.cxx:201
 TMehrotraSolver.cxx:202
 TMehrotraSolver.cxx:203
 TMehrotraSolver.cxx:204
 TMehrotraSolver.cxx:205
 TMehrotraSolver.cxx:206
 TMehrotraSolver.cxx:207
 TMehrotraSolver.cxx:208
 TMehrotraSolver.cxx:209
 TMehrotraSolver.cxx:210
 TMehrotraSolver.cxx:211
 TMehrotraSolver.cxx:212
 TMehrotraSolver.cxx:213
 TMehrotraSolver.cxx:214
 TMehrotraSolver.cxx:215
 TMehrotraSolver.cxx:216
 TMehrotraSolver.cxx:217
 TMehrotraSolver.cxx:218
 TMehrotraSolver.cxx:219
 TMehrotraSolver.cxx:220
 TMehrotraSolver.cxx:221
 TMehrotraSolver.cxx:222
 TMehrotraSolver.cxx:223
 TMehrotraSolver.cxx:224
 TMehrotraSolver.cxx:225
 TMehrotraSolver.cxx:226
 TMehrotraSolver.cxx:227
 TMehrotraSolver.cxx:228
 TMehrotraSolver.cxx:229
 TMehrotraSolver.cxx:230
 TMehrotraSolver.cxx:231
 TMehrotraSolver.cxx:232
 TMehrotraSolver.cxx:233
 TMehrotraSolver.cxx:234
 TMehrotraSolver.cxx:235
 TMehrotraSolver.cxx:236