2021

[3]Alain Zemkoho

1]School of Mathematics and Statistics, Beijing Key Laboratory on MCAACI/Key
Laboratory of Mathematical Theory and Computation in Information Security,
Beijing Institute of Technology, Beijing, 100081, P. R. China 2]School of
Mathematics and Statistics, Beijing Institute of Technology, Beijing, 100081,
P. R. China [3]School of Mathematical Sciences, University of Southampton,
Southampton, SO17 1BJ, United Kingdom

# Bilevel hyperparameter optimization for support vector classification:
theoretical analysis and a solution method

Qingna Li<EMAIL_ADDRESS>Zhen Li<EMAIL_ADDRESS><EMAIL_ADDRESS>[ [ *

###### Abstract

Support vector classification (SVC) is a classical and well-performed learning
method for classification problems. A regularization parameter, which
significantly affects the classification performance, has to be chosen and
this is usually done by the cross-validation procedure. In this paper, we
reformulate the hyperparameter selection problem for support vector
classification as a bilevel optimization problem in which the upper-level
problem minimizes the average number of misclassified data points over all the
cross-validation folds, and the lower-level problems are the $l_{1}$-loss SVC
problems, with each one for each fold in T-fold cross-validation. The
resulting bilevel optimization model is then converted to a mathematical
program with equilibrium constraints (MPEC). To solve this MPEC, we propose a
global relaxation cross-validation algorithm (GR-CV) based on the well-know
Sholtes-type global relaxation method (GRM). It is proven to converge to a
C-stationary point. Moreover, we prove that the MPEC-tailored version of the
Mangasarian-Fromovitz constraint qualification (MFCQ), which is a key property
to guarantee the convergence of the GRM, automatically holds at each feasible
point of this MPEC. Extensive numerical results verify the efficiency of the
proposed approach. In particular, compared with other methods, our algorithm
enjoys superior generalization performance over almost all the data sets used
in this paper.

###### keywords:

Support vector classification, Hyperparameter selection, Bilevel optimization,
Mathematical program with equilibrium constraints, C-stationarity

##  1 Introduction

Support vector classification (SVC) is a classical and widely used learning
method for classification problems; see, e.g., cortes1995support ;
Chauhan2019problem ; Vapnik2013nature . In SVC, the selection of
hyperparameters, also known as hyperparameter selection, is a critical issue
and has been addressed by many researchers both theoretically and practically
chapelle2002choosing ; duan2003evaluation ; Keerthi2007Efficient ;
kunapuli2008bilevel1 ; couellan2015bi ; kunapuli2008bilevel ;
kunapuli2008classification . While there have been many interesting attempts
to use bounds, gradient descent methods or other techniques to identify these
hyperparameters chapelle2002choosing ; duan2003evaluation ;
Keerthi2007Efficient , one of the most widely used methods is cross-validation
(CV). A classical approach for cross-validation is the grid search method
momma2002pattern , where one needs to define a grid over the hyperparameters
of interest, and search for the combination of hyperparameters that minimize
the cross-validation error (CV error). Bennett et al. bennett2006model
emphasize that one of the drawbacks of the grid search approach is that the
continuity of the hyperparameter is ignored by the discretization. A
formulation of the bilevel optimization model is proposed to choose
hyperparameters bennett2006model ; kunapuli2008bilevel1 . Below, we will focus
on the bilevel optimization approach which is the most relevant to our work.
We refer to Yu2020hyper ; Luo2016review for a survey of various
hyperparameters optimization methods and applications.

In terms of selecting hyperparameters through bilevel optimization, different
models and approaches have been considered in the literature. For example,
Okuno et al. okuno2018hyperparameter propose a bilevel optimization model to
select the best hyperparameter for a nonsmooth, possibly nonconvex,
$l_{p}$-regularized problem. They then present a smoothing-type algorithm with
convergence analysis to solve this bilevel optimization model. Kunisch and
Pock kunisch2013bilevel formulate a parameter learning problem for variational
image denoising model into a bilevel optimization problem. They design a
semismooth Newton’s method for solving the resulting nonsmooth bilevel
optimization problems. Moore et al. mooregradient develop an implicit
gradient-type algorithm for selecting hyperparameters for linear SVM-type
machine learning models which are expressed as bilevel optimization problems.
Moore et al. moore2009nonsmooth propose a nonsmooth bilevel model to select
hyperparameters for support vector regression (SVR) via T-fold cross-
validation. They design a proximity control approximation algorithm to solve
this bilevel optimization model. Couellan et al. couellan2015bi design a
bilevel stochastic gradient algorithm for training large scale SVM with
automatic selection of the hyperparameter. We refer to colson2007overview ;
dempe2002foundations ; dempebilevelbook for recent general surveys on bilevel
optimization, as well as mejia2019metaheuristic ; zemkoho2021theoretical ;
fischer2019semismooth ; lin2014solving ; ye2010new ; ochs2016techniques ;
ochs2015bilevel for some of the latest algorithms on the subject. Next, we
provide a brief overview of the MPEC reformulation of the bilevel optimization
problem, which will play a fundamental role in this paper.

For a bilevel program, replacing the lower-level problem by its Karush-Kuhn-
Tucker (KKT) conditions will result in a mathematical program with equilibrium
constraints (MPEC) luo1996mathematical . Therefore, various algorithms for
MPECs can be potentially applied to solve bilevel optimization problems,
although one might want to pay attention to the fact that both problems are
not necessarily equivalent. Bennett and her collaborators did a series of
works bennett2006model ; kunapuli2008classification ; bennett2008bilevel ;
kunapuli2008bilevel ; kunapuli2008bilevel1 on hyperparameter selection by
reformulating a bilevel program into an MPEC. For example,
kunapuli2008classification considers a bilevel optimization model for
selecting many hyperparameters for $l_{1}$-loss SVC problems, in which the
upper-level problem has box constraints for the regularization parameter and
feature selection. They reformulate this bilevel program into an MPEC and
solve it by the inexact cross-validation method. Other methods include Newton-
type algorithms wu2015inexact ; harder2021reformulation ; lee2015global .

Considering these works, a natural question is whether one can build up a
bilevel hyperparameter selection for SVC? If yes, whether there are some
special and hidden properties if we transfer the corresponding bilevel
optimization problem to its corresponding MPEC and how we can solve it
efficiently? This is the main motivation the work in this paper.

In this paper, we consider a bilevel optimization model for selecting the
hyperparameter in SVC. This regularization hyperparameter $C$ is selected to
minimize the T-fold cross-validated estimation of the out-of-sample
misclassification error, which is basically a $0$-$1$ loss function.
Therefore, the upper-level problem minimizes the average misclassification
error in T-fold cross-validation based on the optimal solution of the lower-
level problem (we use the typical $l_{1}$-loss SVC model) for all the possible
values of the hyperparameter $C$. There are several challenges to design
efficient algorithms for such potentially large-scale bilevel programs.
Firstly, the objective function in the upper-level problem is a $0$-$1$ loss
function, which is discontinuous and nonconvex. Secondly, the constraints for
the upper-level problem involve the optimal solution set of the lower-level
problem, i.e., the $l_{1}$-loss SVC optimization model, for which the optimal
solution is not explicitly given. To deal with the first challenge, we
reformulate the minimization of the $0$-$1$ loss function into a linear
optimization problem inspired by the technique in
mangasarian1994misclassification . We then replace the lower-level problem by
its optimality conditions to tackle the second challenge. This therefore leads
to an MPEC.

The contributions of the paper are as follows. Firstly, we propose a bilevel
optimization model for hyperparameter selection in a binary SVC and study its
reformulation as an MPEC. Secondly, we apply the GRM originating from
scholtes2001convergence to solve this MPEC, which is shown to converge to a
C-stationary point. The resulting algorithm is called the GR-CV, which is a
concrete implementation of the GRM for selecting the hyperparameter $C$ in
SVC. Thirdly, we prove the MPEC-Mangasarian-Fromovitz constraint qualification
(MPEC-MFCQ, for short) property for each feasible point of our MPEC. The MPEC-
MFCQ is a key property to guarantee the convergence of the GRM. We show that
it automatically holds for our problem thanks to its special structure.
Finally, we conduct extensive numerical experiments, which show that our
method is very efficient; in particular, it enjoys superior generalization
performance over almost all the data sets used in this paper.

The paper is organized as follows. In Section 2, based on T-fold cross-
validation for SVC, we introduce a bilevel optimization model to select an
optimal hyperparameter for SVC. We also analyze the interesting properties of
the lower-level problem. In Section 3, we reformulate the bilevel optimization
problem as an MPEC (also known as the KKT reformulation), and apply the GRM
for solving the MPEC. In Section 4, we prove that every feasible point of this
MPEC satisfies the regularity condition MPEC-MFCQ, which is a key property to
guarantee the convergence of the GRM. In Section 5, we present some
computational experiments comparing the resulting GR-CV based on the GRM with
two other ones, which have been used in the literature for a similar purpose;
i.e., the inexact cross-validation method (In-CV) and the grid search method
(G-S). We conclude the paper in Section 6.

Notations. For $x\in\mathbb{R}^{n}$, $\|x\|_{0}$ denotes the number of nonzero
elements in $x$, while $\|x\|_{1}$ and $\|x\|_{2}$ correspond to the
$l_{1}$-norm and $l_{2}$-norm of $x$, respectively. Also, we will use
$x_{+}=((x_{1})_{+},\ \cdots,\ (x_{n})_{+})\in\mathbb{R}^{n},$ where
$(x_{i})_{+}=\max(x_{i},\ 0).\ \mid\\!\Omega\\!\mid$ denotes the number of
elements in the set $\Omega\subset\mathbb{R}^{n}$. We use $\mathbf{1}_{k}$ to
denote a vector with elements all ones in $\mathbb{R}^{k}$. $I_{k}$ is the
identity matrix in $\mathbb{R}^{k\times k}$, while $e^{k}_{\gamma}$ is the
$\gamma$-th row vector of an identity matrix in $\mathbb{R}^{k\times k}$. The
notation $\mathbf{0}_{k\times q}$ represents a zero matrix in
$\mathbb{R}^{k\times q}$ and $\mathbf{0}_{k}$ stands for a zero vector in
$\mathbb{R}^{k}$. On the other hand, $\mathbf{0}_{(\tau,\ \kappa)}$ will be
used for a submatrix of the zero matrix, where $\tau$ is the index set of the
rows and $\kappa$ is the index set of the columns. Similarly to the case of
zero matrix, $I_{(\tau,\ \tau)}$ corresponds to a submatrix of an identity
matrix indexed by both rows and columns in the set $\tau$. Finally,
$\Theta_{(\tau,\ \cdot)}$ represents a submatrix of the matrix $\Theta$, where
$\tau$ is the index set of the rows, and $x_{\tau}$ is a subvector of the
vector $x$ corresponding to the index set $\tau$.

##  2 Bilevel hyperparameter optimization for SVC

We start this section by first introducing the problem settings in relation to
the T-fold cross-validation for SVC. Subsequently, we present the lower-level
problem with some interesting and relevant properties for further analysis in
the later parts of the paper. Finally, we introduce the upper-level problem,
that is, the bilevel optimization model for hyperparameter selection in SVC.

###  2.1 T-fold cross-validation for SVC

As discussed in the introduction, the most commonly used method for selecting
the hyperparameter $C$ is $T$-fold cross-validation. In $T$-fold cross-
validation, the data set is split into a subset $\Omega$ with $l_{1}$ points,
which is used for cross-validation, and a hold-out test set $\Theta$ with
$l_{2}$ points. Here,
$\Omega=\\{(x_{i},y_{i})\\}_{i=1}^{l_{1}}\in\mathbb{R}^{n+1}$, where
$x_{i}\in\mathbb{R}^{n}$ denotes a data point and $y_{i}\in\\{\pm 1\\}$ the
corresponding label. For T-fold cross-validation, $\Omega$ is equally
partitioned into $T$ pairwise disjoint subsets, one for each fold. The process
is executed T iterations. For the $t$-th iteration ($t=1,\ldots,T$), the
$t$-th fold is the validation set $\Omega_{t}$, and the remaining $T-1$ folds
make up the training set $\overline{\Omega}_{t}=\Omega\backslash\Omega_{t}$.
Therefore, in the $t$-th iteration, the separating hyperplane is trained using
the training set $\overline{\Omega}_{t}$, and the validation error is computed
on the validation set $\Omega_{t}$.

Then, the cross-validation error (CV error) is the average of the validation
error over all the $T$ iterations. The value of $C$ that gives the best CV
error will be selected. Finally, the final classifier is trained using all the
data in $\Omega$ and the rescaled optimal $C$. The test error is computed on
the test set $\Theta$. Note that the CV error and the test error are the
evaluation indices for the classification performance in T-fold cross-
validation. As shown in Figure 1, for three-fold cross-validation, the yellow
part is the subset $\Omega$ which is used for three-fold cross-validation. In
the first iteration, the blue part is the validation set $\Omega_{1}$, and the
remaining two folds are the training set $\overline{\Omega}_{1}$. The second
and third iterations have similar meanings.

Figure 1: Three-fold cross-validation.

Let $m_{1}$ be the size of the validation set $\Omega_{t}$ and $m_{2}$ the
size of the training set $\overline{\Omega}_{t}$. The corresponding index sets
for the validation and training sets are $\mathcal{N}_{t}$ and
$\overline{\mathcal{N}}_{t}$, respectively. In T-fold cross-validation, there
are $T$ validation sets. Therefore, there are totally $Tm_{1}$ validation
points in T-fold cross-validation. We use the index set

$Q_{u}:=\\{i\ \mid\ i=1,\ 2,\ \cdots,\ Tm_{1}\\}$ (1)

to represent all the validation points in T-fold cross-validation. Similarly,
there are totally $Tm_{2}$ training points in T-fold cross-validation. We use
the index set

$Q_{l}:=\\{i\ \mid\ i=1,\ 2,\ \cdots,\ Tm_{2}\\}$ (2)

to represent all the training points in T-fold cross-validation. These two
index sets will be used later.

Before analyzing different cases of the data points in the training set and
the validation set, we use Figure 2 to show geometric relationships of
different cases in soft-margin support vector classification (without bias
term) cristianini2000introduction ; galli2021study . Specifically, we consider
an $l_{1}$-loss SVC model as the lower-level problem.

For a sample $(x_{i},y_{i})$, the point $x_{i}$ is referred to as a positive
point if $y_{i}=1$; the point $x_{i}$ is referred to as a negative point if
$y_{i}=-1$. In Figure 2, the plus signs ‘$+$’ are the positive points (i.e.,
$y_{i}=1$) and the minus signs ‘$-$’ are the negative ones (i.e., $y_{i}=-1$).
The distance between the hyperplanes $H_{1}:w^{\top}x=1$ and
$H_{2}:w^{\top}x=-1$ is called _margin_. The _separating hyperplane_ $H$ lies
between $H_{1}$ and $H_{2}$. Clearly, the hyperplanes $H_{1}$ and $H_{2}$ are
the boundaries of the margin. Therefore, if a positive point lies on the
hyperplane $H_{1}$ or a negative point lies on the hyperplane $H_{2}$, we call
it lying on the boundary of the margin (indicated by ‘①’ in Figure 2). If a
positive point lies between the separating hyperplane $H$ and the hyperplane
$H_{1}$, or a negative point lies between the separating hyperplane $H$ and
the hyperplane $H_{2}$, we call it lying between the separating hyperplane $H$
and the boundary of the margin (indicated by ‘②’ in Figure 2). Similarly, if a
positive point lies on the correctly classified side of the hyperplane
$H_{1}$, or a negative point lies on the correctly classified side of the
hyperplane $H_{2}$, we call it lying on the correctly classified side of the
boundary of the margin (indicated by ‘③’ in Figure 2).

Figure 2: Training points in soft-margin support vector machine.

Based on Figure 2, we have the following observations which address different
cases for the data points in the training set.

######  Proposition 1.

Let $w^{t}$ be an optimal solution of the $t$-th lower-level problem
($l_{1}$-loss SVC model). For $i\in\overline{\mathcal{N}}_{t}$, consider a
positive point $x_{i}$. Then it holds that:

  * (a)

$x_{i}$ satisfies $(w^{t})^{\top}x_{i}<0$ if and only if it lies on the
misclassified side of the separating hyperplane $H$, and is therefore
misclassified.

  * (b)

$x_{i}$ satisfies $(w^{t})^{\top}x_{i}=0$ if and only if it lies on the
separating hyperplane $H$, and is therefore correctly classified.

  * (c)

$x_{i}$ satisfies $0<(w^{t})^{\top}x_{i}<1$ if and only if it lies between the
separating hyperplane $H$ and the boundary of the margin; hence, it is
correctly classified.

  * (d)

$x_{i}$ satisfies $(w^{t})^{\top}x_{i}=1$ if and only if it lies on the
boundary of the margin, and is therefore correctly classified.

  * (e)

$x_{i}$ satisfies $(w^{t})^{\top}x_{i}>1$ if and only if it lies on the
correctly classified side of the boundary of the margin, and is therefore
correctly classified.

A result analogous to Proposition 1 can be stated for the negative points. In
Figure 3, any point $x_{i}\in\overline{\Omega}_{t}$ in blue is a training
point in each case (notation is the same as in Figure 5).

(a) (a) $(w^{t})^{\top}x_{i}<0.$ (b) (b) $(w^{t})^{\top}x_{i}=0.$ (c) (c)
$0<(w^{t})^{\top}x_{i}<1.$ (d) (d) $(w^{t})^{\top}x_{i}=1.$

(e) (e) $(w^{t})^{\top}x_{i}>1.$

Figure 3: Each case for different values of $(w^{t})^{\top}x_{i}$ in the
training set.

As for data points in the validation set, we have the following scenarios.

######  Proposition 2.

Let $w^{t}$ be an optimal solution of the $t$-th lower-level problem. For
$i\in\mathcal{N}_{t}$, consider a positive point $x_{i}$. Then it holds that:

  * (a)

$x_{i}$ satisfies $(w^{t})^{\top}x_{i}<0$ if and only if it lies on the
misclassified side of the separating hyperplane $H$, and is therefore
misclassified.

  * (b)

$x_{i}$ satisfies $(w^{t})^{\top}x_{i}=0$ if and only if it lies on the
separating hyperplane $H$, and is therefore correctly classified.

  * (c)

$x_{i}$ satisfies $(w^{t})^{\top}x_{i}>0$ if and only if it lies on the
correctly classified side of the separating hyperplane $H$, and it is hence
correctly classified.

A result analogous to Proposition 2 can be stated for the negative points. In
Figure 4, any point $x_{i}\in\Omega_{t}$ in blue is a validation point in each
case (notation is the same as in Figure 6). Note that Propositions 1 and 2
will be used in the proof of Propositions 3 and 4.

(a) (a) $(w^{t})^{\top}x_{i}<0.$ (b) (b) $(w^{t})^{\top}x_{i}=0.$ (c) (c)
$(w^{t})^{\top}x_{i}>0.$

Figure 4: Each case for different values of $(w^{t})^{\top}x_{i}$ in the
validation set.

###  2.2 The lower-level problem

In this part, we focus on the lower-level problem. That is, given
hyperparameter $C$ and the training set $\overline{\Omega}_{t}$, we train the
dataset via $l_{1}$-loss SVC model. We will also discuss the properties of the
lower-level problem.

####  2.2.1 The training model: $l_{1}$-loss SVC

In T-fold cross-validation, there are T lower-level problems. In the $t$-th
lower-level problem, we train the $t$-th fold training data set
$\overline{\Omega}_{t}$ by the $l_{1}$-loss SVC model without bias term
galli2021study ; mangasarian1994misclassification ; hsieh2008dual . That is,
given $C$, we solve the following optimization problem:

$\underset{w^{t}\in\mathbb{R}^{n}}{\operatorname{min}}\frac{1}{2}\|w^{t}\|_{2}^{2}+C\sum_{i\in\overline{\mathcal{N}}_{t}}(\mathbf{1}-y_{i}(x_{i}^{\top}w^{t}))_{+}.$

A popular reformulation of the problem above is the convex quadratic
optimization problem obtained by introducing slack variables
$\xi^{t}\in\mathbb{R}^{m_{2}}$:

$\begin{array}[]{l}\underset{w^{t}\in\mathbf{R}^{n},\xi^{t}\in\mathbf{R}^{m_{2}}}{\min}\quad\frac{1}{2}\left\|w^{t}\right\|_{2}^{2}+C\sum\limits_{i=1}^{m_{2}}\xi^{t}_{i}\\\
\quad\quad\ \hbox{s.t.}\quad\quad\quad\ B^{t}w^{t}\geq\mathbf{1}-\xi^{t},\\\
\quad\quad\quad\quad\quad\quad\quad\xi^{t}\geq\mathbf{0},\end{array}$ (3)

where, for $t=1,\cdots,T$ and $k=m_{1}+1,\cdots,l_{1}$, we have

$B^{t}\\!=\\!\left[\begin{array}[]{c}y_{t_{m_{1}+1}}x_{t_{m_{1}+1}}^{\top}\\\
\vdots\\\
y_{t_{l_{1}}}x_{t_{l_{1}}}^{\top}\end{array}\right]\\!\in\\!\mathbb{R}^{m_{2}\times
n},\;\;\,(x_{t_{k}},y_{t_{k}})\in\overline{\Omega}_{t},$

and we use $\xi^{t}_{i}$ to denote the $i$-th element of
$\xi^{t}\in\mathbb{R}^{m_{2}}$.

Let $\alpha^{t}\in\mathbb{R}^{m_{2}}$ and $\mu^{t}\in\mathbb{R}^{m_{2}}$ be
the multipliers of the constraints in (3). We can write the KKT conditions for
the lower-level problem (3) as

$\displaystyle\mathbf{0}\leq\alpha^{t}\perp
B^{t}w^{t}-\mathbf{1}+\xi^{t}\geq\mathbf{0},$ (4a)
$\displaystyle\mathbf{0}\leq\xi^{t}\perp\mu^{t}\geq\mathbf{0},$ (4b)
$\displaystyle w^{t}-(B^{t})^{\top}\alpha^{t}=\mathbf{0},$ (4c) $\displaystyle
C\mathbf{1}-\alpha^{t}-\mu^{t}=\mathbf{0},$ (4d)

where for two vectors $a$ and $b$, writing $\mathbf{0}\leq a\perp
b\geq\mathbf{0}$ means that we have $a^{\top}b=0,\ a\geq\mathbf{0}$ and
$b\geq\mathbf{0}$. Also note that each complementary constraint in (4a)
corresponds to a training point $x_{i}$ with $i\in Q_{l}$ (2). Each training
point corresponds to a slack variable $\xi^{t}_{i}$. So we have each
complementary constraint in (4b) corresponds to a training point $x_{i}$ with
$i\in Q_{l}$ (2). Therefore, there is a one-to-one correspondence between the
index set of the training points $Q_{l}$ and the complementary constraints in
(4a) and (4b), respectively. This will be used in the definition of some index
sets below.

Furthermore, we would like to emphasize the support vectors implied in (4).
From (4c), the weight vector
$w^{t}=(B^{t})^{\top}\alpha^{t}=\sum\limits_{i\in\overline{\mathcal{N}}_{t}}\alpha^{t}_{i}y_{i}x_{i}$.
It implies that only the data points $x_{i}\in\overline{\Omega}_{t}$ which
correspond to $\alpha^{t}_{i}\neq 0$ are involved. By $\alpha^{t}_{i}\geq 0$
in (4a), it means that only $x_{i}\in\overline{\Omega}_{t}$ with
$\alpha^{t}_{i}>0$ are involved. It is for this reason that they are called
_support vectors_. By eliminating $\mu^{t}$ and $w^{t}$ from the system in
(4), we get the reduced KKT conditions for problem (3) as follows:

$\left\\{\begin{aligned} &\mathbf{0}\leq\alpha^{t}\perp
B^{t}(B^{t})^{\top}\alpha^{t}-\mathbf{1}+\xi^{t}\geq\mathbf{0},\\\
&\mathbf{0}\leq\xi^{t}\perp
C\mathbf{1}-\alpha^{t}\geq\mathbf{0}.\end{aligned}\right.$ (5)

####  2.2.2 Some properties of the lower-level problem

Let $\alpha\in\mathbb{R}^{Tm_{2}},\ \xi\in\mathbb{R}^{Tm_{2}},\
w\in\mathbb{R}^{Tn}$, and $B\in\mathbb{R}^{Tm_{2}\times Tn}$ be defined by

$\alpha:=\left[\begin{array}[]{l}\alpha^{1}\\\ \alpha^{2}\\\ \vdots\\\
\alpha^{T}\end{array}\right],\,\xi:=\left[\begin{array}[]{l}\xi^{1}\\\
\xi^{2}\\\ \vdots\\\
\xi^{T}\end{array}\right],\,w:=\left[\begin{array}[]{l}w^{1}\\\ w^{2}\\\
\vdots\\\ w^{T}\end{array}\right],\,\mbox{ and
}\,B:=\left[\begin{array}[]{cccc}B^{1}&\mathbf{0}&\cdots&\mathbf{0}\\\
\mathbf{0}&B^{2}&\cdots&\mathbf{0}\\\ \vdots&\vdots&\ddots&\vdots\\\
\mathbf{0}&\mathbf{0}&\cdots&B^{T}\end{array}\right],$ (6)

respectively. The KKT conditions in (5) can be decomposed as

$\displaystyle\Lambda_{1}$ $\displaystyle:=$ $\displaystyle\\{i\in Q_{l}\
\mid\ \alpha_{i}=0,\ (BB^{\top}\alpha-\mathbf{1}+\xi)_{i}=0,\ \xi_{i}=0\\},$
(7) $\displaystyle\Lambda_{2}$ $\displaystyle:=$ $\displaystyle\\{i\in Q_{l}\
\mid\ \alpha_{i}=0,\ (BB^{\top}\alpha-\mathbf{1}+\xi)_{i}>0,\ \xi_{i}=0\\},$
(8) $\displaystyle\Lambda_{3}$ $\displaystyle:=$ $\displaystyle\\{i\in Q_{l}\
\mid\ 0<\alpha_{i}\leq C,\ (BB^{\top}\alpha-\mathbf{1}+\xi)_{i}=0,\
\xi_{i}=0\\},$ (9) $\displaystyle\Lambda_{4}$ $\displaystyle:=$
$\displaystyle\\{i\in Q_{l}\ \mid\ \alpha_{i}=C,\
(BB^{\top}\alpha-\mathbf{1}+\xi)_{i}=0,\ 0<\xi_{i}<1\\},$ (10)
$\displaystyle\Lambda_{5}$ $\displaystyle:=$ $\displaystyle\\{i\in Q_{l}\
\mid\ \alpha_{i}=C,\ (BB^{\top}\alpha-\mathbf{1}+\xi)_{i}=0,\ \xi_{i}=1\\},$
(11) $\displaystyle\Lambda_{6}$ $\displaystyle:=$ $\displaystyle\\{i\in Q_{l}\
\mid\ \alpha_{i}=C,\ (BB^{\top}\alpha-\mathbf{1}+\xi)_{i}=0,\ \xi_{i}>1\\}.$
(12)

Obviously, the intersection of any pair of these index sets $\Lambda_{i}$ for
$i=1,\ldots,6$ is empty. An illustrative representation of data points
corresponding to these index sets is given in Figure 5.

(a) (a) Points with indices in $\Lambda_{1}$ (b) (b) Points with indices in
$\Lambda_{2}$ (c) (c) Points with indices in $\Lambda_{3}$ (d) (d) Points with
indices in $\Lambda_{4}$

(e) (e) Points with indices in $\Lambda_{5}$ (f) (f) Points with indices in
$\Lambda_{6}$

Figure 5: Representation of points with index sets $\Lambda_{j}$,
$j=1,\ldots,6$

######  Proposition 3.

Considering the training points corresponding to $Q_{l}$ in (2), let
$(\alpha,\,\xi)$ satisfy the conditions in (5). Then, the following statements
hold true:

  * (a)

The points $\\{x_{i}\\}_{i\in\Lambda_{1}}$ lie on the boundary of the margin;
they are correctly classified points, but are not support vectors.

  * (b)

The points $\\{x_{i}\\}_{i\in\Lambda_{2}}$ lie on the correctly classified
side of the boundary of the margin; they are correctly classified points, but
are not support vectors.

  * (c)

The points $\\{x_{i}\\}_{i\in\Lambda_{3}}$ lie on the boundary of the margin;
they are correctly classified points and are support vectors.

  * (d)

The points $\\{x_{i}\\}_{i\in\Lambda_{4}}$ lie between the separating
hyperplane $H$ and the boundary of the margin; they are correctly classified
therefore support vectors.

  * (e)

The points $\\{x_{i}\\}_{i\in\Lambda_{5}}$ lie on the separating hyperplane
$H$; they are correctly classified points and are support vectors.

  * (f)

The points $\\{x_{i}\\}_{i\in\Lambda_{6}}$ lie on the misclassified side of
the separating hyperplane $H$; they are misclassified points and are support
vectors.

Proof: We take positive points for example. The same analysis can be applied
to negative ones. Since $w=B^{\top}\alpha$ in (4c), we get
$(BB^{\top}\alpha-\mathbf{1}+\xi)_{i}=(Bw-\mathbf{1}+\xi)_{i}$.

  * (a)

For the points $\\{x_{i}\\}_{i\in\Lambda_{1}}$, since $\xi_{i}=0$ in (7), we
have $(Bw-\mathbf{1}+\xi)_{i}=(Bw-\mathbf{1})_{i}=0$, that is,
$y_{i}(w^{\top}x_{i})-1=0$. For a positive point, $y_{i}=1$, it implies that
$w^{\top}x_{i}=1$. It corresponds to (d) in Proposition 1. Therefore, it means
that the point $x_{i}$ lies on the boundary of the margin. It is correctly
classified, and it is not a support vector, since $\alpha_{i}=0$.

  * (b)

For the points $\\{x_{i}\\}_{i\in\Lambda_{2}}$, since $\xi_{i}=0$ in (8), we
have $(Bw-\mathbf{1}+\xi)_{i}=(Bw-\mathbf{1})_{i}>0$, that is,
$y_{i}(w^{\top}x_{i})-1>0$. For a positive point, $y_{i}=1$, it implies that
$w^{\top}x_{i}>1$. It corresponds to (e) in Proposition 1. Therefore, it means
that the point $x_{i}$ lies on the correctly classified side of the boundary
of the margin. It is correctly classified, but not a support vector, as
$\alpha_{i}=0$.

  * (c)

For the points $\\{x_{i}\\}_{i\in\Lambda_{3}}$, since $\xi_{i}=0$ in (9), we
have $(Bw-\mathbf{1}+\xi)_{i}=(Bw-\mathbf{1})_{i}=0$, that is,
$y_{i}(w^{\top}x_{i})-1=0$. For a positive point, $y_{i}=1$, it implies that
$w^{\top}x_{i}=1$. It corresponds to (d) in Proposition 1. Therefore, it means
that the point $x_{i}$ lies on the boundary of the margin. It is correctly
classified, and it is a support vector, since $\alpha_{i}>0$.

  * (d)

For the points $\\{x_{i}\\}_{i\in\Lambda_{4}}$, since $0<\xi_{i}<1$ in (10),
we have $0<(Bw)_{i}<1$, that is, $0<y_{i}(w^{\top}x_{i})<1$. For a positive
point, $y_{i}=1$, it implies that $0<w^{\top}x_{i}<1$. It corresponds to (c)
in Proposition 1. Therefore, $x_{i}$ lies between the separating hyperplane
$H$ and the boundary of the margin. It is correctly classified, and it is a
support vector, since $\alpha_{i}>0$.

  * (e)

For the points $\\{x_{i}\\}_{i\in\Lambda_{5}}$, since $\xi_{i}=1$ in (11), we
have $(Bw-\mathbf{1}+\xi)_{i}=(Bw)_{i}=0$, that is, $y_{i}(w^{\top}x_{i})=0$.
For a positive point, $y_{i}=1$, it implies that $w^{\top}x_{i}=0$. It
corresponds to (b) in Proposition 1. Therefore, it means that the point
$x_{i}$ lies on the separating hyperplane $H$. It is correctly classified, and
it is a support vector, since $\alpha_{i}>0$.

  * (f)

For the points $\\{x_{i}\\}_{i\in\Lambda_{6}}$, since $\xi_{i}>1$ in (12), we
have $(Bw)_{i}<0$, that is, $y_{i}(w^{\top}x_{i})<0$. For a positive point,
$y_{i}=1$, it implies that $w^{\top}x_{i}<0$. It corresponds to (a) in
Proposition 1. Therefore, it means that the point $x_{i}$ lies on the
misclassified side of the separating hyperplane $H$. It is misclassified, and
it is a support vector, since $\alpha_{i}>0$.

###  2.3 The upper-level problem

In this part, we introduce the upper-level problem, that is, the bilevel
optimization model for hyperparameter selection in SVC under the settings of
T-fold cross-validation. Note that the aim of the upper-level problem is to
minimize the T-fold cross-validation error (CV error) measured on the
validation sets based on the optimal solutions of the lower-level problems.
Specifically, the basic bilevel optimization model for selecting the
hyperparameter $C$ in SVC is formulated as

$\displaystyle\min\limits_{C\in\mathbb{R},\ w^{t}\in\mathbb{R}^{n},\
j=1,\cdots,T}$
$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\frac{1}{m_{1}}\sum_{i\in\mathcal{N}_{t}}\|\left(-y_{i}\left(x_{i}^{\top}w^{t}\right)\right)_{+}\|_{0}$
(13) s.t. $\displaystyle C\geq 0,$ $\displaystyle\text{and for}\quad
t=1,\cdots,T:$ $\displaystyle
w^{t}\in\underset{w\in\mathbb{R}^{n}}{\operatorname{argmin}}\left\\{\frac{1}{2}\|w\|_{2}^{2}+C\sum_{i\in\overline{\mathcal{N}}_{t}}\left(\mathbf{1}-y_{i}\left(x_{i}^{\top}w\right)\right)_{+}\right\\}.$

Here, the expression
$\sum_{i\in\mathcal{N}_{t}}\|\left(-y_{i}\left(x_{i}^{\top}w^{t}\right)\right)_{+}\|_{0}$
basically counts the number of data points that are misclassified in the
validation set $\Omega_{t}$, while the outer summation (i.e., the objective
function in (13)) averages the misclassification error over all the folds.

Problem (13) can be equivalently written in the matrix form as follows

$\displaystyle\min\limits_{C\in\mathbb{R},\ w^{t}\in\mathbb{R}^{n},\
j=1,\cdots,T}$
$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\frac{1}{m_{1}}\|\left(-A^{t}w^{t}\right)_{+}\|_{0}$
(14) s.t. $\displaystyle C\geq 0,$ $\displaystyle\text{and for}\quad
t=1,\cdots,T:$ $\displaystyle
w^{t}\in\underset{w\in\mathbb{R}^{n}}{\operatorname{argmin}}\left\\{\frac{1}{2}\|w\|_{2}^{2}+C\|\left(\mathbf{1}-B^{t}w\right)_{+}\|_{1}\right\\},$

where, for $t=1,\ \cdots,\ T$ and $k=1,\ \cdots,\ m_{1}$, we have

$A^{t}=\left[\begin{array}[]{c}y_{t_{1}}x_{t_{1}}^{\top}\\\ \vdots\\\
y_{t_{m_{1}}}x_{t_{m_{1}}}^{\top}\end{array}\right]\in\mathbb{R}^{m_{1}\times
n}\;\,\mbox{ and }\;\,(x_{t_{k}},y_{t_{k}})\in\Omega_{t}.$

######  Remark 1.

Compared with the model in kunapuli2008classification , for example, we
consider a simpler bilevel optimization model, without the box constraints in
the upper-level problem,

##  3 Single-level reformulation and method

In this section, we first reformulate the bilevel optimization problem as a
single-level optimization problem, precisely, we write the problem as an MPEC.
Then we present the properties of this single-level problem. Finally, we
discuss the GRM to solve the MPEC problem.

###  3.1 The MPEC reformulation

Recall the upper-level objective function in (14) is a measure of
misclassification error based on the $T$ out-of-sample validation sets, which
we minimize. The measure used here is the classical cross-validation error (CV
error) for classification, the average number of the data points
misclassified. It is clear that $\|(\cdot)_{+}\|_{0}$ is discontinuous and
nonconvex. However, the function $\|(\cdot)_{+}\|_{0}$ can be characterized as
the sum of all elements of the solution to the following linear optimization
problem as demonstrated in mangasarian1994misclassification , i.e.,

$\|r_{+}\|_{0}=\left\\{\sum\limits_{i=1}^{m_{1}}\zeta_{i}:\;\zeta=\underset{u}{\operatorname{argmin}}\left\\{-u^{\top}r\
:\ \mathbf{0}\leq u\leq\mathbf{1}\right\\}\right\\}.$

Therefore, for each fold, $\|\left(-A^{t}w^{t}\right)_{+}\|_{0}$ is the sum of
all elements of the solution to the following linear optimization problem:

$\displaystyle\min\limits_{\zeta^{t}\in\mathbb{R}^{m_{1}}}\
-(\zeta^{t})^{\top}(-A^{t}w^{t})$ (15) $\displaystyle\ \
\begin{array}[]{ll}\hbox{s.t.}\ \ \zeta^{t}\geq\mathbf{0},\\\
\quad\quad\mathbf{1}-\zeta^{t}\geq\mathbf{0}.\end{array}$

This implies that
$\|\left(-A^{t}w^{t}\right)_{+}\|_{0}=\sum\limits_{i=1}^{m_{1}}\zeta^{t}_{i}$
in each fold. According to Proposition 2, there are two cases for the
validation points:

  * 1.

If the validation point $(x_{i},y_{i})\in\Omega_{t}$ is misclassified, then
$y_{i}\left(x_{i}^{\top}w^{t}\right)<0$. That is, $(-A^{t}w^{t})_{i}>0$, which
corresponds to $(\left(-A^{t}w^{t}\right)_{+})_{i}>0$.

  * 2.

If the validation point $(x_{i},y_{i})\in\Omega_{t}$ is correctly classified,
we have $y_{i}\left(x_{i}^{\top}w^{t}\right)\geq 0$. There are two cases.
Firstly, $x_{i}$ lies on the separating hyperplane $H$, that is,
$y_{i}\left(x_{i}^{\top}w^{t}\right)=0$. For $y_{i}=1$, there is
$(-A^{t}w^{t})_{i}=0$, which corresponds to
$(\left(-A^{t}w^{t}\right)_{+})_{i}=0$. Secondly, $x_{i}$ lies on the
correctly classified side of the separating hyperplane $H$, that is,
$y_{i}\left(x_{i}^{\top}w^{t}\right)>0$. For $y_{i}=1$, there is
$(-A^{t}w^{t})_{i}<0$, which corresponds to
$(\left(-A^{t}w^{t}\right)_{+})_{i}=0$.

Combining with
$\|\left(-A^{t}w^{t}\right)_{+}\|_{0}=\sum\limits_{i=1}^{m_{1}}\zeta^{t}_{i}$,
it means that

$\zeta^{t}_{i}=\left\\{\begin{array}[]{ll}1,\quad\quad\text{if}\quad(x_{i},y_{i})\in\Omega_{t}\
\text{is misclassified},\\\
0,\quad\quad\text{if}\quad(x_{i},y_{i})\in\Omega_{t}\ \text{is correctly
classified},\end{array}\right.$ (16)

where $\zeta^{t}_{i}$ is the $i$-th element of $\zeta^{t}$ in the $t$-th fold.

The linear programs (LPs) (15), for $t=1,\ldots,T$, are inserted into the
bilevel optimization problem in order to recast the discontinuous upper-level
objective function into a continuous one. Each LP in the form of (15) can also
be replaced with its KKT conditions as follows

$\left\\{\begin{aligned}
&\begin{array}[]{l}\mathbf{0}\leq\zeta^{t}\perp\lambda^{t}\geq\mathbf{0},\\\
\mathbf{0}\leq z^{t}\perp\mathbf{1}-\zeta^{t}\geq\mathbf{0},\\\
A^{t}w^{t}-\lambda^{t}+z^{t}=\mathbf{0}.\end{array}\end{aligned}\right.$

By eliminating $\lambda^{t}$ and $w^{t}$ with $w^{t}=(B^{t})^{\top}\alpha^{t}$
in (4c), we get the reduced KKT conditions for problem (15) with

$\displaystyle\mathbf{0}\leq\zeta^{t}\perp
A^{t}(B^{t})^{\top}\alpha^{t}+z^{t}\geq\mathbf{0},$ (17a)
$\displaystyle\mathbf{0}\leq z^{t}\perp\mathbf{1}-\zeta^{t}\geq\mathbf{0}.$
(17b)

Note that each complementary constraint in (17a) corresponds to a validation
point $x_{i}$ with $i\in Q_{u}$ (1). Each validation point corresponds to a
variable $\zeta^{t}_{i}$. So we have each complementary constraint in (17b)
corresponds to a validation point $x_{i}$ with $i\in Q_{u}$ (1). Therefore,
there is a one-to-one correspondence between the index set of the validation
points $Q_{u}$ and the complementary constraints in (17a) and (17b),
respectively.

Combining the systems in (5) and (17), we can transform the bilevel
optimization problem (14) into the single-level optimization problem

$\displaystyle\min_{\begin{subarray}{l}\quad\quad\ C\in\mathbb{R}\\\
\zeta^{t}\in\mathbb{R}^{m_{1}},\ z^{t}\in\mathbb{R}^{m_{1}}\\\
\alpha^{t}\in\mathbb{R}^{m_{2}},\ \xi^{t}\in\mathbb{R}^{m_{2}}\\\ \quad\ t=1,\
\cdots,\ T\end{subarray}}$
$\displaystyle\frac{1}{Tm_{1}}\sum_{i=1}^{m_{1}}\sum_{t=1}^{T}\zeta^{t}_{i}$
(18) s.t. $\displaystyle C\geq 0,$ $\displaystyle\text{and for}\quad t=1,\
\cdots,\ T:$
$\displaystyle\left\\{\begin{array}[]{ll}\mathbf{0}\leq\zeta^{t}\perp
A^{t}(B^{t})^{\top}\alpha^{t}+z^{t}\geq\mathbf{0},\\\ \mathbf{0}\leq
z^{t}\perp\mathbf{1}-\zeta^{t}\geq\mathbf{0},\\\ \mathbf{0}\leq\alpha^{t}\perp
B^{t}(B^{t})^{\top}\alpha^{t}-\mathbf{1}+\xi^{t}\geq\mathbf{0},\\\
\mathbf{0}\leq\xi^{t}\perp
C\mathbf{1}-\alpha^{t}\geq\mathbf{0}.\end{array}\right.$

Note that the constraints $C\mathbf{1}-\alpha^{t}\geq\mathbf{0}$ and
$\alpha^{t}\geq\mathbf{0}$ imply $C\geq 0$. Therefore, we remove the redundant
constraint $C\geq 0$, and get an equivalent form of the problem above as
follows

$\displaystyle\min_{\begin{subarray}{l}\quad\quad\ C\in\mathbb{R}\\\
\zeta^{t}\in\mathbb{R}^{m_{1}},\ z^{t}\in\mathbb{R}^{m_{1}}\\\
\alpha^{t}\in\mathbb{R}^{m_{2}},\ \xi^{t}\in\mathbb{R}^{m_{2}}\\\ \quad\ t=1,\
\cdots,\ T\end{subarray}}$
$\displaystyle\frac{1}{Tm_{1}}\sum_{i=1}^{m_{1}}\sum_{t=1}^{T}\zeta^{t}_{i}$
(19) s.t. $\displaystyle\text{for}\quad t=1,\ \cdots,\ T:$
$\displaystyle\left\\{\begin{array}[]{ll}\mathbf{0}\leq\zeta^{t}\perp
A^{t}(B^{t})^{\top}\alpha^{t}+z^{t}\geq\mathbf{0},\\\ \mathbf{0}\leq
z^{t}\perp\mathbf{1}-\zeta^{t}\geq\mathbf{0},\\\ \mathbf{0}\leq\alpha^{t}\perp
B^{t}(B^{t})^{\top}\alpha^{t}-\mathbf{1}+\xi^{t}\geq\mathbf{0},\\\
\mathbf{0}\leq\xi^{t}\perp
C\mathbf{1}-\alpha^{t}\geq\mathbf{0}.\end{array}\right.$

The presence of the equilibrium constraints makes problem (19) an instance of
an MPEC, which is sometimes labelled as an extension of a bilevel optimization
problem luo1996mathematical . The optimal hyperparameter is now well defined
as a global optimal solution to the MPEC lee2015global . Now that we have
transformed a bilevel classification model into the MPEC (19), we can rewrite
it in a compact form

$\displaystyle\min_{\begin{subarray}{c}C\in\mathbb{R}\\\
\zeta\in\mathbb{R}^{Tm_{1}},\ z\in\mathbb{R}^{Tm_{1}}\\\
\alpha\in\mathbb{R}^{Tm_{2}},\
\xi\in\mathbb{R}^{Tm_{2}}\end{subarray}}\frac{1}{Tm_{1}}\mathbf{1}^{\top}\zeta$
(20) $\displaystyle\quad\quad\ \begin{array}[]{ll}\hbox{s.t.}\ \
\mathbf{0}\leq\zeta\perp AB^{\top}\alpha+z\geq\mathbf{0},\\\
\quad\quad\mathbf{0}\leq z\perp\mathbf{1}-\zeta\geq\mathbf{0},\\\
\quad\quad\mathbf{0}\leq\alpha\perp
BB^{\top}\alpha-\mathbf{1}+\xi\geq\mathbf{0},\\\
\quad\quad\mathbf{0}\leq\xi\perp C\mathbf{1}-\alpha\geq\mathbf{0},\end{array}$

where $\alpha$, $\xi$ and $B$ are defined in (6), while

$\begin{array}[]{c}\zeta\\!:=\\!\left[\begin{array}[]{l}\zeta^{1}\\\
\zeta^{2}\\\ \vdots\\\
\zeta^{T}\end{array}\right]\\!\in\\!\mathbb{R}^{Tm_{1}},\
z\\!:=\\!\left[\begin{array}[]{l}z^{1}\\\ z^{2}\\\ \vdots\\\
z^{T}\end{array}\right]\\!\in\\!\mathbb{R}^{Tm_{1}},\
A:=\left[\begin{array}[]{cccc}A^{1}&\mathbf{0}&\cdots&\mathbf{0}\\\
\mathbf{0}&A^{2}&\cdots&\mathbf{0}\\\ \vdots&\vdots&\ddots&\vdots\\\
\mathbf{0}&\mathbf{0}&\cdots&A^{T}\end{array}\right]\in\mathbb{R}^{Tm_{1}\times{Tn}},\end{array}$

From now on, all our analysis is going to be based on the model in (20).

###  3.2 Some properties of the MPEC reformulation

Observe that the last two constraints of problem (20) correspond to the
complementarity systems that are part of the KKT conditions of the lower-level
problem in (5). As the latter conditions are carefully studied in Proposition
3, it remains to analyze the first two complementarity systems describing the
feasible set of problem (20). Hence, we partition them as follows

$\displaystyle\Psi_{1}$ $\displaystyle:=$ $\displaystyle\left\\{i\in Q_{u}\
\mid\ 0\leq\zeta_{i}<1,\ (AB^{\top}\alpha+z)_{i}=0,\ z_{i}=0\right\\},$ (21)
$\displaystyle\Psi_{2}$ $\displaystyle:=$ $\displaystyle\left\\{i\in Q_{u}\
\mid\ \zeta_{i}=0,\ (AB^{\top}\alpha+z)_{i}>0,\ z_{i}=0\right\\},$ (22)
$\displaystyle\Psi_{3}$ $\displaystyle:=$ $\displaystyle\left\\{i\in Q_{u}\
\mid\ \zeta_{i}=1,\ (AB^{\top}\alpha+z)_{i}=0,\ z_{i}>0\right\\}.$ (23)

Similarly to (7)–(12), the intersection of any pair of the index sets
$\Psi_{j}$ for $j=1,\,2,\,3$ is empty. In the same vein, an illustrative
representation of data points corresponding to the index sets $\Psi_{j}$ for
$j=1,\,2,\,3$ is given in Figure 6.

(a) (a) Points with indices in $\Psi_{1}$ (b) (b) Points with indices in
$\Psi_{2}$ (c) (c) Points with indices in $\Psi_{3}$

Figure 6: Representation of points with index sets $\Psi_{j}$, $j=1,\,2,\,3$

######  Proposition 4.

Considering the validation points corresponding to $Q_{u}$ in (1), let
$(\zeta,\ z,\,\alpha)$ satisfy the first two complementarity systems
describing the feasible set of problem (20). Then, the following statements
hold true:

  * (a)

The points $\\{x_{i}\\}_{i\in\Psi_{1}}$ lie on the separating hyperplane $H$
and are therefore correctly classified.

  * (b)

The points $\\{x_{i}\\}_{i\in\Psi_{2}}$ lie on the correctly classified side
of the separating hyperplane $H$ and are therefore correctly classified.

  * (c)

The points $\\{x_{i}\\}_{i\in\Psi_{3}}$ lie on the misclassified side of the
separating hyperplane $H$ and are therefore misclassified.

Proof: We take positive points for example. The same analysis can be applied
to negative ones. Since $w=B^{\top}\alpha$ in (4c), we get
$(AB^{\top}\alpha+z)_{i}=(Aw+z)_{i}$.

  * (a)

For the points $\\{x_{i}\\}_{i\in\Psi_{1}}$, since $z_{i}=0$ in (21), we have
$(Aw+z)_{i}=(Aw)_{i}=0$, that is, $y_{i}(w^{\top}x_{i})=0$. For a positive
point, $y_{i}=1$, it implies that $w^{\top}x_{i}=0$. It corresponds to (b) in
Proposition 2. Therefore, it means that the point $x_{i}$ lies on the
separating hyperplane $H$. It is correctly classified.

  * (b)

For the points $\\{x_{i}\\}_{i\in\Psi_{2}}$, since $z_{i}=0$ in (22), we have
$(Aw+z)_{i}=(Aw)_{i}>0$, that is, $y_{i}(w^{\top}x_{i})>0$. For a positive
point, $y_{i}=1$, it implies that $w^{\top}x_{i}>0$. It corresponds to (c) in
Proposition 2. Therefore, it means that the point $x_{i}$ lies on the
correctly classified side of the separating hyperplane $H$. It is correctly
classified.

  * (c)

For the points $\\{x_{i}\\}_{i\in\Psi_{3}}$, since $z_{i}>0$ in (23), we have
$(Aw)_{i}<0$, that is, $y_{i}(w^{\top}x_{i})<0$. For a positive point,
$y_{i}=1$, it implies that $w^{\top}x_{i}<0$. It corresponds to (a) in
Proposition 2. Therefore, it means that the point $x_{i}$ lies on the
misclassified side of the separating hyperplane $H$.

In Section 4, Proposition 4 will be combined with Proposition 3 to prove
Proposition 5. It might also be important to note that if a validation point
$x_{i}$ lies on the separating hyperplane $H$, then we will have
$0\leq\zeta_{i}<1$.

###  3.3 The global relaxation method (GRM)

Here, we present a numerical algorithm to solve the MPEC (20). There are
various methods for solving MPECs, we refer to dempe2003annotated ;
luo1996mathematical for some surveys on the problem and to jane2005necessary ;
flegel2005constraint ; wu2015inexact ; harder2021reformulation ;
guo2015solving ; jara2018study ; judice2012algorithms ; li2015superlinearly ;
yu2019solving ; dempe2003annotated ; anitescu2000solving ; facchinei2007finite
; fletcher2006local ; fukushima2002implementable for some of the latest
methods to solve the problem. Among methods to solve MPECs, one of the most
popular ones is the relaxation method due to Scholtes scholtes2001convergence
. Recently, Kanzow et al. hoheisel2013theoretical provided comparisons of five
relaxation methods for solving MPECs, where it appears that the GRM has the
best theoretical (in terms of requiring weaker assumptions for convergence)
and numerical performance. Therefore, we will apply the GRM to solve our MPEC
(20).

To simplify the presentation of the method, we now write problem (20) into
further compact format. Let $v=\left[C,\ \zeta^{\top},\ z^{\top},\
\alpha^{\top},\ \xi^{\top}\right]^{\top}\in\mathbb{R}^{\overline{m}+1}$ with
$\overline{m}=2T(m_{1}+m_{2})$ and define the functions

$F(v)\\!=\\!M^{\top}v,\;\;G(v)\\!=\\!Pv+a,\;\mbox{ and }\;H(v)\\!=\\!Qv,$ (24)

where

$M\\!=\\!\frac{1}{Tm_{1}}\left[\begin{array}[]{c}0\\\ \mathbf{1}_{Tm_{1}}\\\
\mathbf{0}_{Tm_{1}}\\\ \mathbf{0}_{Tm_{2}}\\\
\mathbf{0}_{Tm_{2}}\end{array}\right]\\!\in\\!\mathbb{R}^{\overline{m}+1},\
a\\!=\\!\left[\begin{array}[]{l}\mathbf{0}_{Tm_{1}}\\\ \mathbf{1}_{Tm_{1}}\\\
-\mathbf{1}_{Tm_{2}}\\\
\mathbf{0}_{Tm_{2}}\end{array}\right]\\!\in\\!\mathbb{R}^{\overline{m}},\
Q\\!=\\!\left[\begin{array}[]{cc}\mathbf{0}_{\overline{m}}&I_{\overline{m}}\end{array}\right]\\!\in\\!\mathbb{R}^{\overline{m}\times(\overline{m}+1)},$
$P\\!=\\!\left[\begin{array}[]{ccccc}\mathbf{0}_{Tm_{1}}&\mathbf{0}_{Tm_{1}\times
Tm_{1}}&I_{Tm_{1}}&AB^{\top}&\mathbf{0}_{Tm_{1}\times Tm_{2}}\\\
\mathbf{0}_{Tm_{1}}&-I_{Tm_{1}}&\mathbf{0}_{Tm_{1}\times
Tm_{1}}&\mathbf{0}_{Tm_{1}\times Tm_{2}}&\mathbf{0}_{Tm_{1}\times Tm_{2}}\\\
\mathbf{0}_{Tm_{2}}&\mathbf{0}_{Tm_{2}\times Tm_{1}}&\mathbf{0}_{Tm_{2}\times
Tm_{1}}&BB^{\top}&I_{Tm_{2}}\\\ \mathbf{1}_{Tm_{2}}&\mathbf{0}_{Tm_{2}\times
Tm_{1}}&\mathbf{0}_{Tm_{2}\times Tm_{1}}&-I_{Tm_{2}}&\mathbf{0}_{Tm_{2}\times
Tm_{2}}\end{array}\right]\\!\in\\!\mathbb{R}^{\overline{m}\times(\overline{m}+1)}.$

Problem (20) can then be written in the form

$\displaystyle\min_{v\in\mathbb{R}^{\overline{m}+1}}F(v)$ (25)
$\displaystyle\quad\hbox{s.t.}\ \ \mathbf{0}\leq H(v)\perp
G(v)\geq\mathbf{0}.$

The basic idea of the GRM is as follows. Let $\\{t_{k}\\}\downarrow 0$. At
each iteration, we replace the MPEC (25) by the nonlinear program (NLP) of the
following form, parameterized in $t_{k}$:

$\displaystyle\min_{v}\ F(v)$ (NLP-$t_{k}$)
$\displaystyle\begin{array}[]{ll}\hbox{s.t.}\ \ G_{i}(v)\geq 0\quad\forall\
i=1,\ \cdots,\ \overline{m},\\\ \quad\quad H_{i}(v)\geq 0\quad\forall\ i=1,\
\cdots,\ \overline{m},\\\ \quad\quad G_{i}(v)H_{i}(v)\leq t_{k}\quad\forall\
i=1,\ \cdots,\ \overline{m}.\end{array}$

The details of the GRM are shown in Algorithm 1.

Algorithm 1 The Global Relaxation Method (GRM) $(v_{0},\ t_{0},\ \sigma,\
t_{min})$

1:Require a starting vector $v_{0}$, an initial relaxation parameter $t_{0}$,
and parameters $\sigma\in(0,1),\ t_{\min}>0$.

2:Set $k:=0$.

3:while $t_{k}>t_{\min}$ do

4:Find an approximate solution $v^{k+1}$ of the relaxed problem (NLP-$t_{k}$)
using $v^{k}$ as a starting point.

5:Let $t_{k+1}\leftarrow\sigma\cdot t_{k}$ and $k\leftarrow k+1$.

6:end while

7:Return the final iterate $v_{opt}:=v^{k}$, the corresponding function value
$F(v_{opt})$, and the maximum constraint violation Vio($v_{opt}$).

Here, the maximum violation of all constraints Vio defined by

$\operatorname{Vio}\left(v_{opt}\right)=\|\min\\{G(v_{opt}),\
H(v_{opt})\\}\|_{\infty}$ (26)

is used to measure the feasibility of the final iterate $v_{opt}$, where
$\|\cdot\|_{\infty}$ denotes the $l_{\infty}$ norm. We use the GRM in
Algorithm 1 to solve the MPEC (25), and get the optimal hyperparameter $C$ and
the corresponding function value $F(v_{opt})$ which is the cross-validation
error (CV error) measured on the validation sets in T-fold cross-validation.
To analyze the convergence of the GRM, we need the concept of C-stationarity,
which we define next.

To proceed, let $v$ be a feasible point for the MPEC $(\ref{eq16})$ and recall
that $F(v),G(v)$ and $H(v)$ defined in (24). Based on $v$, let

$\displaystyle I_{G}$ $\displaystyle:=$ $\displaystyle\\{i\ \mid\ G_{i}(v)=0,\
H_{i}(v)>0\\},$ $\displaystyle I_{GH}$ $\displaystyle:=$ $\displaystyle\\{i\
\mid\ G_{i}(v)=0,\ H_{i}(v)=0\\},$ $\displaystyle I_{H}$ $\displaystyle:=$
$\displaystyle\\{i\ \mid\ G_{i}(v)>0,\ H_{i}(v)=0\\}.$

######  Definition 1.

(C-stationarity) Let $v$ be a feasible point for the MPEC (25). Then $v$ is
said to be a C-stationary point, if there are multipliers $\gamma,\
\nu\in\mathbb{R}^{\overline{m}}$, such that

$\nabla F\left(v\right)-\sum_{i=1}^{\overline{m}}\gamma_{i}\nabla
G_{i}\left(v\right)-\sum_{i=1}^{\overline{m}}\nu_{i}\nabla
H_{i}\left(v\right)=0,$

and $\gamma_{i}=0$ for $i\in I_{H},\ \nu_{i}=0$ for $i\in I_{G}$, and
$\gamma_{i}\nu_{i}\geq 0$ for $i\in I_{GH}$.

Note that for problem (25), C-stationarity holds at any local optimal solution
that satisfies the MPEC-MFCQ, which can be defined as follows
hoheisel2013theoretical .

######  Definition 2.

A feasible point $v$ for problem $(\ref{eq16})$ satisfies the MPEC-MFCQ if and
only if the set of gradient vectors

$\displaystyle\left\\{\nabla G_{i}\left(v\right)\mid i\in I_{G}\cup
I_{GH}\right\\}\cup\left\\{\nabla H_{i}\left(v\right)\mid i\in I_{H}\cup
I_{GH}\right\\}$ (27)

is positive-linearly independent.

Recall that the set of gradient vectors in (27) is said to be positive-
linearly _dependent_ if there exist scalars $\\{\delta_{i}\\}_{i\in I_{G}\cup
I_{GH}}$ and $\\{\beta_{i}\\}_{i\in I_{H}\cup I_{GH}}$ with $\delta_{i}\geq 0$
for $i\in I_{G}\cup I_{GH}$, $\beta_{i}\geq 0$ for $i\in I_{H}\cup I_{GH}$,
not all of them being zero, such that $\Sigma_{i\in I_{G}\cup
I_{GH}}\delta_{i}\nabla G_{i}(v)+\Sigma_{i\in I_{H}\cup I_{GH}}\beta_{i}\nabla
H_{i}(v)=0$. Otherwise, we say that this set of gradient vectors is positive-
linearly _independent_.

Also note that various other stationarity concepts can be defined for problem
(25); for more details on this, interested readers are referred to
dempe2012karush ; flegel2005constraint .

The following result establishes the well-definiteness of Algorithm 1, as it
provides a framework ensuring that a solutions (or a stationary points, to be
precise) exist for problem (NLP-$t_{k}$) as required.

######  Theorem 1.

hoheisel2013theoretical Let $v$ be a feasible point for the MPEC
$(\ref{eq16})$ such that MPEC-MFCQ is satisfied at $v$. Then there exists a
neighborhood $N$ of $v$ and $\overline{t}>0$ such that standard MFCQ for
(NLP-$t_{k}$) at $t_{k}=t$ is satisfied at all feasible points of
(NLP-$t_{k}$) at $t_{k}=t$ in this neighborhood $N$ for all $t\in(0,\
\overline{t})$.

Subsequently, we have the following convergence result, which ensures that a
sequence of stationary points of problem (NLP-$t_{k}$), computed by Algorithm
1, converges to a C-stationary point of problem (25).

######  Theorem 2.

hoheisel2013theoretical Let $\\{t_{k}\\}\downarrow 0$ and let $v^{k}$ be a
stationary point of (NLP-$t_{k}$) with $v^{k}\rightarrow v$ such that MPEC-
MFCQ holds at the feasible point $v$. Then $v$ is a C-stationary point of the
MPEC $(\ref{eq16})$.

Clearly, the MPEC-MFCQ is crucial for the analysis of problem (25), as it not
only ensures that the C-stationarity condition can hold at a locally optimal
point, but also helps in establishing the two fundamental results in Theorems
1 and 2. Considering this importance of the condition, we carefully analyze it
in the next section, and show, in particular, that it automatically holds at
any feasible point of problem $(\ref{eq16})$.

##  4 Fulfilment of the MPEC-MFCQ

In this section, we prove that every point in the feasible set of the MPEC
(25) satisfies the MPEC-MFCQ. The rough idea of our proof is as follows.
Firstly, by analyzing the relationship of different index sets (Proposition
5), we reach a reduced form of the MPEC-MFCQ (Proposition 6). Then based on
the positive-linear independence of three submatrices (Lemma 1-Lemma 3), we
eventually show the MPEC-MFCQ in Theorem 3. The roadmap of the proof is
summarized in Figure 7.

Figure 7: The roadmap of the proof of the MPEC-MFCQ.

###  4.1 Relationships between the index sets

In this part, we first explore more properties about the index sets $I_{H},\
I_{G},\ I_{GH}$, as they are key to the analysis of the positive-linear
independence of the vectors in (27). Let
$I_{H}:=\underset{k=1}{\overset{4}{\cup}}I_{H_{k}},\
I_{G}:=\underset{k=1}{\overset{4}{\cup}}I_{G_{k}},$ and
$I_{GH}:=\underset{k=1}{\overset{4}{\cup}}I_{GH_{k}}$, where

$\displaystyle I_{H_{1}}\ \;:=\;\\{i\in Q_{u}\ \mid\ \zeta_{i}=0,\
(AB^{\top}\alpha+z)_{i}>0\\},$ (28a) $\displaystyle I_{H_{2}}\ \;:=\;\\{i\in
Q_{u}\ \mid\ z_{i}=0,\ 1-\zeta_{i}>0\\},$ (28b) $\displaystyle I_{H_{3}}\
\;:=\;\\{i\in Q_{l}\ \mid\ \alpha_{i}=0,\
(BB^{\top}\alpha-\mathbf{1}+\xi)_{i}>0\\},$ (28c) $\displaystyle I_{H_{4}}\
\;:=\;\\{i\in Q_{l}\ \mid\ \xi_{i}=0,\ C-\alpha_{i}>0\\},$ (28d)
$\displaystyle I_{G_{1}}\ \;:=\;\\{i\in Q_{u}\ \mid\ \zeta_{i}>0,\
(AB^{\top}\alpha+z)_{i}=0\\},$ (28e) $\displaystyle I_{G_{2}}\ \;:=\;\\{i\in
Q_{u}\ \mid\ z_{i}>0,\ 1-\zeta_{i}=0\\},$ (28f) $\displaystyle I_{G_{3}}\
\;:=\;\\{i\in Q_{l}\ \mid\ \alpha_{i}>0,\
(BB^{\top}\alpha-\mathbf{1}+\xi)_{i}=0\\},$ (28g) $\displaystyle I_{G_{4}}\
\;:=\;\\{i\in Q_{l}\ \mid\ \xi_{i}>0,\ C-\alpha_{i}=0\\},$ (28h)
$\displaystyle I_{GH_{1}}:=\;\\{i\in Q_{u}\ \mid\ \zeta_{i}=0,\
(AB^{\top}\alpha+z)_{i}=0\\},$ (28i) $\displaystyle I_{GH_{2}}:=\;\\{i\in
Q_{u}\ \mid\ z_{i}=0,\ 1-\zeta_{i}=0\\},$ (28j) $\displaystyle
I_{GH_{3}}:=\;\\{i\in Q_{l}\ \mid\ \alpha_{i}=0,\
(BB^{\top}\alpha-\mathbf{1}+\xi)_{i}=0\\},$ (28k) $\displaystyle
I_{GH_{4}}:=\;\\{i\in Q_{l}\ \mid\ \xi_{i}=0,\ C-\alpha_{i}=0\\}.$ (28l)

Here, $Q_{u},\ Q_{l}$ are defined in (1) and (2), respectively. Furthermore,
let

$I^{k}:=I_{H_{k}}\cup I_{G_{k}}\cup I_{GH_{k}},\ k=1,\ 2,\ 3,\ 4.$

It can be observed that each index set $I^{k},\ k=1,\ 2,\ 3,\ 4$ corresponds
to the union of the three components in the partition involved in the
corresponding part of the complementarity systems in (20); that is,

  * Part 1: $I^{1}$ for the partition of the system $\mathbf{0}\leq\zeta\perp\ AB^{T}\alpha+z\geq\mathbf{0}$;

  * Part 2: $I^{2}$ for the partition of the system $\mathbf{0}\leq z\perp\mathbf{1}-\zeta\geq\mathbf{0}$;

  * Part 3: $I^{3}$ for the partition of the system $\mathbf{0}\leq\alpha\perp BB^{T}\alpha-\mathbf{1}+\xi\geq\mathbf{0}$;

  * Part 4: $I^{4}$ for the partition of the system $\mathbf{0}\leq\xi\perp C\mathbf{1}-\alpha\geq\mathbf{0}$.

In the previous section, we have clarified a one-to-one correspondence between
the index set of the validation points $Q_{u}$ in (1) and the complementary
constraints in Part 1 and Part 2, respectively. It is clearly that
$I^{1}=I^{2}=Q_{u}$. Similarly, we have $I^{3}=I^{4}=Q_{l}$.

(a) (a) Part 1. (b) (b) Part 2. (c) (c) Part 3.

(d) (d) Part 4.

Figure 8: The index sets corresponding to the complementarity constraints in
Parts 1–4.

Next, we give the relationships between the index sets in (28); recall that we
already have some index sets described in Propositions 3 and 4. For the
convenience of the analysis, we divide the index set $\Lambda_{3}$ in (9) into
two subsets $\Lambda^{+}_{3}$ and $\Lambda^{c}_{3}$, as well as $\Psi_{1}$ in
(21) into $\Psi^{0}_{1}$ and $\Psi^{+}_{1}$:

$\displaystyle\Lambda^{+}_{3}$ $\displaystyle:=$ $\displaystyle\\{i\in Q_{l}\
\mid\ 0<\alpha_{i}<C,\ (BB^{\top}\alpha-\mathbf{1}+\xi)_{i}=0,\ \xi_{i}=0\\},$
(29) $\displaystyle\Lambda^{c}_{3}$ $\displaystyle:=$ $\displaystyle\\{i\in
Q_{l}\ \mid\ \alpha_{i}=C,\ (BB^{\top}\alpha-\mathbf{1}+\xi)_{i}=0,\
\xi_{i}=0\\},$ (30) $\displaystyle\Psi^{0}_{1}$ $\displaystyle:=$
$\displaystyle\\{i\in Q_{u}\ \mid\ \zeta_{i}=0,\ (AB^{\top}\alpha+z)_{i}=0,\
z_{i}=0\\},$ (31) $\displaystyle\Psi^{+}_{1}$ $\displaystyle:=$
$\displaystyle\\{i\in Q_{u}\ \mid\ 0<\zeta_{i}<1,\ (AB^{\top}\alpha+z)_{i}=0,\
z_{i}=0\\}.$ (32)

######  Proposition 5.

The index sets in $(\ref{eq23})$ and the index sets in Proposition 3 and
Proposition 4 have the following relationship:

  * (a)

In Part $1,\ I_{H_{1}}=\Psi_{2},\ I_{G_{1}}=\Psi^{+}_{1}\cup\Psi_{3},\
I_{GH_{1}}=\Psi^{0}_{1}.$

  * (b)

In Part $2,\ I_{H_{2}}=\Psi_{1}\cup\Psi_{2},\ I_{G_{2}}=\Psi_{3},\
I_{GH_{2}}=\emptyset.$

  * (c)

In Part $3,\ I_{H_{3}}=\Lambda_{2},\ I_{G_{3}}=\Lambda_{3}\cup\Lambda_{u},\
I_{GH_{3}}=\Lambda_{1}.$

  * (d)

In Part $4,\ I_{H_{4}}=\Lambda_{1}\cup\Lambda_{2}\cup\Lambda^{+}_{3},\
I_{G_{4}}=\Lambda_{u},\ I_{GH_{4}}=\Lambda^{c}_{3}.$

Here, $\Lambda_{u}$ is defined as follows

$\Lambda_{u}:=\left\\{i\in Q_{l}\ \mid\ \alpha_{i}=C,\
(BB^{\top}\alpha-\mathbf{1}+\xi)_{i}=0,\
\xi_{i}>0\right\\}=\Lambda_{4}\cup\Lambda_{5}\cup\Lambda_{6}.$ (33)

Proof: According to the definition of the index sets in $(\ref{eq23})$ and the
index sets in Proposition 3 and Proposition 4, we have the following analysis.

  * (a)

In Part 1, for $i\in I_{H_{1}}$, compared with the index set $\Psi_{2}$ in
(22), it follows that we have $z_{i}=0$ and $I_{H_{1}}=\Psi_{2}$. For $i\in
I_{G_{1}}$, compared with the index sets $\Psi^{+}_{1}$ in (32) and $\Psi_{3}$
in (23), we get $0<\zeta_{i}<1,\ z_{i}=0$ or $\zeta_{i}=1,\ z_{i}>0$, and
$I_{G_{1}}=\Psi^{+}_{1}\cup\Psi_{3}$. For $i\in I_{GH_{1}}$, compared with the
index set $\Psi^{0}_{1}$ in (31), we get $z_{i}=0$ and
$I_{GH_{1}}=\Psi^{0}_{1}$.

  * (b)

In Part 2, for $i\in I_{H_{2}}$, compared with the index sets $\Psi_{1}$ in
(21) and $\Psi_{2}$ in (22), we get $I_{H_{2}}=\Psi_{1}\cup\Psi_{2}.$ For
$i\in I_{G_{2}}$, compared with the index set $\Psi_{3}$ in (23), we get
$(AB^{\top}\alpha+z)_{i}=0$ and $I_{G_{2}}=\Psi_{3}$. For $i\in I_{GH_{2}}$,
there is no index set in Proposition 4 corresponds to the index set
$I_{GH_{2}}$. Therefore, $I_{GH_{2}}=\emptyset.$

  * (c)

In Part 3, for $i\in I_{H_{3}}$, compared with the index set $\Lambda_{2}$ in
(8), we get $\xi_{i}=0$ and $I_{H_{3}}=\Lambda_{2}$. For $i\in I_{G_{3}}$,
compared with the index sets $\Lambda_{3}$ in (9) and $\Lambda_{u}$ in (33),
we get $I_{G_{3}}=\Lambda_{3}\cup\Lambda_{u}.$ For $i\in I_{GH_{3}}$, compared
with the index set $\Lambda_{1}$ in (7), we get $\xi_{i}=0$ and
$I_{GH_{3}}=\Lambda_{1}$.

  * (d)

In Part 4, for $i\in I_{H_{4}}$, compared with the index sets $\Lambda_{1}$ in
(7), $\Lambda_{2}$ in (8) and $\Lambda^{+}_{3}$ in (29), we get
$I_{H_{4}}=\Lambda_{1}\cup\Lambda_{2}\cup\Lambda^{+}_{3}.$ For $i\in
I_{G_{4}}$, compared with the index set $\Lambda_{u}$ in (33), we get
$(Bw-\mathbf{1}+\xi)_{i}=0$ and $I_{G_{4}}=\Lambda_{u}.$ For $i\in
I_{GH_{4}}$, compared with the index set $\Lambda^{c}_{3}$ in (30), it results
that we have $(Bw-\mathbf{1}+\xi)_{i}=0$ and $I_{GH_{4}}=\Lambda^{c}_{3}$.

The results in Proposition 5 are demonstrated in Figure 8. For example, for
(a) in Proposition 5, the index sets of complementarity constraints in Part 1
are shown in Figure 8 (a), which is about the relationship of $I_{H_{1}},\
I_{G_{1}},\ I_{GH_{1}}$ in (28) and the index sets (21)–(23). In Figure 8 (a),
the red shaded part represents the index set $I_{G_{1}}$, which contains the
index sets $\Psi^{+}_{1}$ and $\Psi_{3}$. (b)–(d) in Proposition 5 are
demonstrated in Figure 8 (b)–(d). Specially, in Figure 8 (b), the red shaded
part represents the index set $I_{H_{2}}$, which contains the index sets
$\Psi_{1}$ (or $\Psi^{0}_{1}\cup\Psi^{+}_{1}$) and $\Psi_{2}$. In Figure 8
(c), the red shaded part represents the index set $I_{G_{3}}$, which contains
the index sets $\Lambda_{3}$ (or $\Lambda^{+}_{3}\cup\Lambda^{c}_{3}$) and
$\Lambda_{u}$. In Figure 8 (d), the red shaded part represents the index set
$I_{H_{4}}$, which contains the index sets $\Lambda_{1},\ \Lambda_{2}$, and
$\Lambda^{+}_{3}$.

###  4.2 The reduced form of the MPEC-MFCQ

Here we provide a matrix representation of the union of gradients in (27).

######  Proposition 6.

The set of gradient vectors in (27) at a feasible point $v$ for the MPEC (25)
can be written in the matrix form

$\Gamma=\left[\begin{array}[]{ccccc}\mathbf{0}_{(I_{G_{1}},\
L_{1})}&\mathbf{0}_{(I_{G_{1}},\
L_{2})}&\pagecolor{green!50}\Gamma_{a}^{3}&(AB^{\top})_{(I_{G_{1}},\ \cdot\
)}&\mathbf{0}_{(I_{G_{1}},\ L_{5})}\\\ \mathbf{0}_{(I_{GH_{1}},\
L_{1})}&\mathbf{0}_{(I_{GH_{1}},\
L_{2})}&\pagecolor{green!50}\Gamma_{b}^{3}&(AB^{\top})_{(I_{GH_{1}},\ \cdot\
)}&\mathbf{0}_{(I_{GH_{1}},\ L_{5})}\\\ \mathbf{0}_{(I_{GH_{1}},\
L_{1})}&\pagecolor{blue!50}\Gamma_{c}^{2}&\mathbf{0}_{(I_{GH_{1}},\
L_{3})}&\mathbf{0}_{(I_{GH_{1}},\ L_{4})}&\mathbf{0}_{(I_{GH_{1}},\ L_{5})}\\\
\mathbf{0}_{(I_{H_{1}},\
L_{1})}&\pagecolor{blue!50}\Gamma_{d}^{2}&\mathbf{0}_{(I_{H_{1}},\
L_{3})}&\mathbf{0}_{(I_{H_{1}},\ L_{4})}&\mathbf{0}_{(I_{H_{1}},\ L_{5})}\\\
\mathbf{0}_{(I_{G_{2}},\
L_{1})}&\pagecolor{blue!50}\Gamma_{e}^{2}&\mathbf{0}_{(I_{G_{2}},\
L_{3})}&\mathbf{0}_{(I_{G_{2}},\ L_{4})}&\mathbf{0}_{(I_{G_{2}},\ L_{5})}\\\
\mathbf{0}_{(I_{H_{2}},\ L_{1})}&\mathbf{0}_{(I_{H_{2}},\
L_{2})}&\pagecolor{green!50}\Gamma_{f}^{3}&\mathbf{0}_{(I_{H_{2}},\
L_{4})}&\mathbf{0}_{(I_{H_{2}},\ L_{5})}\\\ \mathbf{0}_{(I_{G_{3}},\
L_{1})}&\mathbf{0}_{(I_{G_{3}},\ L_{2})}&\mathbf{0}_{(I_{G_{3}},\
L_{3})}&\pagecolor{yellow!50}(BB^{\top})_{(I_{G_{3}},\ \cdot\
)}&\pagecolor{yellow!50}\Gamma_{g}^{5}\\\ \mathbf{0}_{(I_{GH_{3}},\
L_{1})}&\mathbf{0}_{(I_{GH_{3}},\ L_{2})}&\mathbf{0}_{(I_{GH_{3}},\
L_{3})}&\pagecolor{yellow!50}(BB^{\top})_{(I_{GH_{3}},\ \cdot\
)}&\pagecolor{yellow!50}\Gamma_{h}^{5}\\\ \mathbf{0}_{(I_{GH_{3}},\
L_{1})}&\mathbf{0}_{(I_{GH_{3}},\ L_{2})}&\mathbf{0}_{(I_{GH_{3}},\
L_{3})}&\pagecolor{yellow!50}\Gamma_{i}^{4}&\pagecolor{yellow!50}\mathbf{0}_{(I_{GH_{3}},\
L_{5})}\\\ \mathbf{0}_{(I_{H_{3}},\ L_{1})}&\mathbf{0}_{(I_{H_{3}},\
L_{2})}&\mathbf{0}_{(I_{H_{3}},\
L_{3})}&\pagecolor{yellow!50}\Gamma_{j}^{4}&\pagecolor{yellow!50}\mathbf{0}_{(I_{H_{3}},\
L_{5})}\\\ \mathbf{1}_{(I_{G_{4}},\ L_{1})}&\mathbf{0}_{(I_{G_{4}},\
L_{2})}&\mathbf{0}_{(I_{G_{4}},\
L_{3})}&\Gamma_{k}^{4}&\mathbf{0}_{(I_{G_{4}},\ L_{5})}\\\
\mathbf{1}_{(I_{GH_{4}},\ L_{1})}&\mathbf{0}_{(I_{GH_{4}},\
L_{2})}&\mathbf{0}_{(I_{GH_{4}},\
L_{3})}&\Gamma_{l}^{4}&\mathbf{0}_{(I_{GH_{4}},\ L_{5})}\\\
\mathbf{0}_{(I_{GH_{4}},\ L_{1})}&\mathbf{0}_{(I_{GH_{4}},\
L_{2})}&\mathbf{0}_{(I_{GH_{4}},\
L_{3})}&\pagecolor{yellow!50}\mathbf{0}_{(I_{GH_{4}},\
L_{4})}&\pagecolor{yellow!50}\Gamma_{m}^{5}\\\ \mathbf{0}_{(I_{H_{4}},\
L_{1})}&\mathbf{0}_{(I_{H_{4}},\ L_{2})}&\mathbf{0}_{(I_{H_{4}},\
L_{3})}&\pagecolor{yellow!50}\mathbf{0}_{(I_{H_{4}},\
L_{4})}&\pagecolor{yellow!50}\Gamma_{n}^{5}\end{array}\right],$ (34)

where $L_{q},\ q=1,\ \cdots,\ 5$ are the index sets of columns corresponding
to the variables $C$, $\zeta$, $z$, $\alpha$, and $\xi$, respectively, and

$\left.\begin{array}[]{lll}\Gamma_{a}^{3}&:=&\left[\begin{array}[]{cc}\mathbf{0}_{(I_{G_{1}},\
\Psi^{0}_{1}\cup\Psi_{2})}&I_{(I_{G_{1}},\
\Psi^{+}_{1}\cup\Psi_{3})}\end{array}\right]\\\
\Gamma_{b}^{3}&:=&\left[\begin{array}[]{cc}I_{(I_{GH_{1}},\
\Psi^{0}_{1})}&\mathbf{0}_{(I_{GH_{1}},\
\Psi^{+}_{1}\cup\Psi_{2}\cup\Psi_{3})}\end{array}\right]\\\
\Gamma_{c}^{2}&:=&\left[\begin{array}[]{cc}I_{(I_{GH_{1}},\
\Psi^{0}_{1})}&\mathbf{0}_{(I_{GH_{1}},\
\Psi^{+}_{1}\cup\Psi_{2}\cup\Psi_{3})}\end{array}\right]\\\
\Gamma_{d}^{2}&:=&\left[\begin{array}[]{cc}\mathbf{0}_{(I_{H_{1}},\
\Psi_{1}\cup\Psi_{3})}&I_{(I_{H_{1}},\ \Psi_{2})}\end{array}\right]\\\
\Gamma_{e}^{2}&:=&\left[\begin{array}[]{cc}\mathbf{0}_{(I_{G_{2}},\
\Psi_{1}\cup\Psi_{2})}&-I_{(I_{G_{2}},\ \Psi_{3})}\end{array}\right]\\\
\Gamma_{f}^{3}&:=&\left[\begin{array}[]{cc}I_{(I_{H_{2}},\
\Psi_{1}\cup\Psi_{2})}&\mathbf{0}_{(I_{H_{2}},\
\Psi_{3})}\end{array}\right]\\\
\Gamma_{g}^{5}&:=&\left[\begin{array}[]{cc}\mathbf{0}_{(I_{G_{3}},\
\Lambda_{1}\cup\Lambda_{2})}&I_{(I_{G_{3}},\
\Lambda_{3}\cup\Lambda_{u})}\end{array}\right]\\\
\Gamma_{h}^{5}&:=&\left[\begin{array}[]{cc}I_{(I_{GH_{3}},\
\Lambda_{1})}&\mathbf{0}_{(I_{GH_{3}},\
\Lambda_{2}\cup\Lambda_{3}\cup\Lambda_{u})}\end{array}\right]\\\
\Gamma_{i}^{4}&:=&\left[\begin{array}[]{cc}I_{(I_{GH_{3}},\
\Lambda_{1})}&\mathbf{0}_{(I_{GH_{3}},\
\Lambda_{2}\cup\Lambda_{3}\cup\Lambda_{u})}\end{array}\right]\\\
\Gamma_{j}^{4}&:=&\left[\begin{array}[]{cc}\mathbf{0}_{(I_{H_{3}},\
\Lambda_{1}\cup\Lambda_{3}\cup\Lambda_{u})}&I_{(I_{H_{3}},\
\Lambda_{2})}\end{array}\right]\\\
\Gamma_{k}^{4}&:=&\left[\begin{array}[]{cc}\mathbf{0}_{(I_{G_{4}},\
\Lambda_{1}\cup\Lambda_{2}\cup\Lambda_{3})}&-I_{(I_{G_{4}},\
\Lambda_{u})}\end{array}\right]\\\
\Gamma_{l}^{4}&:=&\left[\begin{array}[]{cc}\mathbf{0}_{(I_{GH_{4}},\
\Lambda_{1}\cup\Lambda_{2}\cup\Lambda^{+}_{3}\cup\Lambda_{u})}&-I_{(I_{GH_{4}},\
\Lambda^{c}_{3})}\end{array}\right]\\\
\Gamma_{m}^{5}&:=&\left[\begin{array}[]{cc}\mathbf{0}_{(I_{GH_{4}},\
\Lambda_{1}\cup\Lambda_{2}\cup\Lambda^{+}_{3}\cup\Lambda_{u})}&I_{(I_{GH_{4}},\
\Lambda^{c}_{3})}\end{array}\right]\\\
\Gamma_{n}^{5}&:=&\left[\begin{array}[]{cc}I_{(I_{H_{4}},\
\Lambda_{1}\cup\Lambda_{2}\cup\Lambda^{+}_{3})}&\mathbf{0}_{(I_{H_{4}},\
\Lambda^{c}_{3}\cup\Lambda_{u})}\end{array}\right]\end{array}\right\\}.$ (35)

Proof: Based on Definition 2, we can write the system of gradient vectors in
(27), at a feasible point $v$, in the equivalent matrix form

$\Gamma=\left[\begin{array}[]{l}\nabla G(v)_{I_{G_{1}}}\\\ \nabla
G(v)_{I_{GH_{1}}}\\\ \nabla H(v)_{I_{GH_{1}}}\\\ \nabla H(v)_{I_{H_{1}}}\\\
\nabla G(v)_{I_{G_{2}}}\\\ \nabla H(v)_{I_{H_{2}}}\\\ \nabla
G(v)_{I_{G_{3}}}\\\ \nabla G(v)_{I_{GH_{3}}}\\\ \nabla H(v)_{I_{GH_{3}}}\\\
\nabla H(v)_{I_{H_{3}}}\\\ \nabla G(v)_{I_{G_{4}}}\\\ \nabla
G(v)_{I_{GH_{4}}}\\\ \nabla H(v)_{I_{GH_{4}}}\\\ \nabla
H(v)_{I_{H_{4}}}\end{array}\right]$

that we can easily show to be equivalent to (34). To proceed, first note that
from Proposition 5 (a) and (b), we have

$\begin{array}[]{l}I_{H_{1}}\\!=\\!\Psi_{2},\
I_{G_{1}}\\!=\\!\Psi^{+}_{1}\cup\Psi_{3},\ I_{GH_{1}}\\!=\\!\Psi^{0}_{1},\
I_{H_{2}}\\!=\\!\Psi_{1}\cup\Psi_{2},\\\\[4.30554pt]
I_{G_{2}}\\!=\\!\Psi_{3},\
Q_{u}\\!=\\!\Psi_{1}\cup\Psi_{2}\cup\Psi_{3}.\end{array}$

So, we get $\Gamma_{a}^{3},\ \Gamma_{b}^{3},\ \Gamma_{c}^{2},\
\Gamma_{d}^{2},\ \Gamma_{e}^{2}$, and $\Gamma_{f}^{3}$ in (35). On the other
hand, it follows from Proposition 5 (c) and (d), we have

$\begin{array}[]{l}I_{H_{3}}\\!=\\!\Lambda_{2},\
I_{G_{3}}\\!=\\!\Lambda_{3}\cup\Lambda_{u},\ I_{GH_{3}}\\!=\\!\Lambda_{1},\
I_{H_{4}}\\!=\\!\Lambda_{1}\cup\Lambda_{2}\cup\Lambda^{+}_{3},\\\\[4.30554pt]
I_{G_{4}}\\!=\\!\Lambda_{u},\
I_{GH_{4}}\\!=\\!\Lambda^{c}_{3},\;\;Q_{l}\\!=\\!\Lambda_{1}\cup\Lambda_{2}\cup\Lambda_{3}\cup\Lambda_{u}.\end{array}$

Subsequently, it follows that $\Gamma_{g}^{5},\ \Gamma_{h}^{5},\
\Gamma_{i}^{4},\ \Gamma_{j}^{4},\ \Gamma_{k}^{4},\ \Gamma_{l}^{4},\
\Gamma_{m}^{5}$, and $\Gamma_{n}^{5}$ in (35). Therefore, we obtain the form
of the matrix $\Gamma$ in (34).

###  4.3 Three important lemmas

Due to the complicated form of $\Gamma$ in (34), in this part, we first
present three lemmas, addressing the positive-linear independence of three
submatrices in $\Gamma$ marked by blue, green and yellow, respectively. To
proceed from here on, we define the size of each index set in (28) and
Propositions 3-4 as follows. We denote the size of the index set $I_{G_{1}}$
by $S_{1}$, that is, $\mid\\!I_{G_{1}}\mid=S_{1}$. Similarly,

$\begin{array}[]{lllll}\mid\\!I_{G_{2}}\\!\mid=S_{2},&\mid\\!I_{G_{3}}\\!\mid=S_{3},&\mid\\!I_{G_{4}}\\!\mid=S_{4},&{}\\\
\mid\\!I_{H_{1}}\\!\mid=U_{1},&\mid\\!I_{H_{2}}\\!\mid=U_{2},&\mid\\!I_{H_{3}}\\!\mid=U_{3},&\mid\\!I_{H_{4}}\\!\mid=U_{4},&{}\\\
\mid\\!I_{GH_{1}}\\!\mid=W_{1},&\mid\\!I_{GH_{3}}\\!\mid=W_{2},&\mid\\!I_{GH_{4}}\\!\mid=W_{3},&{}&{}\\\
\mid\\!\Lambda_{1}\\!\mid=D_{1},&\mid\\!\Lambda_{2}\\!\mid=D_{2},&\mid\\!\Lambda^{+}_{3}\\!\mid=D_{3},&\mid\\!\Lambda^{c}_{3}\\!\mid=D_{4},&\mid\\!\Lambda_{u}\\!\mid=D_{5},\\\
\mid\\!\Psi^{0}_{1}\\!\mid=N_{1},&\mid\\!\Psi^{+}_{1}\\!\mid=N_{2},&\mid\\!\Psi_{2}\\!\mid=N_{3},&\mid\\!\Psi_{3}\\!\mid=N_{4}.&{}\end{array}$

Further, we denote the index corresponding to each row in the matrices
$\Gamma_{a}^{3},\ \cdots\ \Gamma_{n}^{5}$ in (35) by $a_{s},\ \cdots\ n_{s}$,
respectively.

######  Lemma 1.

The row vectors in the following matrix

$\left[\begin{array}[]{l}\Gamma_{c}^{2}\\\ \Gamma_{d}^{2}\\\
\Gamma_{e}^{2}\end{array}\right]=\left[\begin{array}[]{cccc}I_{(I_{GH_{1}},\
\Psi^{0}_{1})}&\mathbf{0}_{(I_{GH_{1}},\
\Psi^{+}_{1})}&\mathbf{0}_{(I_{GH_{1}},\ \Psi_{2})}&\mathbf{0}_{(I_{GH_{1}},\
\Psi_{3})}\\\ \mathbf{0}_{(I_{H_{1}},\ \Psi^{0}_{1})}&\mathbf{0}_{(I_{H_{1}},\
\Psi^{+}_{1})}&I_{(I_{H_{1}},\ \Psi_{2})}&\mathbf{0}_{(I_{H_{1}},\
\Psi_{3})}\\\ \mathbf{0}_{(I_{G_{2}},\ \Psi^{0}_{1})}&\mathbf{0}_{(I_{G_{2}},\
\Psi^{+}_{1})}&\mathbf{0}_{(I_{G_{2}},\ \Psi_{2})}&-I_{(I_{G_{2}},\
\Psi_{3})}\\\ \end{array}\right]$ (36)

are positive-linearly independent.

Proof: Assume that there exist $\overline{\rho}^{c}\in\mathbb{R}^{W_{1}}\
\text{and}\ \overline{\rho}^{c}\geq\mathbf{0},\
\overline{\rho}^{d}\in\mathbb{R}^{U_{1}}\ \text{and}\
\overline{\rho}^{d}\geq\mathbf{0},\ \overline{\rho}^{e}\in\mathbb{R}^{S_{2}}\
\text{and}\ \overline{\rho}^{e}\geq\mathbf{0},$ such that

$\sum\limits_{s=1}^{W_{1}}\rho_{s}^{c}\left[\begin{array}[]{c}e^{W_{1}}_{c_{s}}\\\
\mathbf{0}_{N_{2}}\\\ \mathbf{0}_{N_{3}}\\\
\mathbf{0}_{N_{4}}\end{array}\right]+\sum\limits_{s=1}^{U_{1}}\rho_{s}^{d}\left[\begin{array}[]{c}\mathbf{0}_{N_{1}}\\\
\mathbf{0}_{N_{2}}\\\ e^{U_{1}}_{d_{s}}\\\ \mathbf{0}_{N_{4}}\\\
\end{array}\right]+\sum\limits_{s=1}^{S_{2}}\rho_{s}^{e}\left[\begin{array}[]{c}\mathbf{0}_{N_{1}}\\\
\mathbf{0}_{N_{2}}\\\ \mathbf{0}_{N_{3}}\\\
-e^{S_{2}}_{e_{s}}\end{array}\right]=\mathbf{0}.$

The above equation is equivalent to the following system

$\left[\begin{array}[]{c}\overline{\rho}^{c}\\\ \mathbf{0}_{N_{2}}\\\
\overline{\rho}^{d}\\\ -\overline{\rho}^{e}\end{array}\right]=\mathbf{0}.$
(37)

Since $\overline{\rho}^{c}\geq\mathbf{0},\ \overline{\rho}^{d}\geq\mathbf{0},\
\overline{\rho}^{e}\geq\mathbf{0}$, we get $\overline{\rho}^{c}=\mathbf{0},\
\overline{\rho}^{d}=\mathbf{0},\ \overline{\rho}^{e}=\mathbf{0}$ from Equation
(37). Therefore, the row vectors in the matrix (36) are positive-linearly
independent.

######  Lemma 2.

The row vectors in the following matrix

$\left[\begin{array}[]{l}\Gamma_{a}^{3}\\\ \Gamma_{b}^{3}\\\
\Gamma_{f}^{3}\end{array}\right]=\left[\begin{array}[]{cccc}\mathbf{0}_{(\Psi^{+}_{1},\
\Psi^{0}_{1})}&I_{(\Psi^{+}_{1},\ \Psi^{+}_{1})}&\mathbf{0}_{(\Psi^{+}_{1},\
\Psi_{2})}&\mathbf{0}_{(\Psi^{+}_{1},\ \Psi_{3})}\\\ \mathbf{0}_{(\Psi_{3},\
\Psi^{0}_{1})}&\mathbf{0}_{(\Psi_{3},\ \Psi^{+}_{1})}&\mathbf{0}_{(\Psi_{3},\
\Psi_{2})}&I_{(\Psi_{3},\ \Psi_{3})}\\\ I_{(I_{GH_{1}},\
\Psi^{0}_{1})}&\mathbf{0}_{(I_{GH_{1}},\
\Psi^{+}_{1})}&\mathbf{0}_{(I_{GH_{1}},\ \Psi_{2})}&\mathbf{0}_{(I_{GH_{1}},\
\Psi_{3})}\\\ I_{(\Psi^{0}_{1},\ \Psi^{0}_{1})}&\mathbf{0}_{(\Psi^{0}_{1},\
\Psi^{+}_{1})}&\mathbf{0}_{(\Psi^{0}_{1},\
\Psi_{2})}&\mathbf{0}_{(\Psi^{0}_{1},\ \Psi_{3})}\\\
\mathbf{0}_{(\Psi^{+}_{1},\ \Psi^{0}_{1})}&I_{(\Psi^{+}_{1},\
\Psi^{+}_{1})}&\mathbf{0}_{(\Psi^{+}_{1},\
\Psi_{2})}&\mathbf{0}_{(\Psi^{+}_{1},\ \Psi_{3})}\\\ \mathbf{0}_{(\Psi_{2},\
\Psi^{0}_{1})}&\mathbf{0}_{(\Psi_{2},\ \Psi^{+}_{1})}&I_{(\Psi_{2},\
\Psi_{2})}&\mathbf{0}_{(\Psi_{2},\ \Psi_{3})}\end{array}\right]$ (38)

are positive-linearly independent.

Proof: Assume that there exist $\overline{\rho}^{a}\in\mathbb{R}^{S_{1}}\
\text{and}\ \overline{\rho}^{a}\geq\mathbf{0},\
\overline{\rho}^{b}\in\mathbb{R}^{W_{1}}\ \text{and}\
\overline{\rho}^{b}\geq\mathbf{0},\ \overline{\rho}^{f}\in\mathbb{R}^{U_{2}}\
\text{and}\ \overline{\rho}^{f}\geq\mathbf{0},$ such that

$\sum\limits_{s=1}^{S_{1}}\rho_{s}^{a}\left[\begin{array}[]{c}\mathbf{0}_{N_{1}+N_{3}}\\\
e^{S_{1}}_{a_{s}}\end{array}\right]+\sum\limits_{s=1}^{W_{1}}\rho_{s}^{b}\left[\begin{array}[]{c}e^{W_{1}}_{b_{s}}\\\
\mathbf{0}_{N_{2}+N_{3}+N_{4}}\end{array}\right]+\sum\limits_{s=1}^{U_{2}}\rho_{s}^{f}\left[\begin{array}[]{c}e^{U_{2}}_{f_{s}}\\\
\mathbf{0}_{N_{4}}\end{array}\right]=\mathbf{0}.$

The above equation is equivalent to the following system

$\left[\begin{array}[]{c}\overline{\rho}^{b}+\overline{\rho}_{\Psi^{0}_{1}}^{f}\\\
\overline{\rho}_{\Psi^{+}_{1}}^{a}+\overline{\rho}_{\Psi^{+}_{1}}^{f}\\\
\overline{\rho}_{\Psi_{2}}^{f}\\\
\overline{\rho}_{\Psi_{3}}^{a}\end{array}\right]=\mathbf{0}.$ (39)

Since $\overline{\rho}^{a}\geq\mathbf{0},\ \overline{\rho}^{b}\geq\mathbf{0},\
\overline{\rho}^{f}\geq\mathbf{0}$, we get $\overline{\rho}^{a}=\mathbf{0},\
\overline{\rho}^{b}=\mathbf{0},\ \overline{\rho}^{f}=\mathbf{0}$ from Equation
(39). Therefore, the row vectors in the matrix (38) are positive-linearly
independent.

######  Lemma 3.

The row vectors in the matrix $\Gamma_{sub}$ defined by

$\begin{array}[]{c}\Gamma_{sub}=\left[\begin{array}[]{cc}(BB^{\top})_{(I_{G_{3}},\
\cdot\ )}&\Gamma_{g}^{5}\\\ (BB^{\top})_{(I_{GH_{3}},\ \cdot\
)}&\Gamma_{h}^{5}\\\ \Gamma_{i}^{4}&\mathbf{0}_{(I_{GH_{3}},\ L_{5})}\\\
\Gamma_{j}^{4}&\mathbf{0}_{(I_{H_{3}},\ L_{5})}\\\ \mathbf{0}_{(I_{GH_{4}},\
L_{4})}&\Gamma_{m}^{5}\\\ \mathbf{0}_{(I_{H_{4}},\
L_{4})}&\Gamma_{n}^{5}\end{array}\right]\end{array}$ (40)

are positive-linearly independent.

Proof: For the convenience of analysis, note that

$\left[\begin{array}[]{c}\Gamma_{g}^{5}\\\ \Gamma_{h}^{5}\\\ \Gamma_{m}^{5}\\\
\Gamma_{n}^{5}\end{array}\right]=\left[\begin{array}[]{ccccc}\mathbf{0}_{(\Lambda^{+}_{3},\
\Lambda_{1})}&\mathbf{0}_{(\Lambda^{+}_{3},\
\Lambda_{2})}&I_{(\Lambda^{+}_{3},\
\Lambda^{+}_{3})}&\mathbf{0}_{(\Lambda^{+}_{3},\
\Lambda^{c}_{3})}&\mathbf{0}_{(\Lambda^{+}_{3},\ \Lambda_{u})}\\\
\mathbf{0}_{(\Lambda^{c}_{3},\ \Lambda_{1})}&\mathbf{0}_{(\Lambda^{c}_{3},\
\Lambda_{2})}&\mathbf{0}_{(\Lambda^{c}_{3},\
\Lambda^{+}_{3})}&I_{(\Lambda^{c}_{3},\
\Lambda^{c}_{3})}&\mathbf{0}_{(\Lambda^{c}_{3},\ \Lambda_{u})}\\\
\mathbf{0}_{(\Lambda_{u},\ \Lambda_{1})}&\mathbf{0}_{(\Lambda_{u},\
\Lambda_{2})}&\mathbf{0}_{(\Lambda_{u},\
\Lambda^{+}_{3})}&\mathbf{0}_{(\Lambda_{u},\
\Lambda^{c}_{3})}&I_{(\Lambda_{u},\ \Lambda_{u})}\\\ I_{(I_{GH_{3}},\
\Lambda_{1})}&\mathbf{0}_{(I_{GH_{3}},\
\Lambda_{2})}&\mathbf{0}_{(I_{GH_{3}},\
\Lambda^{+}_{3})}&\mathbf{0}_{(I_{GH_{3}},\
\Lambda^{c}_{3})}&\mathbf{0}_{(I_{GH_{3}},\ \Lambda_{u})}\\\
\mathbf{0}_{(I_{GH_{4}},\ \Lambda_{1})}&\mathbf{0}_{(I_{GH_{4}},\
\Lambda_{2})}&\mathbf{0}_{(I_{GH_{4}},\ \Lambda^{+}_{3})}&I_{(I_{GH_{4}},\
\Lambda^{c}_{3})}&\mathbf{0}_{(I_{GH_{4}},\ \Lambda_{u})}\\\ I_{(\Lambda_{1},\
\Lambda_{1})}&\mathbf{0}_{(\Lambda_{1},\
\Lambda_{2})}&\mathbf{0}_{(\Lambda_{1},\
\Lambda^{+}_{3})}&\mathbf{0}_{(\Lambda_{1},\
\Lambda^{c}_{3})}&\mathbf{0}_{(\Lambda_{1},\ \Lambda_{u})}\\\
\mathbf{0}_{(\Lambda_{2},\ \Lambda_{1})}&I_{(\Lambda_{2},\
\Lambda_{2})}&\mathbf{0}_{(\Lambda_{2},\
\Lambda^{+}_{3})}&\mathbf{0}_{(\Lambda_{2},\
\Lambda^{c}_{3})}&\mathbf{0}_{(\Lambda_{2},\ \Lambda_{u})}\\\
\mathbf{0}_{(\Lambda^{+}_{3},\ \Lambda_{1})}&\mathbf{0}_{(\Lambda^{+}_{3},\
\Lambda_{2})}&I_{(\Lambda^{+}_{3},\
\Lambda^{+}_{3})}&\mathbf{0}_{(\Lambda^{+}_{3},\
\Lambda^{c}_{3})}&\mathbf{0}_{(\Lambda^{+}_{3},\ \Lambda_{u})}\\\
\end{array}\right],$

and assume that we can find some vectors
$\overline{\rho}^{g}\in\mathbb{R}^{S_{3}}$ and
$\overline{\rho}^{g}\geq\mathbf{0}$,
$\overline{\rho}^{h}\in\mathbb{R}^{W_{2}}$ and
$\overline{\rho}^{h}\geq\mathbf{0}$,
$\overline{\rho}^{i}\in\mathbb{R}^{W_{2}}$ and
$\overline{\rho}^{i}\geq\mathbf{0}$,
$\overline{\rho}^{j}\in\mathbb{R}^{U_{3}}$ and
$\overline{\rho}^{j}\geq\mathbf{0}$,
$\overline{\rho}^{m}\in\mathbb{R}^{W_{3}}$ and
$\overline{\rho}^{m}\geq\mathbf{0}$, and
$\overline{\rho}^{n}\in\mathbb{R}^{U_{4}}$ and
$\overline{\rho}^{n}\geq\mathbf{0}$, such that

$\begin{array}[]{l}\sum\limits_{s=1}^{S_{3}}\rho_{s}^{g}\left[\begin{array}[]{c}\left(BB^{\top}\right)_{(g_{s},\
\cdot\ )}^{\top}\\\ \left[\begin{array}[]{c}\mathbf{0}_{D_{1}+D_{2}}\\\
e^{S_{3}}_{g_{s}}\end{array}\right]\end{array}\right]\\!+\\!\sum\limits_{s=1}^{W_{2}}\rho_{s}^{h}\left[\begin{array}[]{c}\left(BB^{\top}\right)_{(h_{s},\
\cdot\ )}^{\top}\\\ \left[\begin{array}[]{c}e^{W_{2}}_{h_{s}}\\\
\mathbf{0}_{Tm_{2}-D_{1}}\end{array}\right]\end{array}\right]\\!+\\!\sum\limits_{s=1}^{W_{2}}\rho_{s}^{i}\left[\begin{array}[]{c}\left[\begin{array}[]{c}e^{W_{2}}_{i_{s}}\\\
\mathbf{0}_{Tm_{2}-D_{1}}\end{array}\right]\\\
\mathbf{0}_{Tm_{2}}\end{array}\right]\\!+\\!\\\
\sum\limits_{s=1}^{U_{3}}\rho_{s}^{j}\left[\begin{array}[]{c}\left[\begin{array}[]{c}\mathbf{0}_{D_{1}}\\\
e^{U_{3}}_{j_{s}}\\\ \mathbf{0}_{D_{3}+D_{4}+D_{5}}\end{array}\right]\\\
\mathbf{0}_{Tm_{2}}\end{array}\right]\\!+\\!\sum\limits_{s=1}^{W_{3}}\rho_{s}^{m}\left[\begin{array}[]{c}\mathbf{0}_{Tm_{2}}\\\
\left[\begin{array}[]{c}\mathbf{0}_{(D_{1}+D_{2}+D_{3})}\\\
e^{W_{3}}_{m_{s}}\\\ \mathbf{0}_{D_{5}}\\\
\end{array}\right]\end{array}\right]\\!+\\!\sum\limits_{s=1}^{U_{4}}\rho_{s}^{n}\left[\begin{array}[]{c}\mathbf{0}_{Tm_{2}}\\\
\left[\begin{array}[]{c}e^{U_{4}}_{n_{s}}\\\ \mathbf{0}_{D_{4}+D_{5}}\\\
\end{array}\right]\end{array}\right]\\!=\\!\mathbf{0}.\end{array}$

The above equation is equivalent to the compact system

$\left[\begin{array}[]{c}\sum\limits_{s=1}^{S_{3}}\rho_{s}^{g}\left(\left(BB^{\top}\right)_{(g_{s},\
\cdot)}\right)^{\top}+\sum\limits_{s=1}^{W_{2}}\left(\left(BB^{\top}\right)_{(h_{s},\
\cdot)}\right)^{\top}+\left[\begin{array}[]{c}\overline{\rho}^{i}\\\
\overline{\rho}^{j}\\\ \mathbf{0}_{D_{3}+D_{4}+D_{5}}\end{array}\right]\\\
\overline{\rho}^{h}+\overline{\rho}_{\Lambda_{1}}^{n}\\\
\overline{\rho}_{\Lambda_{2}}^{n}\\\
\overline{\rho}_{\Lambda^{+}_{3}}^{g}+\overline{\rho}_{\Lambda^{+}_{3}}^{n}\\\
\overline{\rho}_{\Lambda^{c}_{3}}^{g}+\overline{\rho}^{m}\\\
\overline{\rho}_{\Lambda_{u}}^{g}\end{array}\right]=\mathbf{0},$

which leads to $\overline{\rho}^{g}=\mathbf{0},\
\overline{\rho}^{h}=\mathbf{0},\ \overline{\rho}^{i}=\mathbf{0},\
\overline{\rho}^{j}=\mathbf{0},\ \overline{\rho}^{m}=\mathbf{0},\
\overline{\rho}^{n}=\mathbf{0}$, given that
$\overline{\rho}^{g}\geq\mathbf{0},\ \overline{\rho}^{h}\geq\mathbf{0},\
\overline{\rho}^{i}\geq\mathbf{0},\ \overline{\rho}^{j}\geq\mathbf{0},\
\overline{\rho}^{m}\geq\mathbf{0},\ \overline{\rho}^{n}\geq\mathbf{0}$.
Therefore, the row vectors in the matrix $\Gamma_{sub}$ are positively-
linearly independent.

###  4.4 The main result

Based on the above lemmas, we are ready to present the main theorem on the
MPEC-MFCQ.

######  Theorem 3.

Let $v=(C,\zeta,z,\alpha,\xi)$ be any feasible point for the MPEC (25), then
$v$ satisfies the MPEC-MFCQ.

Proof: Assume there exist $\overline{\rho}^{a}\in\mathbb{R}^{S_{1}}\
\text{and}\ \overline{\rho}^{a}\geq\mathbf{0},\
\overline{\rho}^{b}\in\mathbb{R}^{W_{1}}\ \text{and}\
\overline{\rho}^{b}\geq\mathbf{0},\ \overline{\rho}^{c}\in\mathbb{R}^{W_{1}}\
\text{and}\ \overline{\rho}^{c}\geq\mathbf{0},\
\overline{\rho}^{d}\in\mathbb{R}^{U_{1}}\ \text{and}\
\overline{\rho}^{d}\geq\mathbf{0},\ \overline{\rho}^{e}\in\mathbb{R}^{S_{2}}\
\text{and}\ \overline{\rho}^{e}\geq\mathbf{0},\
\overline{\rho}^{f}\in\mathbb{R}^{U_{2}}\ \text{and}\
\overline{\rho}^{f}\geq\mathbf{0},\ \overline{\rho}^{g}\in\mathbb{R}^{S_{3}}\
\text{and}\ \overline{\rho}^{g}\geq\mathbf{0},\
\overline{\rho}^{h}\in\mathbb{R}^{W_{2}}\ \text{and}\ \rho^{h}\geq\mathbf{0},\
\overline{\rho}^{i}\in\mathbb{R}^{W_{2}}\ \text{and}\
\overline{\rho}^{i}\geq\mathbf{0},\ \overline{\rho}^{j}\in\mathbb{R}^{U_{3}}\
\text{and}\ \overline{\rho}^{j}\geq\mathbf{0},\
\overline{\rho}^{k}\in\mathbb{R}^{S_{4}}\ \text{and}\
\overline{\rho}^{k}\geq\mathbf{0},\ \overline{\rho}^{l}\in\mathbb{R}^{W_{3}}\
\text{and}\ \overline{\rho}^{l}\geq\mathbf{0},\
\overline{\rho}^{m}\in\mathbb{R}^{W_{3}}\ \text{and}\
\overline{\rho}^{m}\geq\mathbf{0},\ \overline{\rho}^{n}\in\mathbb{R}^{U_{4}}\
\text{and}\ \overline{\rho}^{n}\geq\mathbf{0},$ such that the following holds

$\sum\limits_{s=1}^{S_{1}}\rho_{s}^{a}\left[\begin{array}[]{c}0\\\
\mathbf{0}_{Tm_{1}}\\\ \left(\Gamma_{a}^{3}\right)_{(a_{s},\ \cdot\
)}^{\top}\\\ \left(AB^{\top}\right)_{(a_{s},\ \cdot\ )}^{\top}\\\
\mathbf{0}_{Tm_{2}}\end{array}\right]+\sum\limits_{s=1}^{W_{1}}\rho_{s}^{b}\left[\begin{array}[]{c}0\\\
\mathbf{0}_{Tm_{1}}\\\ \left(\Gamma_{b}^{3}\right)_{(b_{s},\ \cdot\
)}^{\top}\\\ \left(AB^{\top}\right)_{(b_{s},\ \cdot\ )}^{\top}\\\
\mathbf{0}_{Tm_{2}}\end{array}\right]+\sum\limits_{s=1}^{W_{1}}\rho_{s}^{c}\left[\begin{array}[]{c}0\\\
\left(\Gamma_{c}^{2}\right)_{(c_{s},\ \cdot\ )}^{\top}\\\
\mathbf{0}_{Tm_{1}}\\\ \mathbf{0}_{Tm_{2}}\\\
\mathbf{0}_{Tm_{2}}\end{array}\right]$
$\begin{array}[]{l}+\sum\limits_{s=1}^{U_{1}}\rho_{s}^{d}\left[\begin{array}[]{c}0\\\
\left(\Gamma_{d}^{2}\right)_{(d_{s},\ \cdot\ )}^{\top}\\\
\mathbf{0}_{Tm_{1}}\\\ \mathbf{0}_{Tm_{2}}\\\
\mathbf{0}_{Tm_{2}}\end{array}\right]+\sum\limits_{s=1}^{S_{2}}\rho_{s}^{e}\left[\begin{array}[]{c}0\\\
\left(\Gamma_{e}^{2}\right)_{(e_{s},\ \cdot\ )}^{\top}\\\
\mathbf{0}_{Tm_{1}}\\\ \mathbf{0}_{Tm_{2}}\\\
\mathbf{0}_{Tm_{2}}\end{array}\right]+\sum\limits_{s=1}^{U_{2}}\rho_{s}^{f}\left[\begin{array}[]{c}0\\\
\mathbf{0}_{Tm_{1}}\\\ \left(\Gamma_{f}^{3}\right)_{(f_{s},\ \cdot\
)}^{\top}\\\ \mathbf{0}_{Tm_{2}}\\\ \mathbf{0}_{Tm_{2}}\end{array}\right]\\\
+\sum\limits_{s=1}^{S_{3}}\rho_{s}^{g}\left[\begin{array}[]{c}0\\\
\mathbf{0}_{Tm_{1}}\\\ \mathbf{0}_{Tm_{1}}\\\ \left(BB^{\top}\right)_{(g_{s},\
\cdot\ )}^{\top}\\\ \left(\Gamma_{g}^{5}\right)_{(g_{s},\ \cdot\
)}^{\top}\end{array}\right]+\sum\limits_{s=1}^{W_{2}}\rho_{s}^{h}\left[\begin{array}[]{c}0\\\
\mathbf{0}_{Tm_{1}}\\\ \mathbf{0}_{Tm_{1}}\\\ \left(BB^{\top}\right)_{(h_{s},\
\cdot\ )}^{\top}\\\ \left(\Gamma_{h}^{5}\right)_{(h_{s},\ \cdot\
)}^{\top}\end{array}\right]+\sum\limits_{s=1}^{W_{2}}\rho_{s}^{i}\left[\begin{array}[]{c}0\\\
\mathbf{0}_{Tm_{1}}\\\ \mathbf{0}_{Tm_{1}}\\\
\left(\Gamma_{i}^{4}\right)_{(i_{s},\ \cdot\ )}^{\top}\\\
\mathbf{0}_{Tm_{2}}\end{array}\right]\\\
+\sum\limits_{s=1}^{U_{3}}\rho_{s}^{j}\left[\begin{array}[]{c}0\\\
\mathbf{0}_{Tm_{1}}\\\ \mathbf{0}_{Tm_{1}}\\\
\left(\Gamma_{j}^{4}\right)_{(j_{s},\ \cdot\ )}^{\top}\\\
\mathbf{0}_{Tm_{2}}\end{array}\right]+\sum\limits_{s=1}^{S_{4}}\rho_{s}^{k}\left[\begin{array}[]{c}1\\\
\mathbf{0}_{Tm_{1}}\\\ \mathbf{0}_{Tm_{1}}\\\
\left(\Gamma_{k}^{4}\right)_{(k_{s},\ \cdot\ )}^{\top}\\\
\mathbf{0}_{Tm_{2}}\end{array}\right]+\sum\limits_{s=1}^{W_{3}}\rho_{s}^{l}\left[\begin{array}[]{c}1\\\
\mathbf{0}_{Tm_{1}}\\\ \mathbf{0}_{Tm_{1}}\\\
\left(\Gamma_{l}^{4}\right)_{(l_{s},\ \cdot\ )}^{\top}\\\
\mathbf{0}_{Tm_{2}}\end{array}\right]\\\
+\sum\limits_{s=1}^{W_{3}}\rho_{s}^{m}\left[\begin{array}[]{c}0\\\
\mathbf{0}_{Tm_{1}}\\\ \mathbf{0}_{Tm_{1}}\\\ \mathbf{0}_{Tm_{2}}\\\
\left(\Gamma_{m}^{5}\right)_{(m_{s},\ \cdot\
)}^{\top}\end{array}\right]+\sum\limits_{s=1}^{U_{4}}\rho_{s}^{n}\left[\begin{array}[]{c}0\\\
\mathbf{0}_{Tm_{1}}\\\ \mathbf{0}_{Tm_{1}}\\\ \mathbf{0}_{Tm_{2}}\\\
\left(\Gamma_{n}^{5}\right)_{(n_{s},\ \cdot\
)}^{\top}\end{array}\right]=\mathbf{0}.\end{array}$ (41)

From the first row in Equation (41), we get
$\sum\limits_{s=1}^{S_{4}}\rho_{s}^{k}+\sum\limits_{s=1}^{W_{3}}\rho_{s}^{l}=0$.
Together with the fact that $\overline{\rho}^{k}\geq\mathbf{0},\
\overline{\rho}^{l}\geq\mathbf{0}$, we get $\overline{\rho}^{k}=\mathbf{0}$
and $\overline{\rho}^{l}=\mathbf{0}$. From Lemma 1, we get
$\overline{\rho}^{c}=\mathbf{0},\ \overline{\rho}^{d}=\mathbf{0},\
\overline{\rho}^{e}=\mathbf{0}$ in Equation (41). From Lemma 2, we get
$\overline{\rho}^{a}=\mathbf{0},\ \overline{\rho}^{b}=\mathbf{0},\
\overline{\rho}^{f}=\mathbf{0}$ in Equation (41). From Lemma 3, we get
$\overline{\rho}^{g}=\mathbf{0},\ \overline{\rho}^{h}=\mathbf{0},\
\overline{\rho}^{i}=\mathbf{0},\ \overline{\rho}^{j}=\mathbf{0},\
\overline{\rho}^{m}=\mathbf{0},\ \overline{\rho}^{n}=\mathbf{0}$ in Equation
(41).

In summary, the row vectors in the matrix $\Gamma$ (34) are positive-linearly
independent at every feasible point $v$ for the MPEC (25). That is to say,
every feasible point $v$ for the MPEC (25) satisfies the MPEC-MFCQ.

##  5 Numerical results

In this section, we present the GR-CV, which is a concrete implementation of
the GRM in Algorithm 1 for selecting the hyperparameter $C$ in SVC, as shown
in Algorithm 2. We show numerical results of the proposed GR-CV, and compare
it with other approaches.

Algorithm 2 The Global Relaxation Cross-Validation Algorithm (GR-CV)

1:Given $T$, split the data set into a subset $\Omega$ with $l_{1}$ points and
a hold-out test set $\Theta$ with $l_{2}$ points. The set $\Omega$ is equally
partitioned into $T$ pairwise disjoint subsets, one for each fold.

2:Select an optimal hyperparameter $\widehat{C}$ by the GRM in Algorithm 1.

3:Post-processing procedure. The regularization hyperparameter $\widehat{C}$
is rescaled by a factor $\frac{T}{T-1}$. Then, an $l_{1}$-loss SVC problem is
solved on the subset $\Omega$ using $\frac{T}{T-1}\widehat{C}$ by ALM-SNCG
algorithm in Yan2020efficient . This gives the final classifier $\widehat{w}$.

All the numerical tests are conducted in Matlab R2018a on a Windows 7 Dell
Laptop with an Intel(R) Core(TM) i5-6500U CPU at 3.20GHz and 8 GB of RAM. All
the data sets are collected from the LIBSVM library:
https://www.csie.ntu.edu.tw/cjlin/ libsvmtools/datasets/. Each data set is
split into a subset $\Omega$ with $l_{1}$ points (it is used for cross-
validation) and a hold-out test set $\Theta$ with $l_{2}$ points. The data
descriptions are shown in Table 1.

Table 1: Descriptions of data sets. Data set | $l_{1}$ | $l_{2}$ | n | Data set | $l_{1}$ | $l_{2}$ | n
---|---|---|---|---|---|---|---
heart | 189 | 81 | 13 | splice | 300 | 700 | 60
breast | 240 | 172 | 10 | fourclass | 300 | 562 | 2
colon-cancer | 36 | 26 | 2000 | w1a | 240 | 260 | 300
ionosphere | 246 | 105 | 34 | w2a | 300 | 500 | 300
australian | 270 | 420 | 14 | a1a | 300 | 200 | 119
diabetes | 270 | 498 | 8 | german.number | 207 | 793 | 24

We compare our GR-CV with two other approaches: the inexact cross-validation
method (In-CV) and the grid search algorithm (G-S). In-CV
kunapuli2008classification is a relaxation method based on the relaxation of
the complementarity constraints by a prescribed tolerance parameter
$\mathbf{tol}>0$. That is, solving (NLP-$t_{k}$) with $t_{k}=\mathbf{tol}$ as
a fixed tolerance rather than decreasing $t_{k}$ gradually.

The parameters of three methods are set as follows. For GR-CV, we set the
initial values as $v_{0}=\left[1,\
\mathbf{0}_{1\times\overline{m}}\right]^{\top}$, $t_{0}=1,\ t_{\min}=10^{-8},\
\sigma=0.01.$ The relaxed subproblems (NLP-$t_{k}$) are solved by the snsolve
function, which is part of the SNOPT solver philip2002user . For In-CV, we use
the same $v_{0}$ as in GR-CV and $\mathbf{tol}=10^{-4}$. For G-S, a typical
grid range for $C$ would be $C\in\\{10^{-4},\ 10^{-3},\ 10^{-2}$, $10^{-1},\
1,\ 10^{1},\ 10^{2},\ 10^{3},\ 10^{4}\\}$ kunapuli2008classification . In each
training process, the ALM-SNCG algorithm from Yan2020efficient , which is
outstanding and competitive with the most popular methods in LIBLINEAR
(https://www.csie.ntu.edu.tw/ cjlin/liblinear/) in both speed and accuracy, is
used to solve the $l_{1}$-loss SVC problem.

We compare the aforementioned methods in the following three aspects:

  * 1.

Test error ($E_{t}$) as defined by

$E_{t}=\frac{1}{l_{2}}\sum_{(x,y)\in\Theta}\frac{1}{2}\mid\operatorname{sign}\left(\widehat{w}^{\top}x\right)-y\mid,$

which is a measure of the ability of generalization.

  * 2.

CV error ($E_{C}$) as defined in the objective function of problem (13).

  * 3.

The number of iterations $k$ for an algorithm, and the total number of
iterations $it$ for solving the subproblems (short for $(k,\ it$)).

We also report the maximum violation of all constraints defined as in (26), to
measure the feasibility of the final solution given by GR-CV and In-CV.

The results are reported in Table 2, where we mark the winners of test error
$E_{t}$, CV error $E_{C}$ and the maximum violation of all constraints Vio in
bold. We also show the comparisons of the three methods for different data
sets on test error $E_{t}$ and CV error $E_{C}$ in Figures 9 and 10,
respectively. The data sets on the horizontal axis are arranged in the order
shown in Table 2.

From Figure 9, Figure 10 and Table 2, we have the following observations.
Firstly, GR-CV performs the best in terms of test error, implying that our
approach is more capable of generalization. Secondly, in terms of test error
in Figure 9, GR-CV is competitive with G-S. GR-CV is the winner in five data
sets of all the twelve datasets where as G-S wins in eight datasets among the
twelve datasets. Finally, comparing GR-CV with In-CV, the feasibility of the
solution returned by GR-CV is significantly better than that by In-CV since
Vio given by GR-CV is much smaller than that by In-CV. In terms of cpu time,
it is obvious that In-CV takes less time than GR-CV since it only solves the
relaxation problem (NLP-$t_{k}$) once. Since G-S is basically solving a
completely different type of problem to find the hyperparameter $C$, it is
does not make sense to compare the cpu time between GR-CV and G-S.

Table 2: Computational results for $T=3$. | Data set | Method |  $E_{t}$ ($\%$) |  $E_{C}$ ($\%$) | Vio | $(k,\ it)$
---|---|---|---|---|---|---
1 | heart | GR-CV | 9.88 | 17.46 | 1.51e$-$6 | (5, 24165)
|  | In-CV | 9.88 | 17.95 | 0.010 | (1,12418)
|  | G-S | 13.58 | 17.46 | $-$ | (27,425)
2 | breast | GR-CV | 4.07 | 5.42 | 4.98e$-$4 | (5,17092)
|  | In-CV | 4.07 | 5.42 | 0.006 | (1,14971)
|  | G-S | 4.07 | 6.25 | $-$ | (27,298)
3 | colon-cancer | GR-CV | 19.23 | 2.78 | 9.69e$-$5 | (5,2166)
|  | In-CV | 23.08 | 2.78 | 0.005 | (1,1102)
|  | G-S | 26.92 | 2.78 | $-$ | (27,167)
4 | ionosphere | GR-CV | 0.95 | 27.61 | 0.03 | (5,96200)
|  | In-CV | 1.90 | 29.76 | 0.03 | (1,29530)
|  | G-S | 4.76 | 18.70 | $-$ | (27,522)
5 | australian | GR-CV | 14.29 | 14.44 | 3.03e$-$6 | (5,32583)
|  | In-CV | 14.52 | 14.81 | 0.008 | (1,26703)
|  | G-S | 14.52 | 14.44 | $-$ | (27,430)
6 | diabetes | GR-CV | 20.48 | 24.44 | 1.75e$-$5 | (5,33294)
|  | In-CV | 20.48 | 25.18 | 0.005 | (1,26558)
|  | G-S | 20.48 | 25.19 | $-$ | (27,416)
7 | splice | GR-CV | 23.29 | 29.01 | 0.009 | (5,83306)
|  | In-CV | 26.29 | 24.63 | 0.005 | (1,24333)
|  | G-S | 23.29 | 23.33 | $-$ | (27,526)
8 | fourclass | GR-CV | 22.06 | 28.67 | 5.83e$-$5 | (5,17275)
|  | In-CV | 22.24 | 28.65 | 0.008 | (1,8989)
|  | G-S | 22.24 | 23.33 | $-$ | (27,349)
9 | w1a | GR-CV | 0.00 | 23.33 | 4.26e$-$4 | (5,75793)
|  | In-CV | 0.00 | 22.88 | 0.009 | (1,28810)
|  | G-S | 0.00 | 30.00 | $-$ | (27,366)
10 | w2a | GR-CV | 0.00 | 25.93 | 1.50e$-$4 | (5,88758)
|  | In-CV | 0.00 | 22.11 | 0.009 | (1,31708)
|  | G-S | 0.00 | 35.67 | $-$ | (27,522)
11 | a1a | GR-CV | 19.50 | 15.33 | 7.64e$-$5 | (5,64349)
|  | In-CV | 19.50 | 15.65 | 0.013 | (1,36010)
|  | G-S | 20.00 | 14.67 | $-$ | (27,533)
12 | german. | GR-CV | 25.73 | 26.09 | 5.29e$-$5 | (5,33317)
| number | In-CV | 26.86 | 26.08 | 0.068 | (1,24850)
|  | G-S | 26.86 | 25.60 | $-$ | (27,482)
Figure 9: The comparison among the three methods on test error. Figure 10: The
comparison among the three methods on CV error. Figure 11: Effect of
increasing the number of folds on test error and CV error.

To further study the effect of increasing the number of folds on test error
$E_{t}$ and CV error $E_{C}$ in the three methods, we report the results on
the Australian data set in Figure 11. The results show that as $T$ changes,
the test error for GR-CV is always the lowest, and the CV error for GR-CV is
competitive with the other two methods. Meanwhile it is clear that larger
number of folds can be successfully solved for GR-CV, the computing time grows
with the number of folds because of the increasing number of variables and
constraints for the MPEC to be solved. The ranges of the test error and CV
error for different numbers of folds are not large, so $T=3$ represents a
reasonable choice.

##  6 Conclusion

We have proposed a bilevel optimization model for the hyperparameter selection
for support vector classification in which the upper-level problem minimizes a
T-fold cross validation error and the lower-level problems are T $l_{1}$-loss
SVC problems on the training sets. We reformulated the bilevel optimization
problem into an MPEC, and proposed the GR-CV to solve it based on the GRM from
scholtes2001convergence . We also proved that the MPEC-MFCQ automatically
holds at each feasible point. Extensive numerical results on the data sets
from the LIBSVM library demonstrated the superior generalization performance
of the proposed method over almost all the data sets used in this paper.

## Acknowledgments.

The work of AZ is supported by the EPSRC grant EP/V049038/1 and the Alan
Turing Institute under the EPSRC grant EP/N510129/1.

## References

  *   * (1) Cortes, C., Vapnik, V.: Support-vector networks. Machine Learning 20(3), 273–297 (1995)
  * (2) Chauhan, V.K., Dahiya, K., Sharma, A.: Problem formulations and solvers in linear svm: a review. Artificial Intelligence Review 52(2), 803–855 (2019)
  * (3) Vapnik, V.: The Nature of Statistical Learning Theory. Springer, New York (2013)
  * (4) Chapelle, O., Vapnik, V., Bousquet, O., Mukherjee, S.: Choosing multiple parameters for support vector machines. Machine Learning 46(1), 131–159 (2002)
  * (5) Duan, K.B., Keerthi, S.S., Poo, A.N.: Evaluation of simple performance measures for tuning svm hyperparameters. Neurocomputing 51, 41–59 (2003)
  * (6) Keerthi, S.S., Sindhwani, V., Chapelle, O.: An efficient method for gradient-based adaptation of hyperparameters in svm models. MIT Press (2007)
  * (7) Kunapuli, G.: A Bilevel Optimization Approach to Machine Learning. Rensselaer Polytechnic Institute, New York (2008)
  * (8) Couellan, N., Wang, W.J.: Bi-level stochastic gradient for large scale support vector machine. Neurocomputing 153, 300–308 (2015)
  * (9) Kunapuli, G., Bennett, K.P., Hu, J., Pang, J.-S.: Bilevel model selection for support vector machines. Data mining and mathematical programming 45, 129–158 (2008)
  * (10) Kunapuli, G., Bennett, K.P., Hu, J., Pang, J.-S.: Classification model selection via bilevel programming. Optimization Methods & Software 23(4), 475–489 (2008)
  * (11) Momma, M., Bennett, K.P.: A pattern search method for model selection of support vector regression. In: Proceedings of the 2002 SIAM International Conference on Data Mining, pp. 261–274 (2002)
  * (12) Bennett, K.P., Hu, J., Ji, X.Y., Kunapuli, G., Pang, J.-S.: Model selection via bilevel optimization. In: The 2006 IEEE International Joint Conference on Neural Network Proceedings, pp. 1922–1929 (2006). IEEE
  * (13) Yu, T., Zhu, H.: Hyper-parameter optimization: A review of algorithms and applications. arXiv preprint arXiv:2003.05689 (2020)
  * (14) Luo, G.: A review of automatic selection methods for machine learning algorithms and hyper-parameter values. Network Modeling Analysis in Health Informatics and Bioinformatics 5(1), 1–16 (2016)
  * (15) Okuno, T., Takeda, A., Kawana, A.: Hyperparameter learning for bilevel nonsmooth optimization. arXiv preprint arXiv:1806.01520 (2018)
  * (16) Kunisch, K., Pock, T.: A bilevel optimization approach for parameter learning in variational models. SIAM Journal on Imaging Sciences 6(2), 938–983 (2013)
  * (17) Moore, G., Bergeron, C., Bennett, K.P.: Gradient-type methods for primal SVM model selection. http://opt.kyb.tuebingen.mpg.de/papers/OPT2010-moore.pdf. Online; accessed 10-July-2021
  * (18) Moore, G., Bergeron, C., Bennett, K.P.: Nonsmooth bilevel programming for hyperparameter selection. In: 2009 IEEE International Conference on Data Mining Workshops, pp. 374–381 (2009)
  * (19) Colson, B., Marcotte, P., Savard, G.: An overview of bilevel optimization. Annals of Operations Research 153(1), 235–256 (2007)
  * (20) Dempe, S.: Foundations of Bilevel Programming. Kluwer, Dordrecht (2002)
  * (21) Dempe, S., Zemkoho, A.B.: Bilevel Optimization Advances and Next Challenges. Springer, New York (2020)
  * (22) Mejía-de-Dios, J.-A., Mezura-Montes, E.: A metaheuristic for bilevel optimization using tykhonov regularization and the quasi-newton method. In: 2019 IEEE Congress on Evolutionary Computation, pp. 3134–3141 (2019)
  * (23) Zemkoho, A.B., Zhou, S.L.: Theoretical and numerical comparison of the Karush–Kuhn–Tucker and value function reformulations in bilevel optimization. Computational Optimization and Applications 78(2), 625–674 (2021)
  * (24) Fischer, A., Zemkoho, A.B., Zhou, S.L.: Semismooth newton-type method for bilevel optimization: Global convergence and extensive numerical experiments. Optimization Methods & Software (2021). https://doi.org/10.1080/10556788.2021.1977810
  * (25) Lin, G.-H., Xu, M.W., Ye, J.J.: On solving simple bilevel programs with a nonconvex lower level program. Mathematical Programming 144(1), 277–305 (2014)
  * (26) Ye, J.J., Zhu, D.L.: New necessary optimality conditions for bilevel programs by combining the mpec and value function approaches. SIAM Journal on Optimization 20(4), 1885–1905 (2010)
  * (27) Ochs, P., Ranftl, R., Brox, T., Pock, T.: Techniques for gradient-based bilevel optimization with non-smooth lower level problems. Journal of Mathematical Imaging and Vision 56(2), 175–194 (2016)
  * (28) Ochs, P., Ranftl, R., Brox, T., Pock, T.: Bilevel optimization with nonsmooth lower level problems. In: International Conference on Scale Space and Variational Methods in Computer Vision, pp. 654–665 (2015)
  * (29) Luo, Z.-Q., Pang, J.-S., Ralph, D.: Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Cambridge (1996)
  * (30) Bennett, K.P., Kunapuli, G., Hu, J., Pang, J.-S.: Bilevel optimization and machine learning. In: IEEE World Congress on Computational Intelligence, pp. 25–47 (2008)
  * (31) Wu, J., Zhang, L.W., Zhang, Y.: An inexact newton method for stationary points of mathematical programs constrained by parameterized quasi-variational inequalities. Numerical Algorithms 69(4), 713–735 (2015)
  * (32) Harder, F., Mehlitz, P., Wachsmuth, G.: Reformulation of the m-stationarity conditions as a system of discontinuous equations and its solution by a semismooth newton method. SIAM Journal on Optimization 31(2), 1459–1488 (2021)
  * (33) Lee, Y.-C., Pang, J.-S., Mitchell, J.E.: Global resolution of the support vector machine regression parameters selection problem with lpcc. EURO Journal on Computational Optimization 3(3), 197–261 (2015)
  * (34) Mangasarian, O.L.: Misclassification minimization. Journal of Global Optimization 5(4), 309–323 (1994)
  * (35) Scholtes, S.: Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM Journal on Optimization 11(4), 918–936 (2001)
  * (36) Cristianini, N., Shawe-Taylor, J.: An Introduction to Support Vector Machines and Other Kernel-based Learning Methods. Cambridge University Press, Cambridge (2000)
  * (37) Galli, L., Lin, C.-J.: A study on truncated newton methods for linear classification. IEEE Transactions on Neural Networks and Learning Systems (2021)
  * (38) Hsieh, C.-J., Chang, K.-W., Lin, C.-J., Keerthi, S.S., Sundararajan, S.: A dual coordinate descent method for large-scale linear SVM. In: Proceedings of the 25th International Conference on Machine Learning, pp. 408–415 (2008)
  * (39) Dempe, S.: Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints. Optimization 52(3), 333–359 (2003)
  * (40) Ye, J.J.: Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints. Journal of Mathematical Analysis and Applications 307(1), 350–369 (2005)
  * (41) Flegel, M.L.: Constraint qualifications and stationarity concepts for mathematical programs with equilibrium constraints. PhD thesis, Universität Würzburg (2005)
  * (42) Guo, L., Lin, G.-H., Ye, J.J.: Solving mathematical programs with equilibrium constraints. Journal of Optimization Theory and Applications 166(1), 234–256 (2015)
  * (43) Jara-Moroni, F., Pang, J.-S., Wächter, A.: A study of the difference-of-convex approach for solving linear programs with complementarity constraints. Mathematical Programming 169(1), 221–254 (2018)
  * (44) Júdice, J.J.: Algorithms for linear programming with linear complementarity constraints. TOP 20(1), 4–25 (2012)
  * (45) Li, J.L., Huang, R.S., Jian, J.B.: A superlinearly convergent QP-free algorithm for mathematical programs with equilibrium constraints. Applied Mathematics and Computation 269, 885–903 (2015)
  * (46) Yu, B., Mitchell, J.E., Pang, J.-S.: Solving linear programs with complementarity constraints using branch-and-cut. Mathematical Programming Computation 11(2), 267–310 (2019)
  * (47) Anitescu, M.: On solving mathematical programs with complementarity constraints as nonlinear programs. Preprint ANL/MCS-P$864$-$1200$, Argonne National Laboratory, Argonne, IL 3 (2000)
  * (48) Facchinei, F., Pang, J.-S.: Finite-dimensional Variational Inequalities and Complementarity Problems. Springer, NewYork (2007)
  * (49) Fletcher, R., Leyffer, S., Ralph, D., Scholtes, S.: Local convergence of sqp methods for mathematical programs with equilibrium constraints. SIAM Journal on Optimization 17(1), 259–286 (2006)
  * (50) Fukushima, M., Tseng, P.: An implementable active-set algorithm for computing a b-stationary point of a mathematical program with linear complementarity constraints. SIAM Journal on Optimization 12(3), 724–739 (2002)
  * (51) Hoheisel, T., Kanzow, C., Schwartz, A.: Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints. Mathematical Programming 137(1), 257–288 (2013)
  * (52) Dempe, S., Zemkoho, A.B.: On the Karush–Kuhn–Tucker reformulation of the bilevel optimization problem. Nonlinear Analysis: Theory, Methods & Applications 75(3), 1202–1218 (2012)
  * (53) Yan, Y.Q., Li, Q.N.: An efficient augmented lagrangian method for support vector machine. Optimization Methods and Software 35(4), 855–883 (2020)
  * (54) Gill, P.E., Murray, W., Saunders, M.A.: User’s guide for snopt version 6, a fortran package for large-scale nonlinear programming. University of California, California (2002)