ROOT  6.06/09
Reference Guide
TQpSolverBase.h
Go to the documentation of this file.
1 // @(#)root/quadp:$Id$
2 // Author: Eddy Offermann May 2004
3 
4 /*************************************************************************
5  * Copyright (C) 1995-2000, Rene Brun and Fons Rademakers. *
6  * All rights reserved. *
7  * *
8  * For the licensing terms see $ROOTSYS/LICENSE. *
9  * For the list of contributors see $ROOTSYS/README/CREDITS. *
10  *************************************************************************/
11 
12 /*************************************************************************
13  * Parts of this file are copied from the OOQP distribution and *
14  * are subject to the following license: *
15  * *
16  * COPYRIGHT 2001 UNIVERSITY OF CHICAGO *
17  * *
18  * The copyright holder hereby grants you royalty-free rights to use, *
19  * reproduce, prepare derivative works, and to redistribute this software*
20  * to others, provided that any changes are clearly documented. This *
21  * software was authored by: *
22  * *
23  * E. MICHAEL GERTZ gertz@mcs.anl.gov *
24  * Mathematics and Computer Science Division *
25  * Argonne National Laboratory *
26  * 9700 S. Cass Avenue *
27  * Argonne, IL 60439-4844 *
28  * *
29  * STEPHEN J. WRIGHT swright@cs.wisc.edu *
30  * Computer Sciences Department *
31  * University of Wisconsin *
32  * 1210 West Dayton Street *
33  * Madison, WI 53706 FAX: (608)262-9777 *
34  * *
35  * Any questions or comments may be directed to one of the authors. *
36  * *
37  * ARGONNE NATIONAL LABORATORY (ANL), WITH FACILITIES IN THE STATES OF *
38  * ILLINOIS AND IDAHO, IS OWNED BY THE UNITED STATES GOVERNMENT, AND *
39  * OPERATED BY THE UNIVERSITY OF CHICAGO UNDER PROVISION OF A CONTRACT *
40  * WITH THE DEPARTMENT OF ENERGY. *
41  *************************************************************************/
42 
43 #ifndef ROOT_TQpSolverBase
44 #define ROOT_TQpSolverBase
45 
46 #ifndef ROOT_TError
47 #include "TError.h"
48 #endif
49 
50 #ifndef ROOT_TQpVar
51 #include "TQpVar.h"
52 #endif
53 #ifndef ROOT_TQpDataBase
54 #include "TQpDataBase.h"
55 #endif
56 #ifndef ROOT_TQpResidual
57 #include "TQpResidual.h"
58 #endif
59 #ifndef ROOT_TQpProbBase
60 #include "TQpProbBase.h"
61 #endif
62 #ifndef ROOT_TQpLinSolverBase
63 #include "TQpLinSolverBase.h"
64 #endif
65 
66 #ifndef ROOT_TMatrixD
67 #include "TMatrixD.h"
68 #endif
69 
70 ///////////////////////////////////////////////////////////////////////////
71 // //
72 // Abstract base class for QP solver using interior-point //
73 // //
74 ///////////////////////////////////////////////////////////////////////////
75 
77 {
83 };
84 
85 class TQpSolverBase : public TObject
86 {
87 
88 protected:
90 
91  Double_t fDnorm; // norm of problem data
92 
93  Double_t fMutol; // termination parameters
95 
96  Double_t fGamma_f; // parameters associated with the step length heuristic
98  Double_t fPhi; // merit function, defined as the sum of the complementarity gap
99  // the residual norms, divided by (1+norm of problem data)
100  Int_t fMaxit; // maximum number of iterations allowed
101 
102  Double_t *fMu_history; //[fMaxit] history of values of mu obtained on all iterations to date
103  Double_t *fRnorm_history; //[fMaxit] history of values of residual norm obtained on all iterations to date
104  Double_t *fPhi_history; //[fMaxit] history of values of phi obtained on all iterations to date
105 
106  Double_t *fPhi_min_history; //[fMaxit] the i-th entry of this array contains the minimum value of phi
107  // encountered by the algorithm on or before iteration i
108 
109 public:
110  Int_t fIter; // iteration counter
111 
112  TQpSolverBase();
113  TQpSolverBase(const TQpSolverBase &another);
114 
115  virtual ~TQpSolverBase();
116 
117  virtual void Start (TQpProbBase *formulation,
118  TQpVar *iterate,TQpDataBase *prob,
119  TQpResidual *resid,TQpVar *step);
120  // starting point heuristic
121  virtual void DefStart (TQpProbBase *formulation,
122  TQpVar *iterate,TQpDataBase *prob,
123  TQpResidual *resid,TQpVar *step);
124  // default starting point heuristic
125  virtual void SteveStart (TQpProbBase *formulation,
126  TQpVar *iterate,TQpDataBase *prob,
127  TQpResidual *resid,TQpVar *step);
128  // alternative starting point heuristic
129  virtual void DumbStart (TQpProbBase *formulation,
130  TQpVar *iterate,TQpDataBase *prob,
131  TQpResidual *resid,TQpVar *step);
132  // alternative starting point heuristic: sets the
133  // "complementary" variables to a large positive value
134  // (based on the norm of the problem data) and the
135  // remaining variables to zero
136 
137  virtual Int_t Solve (TQpDataBase *prob,TQpVar *iterate,
138  TQpResidual *resids) = 0;
139  // implements the interior-point method for solving the QP
140 
141  virtual Double_t FinalStepLength
142  (TQpVar *iterate,TQpVar *step);
143  // Mehrotra's heuristic to calculate the final step
144 
145  virtual void DoMonitor (TQpDataBase *data,TQpVar *vars,
146  TQpResidual *resids,Double_t alpha,
147  Double_t sigma,Int_t i,Double_t mu,
148  Int_t stop_code,Int_t level);
149  // perform monitor operation at each interior-point iteration
150  virtual void DefMonitor (TQpDataBase *data,TQpVar *vars,
151  TQpResidual *resids,Double_t alpha,
152  Double_t sigma,Int_t i,Double_t mu,
153  Int_t stop_code,Int_t level) = 0;
154  // default monitor: prints out one line of information
155  // on each interior-point iteration
156  virtual Int_t DoStatus (TQpDataBase *data,TQpVar *vars,
157  TQpResidual *resids,Int_t i,Double_t mu,
158  Int_t level);
159  // this method called to test for convergence status at
160  // at the end of each interior-point iteration
161  virtual Int_t DefStatus (TQpDataBase *data,TQpVar *vars,
162  TQpResidual *resids,Int_t i,Double_t mu,
163  Int_t level);
164  // default method for checking status. May be replaced
165  // by a user-defined method
166 
168  void SetMuTol (Double_t m) { fMutol = m; }
169  Double_t GetMuTol () { return fMutol; }
170 
171  void SetArTol (Double_t ar) { fArtol = ar; }
172  Double_t GetArTol () { return fArtol; }
173  Double_t DataNorm () { return fDnorm; }
174 
175  TQpSolverBase &operator= (const TQpSolverBase &source);
176 
177  ClassDef(TQpSolverBase,1) // Qp Solver class
178 };
179 #endif
Double_t * fRnorm_history
virtual void DoMonitor(TQpDataBase *data, TQpVar *vars, TQpResidual *resids, Double_t alpha, Double_t sigma, Int_t i, Double_t mu, Int_t stop_code, Int_t level)
Monitor progress / convergence aat each interior-point iteration.
Double_t GetMuTol()
virtual void SteveStart(TQpProbBase *formulation, TQpVar *iterate, TQpDataBase *prob, TQpResidual *resid, TQpVar *step)
Starting point algoritm according to Stephen Wright.
virtual void DefStart(TQpProbBase *formulation, TQpVar *iterate, TQpDataBase *prob, TQpResidual *resid, TQpVar *step)
Default starting point.
int Int_t
Definition: RtypesCore.h:41
virtual Double_t FinalStepLength(TQpVar *iterate, TQpVar *step)
Implements a version of Mehrotra starting point heuristic, modified to ensure identical steps in the ...
virtual Int_t DoStatus(TQpDataBase *data, TQpVar *vars, TQpResidual *resids, Int_t i, Double_t mu, Int_t level)
Tests for termination.
TQpSolverBase & operator=(const TQpSolverBase &source)
Assignment operator.
ETerminationCode
Definition: TQpSolverBase.h:76
#define ClassDef(name, id)
Definition: Rtypes.h:254
virtual ~TQpSolverBase()
Deconstructor.
Double_t fGamma_a
Definition: TQpSolverBase.h:97
virtual void Start(TQpProbBase *formulation, TQpVar *iterate, TQpDataBase *prob, TQpResidual *resid, TQpVar *step)
Implements a default starting-point heuristic.
virtual void DumbStart(TQpProbBase *formulation, TQpVar *iterate, TQpDataBase *prob, TQpResidual *resid, TQpVar *step)
Alternative starting point heuristic: sets the "complementary" variables to a large positive value (b...
void SetMuTol(Double_t m)
Double_t fGamma_f
Definition: TQpSolverBase.h:96
Double_t fDnorm
Definition: TQpSolverBase.h:91
Double_t DataNorm()
virtual Int_t DefStatus(TQpDataBase *data, TQpVar *vars, TQpResidual *resids, Int_t i, Double_t mu, Int_t level)
Default status method.
Double_t * fMu_history
TMarker * m
Definition: textangle.C:8
TQpLinSolverBase * fSys
Definition: TQpSolverBase.h:89
void SetArTol(Double_t ar)
virtual void DefMonitor(TQpDataBase *data, TQpVar *vars, TQpResidual *resids, Double_t alpha, Double_t sigma, Int_t i, Double_t mu, Int_t stop_code, Int_t level)=0
double Double_t
Definition: RtypesCore.h:55
virtual Int_t Solve(TQpDataBase *prob, TQpVar *iterate, TQpResidual *resids)=0
Double_t fArtol
Definition: TQpSolverBase.h:94
Mother of all ROOT objects.
Definition: TObject.h:58
TQpLinSolverBase * GetLinearSystem()
Definition: TQpVar.h:65
int iterate(rng_state_t *X)
Definition: mixmax.cxx:57
Double_t fPhi
Definition: TQpSolverBase.h:98
Double_t fMutol
Definition: TQpSolverBase.h:93
Double_t * fPhi_history
Double_t * fPhi_min_history
Double_t GetArTol()