In Dr. Boyd's Convex Optimization homework problems, there is a method described for a so-called Phase I method, which is used to determine a feasible starting point for an LP, to be used later in a log-barrier optimization method. It described here, pg. 3,
https://see.stanford.edu/materials/lsocoee364a/hw8extra.pdf
It basically says in order to obtain a feasible starting point for an LP solve this problem,
$$ \min t, \quad \textrm{s.t.} $$ $$ Ax = b, \quad x \ge (1-t) \vec{1}, \quad t \ge 0 $$
where $t$ is scalar. This problem is also solved with the barrier method, which also requires a starting point but that is simpler, we take $x^0$ of $Ax^0 = b$, and take $t^0 = 2 - \min_i x_i^0$.
But the rest of the steps are less clear: I dont understand is how the intermediate variable $z$ is used, which we are told, is computed as
$$ z = x + (t-1)\vec{1} $$
I have seen numerical coding of this method, they do things like
A1 = [A,-A*ones(n,1)];
b1 = b-A*ones(n,1);
z0 = x0+t0*ones(n,1)-ones(n,1);
c1 = [zeros(n,1);1];
[z_star, history, gap] = lp_barrier(A1,b1,c1,[z0;t0]);
I guess $c$ is made into $c = [0, 0, 0, ..., 1]$ where they multiply existing $x_i$'s with zero, only the extra $x_{i+1}$ remains which can be seen as $t$. Not as clear about what is going on with $A_1$ though. A new column is added to $A$ which is the negative of the sum of each of its rows. One derivation I could come up with
$$ z = x + t \vec{1} - \vec{1} $$
$$ x = z - t\vec{1} + \vec{1} $$
Apply to $Ax = b$ ,
$$ A (z - t\vec{1} + \vec{1}) = b $$
$$ Az - A t\vec{1} = b - A\vec{1} $$
The $b_1$ calculation make sense with this, but is $Az - A t\vec{1}$ equivalent to expanding $A$ with negative sum of its existing rows and adding $t$ as a new dummy variable?
Thanks,
Note: the code for lp_barrier comes from a HW solution, page 7.
Yes, that looks correct. Note that $A t\vec{1}=A \vec{1} t$ because $t$ is a scalar. Also, the introduction of $z$ transforms the $x \ge (1-t) \vec{1}$ constraint into a lower bound of $0$ for $z$, which apparently is a requirement for
lp_barrier.