00001 // @(#)root/quadp:$Id: TQpVar.h 20882 2007-11-19 11:31:26Z rdm $ 00002 // Author: Eddy Offermann May 2004 00003 00004 /************************************************************************* 00005 * Copyright (C) 1995-2000, Rene Brun and Fons Rademakers. * 00006 * All rights reserved. * 00007 * * 00008 * For the licensing terms see $ROOTSYS/LICENSE. * 00009 * For the list of contributors see $ROOTSYS/README/CREDITS. * 00010 *************************************************************************/ 00011 00012 /************************************************************************* 00013 * Parts of this file are copied from the OOQP distribution and * 00014 * are subject to the following license: * 00015 * * 00016 * COPYRIGHT 2001 UNIVERSITY OF CHICAGO * 00017 * * 00018 * The copyright holder hereby grants you royalty-free rights to use, * 00019 * reproduce, prepare derivative works, and to redistribute this software* 00020 * to others, provided that any changes are clearly documented. This * 00021 * software was authored by: * 00022 * * 00023 * E. MICHAEL GERTZ gertz@mcs.anl.gov * 00024 * Mathematics and Computer Science Division * 00025 * Argonne National Laboratory * 00026 * 9700 S. Cass Avenue * 00027 * Argonne, IL 60439-4844 * 00028 * * 00029 * STEPHEN J. WRIGHT swright@cs.wisc.edu * 00030 * Computer Sciences Department * 00031 * University of Wisconsin * 00032 * 1210 West Dayton Street * 00033 * Madison, WI 53706 FAX: (608)262-9777 * 00034 * * 00035 * Any questions or comments may be directed to one of the authors. * 00036 * * 00037 * ARGONNE NATIONAL LABORATORY (ANL), WITH FACILITIES IN THE STATES OF * 00038 * ILLINOIS AND IDAHO, IS OWNED BY THE UNITED STATES GOVERNMENT, AND * 00039 * OPERATED BY THE UNIVERSITY OF CHICAGO UNDER PROVISION OF A CONTRACT * 00040 * WITH THE DEPARTMENT OF ENERGY. * 00041 *************************************************************************/ 00042 00043 #ifndef ROOT_TQpVar 00044 #define ROOT_TQpVar 00045 00046 #ifndef ROOT_TError 00047 #include "TError.h" 00048 #endif 00049 00050 #ifndef ROOT_TMatrixD 00051 #include "TMatrixD.h" 00052 #endif 00053 #ifndef ROOT_TVectorD 00054 #include "TVectorD.h" 00055 #endif 00056 00057 /////////////////////////////////////////////////////////////////////////// 00058 // // 00059 // Class containing the variables for the general QP formulation // 00060 // In terms of in our abstract problem formulation, these variables are // 00061 // the vectors x, y, z and s. // 00062 // // 00063 /////////////////////////////////////////////////////////////////////////// 00064 00065 class TQpVar : public TObject 00066 { 00067 00068 protected: 00069 Int_t fNx; 00070 Int_t fMy; 00071 Int_t fMz; 00072 Int_t fNxup; 00073 Int_t fNxlo; 00074 Int_t fMcup; 00075 Int_t fMclo; 00076 00077 // these variables will be "Used" not copied 00078 TVectorD fXloIndex; 00079 TVectorD fXupIndex; 00080 TVectorD fCupIndex; 00081 TVectorD fCloIndex; 00082 00083 static Double_t StepBound (TVectorD &v,TVectorD &dir,Double_t maxStep); 00084 static Double_t FindBlocking (TVectorD &w,TVectorD &wstep,TVectorD &u,TVectorD &ustep, 00085 Double_t maxStep,Double_t &w_elt,Double_t &wstep_elt,Double_t &u_elt, 00086 Double_t &ustep_elt,int& first_or_second); 00087 static Double_t FindBlockingSub(Int_t n,Double_t *w,Int_t incw,Double_t *wstep,Int_t incwstep, 00088 Double_t *u,Int_t incu,Double_t *ustep,Int_t incustep, 00089 Double_t maxStep,Double_t &w_elt,Double_t &wstep_elt, 00090 Double_t &u_elt,Double_t &ustep_elt,Int_t &first_or_second); 00091 00092 public: 00093 00094 Int_t fNComplementaryVariables; // number of complementary primal-dual variables. 00095 00096 // these variables will be "Used" not copied 00097 TVectorD fX; 00098 TVectorD fS; 00099 TVectorD fY; 00100 TVectorD fZ; 00101 00102 TVectorD fV; 00103 TVectorD fPhi; 00104 00105 TVectorD fW; 00106 TVectorD fGamma; 00107 00108 TVectorD fT; 00109 TVectorD fLambda; 00110 00111 TVectorD fU; 00112 TVectorD fPi; 00113 00114 TQpVar(); 00115 // constructor in which the data and variable pointers are set to point to the given arguments 00116 TQpVar(TVectorD &x_in,TVectorD &s_in,TVectorD &y_in,TVectorD &z_in, 00117 TVectorD &v_in,TVectorD &gamma_in,TVectorD &w_in,TVectorD &phi_in, 00118 TVectorD &t_in,TVectorD &lambda_in,TVectorD &u_in,TVectorD &pi_in, 00119 TVectorD &ixlow_in,TVectorD &ixupp_in,TVectorD &iclow_in,TVectorD &icupp_in); 00120 00121 // constructor that creates variables objects of specified dimensions. 00122 TQpVar(Int_t nx,Int_t my,Int_t mz, 00123 TVectorD &ixlow,TVectorD &ixupp,TVectorD &iclow,TVectorD &icupp); 00124 TQpVar(const TQpVar &another); 00125 00126 virtual ~TQpVar() {} 00127 00128 // Indicates what type is the blocking variable in the step length determination. If kt_block, 00129 // then the blocking variable is one of the slack variables t for a general lower bound, 00130 // and so on. Special value kno_block is for the case in which a step length of 1 can be 00131 // taken without hitting the bound. 00132 00133 enum EVarBlock { kno_block,kt_block,klambda_block,ku_block,kpi_block, 00134 kv_block,kgamma_block,kw_block,kphi_block }; 00135 00136 virtual Double_t GetMu (); // compute complementarity gap, obtained by taking the 00137 // inner product of the complementary vectors and dividing 00138 // by the total number of components 00139 // computes mu = (t'lambda +u'pi + v'gamma + w'phi)/ 00140 // (mclow+mcupp+nxlow+nxupp) 00141 virtual Double_t MuStep (TQpVar *step,Double_t alpha); 00142 // compute the complementarity gap resulting from a step 00143 // of length "alpha" along direction "step" 00144 virtual void Saxpy (TQpVar *b,Double_t alpha); 00145 // given variables b, compute a <- a + alpha b, 00146 // where a are the variables in this class 00147 00148 virtual void Negate (); // negate the value of all the variables in this structure 00149 00150 virtual Double_t StepBound (TQpVar *b); // calculate the largest alpha in (0,1] such that the 00151 // nonnegative variables stay nonnegative in the given 00152 // search direction. In the general QP problem formulation 00153 // this is the largest value of alpha such that 00154 // (t,u,v,w,lambda,pi,phi,gamma) + alpha * (b->t,b->u, 00155 // b->v,b->w,b->lambda,b->pi,b->phi,b->gamma) >= 0. 00156 00157 virtual Double_t FindBlocking(TQpVar *step,Double_t &primalValue,Double_t &primalStep,Double_t &dualValue, 00158 Double_t &dualStep,Int_t &firstOrSecond); 00159 // Performs the same function as StepBound, and supplies 00160 // additional information about which component of the 00161 // nonnegative variables is responsible for restricting 00162 // alpha. In terms of the abstract formulation, the 00163 // components have the following meanings. 00164 // 00165 // primalValue: the value of the blocking component of the 00166 // primal variables (u,t,v,w). 00167 // primalStep: the corresponding value of the blocking 00168 // component of the primal step variables (b->u,b->t, 00169 // b->v,b->w) 00170 // dualValue: the value of the blocking component of the 00171 // dual variables (lambda,pi,phi,gamma). 00172 // dualStep: the corresponding value of the blocking 00173 // component of the dual step variables (b->lambda,b->pi, 00174 // b->phi,b->gamma) 00175 // firstOrSecond: 1 if the primal step is blocking, 2 00176 // if the dual step is block, 0 if no step is blocking. 00177 00178 virtual void InteriorPoint(Double_t alpha,Double_t beta); 00179 // sets components of (u,t,v,w) to alpha and of 00180 // (lambda,pi,phi,gamma) to beta 00181 virtual void ShiftBoundVariables 00182 (Double_t alpha,Double_t beta); 00183 // add alpha to components of (u,t,v,w) and beta to 00184 // components of (lambda,pi,phi,gamma) 00185 virtual Bool_t IsInteriorPoint(); // check whether this is an interior point. Useful as a 00186 // sanity check. 00187 virtual Double_t Violation (); // The amount by which the current variables violate the 00188 // non-negativity constraints. 00189 virtual void Print (Option_t *option="") const; 00190 virtual Double_t Norm1 (); // compute the 1-norm of the variables 00191 virtual Double_t NormInf (); // compute the inf-norm of the variables 00192 virtual Bool_t ValidNonZeroPattern(); 00193 00194 TQpVar &operator= (const TQpVar &source); 00195 00196 ClassDef(TQpVar,1) // Qp Variables class 00197 }; 00198 #endif
1.5.1