最优化：建模、算法与理论|02 Optimization Modeling and Typical Examples(1)

最优化：建模、算法与理论|02

Optimization Modeling and Typical Examples

The Technology Of Modeling

Design Of Objective Function

1. Least Squares Method

The least squares method is commonly used in modeling linear (non - linear) system - of - equations problems. Let ${\varphi }_i(x):{\mathbb{R}}^n\to \mathbb{R},i=1,2,\cdots ,m$ be $n$ - variable functions, and there is the following system of equations:
$$b_i={\varphi }_i(x),i=1,2,\cdots ,m$$
where $b_i\in \mathbb{R}$ are known real numbers.

The solution of the system of equations is widely used in practice, but this problem is not always solvable.First, the number of equations $m$ can exceed the number of independent variables $n$, so the solution of the system of equations may not exist; second, due to factors such as measurement errors, the equality relationship of the system of equations may not hold precisely.

In order to solve for $x$ under such practical circumstances, the idea of the least squares method is to minimize the squared ${\ell }_2$ - norm of the errors, that is:

$$\underset{x\in {\mathbb{R}}^n}{\min }\sum _{i=1}^m{\left(b_i-{\varphi }_i(x)\right)}^2$$

In particular, when all ${\varphi }_i$ are linear functions, we call problem a linear least squares problem; otherwise, it is called a non - linear least squares problem.

However,the least squares method is not always the most reasonable. If we want to minimize the sum of the absolute values of the deviations, the corresponding model is:
$$\underset{x\in {\mathbb{R}}^n}{\min }\sum _{i=1}^m\left|b_i-{\varphi }_i(x)\right|$$

If we want to minimize the maximum deviation, the corresponding optimization model is:
$$\underset{x\in {\mathbb{R}}^n}{\min }\underset{i}{\max }\left|b_i-{\varphi }_i(x)\right|$$

2. Regularization

To make the solution have certain smoothness and overcome the ill - posed nature of the problem the improved model is:

$$\underset{x\in {\mathbb{R}}^n}{\min }\sum _{i=1}^m(b_i-{\varphi }_i(x){)}^2+\mu \Vert x{\Vert }_2^2$$

Here, $\mu >0$ is a balancing parameter. To obtain a sparse solution, we use the ${\ell }_0$ norm to construct:

$$\underset{x\in {\mathbb{R}}^n}{\min }\sum _{i=1}^m(b_i-{\varphi }_i(x){)}^2+\mu \Vert x{\Vert }_0$$

Since the ${\ell }_0$ norm is non - convex and hard to compute, we replace it with the ${\ell }_1$norm for sparsity:

$$\underset{x\in {\mathbb{R}}^n}{\min }\sum _{i=1}^m(b_i-{\varphi }_i(x){)}^2+\mu \Vert x{\Vert }_1$$

For image processing, $x$ itself may not be sparse, but its transformed version often is. We use a transformation $W:{\mathbb{R}}^n\to {\mathbb{R}}^p$ (e.g., wavelets, total variation) and model sparsity in the transformed space:

$$\underset{x\in {\mathbb{R}}^n}{\min }\sum _{i=1}^m(b_i-{\varphi }_i(x){)}^2+\mu \Vert W(x){\Vert }_0$$

and

$$\underset{x\in {\mathbb{R}}^n}{\min }\sum _{i=1}^m(b_i-{\varphi }_i(x){)}^2+\mu \Vert W(x){\Vert }_1$$

Regularization can controls the sparsity of the solution and the magnitude of the parameters.

3. Maximum Likelihood Estimation

Consider a simple case: suppose we know data comes from a specific distribution but are unaware of its parameters. Let $p(a;x)$ denote the probability distribution or density function, where $x$ is the unknown parameter. To estimate $x$, we draw i.i.d. samples {ai,i=1,2,…,n}\{a_i, i = 1,2,\dots,n\}{ai​,i=1,2,…,n}. The likelihood function for parameter $x$ is defined as the joint probability (or density) of observing {ai}\{a_i\}{ai​}:

