QuadraticProgram.h
Go to the documentation of this file.
1 //===========================================================================
2 /*!
3  *
4  *
5  * \brief Quadratic programming for Support Vector Machines
6  *
7  *
8  * \par
9  * This file provides a number of classes representing hugh dense
10  * matrices all related to kernel Gram matices of possibly large
11  * datasets. These classes share a common interface for
12  * (a) providing a matrix entry,
13  * (b) swapping two variable indices, and
14  * (c) returning the matrix size.
15  *
16  * \par
17  * This interface is required by the template class CachedMatrix,
18  * which provides a cache mechanism for restricted matrix rows, as it
19  * is used by various quadratic program solvers within the library.
20  * The PrecomputedMatrix provides a sometimes faster but more memory
21  * intensive alternative to CachedMatrix.
22  *
23  *
24  *
25  *
26  * \author T. Glasmachers
27  * \date 2007-2012
28  *
29  *
30  * \par Copyright 1995-2017 Shark Development Team
31  *
32  * <BR><HR>
33  * This file is part of Shark.
34  * <http://shark-ml.org/>
35  *
36  * Shark is free software: you can redistribute it and/or modify
37  * it under the terms of the GNU Lesser General Public License as published
38  * by the Free Software Foundation, either version 3 of the License, or
39  * (at your option) any later version.
40  *
41  * Shark is distributed in the hope that it will be useful,
42  * but WITHOUT ANY WARRANTY; without even the implied warranty of
43  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
44  * GNU Lesser General Public License for more details.
45  *
46  * You should have received a copy of the GNU Lesser General Public License
47  * along with Shark. If not, see <http://www.gnu.org/licenses/>.
48  *
49  */
50 //===========================================================================
51 
52 
53 #ifndef SHARK_ALGORITHMS_QP_QUADRATICPROGRAM_H
54 #define SHARK_ALGORITHMS_QP_QUADRATICPROGRAM_H
55 
56 #include <cmath>
57 
58 
59 namespace shark {
60 
61 /// reason for the quadratic programming solver
62 /// to stop the iterative optimization process
63 enum QpStopType
64 {
65  QpNone = 0,
66  QpAccuracyReached = 1,
67  QpMaxIterationsReached = 4,
68  QpTimeout = 8,
69 };
70 
71 
72 ///
73 /// \brief stopping conditions for quadratic programming
74 ///
75 /// \par
76 /// The QpStoppingCondition structure defines conditions
77 /// for stopping the optimization procedure.
78 ///
79 //! \par
80 //! For practical considerations the solvers supports
81 //! several stopping conditions. Usually, the optimization
82 //! stops if the Karush-Kuhn-Tucker (KKT) condition for
83 //! optimality are satisfied up to a certain accuracy.
84 //! In the case the optimal function value is known a
85 //! priori it is possible to stop as soon as the objective
86 //! is above a given threshold. In both cases it is very
87 //! difficult to predict the runtime. Therefore the
88 //! solver can stop after a predefined number of
89 //! iterations or after a predefined time period. In
90 //! these cases the solution found will not be near
91 //! optimal. In SVM training, using sensitive settings,
92 //! this should happen only during model selection while
93 //! investigating hyperparameters with poor
94 //! generalization ability.
95 //!
96 struct QpStoppingCondition
97 {
98  /// Constructor
99  QpStoppingCondition(double accuracy = 0.001, unsigned long long iterations = 0xffffffff, double value = 1e100, double seconds = 1e100)
100  {
101  minAccuracy = accuracy;
102  maxIterations = iterations;
103  targetValue = value;
104  maxSeconds = seconds;
105  }
106 
107  /// minimum accuracy to be achieved, usually KKT violation
108  double minAccuracy;
109 
110  /// maximum number of decomposition iterations (default to 0 - not used)
111  unsigned long long maxIterations;
112 
113  /// target objective function value (defaults to 1e100 - not used)
114  double targetValue;
115 
116  /// maximum process time (defaults to 1e100 - not used)
117  double maxSeconds;
118 };
119 
120 
121 ///
122 /// \brief properties of the solution of a quadratic program
123 ///
124 /// \par
125 /// The QpSolutionProperties structure collects statistics
126 /// about the approximate solutions found in a solver run.
127 /// It reports the reason for the iterative solver to stop,
128 /// which was set according to the QpStoppingCondition
129 /// structure. Furthermore it reports the solution accuracy,
130 /// the number of iterations, time elapsed, and the value
131 /// of the objective function in the reported solution.
132 ///
133 struct QpSolutionProperties
134 {
135  QpSolutionProperties()
136  {
137  type = QpNone;
138  accuracy = 1e100;
139  iterations = 0;
140  value = 1e100;
141  seconds = 0.0;
142  }
143 
144  QpStopType type; ///< reason for the solver to stop
145  double accuracy; ///< typically the maximal KKT violation
146  unsigned long long iterations; ///< number of decomposition iterations
147  double value; ///< value of the objective function
148  double seconds; ///< training time
149 };
150 
151 }
152 #endif