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"?



  • 6
    $\begingroup$ A bit more context would help. $\endgroup$ May 20 '13 at 8:42
  • $\begingroup$ A citation of the paper or book in which you found this phrase, for example. $\endgroup$
    – Lee Mosher
    May 20 '13 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$
    – tendow
    May 22 '13 at 3:02

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.

  • $\begingroup$ Thanks. Though the original problem is not LP. I can try understand it with simplex method. $\endgroup$
    – tendow
    May 22 '13 at 3:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.