$$L(x)=\prod _{i=1}^{n}p(a_i;x)$$

Here, $L(x)$ represents the joint probability of the sample under parameter $x$, with $x$ now as the variable to optimize.

The maximum likelihood estimate $\hat{x}$ is the parameter that maximizes $L(x)$:

$$\hat{x}\in {\text{argmax}}_{x\in \mathcal{X}}\ln L(x)$$

For most models, $\ln L(x)$ has a known analytical form, but its global optimum may still require numerical methods.

4. Cost, Loss, and Reward Functions

Many operations research problems reduce to minimizing cost (or loss) or maximizing reward. For example, in portfolio optimization, we minimize risk (loss) or maximize return (reward). These functions directly define the objective in optimization models.

5. Functionals and Variational Methods

Many problems in physics and chemistry can be formulated as minimizing an energy functional.

A functional is a mapping from a set of functions to the real numbers (or complex numbers).

Example 1: The integral of a function over an interval, e.g., $J[f]={\int }_a^{b}f(x)\mathrm{d}x$, where $f(x)$is a function in some function space (e.g., continuous functions on $[a,b]$), and $J[f]$is a scalar.

Example 2: The energy of a physical system, often expressed as a functional of the system’s state function. For a string vibrating with displacement $u(x,t)$, the total energy might be
$$E[u]=\int \left(\frac{1}{2}\rho {\left(\frac{\partial u}{\partial t}\right)}^2+\frac{1}{2}T{\left(\frac{\partial u}{\partial x}\right)}^2\right)\mathrm{d}x$$

where $\rho$ is mass density and $T$ is tension. Here, $E[u]$depends on the entire function $u(x,t)$, so it is a functional.

Variational methods are mathematical techniques used to find functions that minimize or maximize a given functional. They are rooted in the variational principle: many natural phenomena (e.g., physical systems) tend to evolve toward states that extremize (minimize or maximize) a specific functional (e.g., energy, action).

The “Variation” of a Functional

To find the extremum of a functional $J[f]$, we consider small perturbations (called variations) of the function $f$, denoted$\delta f$. A variation $\delta f$ is a small, arbitrary function that vanishes at boundary points (to satisfy constraints).

For $J[f]$ to have an extremum at $f = f_0 $, the first variation of $J $ must vanish:

$$\delta J[f_0]=0$$

This condition is analogous to the derivative being zero for functions (where extrema occur at critical points).

Euler-Lagrange EquationEuler-Lagrange Equation

For a functional of the form:

$$J[f]={\int }_a^{b}L(x,f(x),f^{\prime }(x))\mathrm{d}x$$
where $L$ (called the Lagrangian) depends on the independent variable $x $, the function $f(x)$, and its derivative $f^{\prime }(x)$, the condition $\delta J=0$ leads to the Euler-Lagrange equation:
$$\frac{\partial L}{\partial f}-\frac{\mathrm{d}}{\mathrm{d}x}\left(\frac{\partial L}{\partial f^{\prime }}\right)=0$$

This ordinary differential equation (ODE) must be satisfied by the function $f(x)$ that extremizes $J[f]$.

6. Relaxation
   When it is not easy to solve the original problem, a commonly used technique in optimization is relaxation. The basic idea of this technique is: under the condition of retaining some properties of the original problem, use simple terms to replace the difficult - to - handle terms in the objective function, thereby making the problem easier to solve. For example, the ${\ell }_0$ norm is non - differentiable and non - convex. Since the ${\ell }_1$ norm is an approximation of the ${\ell }_0$ norm to a certain extent, in practice, the ${\ell }_1$ norm is often used to replace the ${\ell }_0$ norm in the objective function. Because the ${\ell }_1$ norm is convex, the theoretical analysis and algorithm design of the corresponding model will be simpler. For the low - rank optimization problem, the rank corresponds to the number of non - zero singular values of a matrix, and it is also non - convex and non - differentiable. A common way is to replace it with the ${\ell }_1$ norm of the nuclear norm of the matrix (the vector composed of the singular values of the matrix), thus obtaining a convex relaxation term that is easier to handle.

