Introduction

Known methods of transition from a primal problem to a dual one are based on qualitative transformations and are meaningful. Formalization and proof of the correctness of the algorithm for constructing a dual problem for an arbitrary form of representation of a primal problem will make it easy to obtain correct pairs of known dual problems. The relevance of research is due to the requirements for simplification of solutions of linear programming problems based on the development of a formal algorithm for the transformation of a primal problem to a dual linear optimization problem [1,6].

Quadratic programming is a area of mathematical programming devoted to the theory of solving problems characterized by a quadratic dependency between variables [2]. The usage of this method is relevant today, as the use of mathematical models is an important factor in improving the planning of the company. Mathematical representation of data allowed to create and model different options for choosing the optimal solution [3,9,11].

The paper considers the Support Vector Machine (SVM) method that is taught by examples and used to classify objects. It is established that SVM can be successfully used to control complex electromechanical systems, it can ensure the adaptability of control algorithms, perform the functions of an observer, an identifier of unknown parameters, a reference model, with its help you can control complex nonlinear objects, as well as objects with stochastic parameters [4,10,17].

The aim of the work is to solve a dual problem by SVM, the comparison with the primal problem and classification of the dataset.

Achieving this goal involves solving specific tasks:  determine the problem of the method of SVM for the dual problem;  compare dual SVM and primary;

 analyze this method;  apply it in practice.

The object of research is to solve a dual problem by the method of SVM. The purpose of the study is to apply the problems of linear and nonlinear programming to study the properties of the studied problems, to determine their advantages and disadvantages.

Methods

Mathematical programming is an applied mathematical discipline that investigates the extremum of a function (maximum or minimum search problems) and develops methods for solving them. Such problems are also called optimization [5,7].

The area of mathematical programming can be applied to the type of objective function and to the system of constraints. As a result, we obtain a division into:  Linear programming -objective function and constraint functions included in the constraint system are linear (first order equation).



Nonlinear programming -the objective function or one of the constraint functions included in the constraint system is nonlinear (higher order equations).



Integer (discrete) programming -if at least one variable has an integer constaint. Dynamic programming -if the parameters of the objective function and / or system of constraints change over time or the objective function has an additive / multiplicative form or the decisionmaking process itself is multi-step [8,12].

Depending on that all the information about the process is known in advance, the field of mathematical programming is divided into:  Stochastic programming -not all information about the process is known in advance: the parameters included in the objective function or in the constraint function are random or have to make decisions in conditions of risk.



Deterministic programming -all information about the process is known in advance. Depending on the number of objective functions, the tasks are divided into:  Single-criteria;  Multicriteria. The optimization problem can be classified as follows: those problems that describe the properties of the constraint system and, accordingly, others that are determined by the objective function:

 Unconditional optimization problems or problems without restrictions -they do not impose restrictions on quantitative variables.



Conditional optimization problems or constrained problems -in these problems, quantitative variables are constrained.



Optimization problems for incomplete data -they have a goal function or a system of constraints depend on some parameter p (numerical, vector), the value of which is completely undefined at the time of solving the problem. The first type includes optimization problems, the task of which is to minimize or maximize the quadratic function of several variables with linear constraints on these variables.

