 # Phase I and Phase II

Phase I of a mathematical program is finding a feasible solution, and Phase II is entered with a feasible solution to find an optimal solution. The standard Phase I is: $LaTeX: \max \sum_i \{u_i\} + \sum_i \{v_i + w_i\}: u, v, w \ge 0,$ $LaTeX: g(x) - u \le 0, h(x) - v + w = 0.$

Then, for any $LaTeX: x,$ one could set $LaTeX: \textstyle u = g(x)^+, v = h(x)^+ and w = -h(x)^-$ to have a feasible solution to the Phase I mathematical program. The optimal objective value is 0 if, and only if, $LaTeX: u=0$ and $LaTeX: v=w=0,$ in which case $LaTeX: x$ is feasible in the original mathematical program (to commence Phase II). The Phase I problem is sometimes called an elastic program (thinking of the artificial variables $LaTeX: (u,v,w)$ as providing "elastic" behavior in the levels of constraint violation).

In linear programming, the standard Phase I & II are:

I. Min ev: $LaTeX: \textstyle x, v \ge 0, Ax + v = b,$ and
II. Max cx: $LaTeX: \textstyle x \ge 0, Ax = b, \mbox{ where } b \ge 0 \mbox{ (multiply by } -1 \mbox{ for } i: b_i < 0.$