This file is indexed.

/usr/include/trilinos/NOX_Solver_InexactTrustRegionBased.H is in libtrilinos-nox-dev 12.10.1-3.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
// $Id$
// $Source$

//@HEADER
// ************************************************************************
//
//            NOX: An Object-Oriented Nonlinear Solver Package
//                 Copyright (2002) Sandia Corporation
//
// Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
// license for use of this work by or on behalf of the U.S. Government.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
// 1. Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//
// 2. Redistributions in binary form must reproduce the above copyright
// notice, this list of conditions and the following disclaimer in the
// documentation and/or other materials provided with the distribution.
//
// 3. Neither the name of the Corporation nor the names of the
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
// Questions? Contact Roger Pawlowski (rppawlo@sandia.gov) or
// Eric Phipps (etphipp@sandia.gov), Sandia National Laboratories.
// ************************************************************************
//  CVS Information
//  $Source$
//  $Author$
//  $Date$
//  $Revision$
// ************************************************************************
//@HEADER

#ifndef NOX_SOLVER_INEXACTTRUSTREGIONBASED_H
#define NOX_SOLVER_INEXACTTRUSTREGIONBASED_H

#include "NOX_Solver_Generic.H"        // base class

// Class data elements
#include "Teuchos_ParameterList.hpp"
#include "NOX_Direction_Utils_InexactNewton.H"
#include "NOX_Solver_PrePostOperator.H"
#include "Teuchos_RCP.hpp"

// Forward declarations
namespace NOX {
  class Utils;
  class GlobalData;
  namespace MeritFunction {
    class Generic;
  }
  namespace Direction {
    class Generic;
  }
}