Another relaxation strategy is to use a lower bound $f_R(x)$ of the objective function in problem to replace $f(x)$ for solution, where $f_R(x)$ should satisfy:
(1) $f_R(x)\le f(x),\forall x\in \mathcal{X}$;
(2) $f_R(x)$ has a simple structure.

Note here that the relaxed problem and the original problem are not necessarily equivalent. Previously, we repeatedly mentioned that the replacement of the ${\ell }_0$ norm with the ${\ell }_1$ norm is carried out under certain conditions, and the ${\ell }_2$ norm generally cannot be used as a relaxation of the ${\ell }_0$ norm.

Design of Constraints

1. Physical Nature of the Problem
   According to the specific forms of actual problems, the decision variables of an optimization problem need to satisfy various constraints. For example, in electronic structure calculations, we assume that orbital functions are orthogonal to each other. In a chemical reaction process, the change in the concentration of each component over time corresponds to a system of differential equations. In shape optimization design, we sometimes need to optimize the shape of an object. For instance, in aircraft wing design, affected by the airflow around the wing, the change in the wing’s shape corresponds to a differential equation. In many cases, we also have non - negative constraints, such as the pixel values of an image, the concentration of an object, and the quantity of available resources. When the observation has noise or more robustness is required, we can also relax equality constraints to inequality constraints.

2. Equivalent Transformation

For an optimization problem, if its objective function is in the form of a composite function, such as
$$\underset{x}{\min }f(Ax+b),$$
we often introduce a variable $y$ and an equality constraint $y=Ax+b$ and consider its equivalent constrained problem:
$$\underset{y}{\min }f(y),\text{ s.t. }y=Ax+b.$$

For the optimization problem
$$\underset{x}{\min }f(x)=h(x)+r(x),$$
we usually introduce $y$ and the constraint $x=y$, and transform it into
$$\underset{x}{\min }h(x)+r(y),\text{ s.t. }x=y.$$

In this way, the objective function is decomposed. For inequality constraints, we can also introduce slack variables to transform them into equality constraints and simple non - negative or non - positive constraints. For example, for the constraint $c(x)\le 0$, by introducing $y\ge 0$, we can equivalently transform it into
$$c(x)+y=0,y\ge 0.$$

In addition, we can also use the definition of the epigraph to obtain the equivalent form of the problem. For the optimization problem
$$\underset{x}{\min }f(x),$$
according to the definition of the epigraph, it is equivalent to the optimization problem
$$\underset{x,t}{\min }t,\text{ s.t. }f(x)\le t.$$

Performing equivalent transformation on the constraints of an optimization problem helps us study the mathematical properties of the problem more conveniently. Problems that seem dissimilar on the surface may become optimization problems of the same type after equivalent transformation, and ultimately enable us to find a unified algorithm.

3. Relaxation

In the context of optimization (as mentioned in your material, especially related to constraint design and problem - solving), relaxation is a powerful technique.

The core idea of relaxation is: when the original optimization problem is difficult to solve (for example, due to non - convexity, non - differentiability, or complex constraints), we modify the problem in a controlled way. We replace the “hard - to - handle” parts (such as complex constraints or non - convex objective functions) with “softer”, more manageable constructs. But we do this while still retaining some key properties of the original problem, so that the relaxed problem is easier to analyze and solve, and can provide useful information (like bounds) for the original problem.

Regression Analysis

In real - life, we often need to make predictions about unknown things based on existing information or knowledge. In machine learning, the task of supervised learning is to learn a model according to a given dataset containing input information, so that the model can make good predictions for new input data. According to whether the type of the output variable is continuous or discrete, classical supervised learning includes two types of problems: regression and classification. Let’s introduces how to establish a model for regression problems.

