[proofplan] We use the finite vertex representation of a polytope: a nonempty polytope is the convex hull of its finitely many vertices. Once $P$ is written as the convex hull of vertices $v_1,\dots,v_r$, every point $x \in P$ is a convex combination of these vertices. The value $c \cdot x$ is therefore the same convex combination of the finitely many vertex values $c \cdot v_i$, so it is bounded above by the largest vertex value. A vertex attaining this largest value is an optimal solution. [/proofplan] [step:Represent the polytope as the convex hull of its vertices] Since $P$ is a nonempty polytope, the finite vertex representation theorem for polytopes gives finitely many vertices $v_1,\dots,v_r \in P$, with $r \in \mathbb{N}$, such that \begin{align*} P = \operatorname{conv}\{v_1,\dots,v_r\}. \end{align*} (citing a result not yet in the wiki: finite vertex representation theorem for polytopes) Thus, for every $x \in P$, there exist coefficients $\lambda_1,\dots,\lambda_r \in [0,\infty)$ such that \begin{align*} \sum_{i=1}^r \lambda_i = 1, \qquad x = \sum_{i=1}^r \lambda_i v_i. \end{align*} [/step] [step:Compare each feasible value with the largest vertex value] Define $M \in \mathbb{R}$ by \begin{align*} M := \max_{1 \le i \le r} c \cdot v_i. \end{align*} This maximum exists because the index set $\{1,\dots,r\}$ is finite. Let $x \in P$ be arbitrary. Choose coefficients $\lambda_1,\dots,\lambda_r \in [0,\infty)$ with $\sum_{i=1}^r \lambda_i = 1$ and $x = \sum_{i=1}^r \lambda_i v_i$. By linearity of the Euclidean [inner product](/page/Inner%20Product) in its second argument, first \begin{align*} c \cdot x = c \cdot \left(\sum_{i=1}^r \lambda_i v_i\right). \end{align*} Applying finite additivity and homogeneity of the second argument gives \begin{align*} c \cdot x = \sum_{i=1}^r \lambda_i (c \cdot v_i). \end{align*} Since $c \cdot v_i \le M$ for each $i \in \{1,\dots,r\}$ and $\lambda_i \ge 0$, summing the inequalities $\lambda_i(c \cdot v_i) \le \lambda_i M$ yields \begin{align*} c \cdot x = \sum_{i=1}^r \lambda_i (c \cdot v_i) \le \sum_{i=1}^r \lambda_i M = M \sum_{i=1}^r \lambda_i = M. \end{align*} Therefore $c \cdot x \le M$ for every $x \in P$. [guided] The point of passing to vertices is that linear functions preserve convex combinations. Define the finite list of vertex values \begin{align*} c \cdot v_1,\dots,c \cdot v_r. \end{align*} Because there are only finitely many of them, there is a largest one. We denote it by \begin{align*} M := \max_{1 \le i \le r} c \cdot v_i. \end{align*} Now take an arbitrary feasible point $x \in P$. Since $P = \operatorname{conv}\{v_1,\dots,v_r\}$, there are coefficients $\lambda_1,\dots,\lambda_r \in [0,\infty)$ such that \begin{align*} \sum_{i=1}^r \lambda_i = 1, \qquad x = \sum_{i=1}^r \lambda_i v_i. \end{align*} These coefficients say exactly that $x$ is a convex combination of the vertices. Apply the linearity of the Euclidean inner product in the second variable. First, \begin{align*} c \cdot x = c \cdot \left(\sum_{i=1}^r \lambda_i v_i\right). \end{align*} Then finite additivity and homogeneity in the second variable give \begin{align*} c \cdot x = \sum_{i=1}^r \lambda_i (c \cdot v_i). \end{align*} Thus the objective value at $x$ is a convex combination of the vertex objective values. Since each vertex value satisfies $c \cdot v_i \le M$ and each coefficient satisfies $\lambda_i \ge 0$, multiplying preserves the inequality: \begin{align*} \lambda_i(c \cdot v_i) \le \lambda_i M \end{align*} for every $i \in \{1,\dots,r\}$. Summing these inequalities and using $\sum_{i=1}^r \lambda_i = 1$ gives \begin{align*} c \cdot x = \sum_{i=1}^r \lambda_i (c \cdot v_i) \le \sum_{i=1}^r \lambda_i M = M \sum_{i=1}^r \lambda_i = M. \end{align*} So no feasible point $x \in P$ can have objective value larger than the largest objective value already achieved among the vertices. [/guided] [/step] [step:Choose a vertex attaining the maximum value] Since $M = \max_{1 \le i \le r} c \cdot v_i$, there exists an index $j \in \{1,\dots,r\}$ such that \begin{align*} c \cdot v_j = M. \end{align*} The point $v_j$ is a vertex of $P$, and the previous step shows that $c \cdot x \le M = c \cdot v_j$ for every $x \in P$. Hence \begin{align*} c \cdot v_j = \max_{x \in P} c \cdot x. \end{align*} Therefore the optimisation problem of maximising $c \cdot x$ over $x \in P$ has an optimal solution at the vertex $v_j$ of $P$. [/step]