namespace NOX {
namespace Solver {

/*!
  \brief %Newton-like solver using a trust region.

Our goal is to solve: \f$ F(x) = 0, \f$ where \f$ F:\Re^n \rightarrow
\Re^n \f$.  Alternatively, we might say that we wish to solve

  
\f$
\min f(x) \equiv \frac{1}{2} \|F(x)\|^2_2.
\f$

The trust region subproblem (TRSP) at iteration \f$k\f$ is given by

  
\f$
\min \; m_k(s) \equiv f_k + g_k^T d + \frac{1}{2} d^T B_k d,
\mbox{ s.t. } \|d\| \leq \Delta_k
\quad \mbox{(TRSP)}
\f$

where

<ul>
<li>\f$ f_k = f(x_k) = \frac{1}{2} \|F(x_k)\|^2_2 \f$,
<li>\f$ g_k = \nabla f(x_k) = J(x_k)^T F(x_k) \f$,
<li>\f$ B_k =  J(x_k)^T J(x_k) \approx \nabla^2 f(x_k) \f$,
<li>\f$ J(x_k)\f$ is the Jacobian of \f$F\f$ at \f$x_k\f$, and
<li>\f$ \Delta_k \f$ is the trust region radius.
</ul>

The "improvement ratio" for a given step \f$ s \f$ is defined as

&nbsp;&nbsp;
\f$
\rho = \displaystyle\frac{ f(x_k) - f(x_k + d) } { m_k(0) - m_k(d) }
\f$

An iteration consists of the following steps.

<ul>
<li> Compute Newton-like direction: \f$n\f$

<li> Compute Cauchy-like direction: \f$c\f$

<li> If this is the first iteration, initialize \f$\Delta\f$ as
     follows: If \f$\|n\|_2 < \Delta_{\min}\f$, then \f$\Delta = 2
     \Delta_{\min}\f$; else, \f$\Delta = \|n\|_2\f$.

<li> Initialize \f$\rho = -1\f$

<li> While \f$\rho < \rho_{\min}\f$ and \f$\Delta > \Delta_{\min}\f$, do the following.

     <ul>
     <li> Compute the direction \f$d\f$ as follows:

          <ul>

          <li> If \f$\|n\|_2 < \Delta\f$, then take a Newton step by
               setting \f$d = n\f$

      <li> Otherwise if \f$\|c\|_2 > \Delta\f$, then take a Cauchy
               step by setting \f$d =
               \displaystyle\frac{\Delta}{\|c\|_2} c\f$

      <li> Otherwise, take a Dog Leg step by setting
               \f$ d = (1-\gamma) c + \gamma n \f$ where
           \f$
           \gamma = \displaystyle\frac
           {-c^T a + \sqrt{ (c^Ta)^2 - (c^Tc - \Delta^2) a^Ta}}{a^Ta}
           \f$
           with \f$a = n-c\f$.

          </ul>

     <li> Set \f$x_{\rm new} = x + d\f$ and calculate \f$f_{\rm new}\f$

     <li> If \f$f_{\rm new} \geq f\f$, then \f$\rho = -1\f$ Otherwise
      \f$ \rho = \displaystyle \frac {f - f_{\rm new}} {| d^T J F
      + \frac{1}{2} (J d)^T (J d)|} \f$

     </ul>

<li> Update the solution: \f$x = x_{\rm new}\f$

<li> Update trust region:

     <ul>

     <li> If \f$\rho < \rho_{\rm s}\f$ and \f$\|n\|_2 < \Delta\f$,
          then shrink the trust region to the size of the Newton step:
          \f$\Delta = \|n\|_2\f$.

     <li> Otherwise if \f$\rho < \rho_{\rm s}\f$, then shrink the
          trust region: \f$\Delta = \max \{ \beta_{\rm s} \Delta,
          \Delta_{\min} \} \f$.

     <li> Otherwise if \f$\rho > \rho_{\rm e}\f$ and \f$\|d\|_2 =
          \Delta\f$, then expand the trust region: \f$\Delta = \min \{
          \beta_{\rm e} \Delta, \Delta_{\rm max} \} \f$.

     </ul>

</ul>

<B>Input Paramters</B>

The following parameters should be specified in the "Trust Region"
sublist based to the solver.

- "Inner Iteration Method" - Choice of trust region algorithm to use.
  Choices are:
  <ul>
  <li> "Standard Trust Region"
  <li> "Inexact Trust Region"
  </ul>

- "Direction" - Sublist of the direction parameters for the %Newton
  point, passed to the NOX::Direction::Manager constructor. If this
  sublist does not exist, it is created by default. Furthermore, if
  "Method" is not specified in this sublist, it is added with a value of
  "Newton".

- "Cauchy %Direction" - Sublist of the direction parameters for the
  Cauchy point, passed to the NOX::Direction::Manager constructor. If
  this sublist does not exist, it is created by default. Furthermore, if
  "Method" is not specified in this sublist, it is added with a value of
  "Steepest Descent" Finally, if the sub-sublist "Steepest Descent" does
  not exist, it is created and the parameter "Scaling Type" is added and
  set to "Quadratic Min Model".

- "Minimum Trust Region Radius" (\f$\Delta_{\min}\f$) - Minimum allowable trust region
  radius. Defaults to 1.0e-6.

- "Maximum Trust Region Radius" (\f$\Delta_{\max}\f$) - Minimum allowable trust region
  radius. Defaults to 1.0e+10.

- "Minimum Improvement Ratio" (\f$\rho_{\min}\f$) - Minimum improvement ratio to accept
  the step. Defaults to 1.0e-4.

- "Contraction Trigger Ratio" (\f$\rho_{\rm s}\f$) - If the improvement ratio is less than
  this value, then the trust region is contracted by the amount
  specified by the "Contraction Factor". Must be larger than "Minimum
  Improvement Ratio". Defaults to 0.1.

- "Contraction Factor" (\f$\beta_{\rm s}\f$) - See above. Defaults to 0.25.

- "Expansion Trigger Ratio" (\f$\rho_{\rm e}\f$) - If the
  improvement ratio is greater than this value, then the trust region
  is contracted by the amount specified by the "Expansion
  Factor". Defaults to 0.75.

- "Expansion Factor"  (\f$\beta_{\rm e}\f$) - See above. Defaults to 4.0.

- "Recovery Step" - Defaults to 1.0.

- "Use Ared/Pred Ratio Calculation" (boolean) - Defaults to false. If
  set to true, this option replaces the algorithm used to compute the
  improvement ratio, \f$ \rho \f$, as described above.  The improvement
  ratio is replaced by an "Ared/Pred" sufficient decrease criteria
  similar to that used in line search algorithms (see Eisenstat and
  Walker, SIAM Journal on Optimization V4 no. 2 (1994) pp 393-422):
  - \f$\rho = \frac{\|F(x) \| - \| F(x + d) \| }
                   {\| F(x) \| - \| F(x) + Jd \| } \f$

- "Use Cauchy in Newton Direction" - Boolean.  Used only by the
  "Inexact Trust Region" algorithm.  If set to true, the initial guess
  for the Newton direction computation will use the Cauchy direction as
  the initial guess.  Defaults to false.

- "Use Dogleg Segment Minimization" - Boolean.  Used only by the
  "Inexact Trust Region" algorithm.  If set to true, the \f$ \tau \f$
  parameter is minimized over the dogleg line segments instead of
  being computed at the trust regioin radius.  Used only by the
  "Inexact Trust Region" algorithm.  Defaults to false.

- "Use Counters" - Boolean.  If set to true, solver statistics will be stored.  Defaults to true.

- "Write Output Parameters" - Boolean.  If set to true, the solver statistics will be written to the relevant "Output" sublists (see Output Parameters).  Defaults to true.

- "Solver Options" - Sublist of general solver options.
   <ul>
   <li> "User Defined Pre/Post Operator" is supported.  See NOX::Parameter::PrePostOperator for more details.
   </ul>

<B>Output Paramters</B>

A sublist called "Output" will be created at the top level of the parameter list and contain the following general solver parameters:

- "Nonlinear Iterations" - Number of nonlinear iterations

- "2-Norm or Residual" - Two-norm of final residual

A sublist called "Output" will be created in the "Trust Region" sublist and contain the following trust region specific output parameters:

- "Number of Cauchy Steps" - Number of cauchy steps taken during the solve.

- "Number of Newton Steps" - Number of Newton steps taken during the solve.

- "Number of Dogleg Steps" - Number of Dogleg steps taken during the solve.

- "Number of Trust Region Inner Iterations" - Number of inner iterations
  required to adjust the trust region radius.

- "Dogleg Steps: Average Fraction of Newton Step Length" - Average value of the fraction a dogleg step took compared to the full Newton step.  The fractional value is computed as \f$ \mbox{frac} = \frac{\| d \|}{\| n\|} \f$.

- "Dogleg Steps: Average Fraction Between Cauchy and Newton Direction" -  Average value of the fraction a dogleg step took between the Cauchy and Newton directions.  This is the \f$ \gamma \f$ variable in the standard dogleg algorithm and the \f$ \tau \f$ parameter in the inexact dogleg algorithm.  A value of 0.0 is a full step in the Cauchy direction and a value of 1.0 is a full step in the Newton direction.

  \author Tammy Kolda (SNL 8950), Roger Pawlowski (SNL 9233)
*/

class InexactTrustRegionBased : public Generic {

public:

