# Optimality conditions and Directions in Simplex method

I am trying to understand the optimality conditions in Simplex -method, more in the chat here -- more precisely the terms such as "reduced cost" i.e. $\bar{c}_j=c_j-\bf{c}'_B \bf{B}^{-1} \bf{A}_j$ and the "feasible direction" (p.83 1). I am stuck to this point on page 83:

"Given that we are interested in the feasible solutions, we require $\bf A (\bf x + \theta \bf d)=\bf b$, and since $\bf x$ is feasible, we also have $\bf A \bf x=\bf b$. Thus, for the equality constraints to be satsified for $\theta>0$, we need $\bf A \bf d=\bf 0$. Recall now that $d_j=1$, and that $d_i=0$ for all other nonbasic indices $i$. Then,

$$\bf{0}=\bf{A}\bf{d}=\sum_{i=1}^n \bf{A}_i d_i=\sum_{i=1}^m \bf{A}_{B(i)}d_{B(i)}+A_j=\bf{B}\bf{d}_B +\bf{A}_j$$

or picture here.

Questions

1. "$d_j=1$ for basic variables" means that all basic vars will be moved by the same amount in the direction $\bf d$, does it?

2. The phrase "$d_i=0$ for all other nonbasic indices $i$" means that we won't move at all in the direction of nonbasic variables, does it?

References

1 Introduction to linear optimization, Bertsimas, 1997

-
...btw this book may cover this topic better here, at least it helped me to understand that the $A_j$ is the shadow-price -term. The Bertsimas is not very explicit in this point about things. –  hhh Aug 27 '12 at 21:48

Bertsimas provides some intuition as to what a "feasible direction" is. If you want to remain inside $P$ starting from $x$ in the direction $d$ (given that $x$ is feasible) then you want to make sure that you can find a positive $\theta$ such that $x + \theta d$ is still inside $P$. Graphically, this means that $d$ is a feasible direction (starting from $x$) if you can move at least a little in the direction of $d$ starting from $x$ and stay inside the feasible region $P$.

To answer your questions, you need to look at what Bertsimas states on page 83 carefully. First, recall that for a basic feasible solution in the case that $x\geq 0$, that all the nonbasic variables are zero. Bertsimas wants to move in a particular direction $d$, and he chooses the direction $d$ where $d_j=1$ for exactly one non-basic coordinate corresponding to the nonbasic variable $x_j$ and $d_j$=0 for all other coordinates corresponding to the the remaining non-basic variables. You can think of this as moving along the $x_j$ axis in the positive direction starting from a "non-basic origin" where $x_i=0$ for all non-basic $i$. To visualize this, imagine an example of moving along the $x$-axis from (0,0,0) if you were in $\mathbb{R}^3$ with axes $x$, $y$ and $z$.

By moving in this particular direction, it is very easy to determine the values of the $d$ coordinates corresponding to the basic variables. It is useful to think of $x_B$ and $d_B$ as functions of the non-basic variables. In particular, for his choice of $d$ you end up with a closed-form solution for $d_B$ which he calls the $j$th basic direction.

Bertsimas defines reduced cost in Definition 3.2. Intuitively, $c_j$ is the cost per unit increase in $x_j$ and $-c_B'B^{-1}A_j$ is the cost of the change in the basic variables that arises from enforcing the condition that $Ax=b$. The reduced cost of the non-basic variable $x_j$ is simply $c_j -c_B'B^{-1}A_j$.

Hopefully, this helps.

-
Let's compare to big M -method where the costs by $\sum_{j=1}^n c_j x_j +M \sum_{i=1}^m y_i$ and example here. Does your explanation apply also to different Simplex -methods such as the big-M-method (Bertsimas p.117)? –  hhh Aug 28 '12 at 10:01
It does. The values of big-M can be chosen so that the auxiliary variables will not be in a basis for an optimal solution. There are different ways of doing this, but the fundamental pivoting action stays the same in the (primal) simplex method: choose a non-basic variable to enter the basis and determine a basic variable to leave. Typically, we choose which non-basic variable to enter the basis using some criteria that is based on the reduced costs. –  shoda Aug 28 '12 at 15:31

The key difference between different simplex implementation is how they calculate the $B^{-1}A_j$. In the Naive Simplex, they calculate $B^{-1}$ again-and-again, time-complexity something like $O(m^3)$. In the revised simplex, you update directly the $B^{-1}$ without recalculating things.

Now the basic and non-basic variables are common with all methods. You have more variables than equations. So you cannot calculate the inverse. This means you need to decide which variable to take into the base so that you have a square matrix $B$ to calculate $B^{-1}$.

When you have a variable in the base, you mark it by definition with $d_i=1$ and when it is not there you mark it with $d_i=0$ where the $d_i=-B^{-1}A_j$ so

$$\bar{c}_j=c_j-\bf{c'}_B \bf{B^{-1}} A_j$$

where $$\bar c_j=c_j+\bf{c_B'}\bf{d_j}$$

so you move along the direction $\bf{d_j}$ until the cost is optimum. In standard form problems, you move always along the sides aka active variables. When you have hit the optimum, you change the base again until you have a new optimum -- in convex problems, it is sufficient to find the local optimum meaning you repeat this until your cost function does not decrease anymore, in convex problems the local optimum is the global optimum -- the key premise behind linear optimization.

The optimality condition is the reduced-cost condition. When reduced costs are positive, you have the optimum.

'"$d_j=1$ for basic variables" means that all basic vars will be moved by the same amount in the direction $d$, does it?'
No, it can be but not always true. If you had the same amount of equations and variables, you would get a point. Now you have more variables than equations. This means you must put some variables to zeros, non-basic, in order to get the $B^{-1}$. You can move along the feasible directions determined by the basic vectors but you move one-by-one. This is how I understand it: you move from one extreme point to another along one direction at each time. Of course, there may be some methods where you choose some heuristic direction but the basic Simplex methods go from one extreme point to another until optimum. Notice in $\bar c_j=c_j+\bf{c_B'}\bf{d_j}$ that the change in direction is determined by the reduced costs and the base so the base variables affect the movement.
'The phrase "$d_i=0$ for all other nonbasic indices i" means that we won't move at all in the direction of nonbasic variables, does it?'