Quadratic programming problems include a special class of NP problems in which the objective function ) (x f is quadratic and concave (or convex), and all constraints are linear [13,15]. Each linear programming problem can be matched to another that relates in some way to the original task. Such problems are called dual, or conjugate. Joint consideration of dual pairs of problems is very important in the economic analysis of the optimal plan. The correspondence between the original and dual problems is to build a dual problem on the basis of the first problem (as the source can be considered any of the conjugate pair of problems). Dual problems are symmetric and asymmetric.

The quadratic programming includes the SVM method. He constructs a model in the form of points in space using a binary linear classifier. This model goes through a series of iterations in which new patterns are displayed in a given space and determine the side of the gap. On the basis of these data the forecast of belonging of samples to a certain category is made.

Observation and analysis of the existing methods and means

Each linear programming problem corresponds to a dual, formed by certain rules directly from the condition of the primal problem. Comparing these two formulated problems, we conclude that the dual linear programming problem is formed from a primal problem by the following rules:

1. Each constraint of a primal problem corresponds to a variable of a dual problem. The number of unknowns of a dual problem is equal to the number of constraints of the primal problem. 2. For the primary problem, a certain variable corresponds to the specified constraint of the double problem and, accordingly, their number determines the number of unknowns in the primary problem.

3. If the objective function of the primary problem goes to max, then the objective function of the double problem goes to min, and vice versa. 4. In the objective function of a double problem, the coefficients of the variables are free values of the system of constraints for the primary problem. 5. The column of free members of the double problem is the coefficients for the variables in the objective function of the primary problem. 6. The coefficients of variables in the system of constraints of the primary problem are written in the matrix and accordingly it is transposed to determine the coefficients of constraints for the double problem.

As a result of intensive research in the field of machine learning, aimed at improving the quality of classifiers, a new generation of methods appeared, in particular -SVM. This method refers to machine learning methods based on vector spatial models, the purpose of which is to find dividing surfaces between classes as far as possible from all points of the study population (perhaps ignoring some points such as emissions or noise) [14,16].

If the training set contains two classes of data that allow linear division, then there are a large number of linear classifiers with which you can divide this data. It is intuitively clear that a dividing surface passing through the middle of a strip separating two classes. For example, the perceptron allows you to find at least one linear, other methods, such as the naive Bayesian method, find the best linear separator using a certain criterion. In particular, SVM necessarily assumes that the decisive function is completely determined by a subset of data that affect the position of the delimiter. In vector space, a point can be considered as a vector passing through the origin. Consider a dataset of n points in the form ) , ( ),..., , (

1 1 n n y x y x

, where

  1 , 1 1   y

identifies to which class the point x belongs.

Each point is a p-dimensional real vector. SVM means to find the maximum hyperplane that separates groups of points belonging to 1  y from 1   y . In Equation 1we write a hyperplane through many points that satisfy the condition:

0 *   b x w , (1)

where w is a optional vector to the hyperplane. Parameter w b determines the displacement of the hyperplane from the origin on the normal vector (Figure 1).

Figure 1: Visual representation of SVM

In Equation 2we define the data that are not linearly separated:

)) ( 1 , 0 max( b wx y i i   . (2)

In Equation 3, we minimize the function:

2 1 )) ( 1 , 0 max( 1 w b wx y n n i i i             ,(3)

where  determines the trade-off between the size of the margin and the guarantee that the point lies on the correct side of the margin. Hence, if  is very small, the second operand becomes insignificant, and the function will behave as with a hard margin. The calculation of the soft margin classifier is to minimize the expression of the form (Equation 4):

2 1 ) ) ( 1 , 0 max( 1 w b wx y n n i i i             . (4)

Therefore, in a further study, we will consider a classifier with a bounded boundary.

Primal problem

Equation 4 presents the minimization of a bounded optimization problem with a differentiated objective function. For each i we enter a variable i e -the least positive number that satisfies

i i i e b x w y   ) * ( and 0  i e .

Equation 5 presents the problem of optimization taking into account additions. (

Solving the primary problem for the dual Lagrange, we obtain a simplified problem (Equation 6):

        n i n j j j j i i i n i i n c y x x c y c c 1 1 1 1 ) * ( 2 1 ) ,..., maxmizef(c , (6) if:    n j i i c y 1 0 and  n c i 2 1 0   .

The quadratic function solves double maximization problems. its results satisfy linear constraints. Equations 7-8 determine the variables i c to determine the second problem. 9shows a linear combination of reference vectors, which determines the offset through a point on the field boundary.

        n i n j j j j i i i n i i n c y x x c y c c 1 1 1 1 ) * ( 2 1 ) ,..., maxmizef(c . (7) i n i i i x c y w    1 . (8i i i i y wx b b wx y      1 ) ( . (9)

Comparison of problems

Equation (Formula 8) gives the optimal value of w in terms of с . Suppose we have adjusted the parameters of our model to the training set, and now we want to make a prediction for the new point

x . Then we will calculate b x w T  and forecast 1  y , if and only if this value is greater than zero. But, using (Formula 3), this value can also be written as (Equation 10):

         n i i i i n i T i i i T b x x c y b x x c y b x w 1 1 ) , ( )) ( ( . (10)

So, if we find i c to make a prediction, we have to calculate a value that depends only on the internal product between

x . Moreover, we have previously seen that i c will be equal to all but zero support vectors. Thus, many terms in the above sum will be zero, and we really only need to find the internal products between

x and the reference vectors (which are often only a small number) to calculate (Formula 9) and make our prediction.

Considering the dual form of the optimization problem, we got a good idea of the structure of the problem, and we can write the whole algorithm in terms of only the internal products between the vectors of the input functions. This property is important to apply kernels to our classification problem. The obtained algorithm, supporting vector machines, will be able to effectively learn in spaces with high dimensions.

Also dual SVM requires fewer kernel estimates than the primary. Therefore, it gives a more stable result in less computational time (Table 1). In terms of stable convergence and learning speed, a dual SVM is better than a basic SVM.

Experiments

The study requires solving a double problem by the method of reference vectors, comparison with the primary problem and classification of the data set.

Achieving this goal involves solving specific tasks:  determine the problem of the method of support vectors for the dual problem;  compare dual SVM and primal;  analyze the algorithm of the method;  apply it in practice.

The Iris dataset was chosen for the implementation of the support vector method. This is a wellknown set of data used in the area of machine learning.

Dataset attribute information: The main purpose of visualizationinterpretation of a large data set into visual graphics to easily understand complex data relationships and quickly get an imagination of the dataset.

The histogram shown in Figure 2 shows the frequencies of the data set, which can be used to understand the trend of length / width of the petals for each type of plant.

Figure 2: Histogram of frequencies

From Figure 2 it is seen that the type of petal virginica is much larger than others and sepals are mostly too, setosa has the smallest size and small range of values, versicolor -medium in size.

The box plot (Figure 3) shows the distribution of data by quartiles, the average values and statistical emissions are highlighted. The vertical lines (whiskers) drawn to the rectangles reflect the variability of the values outside the upper and lower quartiles, any point on these lines is considered a statistical ejection. The other two species are larger and have larger tendrils, which characterize a large scope.

The heatmap (Figure 4) shows the levels of correlation between attributes and their linear dependencies:

 (-0.09; 0.0)(0.0; 0.09) -linear independence;  (-0.3; -0.1)(0.1; 0.3) -low linear dependence;  (-0.5; -0.3) (0.3; 0.5)medium linear dependence;  (-1.0; -0.5) (0.5; 1.0) -high linear dependence. The values of the length of the sepals depend entirely on the values of its width, or vice versa. In the case of a petal, the length and width are independent of each other. It is also interesting that the length of the petal depends on the length and width of the sepals.

In Figure 5 you can see the linear separation between classes. Setosa is linearly separated from Versicolor and Virginica, and Versicolor and Virginica are not linearly separated. It means that in the first case it is necessary to apply SVM with a hard margin, and in the second -with soft. From this statistical in the Table 2 it is seen: that the size of the sepals mostly is larger than the size of the petal. Also, since the variance and standard deviation characterize the scattering of values around the distribution center, it can be concluded that the variation of petal size values between plant species is much larger than for the sepals.

Results

Two arbitrary points from the iris dataset are selected for analysis, and the optimal hyperplane is calculated.

Let first arbitrary point - , where xindex in the dataset, y - length of the sepal (Figure 6).

The point A will be considered negative, You need to find the optimal separate hyperplane.

B -positive, thus 1  yA , 1   yB .

It is known that any hyperplane can be described as (equation 11

): 0   b wx ,(11)

where wnormal vector to the hyperplane and w b -perpendicular distance from the hyperplane to the origin.

To find w and b dual form should be introduced. It contains a quadratic objective function with constraints (equation 12).

j i j i j i j i L i i D a x x y y a a a L , , 1 2 1 max      , (12) if i a y a i L i i i      0 0 1 ,1 max 2 2 2 1 2 1 2 1 2 2 2 1 1 1 2 1 , 1 , a a a a a a a a a a a a a a a a i a L j i j i j i j i L i D a x x y y                                                                    

Using the Lagrange equation we can solve this problem:

) 0 ( * 69 . 10039 48 . 2460 04 . 167 ( 2 1 ) , ( 2 1 2 2 2 1 2 1 2 1         x x x x x x x x X L   .

Under the condition of the extremum of the Lagrange function, we equate the partial derivatives to zero.

Built system: This system can now be written as: Figure 7 shows the hyperplane that best classifies our data, and theoretically all positive points will be on the left and negative points on the right. Dark blue color indicates the hyperplane itself, dotted lines form a margin. Figure 8 shows the calculated results using the program for the entire dataset: )), so the support vectors and their number for each class are found correctly. Plants with an index less than 75 will belong to setosa, and more -to versicolor. But it is necessary to remember about possible cases where the sepal_length value will be considered.

                             0 0 1                                                                    96837,                                                     L S m

Conclusion

The dual method of support vectors is to solve the Lagrange problem, with found Lagrange multipliers it is easy to calculate the normal vector w and draw a separate hyperplane.

Solving the primary problem, it is obtained the optimal w, but nothing about the Lagrange multipliers. To classify the point x, it is needed to clearly calculate the scalar product x w T , which can be very expensive. Solving the dual problem: obtained Lagrange factors (where 0  i a for all but a few points -support vectors). This problem is very efficiently calculated if there are few support vectors. Also, with a scalar product that includes only data vectors, it is possible to use kernel trick for nonlinear problems.

Dual SVM in nonlinear problems is more stable and faster than the primary because it performs fewer kernel estimates.