  /*!
    \brief Constructor

    See reset() for description.
  */
  InexactTrustRegionBased(
     const Teuchos::RCP<NOX::Abstract::Group>& grp,
     const Teuchos::RCP<NOX::StatusTest::Generic>& tests,
     const Teuchos::RCP<Teuchos::ParameterList>& params);

  //! Destructor
  virtual ~InexactTrustRegionBased();

  virtual void reset(const NOX::Abstract::Vector& initialGuess,
             const Teuchos::RCP<NOX::StatusTest::Generic>& tests);
  virtual void reset(const NOX::Abstract::Vector& initialGuess);
  virtual NOX::StatusTest::StatusType getStatus();
  virtual NOX::StatusTest::StatusType step();
  virtual NOX::StatusTest::StatusType solve();
  virtual const NOX::Abstract::Group& getSolutionGroup() const;
  virtual const NOX::Abstract::Group& getPreviousSolutionGroup() const;
  virtual int getNumIterations() const;
  virtual const Teuchos::ParameterList& getList() const;

  inline virtual Teuchos::RCP< const NOX::Abstract::Group > getSolutionGroupPtr() const {return solnPtr;};
  inline virtual Teuchos::RCP< const NOX::Abstract::Group > getPreviousSolutionGroupPtr() const {return oldSolnPtr;};
  inline virtual Teuchos::RCP< const Teuchos::ParameterList > getListPtr() const {return paramsPtr;};

protected:

