ROL
ROL_Bisection.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_BISECTION_H
45#define ROL_BISECTION_H
46
51#include "ROL_LineSearch.hpp"
52#include "ROL_BackTracking.hpp"
53
54namespace ROL {
55
56template<class Real>
57class Bisection : public LineSearch<Real> {
58private:
59 Real tol_;
60 ROL::Ptr<Vector<Real> > xnew_;
61 ROL::Ptr<LineSearch<Real> > btls_;
62
63public:
64
65 virtual ~Bisection() {}
66
67 // Constructor
68 Bisection( 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>()), half(0.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 // Compute value phi(0)
91 Real tl(0);
92 Real val_tl = fval;
93
94 // Compute value phi(alpha)
95 Real tr = alpha;
97 obj.update(*xnew_);
98 Real val_tr = obj.value(*xnew_,tol);
99 ls_neval++;
100
101 // Check if phi(alpha) < phi(0)
102 if ( val_tr < val_tl ) {
103 if ( LineSearch<Real>::status(LINESEARCH_BISECTION,ls_neval,ls_ngrad,tr,fval,gs,val_tr,x,s,obj,con) ) {
104 alpha = tr;
105 fval = val_tr;
106 return;
107 }
108 }
109
110 // Get min( phi(0), phi(alpha) )
111 Real t(0);
112 Real val_t(0);
113 if ( val_tl < val_tr ) {
114 t = tl;
115 val_t = val_tl;
116 }
117 else {
118 t = tr;
119 val_t = val_tr;
120 }
121
122 // Compute value phi(midpoint)
123 Real tc = half*(tl+tr);
125 Real val_tc = obj.value(*xnew_,tol);
126 ls_neval++;
127
128 // Get min( phi(0), phi(alpha), phi(midpoint) )
129 if ( val_tc < val_t ) {
130 t = tc;
131 val_t = val_tc;
132 }
133
134 Real t1(0), val_t1(0);
135 Real t2(0), val_t2(0);
136
137 while ( !LineSearch<Real>::status(LINESEARCH_BISECTION,ls_neval,ls_ngrad,t,fval,gs,val_t,x,s,obj,con)
138 && std::abs(tr - tl) > tol_ ) {
139 t1 = half*(tl+tc);
141 obj.update(*xnew_);
142 val_t1 = obj.value(*xnew_,tol);
143 ls_neval++;
144
145 t2 = half*(tr+tc);
147 obj.update(*xnew_);
148 val_t2 = obj.value(*xnew_,tol);
149 ls_neval++;
150
151 if ( ( (val_tl <= val_tr) && (val_tl <= val_t1) && (val_tl <= val_t2) && (val_tl <= val_tc) )
152 || ( (val_t1 <= val_tr) && (val_t1 <= val_tl) && (val_t1 <= val_t2) && (val_t1 <= val_tc) ) ) {
153 if ( val_tl < val_t1 ) {
154 t = tl;
155 val_t = val_tl;
156 }
157 else {
158 t = t1;
159 val_t = val_t1;
160 }
161
162 tr = tc;
163 val_tr = val_tc;
164 tc = t1;
165 val_tc = val_t1;
166 }
167 else if ( ( (val_tc <= val_tr) && (val_tc <= val_tl) && (val_tc <= val_t1) && (val_tc <= val_t2) ) ) {
168 t = tc;
169 val_t = val_tc;
170
171 tl = t1;
172 val_tl = val_t1;
173 tr = t2;
174 val_tr = val_t2;
175 }
176 else if ( ( (val_t2 <= val_tr) && (val_t2 <= val_tl) && (val_t2 <= val_t1) && (val_t2 <= val_tc) )
177 || ( (val_tr <= val_tl) && (val_tr <= val_t1) && (val_tr <= val_t2) && (val_tr <= val_tc) ) ) {
178 if ( val_tr < val_t2 ) {
179 t = tr;
180 val_t = val_tr;
181 }
182 else {
183 t = t2;
184 val_t = val_t2;
185 }
186
187 tl = tc;
188 val_tl = val_tc;
189 tc = t2;
190 val_tc = val_t2;
191 }
192 }
193
194 fval = val_t;
195 alpha = t;
196
197 if ( alpha < ROL_EPSILON<Real>() ) {
198 btls_->run(alpha,fval,ls_neval,ls_ngrad,gs,s,x,obj,con);
199 }
200 }
201};
202
203}
204
205#endif
Implements a bisection line search.
ROL::Ptr< LineSearch< Real > > btls_
void initialize(const Vector< Real > &x, const Vector< Real > &s, const Vector< Real > &g, Objective< Real > &obj, BoundConstraint< Real > &con)
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)
Bisection(ROL::ParameterList &parlist)
virtual ~Bisection()
ROL::Ptr< Vector< Real > > xnew_
Provides the interface to apply upper and lower bound constraints.
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_BISECTION