1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ How do you want to actually solve the linear program? Most available softwares do not require the user to put the LP in canonical form, so that you may not need to bother about that. Also, I find a bit strange that you see it as an LP: since this is only a feasibility problem (you have no objective function), you could use other methods to solve linear systems. Are you in the case where you are not sure that a feasible solution exists? $\endgroup$ – borisd May 7 '15 at 20:07
  • $\begingroup$ hi @borisd I'm using simplex method to solve for a initial feasible solution :) Yes, I'm not always sure if a feasible solution exists. I'm trying to solve a quadratic program involving equality and inequality constraints. I'm using gradient projection for solving this problem. The problem is that gradient projection needs an initial feasible solution to start up. This is why I need the linear program solution for. Did that answer your question? :) One note also, I don't want to use a package, I want to code this myself in order to fully understand what's going on under the hood :) $\endgroup$ – jjepsuomi May 7 '15 at 20:14
  • $\begingroup$ The question might be stupid, but isn't $x=0$ a feasible solution here? $\endgroup$ – borisd May 7 '15 at 20:22
  • $\begingroup$ hi @borisd you're correct, it is :) I simply wanted to see if I could find other than $x=0$ as an initial solution with simplex. I could possibly get a closer initial solution to the optima than $x=0$. $\endgroup$ – jjepsuomi May 7 '15 at 20:25
  • 1
    $\begingroup$ To answer your initial question (is the tableau ready for phase 1 simplex), 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. The can be used as basic variables for the constraints they appear in (since their cost must be changed to 0). You still need a basic variable for the first constraint. $\endgroup$ – borisd May 7 '15 at 20:33
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.