pg. 201

[alextzik]

In the derivation, we assume FONC conditions (3), (4) hold for non-optimal points, while the fact that condition (2) does not hold indicates non-optimality. Why is this the case?

[tawheeler]

The simplex algorithm traverses from vertex to vertex as it optimizes. The vertices will not satisfy all FONCs until an optimal vertex is found. That being said, we can safely assume FONC 3 and 4 hold because we traverse from vertex to vertex of the constraints polygon. FONC 3 holds because it asserts that any active (\mu_i != 0) constraint has x_i = 0. All vertices are on the boundary of the feasible set, so this will be true. FONC 4 holds because it asserts that the gradient is balanced by any active constraints. Again, all vertices are on the boundary of the feasible set, so this will be true. FONC 2 does not hold as long as we have not reached optimality. It is the condition that ensures our inequality constraints are correctly pushing against the objective gradient. Does that make sense?

[tawheeler]

Marking issue as resolved. Feel free to ping me.

[alextzik]

Thank you. It makes sense! Essentially, to my understanding we are working with an assumption: we assume that a vertex is optimal. Then we know that its \mu_i for its active constraints will be nonzero, but the \mu_i of the non-active constraints will be zero (which gives FONC 3, considering only the >= constraints). We also know that an optimal point satisfies the stationarity condition (FONC 4). However, if the vertex is actually non-optimal not all FONCs will be satisfied and FONC 2 is the one to not be satisfiable by a non-optimal vertex. Is this train of thought accurate?

[tawheeler]

we assume that a vertex is optimal Right. The objective function is linear, so if you draw a polygon in space, at least one vertex will be optimal (or it diverges).

if the vertex is actually non-optimal not all FONCs will be satisfied and FONC 2 is the one to not be satisfiable by a non-optimal vertex Exactly!