ROL
ROL_GoldenSection.hpp
Go to the documentation of this file.
1// @HEADER
2// ************************************************************************
3//
4// Rapid Optimization Library (ROL) Package
5// Copyright (2014) Sandia Corporation
6//
7// Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
8// license for use of this work by or on behalf of the U.S. Government.
9//
10// Redistribution and use in source and binary forms, with or without
11// modification, are permitted provided that the following conditions are
12// met:
13//
14// 1. Redistributions of source code must retain the above copyright
15// notice, this list of conditions and the following disclaimer.
16//
17// 2. Redistributions in binary form must reproduce the above copyright
18// notice, this list of conditions and the following disclaimer in the
19// documentation and/or other materials provided with the distribution.
20//
21// 3. Neither the name of the Corporation nor the names of the
22// contributors may be used to endorse or promote products derived from
23// this software without specific prior written permission.
24//
25// THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
26// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
28// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
29// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
30// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
31// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
32// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
33// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
34// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
35// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36//
37// Questions? Contact lead developers:
38// Drew Kouri (dpkouri@sandia.gov) and
39// Denis Ridzal (dridzal@sandia.gov)
40//
41// ************************************************************************
42// @HEADER
43
44#ifndef ROL_GOLDENSECTION_H
45#define ROL_GOLDENSECTION_H
46
51#include "ROL_LineSearch.hpp"
52#include "ROL_BackTracking.hpp"
53
54namespace ROL {
55
56template<class Real>
57class GoldenSection : public LineSearch<Real> {
58private:
59 Real tol_;
60 ROL::Ptr<Vector<Real> > xnew_;
61 ROL::Ptr<LineSearch<Real> > btls_;
62
63public:
64
65 virtual ~GoldenSection() {}
66
67 // Constructor
68 GoldenSection( ROL::ParameterList &parlist ) : LineSearch<Real>(parlist) {
69 Real oem8(1.e-8);
70 tol_ = parlist.sublist("Step").sublist("Line Search").sublist("Line-Search Method").get("Bracketing Tolerance",oem8);
71 btls_ = ROL::makePtr<BackTracking<Real>>(parlist);
72 }
73
74 void initialize( const Vector<Real> &x, const Vector<Real> &s, const Vector<Real> &g,
76 LineSearch<Real>::initialize(x,s,g,obj,con);
77 xnew_ = x.clone();
78 btls_->initialize(x,s,g,obj,con);
79 }
80
81 void run( Real &alpha, Real &fval, int &ls_neval, int &ls_ngrad,
82 const Real &gs, const Vector<Real> &s, const Vector<Real> &x,
84 Real tol = std::sqrt(ROL_EPSILON<Real>()), zero(0), one(1), two(2), five(5);
85 ls_neval = 0;
86 ls_ngrad = 0;
87 // Get initial line search parameter
88 alpha = LineSearch<Real>::getInitialAlpha(ls_neval,ls_ngrad,fval,gs,x,s,obj,con);
89
90 // Reciprocal of golden ratio
91 Real c = two/(one+sqrt(five));
92
93 // Compute value phi(0)
94 Real tl = zero;
95 Real val_tl = fval;
96
97 // Compute value phi(alpha)
98 Real tr = alpha;
100 obj.update(*xnew_);
101 Real val_tr = obj.value(*xnew_,tol);
102 ls_neval++;
103
104 // Check if phi(alpha) < phi(0)
105 if ( val_tr < val_tl ) {
106 if ( LineSearch<Real>::status(LINESEARCH_GOLDENSECTION,ls_neval,ls_ngrad,tr,fval,gs,val_tr,x,s,obj,con) ) {
107 alpha = tr;
108 fval = val_tr;
109 return;
110 }
111 }
112
113 // Compute min( phi(0), phi(alpha) )
114 Real t = zero;
115 Real val_t = zero;
116 if ( val_tl < val_tr ) {
117 t = tl;
118 val_t = val_tl;
119 }
120 else {
121 t = tr;
122 val_t = val_tr;
123 }
124
125 // Compute value phi(t1)
126 Real tc1 = c*tl + (one-c)*tr;
128 obj.update(*xnew_);
129 Real val_tc1 = obj.value(*xnew_,tol);
130 ls_neval++;
131
132 // Compute value phi(t2)
133 Real tc2 = (one-c)*tl + c*tr;
135 obj.update(*xnew_);
136 Real val_tc2 = obj.value(*xnew_,tol);
137 ls_neval++;
138
139 // Compute min( phi(0), phi(t1), phi(t2), phi(alpha) )
140 if ( val_tl <= val_tc1 && val_tl <= val_tc2 && val_tl <= val_tr ) {
141 val_t = val_tl;
142 t = tl;
143 }
144 else if ( val_tc1 <= val_tl && val_tc1 <= val_tc2 && val_tc1 <= val_tr ) {
145 val_t = val_tc1;
146 t = tc1;
147 }
148 else if ( val_tc2 <= val_tl && val_tc2 <= val_tc1 && val_tc2 <= val_tr ) {
149 val_t = val_tc2;
150 t = tc2;
151 }
152 else {
153 val_t = val_tr;
154 t = tr;
155 }
156
157 while ( !LineSearch<Real>::status(LINESEARCH_GOLDENSECTION,ls_neval,ls_ngrad,t,fval,gs,val_t,x,s,obj,con)
158 && (std::abs(tl-tr) >= tol_) ) {
159 if ( val_tc1 > val_tc2 ) {
160 tl = tc1;
161 val_tl = val_tc1;
162 tc1 = tc2;
163 val_tc1 = val_tc2;
164
165 tc2 = (one-c)*tl + c*tr;
167 obj.update(*xnew_);
168 val_tc2 = obj.value(*xnew_,tol);
169 ls_neval++;
170 }
171 else {
172 tr = tc2;
173 val_tr = val_tc2;
174 tc2 = tc1;
175 val_tc2 = val_tc1;
176
177 tc1 = c*tl + (one-c)*tr;
179 obj.update(*xnew_);
180 val_tc1 = obj.value(*xnew_,tol);
181 ls_neval++;
182 }
183
184 if ( val_tl <= val_tc1 && val_tl <= val_tc2 && val_tl <= val_tr ) {
185 val_t = val_tl;
186 t = tl;
187 }
188 else if ( val_tc1 <= val_tl && val_tc1 <= val_tc2 && val_tc1 <= val_tr ) {
189 val_t = val_tc1;
190 t = tc1;
191 }
192 else if ( val_tc2 <= val_tl && val_tc2 <= val_tc1 && val_tc2 <= val_tr ) {
193 val_t = val_tc2;
194 t = tc2;
195 }
196 else {
197 val_t = val_tr;
198 t = tr;
199 }
200 }
201 alpha = t;
202 fval = val_t;
203
204 if ( alpha < ROL_EPSILON<Real>() ) {
205 btls_->run(alpha,fval,ls_neval,ls_ngrad,gs,s,x,obj,con);
206 }
207 }
208};
209
210}
211
212#endif
Objective_SerialSimOpt(const Ptr< Obj > &obj, const V &ui) z0 zero)()
Provides the interface to apply upper and lower bound constraints.
Implements a golden section line search.
void initialize(const Vector< Real > &x, const Vector< Real > &s, const Vector< Real > &g, Objective< Real > &obj, BoundConstraint< Real > &con)
GoldenSection(ROL::ParameterList &parlist)
ROL::Ptr< LineSearch< Real > > btls_
ROL::Ptr< Vector< Real > > xnew_
void run(Real &alpha, Real &fval, int &ls_neval, int &ls_ngrad, const Real &gs, const Vector< Real > &s, const Vector< Real > &x, Objective< Real > &obj, BoundConstraint< Real > &con)
Provides interface for and implements line searches.
void updateIterate(Vector< Real > &xnew, const Vector< Real > &x, const Vector< Real > &s, Real alpha, BoundConstraint< Real > &con)
virtual void initialize(const Vector< Real > &x, const Vector< Real > &s, const Vector< Real > &g, Objective< Real > &obj, BoundConstraint< Real > &con)
virtual Real getInitialAlpha(int &ls_neval, int &ls_ngrad, const Real fval, const Real gs, const Vector< Real > &x, const Vector< Real > &s, Objective< Real > &obj, BoundConstraint< Real > &con)
Provides the interface to evaluate objective functions.
virtual Real value(const Vector< Real > &x, Real &tol)=0
Compute value.
virtual void update(const Vector< Real > &x, UpdateType type, int iter=-1)
Update objective function.
Defines the linear algebra or vector space interface.
virtual ROL::Ptr< Vector > clone() const =0
Clone to make a new (uninitialized) vector.
@ LINESEARCH_GOLDENSECTION