Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
6  
A bit more context would help. –  Federico Poloni May 20 '13 at 8:42
    
A citation of the paper or book in which you found this phrase, for example. –  Lee Mosher May 20 '13 at 13:09
    
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." –  tendow May 22 '13 at 3:02
add comment

1 Answer

up vote 0 down vote accepted

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.

share|improve this answer
    
Thanks. Though the original problem is not LP. I can try understand it with simplex method. –  tendow May 22 '13 at 3:08
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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