General form

Generally, its general form can be written as follows:

$$b=f(a)+ϵ$$

In it, $a\in {\mathbb{R}}^d$ is the independent variable, $b\in \mathbb{R}$ is the response variable, and $ϵ\in \mathbb{R}$ is the error (or noise) of the model.

To narrow the range of function f in the function space, parameterize f as 
$$b=f(a;x)+\epsilon$$
where $x\in {\mathbb{R}}^n$ is a parameter. This reduces the selection range of f to a finite - dimensional space ${\mathbb{R}}^n$, and solving f becomes solving parameter $x$.

Linear Regression Model

In the parameterized regression model, the simplest one is the linear regression model. Let $(w_i,b_i)$ be the observed independent variable and response variable, and different data points are independent of each other. Then for each data point,

$$b_i=w_{i1}{x}_1+w_{i2}{x}_2+\cdots +w_{i,n-1}{x}_{n-1}+x_n+{\epsilon }_i,i=1,2,\cdots ,m$$
where $x_i$ is the parameter to be determined, ${\epsilon }_i$ is a certain noise and different data points are independent of each other. Write the input features in the training set plus the constant term 1 as $a_i=(w_i^T,1{)}^T$, and let $x=(x_1,x_2,\cdots ,x_n{)}^T\in {\mathbb{R}}^n$. Then the linear regression model can be abbreviated as $$b_i=a_i^{T}x+{\epsilon }_i\text{\hspace{1em}(3.2.2)}$$ In this subsection, the constant term 1 in the linear regression model corresponds to the element $x_n$. Below, we will construct corresponding optimization models under different conditions.
Write the input features in the training set as an $m\times n$ matrix $A$, and write the labels $b_i$ and noises ${\epsilon }_i$ in vector form, that is

$$A=\left[\begin{array}{c}{a}_1^T\\ a_2^T\\ ⋮\\ a_m^T\end{array}\right],b=\left[\begin{array}{c}{b}_1\\ b_2\\ ⋮\\ b_m\end{array}\right],\epsilon =\left[\begin{array}{c}{\epsilon }_1\\ {\epsilon }_2\\ ⋮\\ {\epsilon }_m\end{array}\right]$$

Then we get the matrix form of model
$$b=Ax+\epsilon \text{\hspace{1em}(3.2.3)}$$
Assume that ${\epsilon }_i$ is white Gaussian noise, that is ${\epsilon }_i\sim \mathcal{N}(0,{\sigma }^2)$, then
$$p(b_i\mid a_i;x)=\frac{1}{\sqrt{2\pi {\sigma }^2}}\exp \left(-\frac{(b_i-a_i^{T}x{)}^2}{2{\sigma }^2}\right)$$
Then the log - likelihood function is
$$\ell (x)=\ln \prod _{i=1}^{m}p(b_i\mid a_i;x)=-\frac{m}{2}\ln (2\pi )-m\ln \sigma -\sum _{i=1}^m\frac{(b_i-a_i^{T}x{)}^2}{2{\sigma }^2}$$
The maximum likelihood estimation is to maximize the log - likelihood function. After removing the constant terms, we get the following least - squares problem: $$\underset{x\in {\mathbb{R}}^n}{\min }\frac{1}{2}\Vert Ax-b{\Vert }_2^2\text{\hspace{1em}(3.2.4)}$$ Note that when constructing the maximum likelihood estimation, there is no need to know the variance ${\sigma }^2$ of ${\epsilon }_i$. The most important significance of the above transformation is that it establishes the connection between the least - squares method and regression analysis: when the error is assumed to be white Gaussian noise, the least - squares solution is the maximum likelihood solution of the linear regression model.

