Artificial variables

Figure 3.10 Illustrative example of linear regression between two artificial variables for six experimental units. For each unit, denoted by a different graphical symbol, a closely packed set of five observations with negative slope is measured. The whole data set, if fitted naively, would show a very significant positive slope.

The following figure shows the constraints. If slack variables jc3, x4 and x5 are added respectively to the inequality constraints, you can see from the diagram that the origin is not a feasible point, that is, you cannot start the simplex method by letting x x2 = 0 because then x3 = 20, x4 = -5, and x5 = -33, a violation of the assumption in linear programming that x > 0. What should you do to apply the simplex method to the problem other than start a phase I procedure of introducing artificial variables ... 

In the first phase we invent futher variables to create an identity matrix within the coefficient matrix A. We need, say, r of these, called artificial variables and denoted by si>s2>-- 9sr Exactly one nan-negative artificial variable is added to the left-hand side of each constraint with the sign = or i. A basic solution of this extended matrix equation will be a basic solution... 

Next add a non-negative artificial variable to any equation not having a slack variable or having one with a negative sign. 

This artificial system has an obvious feasible solution, namely Ui = 11, u 2 = 34, and u a = 1, with all of the other variables zero. Such a solution, in which there is one nonzero variable for each constraint, is called a basic solution of the system, and the set of nonzero variables is called a basis. The variables not in the basis are called the nonbasic variables. We want to find a basic solution that is also feasible and which satisfies the side condition that all of the artificial variables must be zero. Since all variables are nonnegative, this side condition is equivalent in our case to... 

In the previous example, the technique used to reduce the artificial variables to zero was in fact Dantzig s simplex method. The linear function optimized was the simple sum of the artificial variables. Any linear function may be optimized in the same manner. The process must start with a basic solution feasible with the constraints, the function to be optimized expressed only in terms of the variables not in the starting basis. From these expressions it is decided what nonbasic variable should be brought into the basis and what basic variable should be forced out. The process is iterated until no further improvement is possible. 

Ordinarily we would introduce artificial variables and begin using the simplex method to reduce the sum of these variables to zero. However, in order to save space, as well as to demonstrate the effect of the quadratic term in the cost function, we shall start with the basis which was optimal in the linear case just solved. This basis, namely x2, x3, and u2, will of course be feasible for the three original constraints. If we filled out the basis by using vly v2, and v2, the basis would be feasible and there would be no artificial variables. Although at first glance it would appear that the basis x2) x3l u2, vlt v2 and v3 is optimal, this is not true because of the complementary slackness condition, which prohibits having both x2 and v2, or both x3 and v3, in the same basis. 

Since the complementary slackness principle does not allow the use of v2 and v3 in the basis, two artificial variables v 2 and v 3 must be introduced. With this basis, x2, x3, u2, vu v 2, and v 3, the tableau of equations is as given below. Notice that the first three lines come directly from the optimal table of the preceding example. The only changes needed in the second trio of equations are in the x columns. The equation below the double line, which is the sum of the fifth and sixth equations, is simply the expression of the sum of artificial variables v 2 + i/3). We shall use the simplex method to minimize this sum, hopefully until it becomes zero. 

For illustrative purposes, in Fig. 1 we showed stability coefficients calculated according to Eqs. (1) and (3) for the 401 experimental variables of the NIR data set and 500 artificial variables. 

With an elaboration of the objective function and the introduction of artificial variables to transform the problem into a QP one. 

---