# Why does the maximum/minimum of linear programming occurs at a vertex?

I'm in high-school and I'm told that the maximum/minimum of a linear programming occurs at the vertex.For more info see the chapter here. For convinience I'm putting relevant excerpt here:

Now, we see that every point in the feasible region satisfies all the constraints, and since there are infinitely many points, it is not evident how we should go about finding a point that gives a maximum value of the objective function. To handle this situation, we use the following theorems which are fundamental in solving linear programming problems. The proofs of these theorems are beyond the scope of the book.

Theorem 1 Let R be the feasible region (convex polygon) for a linear programming problem and let Z = ax + by be the objective function. When Z has an optimal value (maximum or minimum), where the variables x and y are subject to constraints described by linear inequalities, this optimal value must occur at a corner point (vertex) of the feasible region.

Theorem 2 Let R be the feasible region for a linear programming problem, and let Z = ax + by be the objective function. If R is bounded, then the objective function Z has both a maximum and a minimum value on R and each of these occurs at a corner point (vertex) of R

I searched wikipedia here to get under Optimal vertices (and rays) of polyhedra:

"..then the optimum value is always attained on ... This principle underlies the simplex algorithm for solving linear programs.."

But I couldn't understand it. Can someone explain?It might be helful to add that I have studied basic Calculus.

• If you have a hollow triangular mesh and you put a marble inside of it, will not the marble go to any of the vertices? Yes it will. Why? Because the altitude is the lowest there of all points inside of the mesh. For the same reason you will also find the minimum/maximum in a vertex in linear programming. Aug 13, 2014 at 21:25

Suppose your feasible region looks as shown below :

Lets assume we're maximizing the objective function $C=ax+by$

Notice that, for different values of C, you get different straight lines of varying y intercepts but they will have same slope :

Only the lines that cut through the feasible region satisfy all the given constraints because you can cookup x,y values such that they fall in both feasible region and the objective function.

From the second picture it is obvious that the the maximum value of $ax+by=C$ occurs when the y intercept of these feasible lines is maximum. Consequently the vertex A gives the maximum value for the objective function.