When ${\epsilon }_i$ is not white Gaussian noise, solving the linear regression model and solving the least - squares model are not equivalent. Therefore, we need to use the likelihood function to construct objective functions corresponding to other noises. For example, the model constructed under certain noises is actually the least - absolute deviation problem:
$$\underset{x\in {\mathbb{R}}^n}{\min }\Vert Ax-b{\Vert }_1$$

Regularized linear regression model

1. Tikhonov Regularize

To balance the fitting property of the model and the smoothness of the solution, Tikhonov regularization, or ridge regression, adds an ${\ell }_2$-norm squared regularization term. Assuming $e_i$ is Gaussian white noise, the linear regression model with the ${\ell }_2$-norm squared regularization term is actually solving the following problem:

$$\underset{x\in {\mathbb{R}}^n}{\min }\frac{1}{2}\Vert Ax-b{\Vert }_2^2+\mu \Vert x{\Vert }_2^2$$

Due to the existence of the regularization term, the objective function of this problem is a strongly convex function, and the properties of the solution are improved. In the ridge regression problem , the regularization term $\Vert x{\Vert }_2^2$ actually penalizes $x $ with a large norm. Therefore, another common variant is, given a parameter $\sigma >0$, to solve:

$$\underset{x\in {\mathbb{R}}^n}{\min }\frac{1}{2}\Vert Ax-b{\Vert }_2^2\text{s.t.}\Vert x{\Vert }_2\le \sigma$$

2. LASSO Problem and Its Variants

If the solution $x$ we expect to obtain is sparse, then we can consider adding an ${\ell }_1$-norm as the regularization term.LASSO problem is :

$$\underset{x\in {\mathbb{R}}^n}{\min }\frac{1}{2}\Vert Ax-b{\Vert }_2^2+\mu \Vert x{\Vert }_1$$

where $ \mu > 0 $ is a known real number, and $ x $ is the parameter to be estimated. The LASSO problem penalizes the sparsity of the solution through the $ \ell_1 $-norm. If $ x $ is sparse, then the predicted value $ b_i $ is only related to some elements of $ a_i $ that are non - zero. Thus, among the original $ n $ features of the data points, the features that play a role in prediction correspond to the non - zero components of $ x $. Therefore, **the LASSO model serves the function of feature extraction. **

Similarly , we can also consider the problem:

$$\underset{x\in {\mathbb{R}}^n}{\min }\frac{1}{2}\Vert Ax-b{\Vert }_2^2\text{s.t.}\Vert x{\Vert }_1\le \sigma$$

Considering the existence of noise $\epsilon$, we can also, given $\nu >0$, consider the model:

$$\underset{x\in {\mathbb{R}}^n}{\min }\Vert x{\Vert }_1\text{s.t.}\Vert Ax-b{\Vert }_2\le \nu$$

The traditional LASSO problem requires $x$ to be a sparse solution. However, the sparsity in practical problems can have many expressions. If the parameter $x$ has group - sparsity, that is, the components of $x$ can be divided into $G$ groups, and the parameters within each group must be non - zero or zero simultaneously, then the solution of the traditional LASSO problem cannot meet such a requirement. For this reason, people have proposed the group LASSO model:

$$\underset{x\in {\mathbb{R}}^n}{\min }\frac{1}{2}\Vert Ax-b{\Vert }_2^2+\mu \sum _{\ell =1}^G\sqrt{n_{\ell }}\Vert x_{{\mathcal{I}}_{\ell }}{\Vert }_2$$

where ${\mathcal{I}}_{\ell }$ is the index set belonging to the $\ell$ - th group of variables, $|{\mathcal{I}}_{\ell }|=n_{\ell }$, and ${\sum }_{\ell =1}^G{n}_{\ell }=n$. where ${\mathcal{I}}_{\ell }$ is the index set belonging to the $\ell$ - th group of variables, $|{\mathcal{I}}_{\ell }|=n_{\ell }$, and ${\sum }_{\ell =1}^G{n}_{\ell }=n$.

