Constructing canonical tableau for a linear programming problem involving SVM

Question

I have the following set of inequalities and equalites

$$\begin{align}y_1x_1+\cdots +y_nx_n &= 0\\ x_1 &\geq 0\\\vdots\\x_n&\geq0 \\ x_1&\leq c\\\vdots \\x_n&\leq c,\end{align}$$

where $y_i\in \{-1, 1\},\;c\in\mathbb{R}$.

These are the constraints for the optimization problem for finding the optimal weights $\textbf{x}=(x_1, ..., x_n)\in\mathbb{R}^n$ for soft-margin Support Vector Machines model. My task is to find any initial feasible solution that will satisfy these constraints. For that I want to use the simplex-method. In order to achieve this, I will introduce artificial variables and slack variables (for the inequalities involving $c$), so I get my optimization problem for obtaining the initial feasible solution to be:

$$\begin{aligned} & \text{minimize:} & & \;Z=\sum_{i=1}^n a_i\\ & \text{subject to:} & & \; y_1x_1+\cdots +y_nx_n &= 0\\ & & & \; x_1+a_1 &= c\\ & & & \; x_2+a_2&=c\\ & & & \;\;\;\;\;\;\vdots\\ & & & \; x_n+a_n &=c \\ & & & \;\textbf{x}\geq\textbf{0}\\ & & & \;\textbf{a}\geq\textbf{0},\end{aligned}$$

where $\textbf{a}=(a_1, ..., a_n)$ is the vector of artificial variables. From this I get my canonical tableau to be:

$$\left[ \begin{array}{cccccccccc} 1 & 0 & 0 & \cdots & 0 & -1 & -1 & \cdots & -1 & 0 \\ 0 &y_1 & y_2 & \cdots & y_n & 0 & 0 & \cdots & 0 & 0 \\ 0 & 1 & 0 & \cdots & 0 & 1 & 0 & \cdots & 0 & c \\ 0 & 0 & 1 & \cdots & 0 & 0 & 1 & \cdots & 0 & c \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & & 1 & c \end{array} \right],$$

where the first row corresponds to the function $Z$, second to the constraint $y_1x_1+\cdots +y_nx_n = 0$, etc.

Now my questions is: Does my work make sence here? Have I correctly constructed the tableau so that the simplex procedure can be started from here in order to produce an initial feasible solution $\textbf{x}$ for the original constraints?

Thank you!

My references: book (pages 33-54), wiki

Answer 1

The variables $a$ that you added are slack variables, not artificial ones. Thus, you do not need to penalize them since they can take any value within $[0,c]$ in a feasible (w.r.t. the initial LP) solution. They can be used as basic variables for the constraints they appear in (once their cost is changed to $0$).

You still need a basic variable for the first constraint. You can add two artifical variables $+t−s$ in constraint (1), and use $\min s+t$ as objective function. Then, in the objective function, replace $t$ by its expression in function of the other variables using ctr. (1), and the simplex algorithm can be started. Note that you are not guranteed at all not to obtain $x=0$ as optimal solution. You may add another constraint (like $\sum x_i\ge \epsilon$, or anything that makes the solution closer to what you are looking for) in this purpose.