• so, B is minimum? but how does someone prove that vertex will be cut by line of greatest intercept[seems correct intutively because there doesn't seem any contradiction] Aug 13, 2014 at 18:02
• i think it is a property of convex polygons? Aug 13, 2014 at 18:04
• BINGO! thats a good question, and yes this argument holds only when the feasible region is convex - $ax+by=C$ has y intercept of $C/b$ when $b$ is positive, the max value of $C/b$ also yields the maximum value of $C$ (just notice that y intercept is not so special, we can think around this using x intercept also) Aug 13, 2014 at 18:07
• What if the edge AB of the triangle is aligned with the red lines? Every point in the edge would have the same optimal value, the answer is not clear. It would be interesting if someone could give a formal proof here. Apr 24, 2017 at 23:32
• In other words, the theorem is being incorrectly interpreted because "optimal value" is not "optimal point". The theorem only states that there exists a vertex with the optimal value, it doesn't imply that the optimal value will always happen at a vertex. The difference is subtle. If the edge AB is aligned with the red lines, then all points are optimal points, they all have the same optimal value, in particular the vertex has this value. Apr 25, 2017 at 14:43

Some basic linear algebra is essential for this. Have you already studied that a bit?

Say you have point $p$ inside your polyhedron of feasible points inside $\mathbb{R}^n$, and let's say you want to maximize the objective function. The objective function is linear, given by some $c \in \mathbb{R}^n$. If $v \in \mathbb{R}^n$ and $c \cdot v = 0$, then $p+v$ has the same objective value as $p$. In other words, one does not improve $p$ by moving it in a direction orthogonal to the objective function.

If $v$ has some component parallel to $c$, then $p+v$ will be either strictly better or strictly worse than $p$. Therefore, if you are the point $p$ and you want to improve your objective value, then you should look for a direction $v$ in which you can move which has some positive component parallel to $c$, that is $c \cdot v > 0$. You may not be able to walk exactly in the direction of $c$ because a face of the polyhedron may stand in the way. But you may be able to walk in a direction having positive $c$ component. The only way you could get stuck is that for every possible improving direction, some face blocks you. In other words for every $v$ in the open halfspace $\{v:c\cdot v > 0\}$, the point $p+v$ lies outside the feasible polyhedron. This can only happen if either you already stand at a vertex, or you stand on a face of optimal solutions parallel to the hyperplane $\{v:c\cdot v = 0\}$. If you do not already stand at a vertex, then while staying on the hyperplane, you can walk to a vertex without changing your objective value.

In the above explanation, I have used the boundedness of the feasible region: Without boundedness, it might be possible to walk in an improving direction forever, or it might be possible to walk along a face of optimal solutions without ever arriving at a vertex. I have also used convexity: If I do not stand at an optimal solution, then there will always exist an improving direction.

• This is a good point. I'll mention it. Aug 13, 2014 at 18:00
• i was stumped at $\mathbb R^n$ Aug 13, 2014 at 18:21
• Does this apply even when the objective functions isn't linear (read: convex)? Oct 26, 2017 at 20:49

Suppose you are not at a vertex of the convex region. If you are in the strict interior of the convex region, then you can move a little bit in any direction you want. In particular, if your objective is $ax + by$ then you can move a little bit in the direction of $(a,b)$ and get a higher objective function value. Similarly, if you are on an edge, let $(a_1,b_1)$ be a vector parallel to the edge. Then either the dot product of $(a_1,b_1)$ with $(a,b)$ is greater than or equal to zero, or less than or equal to zero. In the first case, you can move along the edge in direction $(a_1,b_1)$ until you hit a vertex and get at least as good of a solution, and in the second case you can move along the edge in direction $(-a_1,-b_1)$ until you hit a vertex and you will get at least as good of a solution. Put all the pieces together and you get that some vertex provides the optimal solution.

If we are searching for an extremum of function $z=ax+by$, then usually we take first partial derivatives, which equal to $a$ and $b$ consequently. As we are considering linear function in polygon, then system

\left\{\begin{aligned}&\frac{\partial z}{\partial x}=0 \\ &\frac{\partial z}{\partial y}=0 \\ \end{aligned}\right. has no solutions (if $a,b\ne 0$) in any regular point. Consequently, we should search for extremum on boundary (in more general case, the piece of boundary can be a solution)

• consequently, why only extremum on boundary Aug 13, 2014 at 17:51
• because partial derivatives exist in any point of interior of polygon, hence, this system describes us situation in any interior point in polygon. As you see, this system has no solutions. That's why extremum can be only on boundary
– cool
Aug 13, 2014 at 17:54
• but doesn't partial derivates occur at extremum, or they don't, maybe that's why you have mentioned extremum as the only solutions Aug 13, 2014 at 17:59
• In general case extremum can be in any point (interior or exterior). But here we showed that those extremums, for which partial derivatives equal to 0, do not exist in this problem. That's why we should take only boundary into consideration.
– cool
Aug 13, 2014 at 18:05
• This answer doesn't explain why one of the vertices will be optimal. Aug 13, 2014 at 18:48

Imagine that your feasible region is a box (possibly in high dimensions). Since the objective function is linear, let's interpret it as the direction of gravity. Drop a marble into the box, and it will roll into a corner, corresponding to an optimal solution.

To be more nuanced, the marble may not necessarily roll into a corner. In this case, either the feasible region is unbounded (and the marble drops forever), or there are infinitely many optimal solutions, for example when a whole face of the box lies flat on the ground, so to speak (i.e., perpendicular to the direction of the objective function). In the latter case, you can still roll the marble into any of the corners of that face.

• I understood all, but why does a marble-gravity location correspond to a optimal solution. Some proofy thing which can be written for an exam[or maybe not] might help me/ Aug 13, 2014 at 17:41
• Since the box is convex, the marble doesn't get stuck at a local optimum. In other words, if it's not already at the solution, then it can continue to fall or roll towards it. Aug 13, 2014 at 18:47
• I think @Philip represents the same thing in algebraic form, because both of these look same to me, atleast the outline of both answers, is it? But yours is a more understandable way. Aug 13, 2014 at 18:51
• @Aditya Yes, they are much the same explanation. I think it is helpful to be able to understand and express the principle both informally, as I have done, and more formally, as he has. Aug 13, 2014 at 19:21
• Great intuition. Can you extend this explanation to the case where the feasible region is an ellipse? In this case, think that the optimum should at the edge of the ellipse, on a tangent but I'm not sure. May 11, 2015 at 18:54

An old question but maybe a simpler answer.

As mentioned, the feasible region $$R$$ is convex. It means that every point $$P \in R$$ can be written as a convex combination of its vertices. Let's take a simple example: let ABC be a triangle (it's a convex shape). Every point $$P \in ABC$$ can be written as $$P = \lambda_1A + \lambda_2B + \lambda_3C$$ with $$\lambda_1 + \lambda_2 + \lambda_3 = 1$$ (it's the definition of a convex combination). Now, since it's the feasible region, every point $$P \in ABC$$ has a value, say $$v_P$$ (the objective function computed at this point). Wlog, we can write $$v_A \leq v_B \leq v_C$$; so:

$$$$\label{eq1} \begin{split} v_P &= \lambda_1 v_A + \lambda_2 v_B + \lambda_3 v_C \\ & = \lambda_1 v_A + \lambda_2 v_B + (1 - \lambda_1 - \lambda_2) v_C \\ &= \lambda_1 v_A + \lambda_2 v_B + v_C - \lambda_1v_C - \lambda_2v_C \\ &= \underbrace{\lambda_1(v_A - v_C)}_{\leq\ 0} + \underbrace{\lambda_2 (v_B - v_C)}_{\leq\ 0} + v_C \\ \end{split}$$$$

proving that every point $$P \in R$$ has a value less that $$v_C$$. The same applies for greater dimension, or a greater number of vertices, of course.