If we need to ensure both group - level and single - feature - level sparsity, we can consider combining two regularization terms, that is, the so - called sparse group LASSO model:

$$\underset{x\in {\mathbb{R}}^n}{\min }\frac{1}{2}\Vert Ax-b{\Vert }_2^2+{\mu }_1\sum _{\ell =1}^G\sqrt{n_{\ell }}\Vert x_{{\mathcal{I}}_{\ell }}{\Vert }_2+{\mu }_2\Vert x{\Vert }_1$$

where ${\mu }_1,{\mu }_2>0$ are given constants. The regularization term of the sparse group LASSO model consists of two parts: $\Vert x{\Vert }_1$ is to ensure the sparsity of $x$ itself, and ${\sum }_{\ell =1}^G\sqrt{n_{\ell }}\Vert x_{{\mathcal{I}}_{\ell }}{\Vert }_2$ is to ensure the group - sparsity of $x$.

For some practical problems, the feature $x$ itself is not sparse, but it is sparse under some transformation. Therefore, we also need to adjust the regularization term accordingly. The general problem form can be:

$$\underset{x\in {\mathbb{R}}^n}{\min }\frac{1}{2}\Vert Ax-b{\Vert }_2^2+\mu \Vert Fx{\Vert }_1$$

Logistic regression

In classification problems, the output variable takes values in a discrete space. For binary classification problems, the predicted variable has only two values, namely $-1$ and $1$. We briefly introduce a classic classification model in machine learning: the logistic regression model.Given a feature $a$, logistic regression assumes that the probability that this sample belongs to class $1$ is:
$$p(1\mid a;x)=P(t=1\mid a)=\theta (a^{T}x),$$
where the Sigmoid function is:
$$\theta (z)=\frac{1}{1+\exp (-z)}.$$
Then, the probability of belonging to class $-1$ is:
$$p(-1\mid a;x)=1-p(1\mid a;x)=\theta (-a^{T}x).$$
Thus, for b∈{−1,1}b \in \{-1, 1\}b∈{−1,1}, the above probability can be concisely written as:
$$p(b\mid a;x)=\theta (b\cdot a^{T}x).$$
Assume that the data pairs {ai,bi},i=1,2,…,m\{a_i, b_i\}, i = 1, 2, \ldots, m{ai​,bi​},i=1,2,…,m are independently and identically distributed. Then, given $a_1,a_2,\dots ,a_m$, the joint probability density of $b_1,b_2,\dots ,b_m$ is: $$p(b_1,b_2,\dots ,b_m\mid a_1,a_2,\dots ,a_m)=\prod _{i=1}^{m}p(b_i\mid a_i).$$ Substituting the form of $p(b_i\mid a_i)$, we get:
$$p(b_1,b_2,\dots ,b_m\mid a_1,a_2,\dots ,a_m)=\frac{1}{{\prod }_{i=1}^m(1+\exp (-b_i\cdot a_i^{T}x))}.$$
Then, the maximum likelihood estimation is to solve the following optimization problem:
$$\underset{x\in {\mathbb{R}}^n}{\min }\sum _{i=1}^m\ln \left(1+\exp (-b_i\cdot a_i^{T}x)\right).$$

Similar to sparse optimization, common models also need to consider the properties of the parameter $x$ and add a regularization term. For example:

1. Tikhonov Regularization Model
   $$\underset{x\in {\mathbb{R}}^n}{\min }\sum _{i=1}^m\ln \left(1+\exp (-b_i\cdot a_i^{T}x)\right)+\lambda \Vert x{\Vert }_2^2$$
2. ${\ell }_1$ Norm Regularization Model
   $$\underset{x\in {\mathbb{R}}^n}{\min }\sum _{i=1}^m\ln \left(1+\exp (-b_i\cdot a_i^{T}x)\right)+\lambda \Vert x{\Vert }_1$$

