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 * <https://shark-ml.github.io/Shark/>
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
59namespace shark {
60
61/// reason for the quadratic programming solver
62/// to stop the iterative optimization process
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//!
96struct 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///
133struct 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