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
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityHello!
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
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.