Assume that the data pairs {ai,bi}\{a_i, b_i\}{ai​,bi​} are generated by the random variable pair {α,β}\{\alpha, \beta\}{α,β}. Then, the loss function can be written in the mean form:
$$\mathbb{E}\left[\ln \left(1+\exp (-\beta \cdot {\alpha }^{T}x)\right)\right].$$

Problems Tikhonnov and ${\ell }_1$ can be written in the sampling form of the following stochastic optimization problem:
$$\underset{x\in {\mathbb{R}}^n}{\min }\mathbb{E}\left[\ln \left(1+\exp (-\beta \cdot {\alpha }^{T}x)\right)\right]+\lambda r(x),$$
where $r(x)$ is the regularization term, and $\lambda$ is the regularization parameter. Many machine learning problems can be written as a more general stochastic optimization problem and its discrete version:
$$\underset{x\in {\mathbb{R}}^n}{\min }f(x)+\lambda r(x),$$
where:
$$f(x)\stackrel{\text{def}}{=}\mathbb{E}[F(x,\xi )]={\int }_{\Omega }F(x,\xi (\omega ))\mathrm{d}P(\omega ),\text{or}f(x)\stackrel{\text{def}}{=}\frac{1}{m}\sum _{i=1}^m{f}_i(x),$$
$\xi :\Omega \to W$ is a random variable defined on a given probability space $(\Omega ,\mathcal{F},P)$, $W$ is a measurable space, $F:{\mathbb{R}}^n\times W\to \mathbb{R}$, and $f_i:{\mathbb{R}}^n\to \mathbb{R},i=1,2,\dots ,m$ correspond to a certain loss function.

SVM

Support Vector Machine (SVM) is another widely applied binary classification model. Given sample points $(a_i,b_i)$ in the training dataset $D$, where $a_i\in {\mathbb{R}}^n$ and bi∈{−1,1}b_i \in \{-1, 1\}bi​∈{−1,1}, the basic idea of SVM is to find a hyperplane that divides the sample points in ${\mathbb{R}}^n$ into two classes. We first consider a simple case: assume the training dataset is linearly separable, that is, the positive and negative classes are just divided to the two sides of the hyperplane $x^{T}w+y=0$.
It can be seen that after a linearly separable dataset is given, the hyperplanes that meet the “division requirement” are generally not unique. An ideal hyperplane should have the following characteristic: the distances from data points to this plane are relatively large. Knowledge from geometry tells us that the distance from a point $w$ in the sample space to the hyperplane $x^{T}w+y=0$ is
$$d=\frac{|x^{T}w+y|}{\Vert x{\Vert }_2}$$
If this hyperplane classifies the sample point $(a_i,b_i)$ correctly, then
$$b_i(a_i^{T}x+y)>0,i=1,2,\dots ,m$$
To find the ideal hyperplane $x^{T}w+y=0$ to separate the data points, we require that the minimum distance from the points of the two classes of data to this hyperplane be as large as possible. Then the following original model can be established:
$$\begin{gathered} \underset{x,y,\gamma }{\max }\gamma , \\ \text{s.t.}\frac{b_i(a_i^{T}x+y)}{\Vert x{\Vert }_2}\ge \gamma ,i=1,2,\dots ,m \end{gathered}$$
The meaning of $\gamma$ in problem is obvious: it represents the minimum value of the distances from all sample points to the hyperplane $x^{T}w+y=0$, and the goal is to maximize it. Next, we perform an equivalent transformation on problem to make its form more natural. Notice that the constraints in problem are equivalent to
$$b_i(a_i^{T}x+y)\ge \gamma \Vert x{\Vert }_2,i=1,2,\dots ,m$$
And scaling $x$ and $y$ by the same positive multiple will not affect the constraints and the objective function of this problem. According to this characteristic, we reduce the feasible region of problem and force $\Vert x{\Vert }_2=\frac{1}{\gamma }$. Then this problem is equivalent to
$$\begin{array}{rl}& \underset{x,y,\gamma }{\max }\gamma ,\\ \text{s.t.}& b_i(a_i^{T}x+y)\ge \gamma \Vert x{\Vert }_2,i=1,2,\dots ,m,\\ & \Vert x{\Vert }_2=\frac{1}{\gamma }\end{array}$$
Finally, we eliminate the variable $\gamma$ and the constraint $\Vert x{\Vert }_2=\frac{1}{\gamma }$ to obtain the optimization problem
$$\begin{array}{rl}\underset{x,y}{\min }& \frac{1}{2}\Vert x{\Vert }_2^2,\\ \text{s.t.}{b}_i& (a_i^{T}x+y)\ge 1,i=1,2,\dots ,m\end{array}$$
By solving problem to get $x,y$, we call the $a_i$ that make $b_i(a_i^{T}x+y)=1$ hold support vectors. It is not difficult to find that the parameters $x,y$ of the hyperplane are completely determined by the support vectors. In other words, removing the data points that are not support vectors will not affect the solution of problem .