  //! "Standard" trust region implementation
  virtual NOX::StatusTest::StatusType iterateStandard();
  //! "Inexact Trust Region"
  virtual NOX::StatusTest::StatusType iterateInexact();

  //! Print out initialization information and calcuation the RHS.
  virtual void init();

  //! Prints the current iteration information.
  virtual void printUpdate();

  //! Print an error message and throw an error during parameter reads
  virtual void invalid(const std::string& param, double value) const;

  //! Print an error message and throw an error
  virtual void throwError(const std::string& method, const std::string& mesage) const;

  //! Resets the counters in the solver.
  virtual void resetCounters();

  //! Check to see if the current step is acceptable.  If not, it reduces the trust region radius accordingly.
  NOX::StatusTest::StatusType checkStep(const NOX::Abstract::Vector& step,
                    double& radius);

  //! Computes the norm of a given vector.
  /*! Defaults to the L-2 norm but could use a user defined norm also. */
  virtual double computeNorm(const NOX::Abstract::Vector& v);

protected:

  //! Type of Trust Region algorithm to use.
  enum TrustRegionType {
    //! Basic trust region method for nonlinear systems (Nocedal and Wright?).
    Standard,
    //! Inexact Trust region WITHOUT minimization of the local linear model over the line segments.
    Inexact
  };

  //! Type of trust region algorithm to use.
  TrustRegionType method;

  //! Return types for inner iteration status test
  enum InnerIterationReturnType {
    //! Converged.
    Converged,
    //! Unconverged.
    Unconverged,
    //! Failed by hitting minimum radius bound.
    Failed
  };

  //! Pointer to the global data object.
  Teuchos::RCP<NOX::GlobalData> globalDataPtr;

  //! Utils
  Teuchos::RCP<NOX::Utils> utils;

  //! Current status of the trust region inner iteration.
  InnerIterationReturnType innerIterationStatus;

  //! Current solution.
  Teuchos::RCP<NOX::Abstract::Group> solnPtr;

  //! Previous solution pointer.
  Teuchos::RCP<NOX::Abstract::Group> oldSolnPtr;

  //! Current newton direction pointer.
  Teuchos::RCP<NOX::Abstract::Vector> newtonVecPtr;

  //! Current cauchy direction pointer.
  Teuchos::RCP<NOX::Abstract::Vector> cauchyVecPtr;

  //! Extra vector used in computations
  Teuchos::RCP<NOX::Abstract::Vector> rCauchyVecPtr;

  //! Extra vector used in computations
  Teuchos::RCP<NOX::Abstract::Vector> residualVecPtr;

  //! Extra vector used in computations
  Teuchos::RCP<NOX::Abstract::Vector> aVecPtr;

  //! Extra vector used in computations
  Teuchos::RCP<NOX::Abstract::Vector> bVecPtr;

  //! Stopping test.
  Teuchos::RCP<NOX::StatusTest::Generic> testPtr;

