Hello!
I come across the word "vertex solution" in the context " We can also assume that x and y are vertex solutions,so that the sequence {x,y} remains in a finite set."
Could anybody know any definition for "Vertex Solution"?
Thanks,
Tendow
$\begingroup$
$\endgroup$
3
-
7$\begingroup$ A bit more context would help. $\endgroup$– Federico PoloniCommented May 20, 2013 at 8:42
-
$\begingroup$ A citation of the paper or book in which you found this phrase, for example. $\endgroup$– Lee MosherCommented May 20, 2013 at 13:09
-
$\begingroup$ Thanks. It is a proof of convergence to critical point in Gauss-Seidel Method. The phrase appears in "Grippo, L., and M. Sciandrone. "On the convergence of the block nonlinear Gauss–Seidel method under convex constraints." Operations Research Letters 26.3 (2000): 127-136." $\endgroup$– tendowCommented May 22, 2013 at 3:02
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
In the context of linear programming, and assuming that you're using the simplex method to solve your LP's rather than an interior point method, it's most likely that the author means "basic feasible solution" (BFS) here. In geometrical terms, the basic feasible solutions of an LP are vertices of the polytope of feasible solutions.
The number of vertices of a polytope defined by a finite system of linear equalitions and inequalities is finite and bounded by a function involving the number of variables and constraints.
Since each iteration of the simplex method ends with a basic feasible solution, any optimal solution returned by the simplex method will be a BFS. An algorithm which solves a sequence of linear programming problems in which the constraints do not change (but the objective function varies) by using the simplex method will produce a sequence of basic feasible solutions from this finite set.
answered May 20, 2013 at 13:47
-
$\begingroup$ Thanks. Though the original problem is not LP. I can try understand it with simplex method. $\endgroup$– tendowCommented May 22, 2013 at 3:08