When the assumption of linear separability does not hold, we introduce non - negative slack variables ${\xi }_i$ for each data point, allowing for misclassified points. Then the constraints in problem are changed to
$$\frac{b_i(a_i^{T}x+y)}{\Vert x{\Vert }_2}\ge \gamma (1-{\xi }_i),{\xi }_i\ge 0,i=1,2,\dots ,m$$
Here, the relative form $\gamma (1-{\xi }_i)$ is used to represent the “distance” of misclassified points. Obviously, there should not be too many misclassified points. We control the degree of error through the function ${\sum }_{i=1}^m{\xi }_i$ of slack variables. After equivalent transformation similar to the previous one, we finally obtain the problem
$$\begin{gathered} \underset{x,y,\xi }{\min }\frac{1}{2}\Vert x{\Vert }_2^2+\mu \sum _{i=1}^m{\xi }_i, \\ \text{s.t.}{b}_i(a_i^{T}x+y)\ge 1-{\xi }_i, \\ {\xi }_i\ge 0,i=1,2,\dots ,m \end{gathered}$$
where $\mu >0$ is a penalty coefficient. Increasing the value of $\mu$ will increase the penalty for misclassification, and decreasing the value of $\mu$ will decrease the penalty for misclassification. The above two optimization problems are special forms of quadratic programming.

Above problem is also equivalent to the unconstrained optimization problem:
min⁡x,y12∥x∥22+μ∑i=1mmax⁡{1−bi(aiTx+y),0}\min_{x, y} \frac{1}{2}\|x\|_2^2 + \mu\sum_{i = 1}^m \max\{1 - b_i(a_i^Tx + y), 0\} x,ymin​21​∥x∥22​+μi=1∑m​max{1−bi​(aiT​x+y),0} Notice that max⁡{1−bi(aiTx+y),0}\max\{1 - b_i(a_i^Tx + y), 0\}max{1−bi​(aiT​x+y),0} is the penalty for the quantity that does not satisfy the inequality $b_i(a_i^{T}x+y)\ge 1$. Therefore, problem can also be regarded as solving the penalty function method of problem . Although max⁡{z,0}\max\{z, 0\}max{z,0} is not differentiable, the simple form of problem (3.4.4) also provides many possibilities for algorithm design. It can be seen that introducing different penalty functions can construct different SVM models. In addition, when there are redundant features in the training data, people also consider replacing the $\Vert x\Vert$ term with the ${\ell }_1$ norm for solution: min⁡x∈Rn∥x∥1+μ∑i=1mmax⁡{1−bi(aiTx+y),0}\min_{x \in \mathbb{R}^n} \|x\|_1 + \mu\sum_{i = 1}^m \max\{1 - b_i(a_i^Tx + y), 0\} x∈Rnmin​∥x∥1​+μi=1∑m​max{1−bi​(aiT​x+y),0}

.......