Debian Codegraph @

packages/rol/example/PDE-OPT/published/TRSPG_Kouri2021/dualksvm/example_01.cpp

raw
1 // @HEADER
2 // *****************************************************************************
3 // Rapid Optimization Library (ROL) Package
4 //
5 // Copyright 2014 NTESS and the ROL contributors.
6 // SPDX-License-Identifier: BSD-3-Clause
7 // *****************************************************************************
8 // @HEADER
9
10 /*! \file example_01.cpp
11 \brief Shows how to minimize a function with binary (0/1) constraints.
12 */
13
14 #include "ROL_Solver.hpp"
15 #include "ROL_Bounds.hpp"
16 #include "ROL_StdObjective.hpp"
17 #include "ROL_StdConstraint.hpp"
18 #include "ROL_ScaledStdVector.hpp"
19 #include "ROL_Stream.hpp"
20 #include "ROL_LinearAlgebra.hpp"
21 #include "ROL_BLAS.hpp"
22
23 #include "Teuchos_Time.hpp"
24 #include "Teuchos_GlobalMPISession.hpp"
25 #include "Teuchos_XMLParameterListHelpers.hpp"
26
27 #include <iostream>
28 #include <fstream>
29 #include <random>
30
31 typedef double RealT;
32
33 template<class Real>
34 class DualSVMObjective : public ROL::StdObjective<Real> {
35 private:
36 const ROL::Ptr<ROL::BLAS<int,Real>> blas_;
37 ROL::LA::Matrix<Real> K_;
38 std::vector<Real> Kx_;
39 const int nrows_;
40 Real alpha_, kappa_;
41 int fval_, grad_, hess_;
42 bool computeKx_;
43
44 Real kernel(const std::vector<Real> &x, const std::vector<Real> &y) const {
45 typename std::vector<Real>::size_type size = x.size();
46 assert(size==y.size());
47 Real val = blas_->DOT(size,&x[0],1,&y[0],1);
48 return std::tanh(kappa_ * val + alpha_);
49 }
50
51 void computeKx(const std::vector<Real> &x) {
52 if (computeKx_) {
53 const Real zero(0), one(1);
54 blas_->SYMM(Teuchos::LEFT_SIDE,Teuchos::UPPER_TRI,nrows_,1,one,K_.values(),nrows_,&x[0],nrows_,zero,&Kx_[0],nrows_);
55 computeKx_ = false;
56 }
57 }
58
59 public:
60 DualSVMObjective(const std::vector<std::vector<Real>> &X, const std::vector<Real> &y,
61 Real alpha = -1.0, Real kappa = 1.0)
62 : blas_(ROL::makePtr<ROL::BLAS<int,Real>>()),
63 nrows_(X.size()), alpha_(alpha), kappa_(kappa),
64 fval_(0), grad_(0), hess_(0), computeKx_(true) {
65 Kx_.resize(nrows_);
66 K_.reshape(nrows_,nrows_);
67 for (int i = 0; i < nrows_; ++i) {
68 for (int j = i; j < nrows_; ++j) {
69 K_(i,j) = y[i]*y[j]*kernel(X[i],X[j]);
70 }
71 }
72 }
73
74 void summarize(std::ostream &stream) const {
75 stream << std::endl;
76 stream << std::string(114,'=') << std::endl;
77 stream << " DualSVMObjective::summarize" << std::endl;
78 stream << " Number of calls to value: " << fval_ << std::endl;
79 stream << " Number of calls to gradient: " << grad_ << std::endl;
80 stream << " Number of calls to hessVec: " << hess_ << std::endl;
81 stream << std::string(114,'=') << std::endl;
82 stream << std::endl;
83 }
84
85 void reset(void) {
86 fval_ = 0; grad_ = 0; hess_ = 0;
87 }
88
89 void update(const std::vector<Real> &x, ROL::UpdateType type, int iter = -1) {
90 if (type != ROL::UpdateType::Revert && type != ROL::UpdateType::Accept)
91 computeKx_ = true;
92 }
93
94 Real value(const std::vector<Real> &x, Real &tol) {
95 fval_++;
96 computeKx(x);
97 Real val = static_cast<Real>(0.5)*blas_->DOT(nrows_,&Kx_[0],1,&x[0],1);
98 for (const auto v : x) val -= v;
99 return val;
100 }
101
102 void gradient(std::vector<Real> &g, const std::vector<Real> &x, Real &tol) {
103 grad_++;
104 const Real one(1);
105 g.assign(nrows_,-one);
106 computeKx(x);
107 blas_->AXPY(nrows_,one,&Kx_[0],1,&g[0],1);
108 }
109
110 void hessVec(std::vector<Real> &hv, const std::vector<Real> &v, const std::vector<Real> &x, Real &tol) {
111 hess_++;
112 const Real zero(0), one(1);
113 blas_->SYMM(Teuchos::LEFT_SIDE,Teuchos::UPPER_TRI,nrows_,1,one,K_.values(),nrows_,&v[0],nrows_,zero,&hv[0],nrows_);
114 }
115
116 };
117
118 template<typename Real>
119 class DualSVMConstraint : public ROL::StdConstraint<Real> {
120 private:
121 const ROL::Ptr<ROL::BLAS<int,Real>> blas_;
122 const std::vector<Real> y_;
123 const int size_;
124
125 public:
126 DualSVMConstraint(const std::vector<Real> &y)
127 : blas_(ROL::makePtr<ROL::BLAS<int,Real>>()),
128 y_(y), size_(y.size()) {}
129
130 void value(std::vector<Real> &c, const std::vector<Real> &x, Real &tol) {
131 c[0] = blas_->DOT(size_,&y_[0],1,&x[0],1);
132 }
133
134 void applyJacobian(std::vector<Real> &jv, const std::vector<Real> &v, const std::vector<Real> &x, Real &tol) {
135 jv[0] = blas_->DOT(size_,&y_[0],1,&v[0],1);
136 }
137
138 void applyAdjointJacobian(std::vector<Real> &ajv, const std::vector<Real> &v, const std::vector<Real> &x, Real &tol) {
139 ajv.assign(y_.begin(),y_.end());
140 blas_->SCAL(size_,v[0],&ajv[0],1);
141 }
142
143 void applyAdjointHessian(std::vector<Real> &ahuv, const std::vector<Real> &u, const std::vector<Real> &v, const std::vector<Real> &x, Real &tol) {
144 ahuv.assign(size_,static_cast<Real>(0));
145 }
146 };
147
148 int main(int argc, char *argv[]) {
149 Teuchos::GlobalMPISession mpiSession(&argc, &argv);
150
151 // This little trick lets us print to std::cout only if a (dummy) command-line argument is provided.
152 int iprint = argc - 1;
153 ROL::Ptr<std::ostream> outStream;
154 ROL::nullstream bhs; // outputs nothing
155 if (iprint > 0)
156 outStream = ROL::makePtrFromRef(std::cout);
157 else
158 outStream = ROL::makePtrFromRef(bhs);
159
160 int errorFlag = 0;
161
162 // *** Example body.
163
164 try {
165
166 /*** Read in XML input ***/
167 std::string filename = "input.xml";
168 Teuchos::RCP<Teuchos::ParameterList> parlist = Teuchos::rcp( new Teuchos::ParameterList() );
169 Teuchos::updateParametersFromXmlFile( filename, parlist.ptr() );
170
171 // Set up problem data
172 bool useRandomProblem = false;
173 int nInstances, nVars;
174 std::vector<std::vector<RealT>> X;
175 std::vector<RealT> y;
176 if (useRandomProblem) {
177 unsigned seed = 111;
178 nInstances = 5e3;
179 nVars = 1e4;
180 std::default_random_engine generator(seed);
181 std::normal_distribution<RealT> dist(0.0,1.0);
182 X.resize(nInstances);
183 y.resize(nInstances,0.0);
184 for (int i = 0; i < nInstances; ++i) {
185 for (int j = 0; j < nVars; ++j) X[i].push_back(dist(generator));
186 }
187 std::vector<RealT> w(nVars);
188 for (int j = 0; j < nVars; ++j) w[j] = dist(generator);
189 RealT yval(0);
190 for (int i = 0; i < nInstances; ++i) {
191 yval = dist(generator);
192 for (int j = 0; j < nVars; ++j) yval += X[i][j]*w[j];
193 y[i] = (yval < static_cast<RealT>(0) ? static_cast<RealT>(-1)
194 : (yval > static_cast<RealT>(0) ? static_cast<RealT>(1)
195 : static_cast<RealT>(0)));
196 }
197 }
198 else {
199 std::ifstream fileD, fileX, fileY;
200 fileD.open("info.txt");
201 fileX.open("data_matrix.txt");
202 fileY.open("label_vector.txt");
203 fileD >> nInstances;
204 fileD >> nVars;
205 X.resize(nInstances);
206 y.resize(nInstances,0.0);
207 for (int i = 0; i < nInstances; ++i) {
208 fileY >> y[i];
209 X[i].resize(nVars);
210 for (int j = 0; j < nVars; ++j) fileX >> X[i][j];
211 }
212 fileD.close();
213 fileX.close();
214 fileY.close();
215 }
216
217 RealT alpha(-0.1), kappa(1.0/static_cast<RealT>(nInstances));
218 bool useScaledVectors = false;
219 ROL::Ptr<ROL::StdVector<RealT>> x, l, u;
220 if (useScaledVectors) {
221 ROL::Ptr<std::vector<RealT>> x_ptr, w_ptr, l_ptr, u_ptr;
222 x_ptr = ROL::makePtr<std::vector<RealT>>(nInstances,0.0);
223 w_ptr = ROL::makePtr<std::vector<RealT>>(nInstances,1.0);
224 l_ptr = ROL::makePtr<std::vector<RealT>>(nInstances,0.0);
225 u_ptr = ROL::makePtr<std::vector<RealT>>(nInstances,1.0);
226 x = ROL::makePtr<ROL::PrimalScaledStdVector<RealT>>(x_ptr,w_ptr);
227 l = ROL::makePtr<ROL::PrimalScaledStdVector<RealT>>(l_ptr,w_ptr);
228 u = ROL::makePtr<ROL::PrimalScaledStdVector<RealT>>(u_ptr,w_ptr);
229 }
230 else {
231 x = ROL::makePtr<ROL::StdVector<RealT>>(nInstances,0.0);
232 l = ROL::makePtr<ROL::StdVector<RealT>>(nInstances,0.0);
233 u = ROL::makePtr<ROL::StdVector<RealT>>(nInstances,1.0);
234 }
235 ROL::Ptr<DualSVMObjective<RealT>> obj = ROL::makePtr<DualSVMObjective<RealT>>(X,y,alpha,kappa);
236 ROL::Ptr<DualSVMConstraint<RealT>> con = ROL::makePtr<DualSVMConstraint<RealT>>(y);
237 ROL::Ptr<ROL::StdVector<RealT>> mul = ROL::makePtr<ROL::StdVector<RealT>>(1,0);
238 ROL::Ptr<ROL::Bounds<RealT>> bnd = ROL::makePtr<ROL::Bounds<RealT>>(l,u);
239 ROL::Ptr<ROL::Problem<RealT>> prob = ROL::makePtr<ROL::Problem<RealT>>(obj,x);
240 prob->addBoundConstraint(bnd);
241 prob->addLinearConstraint("Dual SVM",con,mul);
242 prob->setProjectionAlgorithm(*parlist);
243 prob->finalize(false,true,*outStream);
244 prob->check(true,*outStream);
245
246 ROL::Ptr<ROL::Solver<RealT>> solver;
247 std::vector<RealT> vals(6);
248
249 // SPG
250 obj->reset();
251 x->zero();
252 parlist->sublist("Step").set("Type","Spectral Gradient");
253 Teuchos::Time spgTimer("SPG Time", true);
254 solver = ROL::makePtr<ROL::Solver<RealT>>(prob,*parlist);
255 solver->solve(*outStream);
256 spgTimer.stop();
257 *outStream << "Total optimization time = " << spgTimer.totalElapsedTime() << " seconds.\n";
258 obj->summarize(*outStream);
259 vals[0] = solver->getAlgorithmState()->value;
260
261 // PQN
262 obj->reset();
263 x->zero();
264 parlist->sublist("Step").set("Type","Line Search");
265 parlist->sublist("Step").sublist("Line Search").sublist("Descent Method").set("Type","Quasi-Newton Method");
266 Teuchos::Time pqnTimer("PQN Time", true);
267 solver = ROL::makePtr<ROL::Solver<RealT>>(prob,*parlist);
268 solver->solve(*outStream);
269 pqnTimer.stop();
270 *outStream << "Total optimization time = " << pqnTimer.totalElapsedTime() << " seconds.\n";
271 obj->summarize(*outStream);
272 vals[1] = solver->getAlgorithmState()->value;
273
274 // LMTR
275 obj->reset();
276 x->zero();
277 parlist->sublist("Step").set("Type","Trust Region");
278 parlist->sublist("Step").sublist("Trust Region").set("Subproblem Model","Lin-More");
279 Teuchos::Time lmtrTimer("LMTR Time", true);
280 solver = ROL::makePtr<ROL::Solver<RealT>>(prob,*parlist);
281 solver->solve(*outStream);
282 lmtrTimer.stop();
283 *outStream << "Total optimization time = " << lmtrTimer.totalElapsedTime() << " seconds.\n";
284 obj->summarize(*outStream);
285 vals[2] = solver->getAlgorithmState()->value;
286
287 // TRSPG
288 obj->reset();
289 x->zero();
290 parlist->sublist("Step").set("Type","Trust Region");
291 parlist->sublist("Step").sublist("Trust Region").set("Subproblem Model","SPG");
292 Teuchos::Time trspgTimer("TRSPG Time", true);
293 solver = ROL::makePtr<ROL::Solver<RealT>>(prob,*parlist);
294 solver->solve(*outStream);
295 trspgTimer.stop();
296 *outStream << "Total optimization time = " << trspgTimer.totalElapsedTime() << " seconds.\n";
297 obj->summarize(*outStream);
298 vals[3] = solver->getAlgorithmState()->value;
299
300 // AL-LMTR
301 obj->reset();
302 x->zero();
303 mul->zero();
304 prob->edit();
305 prob->finalize(true,true,*outStream);
306 parlist->sublist("Step").set("Type","Augmented Lagrangian");
307 parlist->sublist("Step").sublist("Augmented Lagrangian").set("Subproblem Step Type","Trust Region");
308 parlist->sublist("Step").sublist("Trust Region").set("Subproblem Model","Lin-More");
309 Teuchos::Time allmtrTimer("AL-LMTR Time", true);
310 solver = ROL::makePtr<ROL::Solver<RealT>>(prob,*parlist);
311 solver->solve(*outStream);
312 allmtrTimer.stop();
313 *outStream << "Total optimization time = " << allmtrTimer.totalElapsedTime() << " seconds.\n";
314 obj->summarize(*outStream);
315 vals[4] = solver->getAlgorithmState()->value;
316
317 // AL-LMTR
318 obj->reset();
319 x->zero();
320 mul->zero();
321 parlist->sublist("Step").set("Type","Augmented Lagrangian");
322 parlist->sublist("Step").sublist("Augmented Lagrangian").set("Subproblem Step Type","Trust Region");
323 parlist->sublist("Step").sublist("Trust Region").set("Subproblem Model","SPG");
324 Teuchos::Time altrspgTimer("AL-TRSPG Time", true);
325 solver = ROL::makePtr<ROL::Solver<RealT>>(prob,*parlist);
326 solver->solve(*outStream);
327 altrspgTimer.stop();
328 *outStream << "Total optimization time = " << altrspgTimer.totalElapsedTime() << " seconds.\n";
329
330 int cnt(0);
331 for (int i = 0; i < nInstances; ++i) {
332 if ((*x->getVector())[i] >= static_cast<RealT>(1e-4)) cnt++;
333 }
334 *outStream << std::endl << "Number of Support Vectors: " << cnt << std::endl << std::endl;
335 obj->summarize(*outStream);
336 vals[5] = solver->getAlgorithmState()->value;
337
338 RealT minval = std::min(vals[0],std::min(vals[1],std::min(vals[2],vals[3])));
339 *outStream << std::scientific << std::setprecision(16);
340 *outStream << "SPG " << (vals[0]-minval)/minval << std::endl;
341 *outStream << "PQN " << (vals[1]-minval)/minval << std::endl;
342 *outStream << "LMTR " << (vals[2]-minval)/minval << std::endl;
343 *outStream << "TRSPG " << (vals[3]-minval)/minval << std::endl;
344 *outStream << "AL-LMTR " << (vals[4]-minval)/minval << std::endl;
345 *outStream << "AL-TRSPG " << (vals[5]-minval)/minval << std::endl;
346 *outStream << std::endl;
347
348 }
349 catch (std::logic_error& err) {
350 *outStream << err.what() << "\n";
351 errorFlag = -1000;
352 }; // end try
353
354 if (errorFlag != 0)
355 std::cout << "End Result: TEST FAILED\n";
356 else
357 std::cout << "End Result: TEST PASSED\n";
358
359 return 0;
360
361 }
362
363