  //! Input parameters.
  Teuchos::RCP<Teuchos::ParameterList> paramsPtr;

  //! Inexact Newton utitilities.
  NOX::Direction::Utils::InexactNewton inNewtonUtils;

  //! %Newton %Search %Direction.
  Teuchos::RCP<NOX::Direction::Generic> newtonPtr;

  //! Cauchy %Search %Direction.
  Teuchos::RCP<NOX::Direction::Generic> cauchyPtr;

  //! Radius of the trust region
  double radius;

  //! Minimum improvement ratio to accept step
  double minRatio;

  //! Minimum trust region radius
  double minRadius;

  //! Maximum trust region radius
  double maxRadius;

  //! ratio < alpha triggers contraction
  double contractTriggerRatio;

  //! ratio > beta triggers expansion
  double expandTriggerRatio;

  //! Expansion factor
  double expandFactor;

  //! Constraction factor
  double contractFactor;

  //! Take a step of this length in the Newton direction if the
  //! trust-region search fails
  double recoveryStep;

  //! Value of \f$ f \f$ at current solution
  double newF;
  //! Value of \f$ f \f$ at previous solution
  double oldF;

  //! norm(xnew - xold)
  double dx;

  //! Number of nonlinear iterations.
  int nIter;

  //! Current linear solve tolerance (inexact only).
  double eta;

  //! Linear solve tolerance used in last iteration (inexact only).
  double eta_last;

  //! %Status of nonlinear solver.
  NOX::StatusTest::StatusType status;

  //! Type of check to use for status tests.  See NOX::StatusTest for more details.
  NOX::StatusTest::CheckType checkType;

  //! Enumerated list for each direction that may be required in the Trust region computation.
  enum StepType
  {
    //! Use the Newton direction
    Newton,
    //! Use the Cauchy direction
    Cauchy,
    //! Use the doglog direction
    Dogleg
  };

  //! Type of step to be taken.
  StepType stepType;

  //! Stores merit function supplied by global data.
  Teuchos::RCP<NOX::MeritFunction::Generic> meritFuncPtr;

  //! If set to true, the initial guess for the Newton direction computation will use the Cauchy direction as the initial guess.
  bool useCauchyInNewtonDirection;

  //! If set to true, statistics/counters will be output to the output list
  bool writeOutputParamsToList;

  //! If set to true, counters will be stored by the solver.
  bool useCounters;

  //! Counter for the number of cauchy steps taken.
  int numCauchySteps;

  //! Counter for the number of Newton steps taken.
  int numNewtonSteps;

  //! Counter for the number of Dogleg steps taken.
  int numDoglegSteps;

  //! Number of inner iterations required to adjust the trust region radius.
  int numTrustRegionInnerIterations;

  //! Hold the sum of the value of the fraction a dogleg step took between the Cauchy and Newton directions.  This is the \f$ \gamma \f$ variable in the standard dogleg algorithm and the \f$ \tau \f$ parameter in the inexact dogleg algorithm.  A value of 0.0 is a full step in the Cauchy direction and a value of 1.0 is a full step in the Newton direction.
  double sumDoglegFracCauchyToNewton;

  //! Holds the sum of the values of the fraction a dogleg step took compared to the full Newton step.  The fractional value is computed as \f$ \mbox{frac} = \frac{\| d \|}{\| n\|} \f$.
  double sumDoglegFracNewtonLength;

  //! If set to true, the minimum improvement ratio condition uses an Ared/Pred approach.
  bool useAredPredRatio;

  //! If set to true, the \f$ \tau \f$ parameter is minimized over the dogleg line segments instead of being computed at the trust regioin radius.
  bool useDoglegMinimization;

  //! Pointer to a user defined NOX::Abstract::PrePostOperator object.
  NOX::Solver::PrePostOperator prePostOperator;

};
} // namespace Solver
} // namespace NOX

#endif