Problem 1

Use the Cutting Plane Method to solve the following integer linear programming problem:

• Consider the relaxation problem, and adding slack variables, the optimal simplex tableau is:

The optimal solution is $x^{(0)} = (11/4,9/4)$, we choose the third constraint to construct a cut:
$x_1-\frac{1}{2}s_1+\frac14s_3=\frac{11}4\Rightarrow x_1-s_1-2=\frac{3}{4}-\frac{1}{2}s_1-\frac{1}{4}s_3\Rightarrow\frac{3}{4}-\frac{1}{2}s_1-\frac{1}{4}s_3\leq0\Rightarrow-2s_1-s_3+s_4=-3$
By applying dual simplex method, we obtain:

The optimal solution is $x^{(1)} = (7/2,0)$, we choose the third constraint to construct a cut:
$x_1+\frac12s_3-\frac14s_4=\frac72\Rightarrow x_1-s_4-3=\frac12-\frac12s_3-\frac{3}{4}s_4\Rightarrow\frac12-\frac12s_3-\frac{3}{4}s_4\leq0\Rightarrow-2s_3-3s_4+s_5=-2$
By applying dual simplex method, we obtain:

The optimal solution is $x^{(2)}=(3,1)$, with optimum of $7$.

---

Problem 2

State and prove the first-order necessary condition, second-order necessary condition, and second-order sufficient condition for the existence of extreme points inmultivariate functions.

• First-order necessary condition: Assume that $\R$ is an open set of Euclidean space $\mathbb E_n$, $f(x)$ is continuously differentiable and $x^*$ is a local minimizer of $f(x)$, then $\frac{\partial f(x^*)}{\partial x_1}=\frac{\partial f(x^*)}{\partial x_2}=\cdots=\frac{\partial f(x^*)}{\partial x_n}=0$.
  Proof: Suppose for contradiction that $∇f (x^∗) \neq 0$. Define the vector
  $p =−∇f(x^∗)$ and note that $p^T∇f (x^∗) = −∥∇f (x^∗)∥^2 < 0$. Because $∇f$ is continuous near $x^∗$, there is a scalar $T > 0$ such that $p^T∇f (x^∗ +tp) < 0$, for all $t ∈ [0,T]$.
  For any $\overline t∈ (0,T]$, we have by Taylor’s theorem that $f (x^∗ +\overline tp) = f (x^∗)+ \overline tp^T∇f (x^∗ +tp)$, for some $t ∈ (0,\overline t)$.
  Therefore, $f (x^∗ + \overline tp) < f (x^∗)$ for all $\overline t∈ (0,T]$. We have found a direction leading away from $x^∗$ along which $f$ decreases, so $x^∗$ is not a local minimizer, and we have a contradiction.
  Second-order necessary condition: If $x^∗$ is a local minimizer of $f$, $∇^2f$ is continuous in an open neighborhood of $x^∗$, then $∇f(x^∗) = 0$, $∇^2f(x^∗)$ is positive semi-definite.
  Proof: We know from First-order necessary condition that $∇f (x^∗) = 0$. For contradiction, assume that $∇^2f (x^∗)$ is not positive semidefinite. Then we can choose a vector $p$ such that $p^T∇^2f (x^∗)p < 0$, and because $∇^2f$ is continuous near $x^∗$, there is a scalar $T > 0$ such that $p^T∇^2f (x^∗ +tp)p < 0$ for all $t ∈ [0,T]$.
  By doing a Taylor series expansion around $x^∗$, we have for all $\overline t∈ (0,T]$ and some $t ∈ (0,\overline t)$ that $f (x^∗ +\overline tp) = f (x^∗)+ \overline tp^T∇f (x^∗) + \frac12 \overline t^2p^T∇^2f (x^∗ + tp)p < f (x^∗)$.
  As in First-order necessary condition, we have found a direction from $x^∗$ along which $f$ is decreasing, and so again, $x^∗$ is not a local minimizer.
  Second-order sufficient condition: Assume that $\R$ is an open set of Euclidean space $\mathbb E_n$, $f(x)$ is twice continuously differentiable in $\R$. If $x^∗$ is a local minimizer of $f$, $∇^2f$ is continuous in an open neighborhood of $x^∗$, $∇f(x^∗) = 0$ and $∇^2f(x^∗)$ is positive definite, then $x^∗ ∈ \R$ is a strict local minimizer of $f(x)$.
  Proof: Because the Hessian is continuous and positive definite at $x^∗$, we can
  choose a radius $r > 0$ so that $∇^2f(x)$ remains positive definite for all $x$ in the
  open ball $D = \{z | ∥z −x^∗∥ < r \}$. Taking any nonzero vector $p$ with $∥p∥ < r$, we have $x^∗ +p ∈ D$ and so $f (x^∗ +p) = f (x^∗)+p^T∇f (x^∗)+ \frac12p^T∇^2f(z)p= f(x^∗)+ \frac12p^T∇^2f(z)p$, where $z = x^∗ +tp$ for some $t ∈ (0,1)$. Since $z ∈ D$, we have $p^T∇^2f(z)p > 0$, and therefore $f (x^∗ + p) > f (x^∗)$, giving the result.

---

Problem 3

Prove: Let $f(x)$ be a differentiable convex function defined on the convex set $R_c$. If there exists a point $x^* \in R_c$ such that, for all $x \in R_c$, the following condition holds:

then $x^*$ is the global minimum point of $f(x)$ on $R_c$.

• Using the first-order characterization of convex functions, we have that for all $x,y∈R_c$, $f(y)≥f(x)+∇f(x)^⊤(y−x)$. And by the convexity inequality at $x=x^∗$, we have that for any $x∈R_c$, $f(x)≥f(x∗)+∇f(x^∗)^⊤(x−x^∗)$. Then consider $\nabla f(x^*)^\top(x-x^*)\geq0$, we have that $f(x)≥f(x^∗)+∇f(x^∗)^⊤(x−x^∗)≥f(x^∗)$, which means $x^∗$ is a global minimum of $f$ on $R_c$.

---

Problem 4

Consider the optimization problem:

This problem is called convex programming if $f(x)$ is a convex function and all $g_j (x)$ are concave functions.
Question: Prove that convex programming has the following properties:

1. The feasible solution set is convex.

• Consider feasible set $F = \{ x \in \mathbb{R}^n \mid g_j(x) \ge 0, \ j=1,\dots,l \}$. Take any two points $x_1, x_2 \in F$, i.e., $g_j(x_1) \ge 0$ and $g_j(x_2) \ge 0$ for all $j$. For any $\theta \in [0,1]$, consider the convex combination $x_\theta = \theta x_1 + (1-\theta) x_2$. Since $g_j$ is concave, we have that $g_j(x_\theta) = g_j(\theta x_1 + (1-\theta)x_2) \ge \theta g_j(x_1) + (1-\theta) g_j(x_2) \ge 0$ for all $j$. Therefore, $x_\theta \in F$, so $F$ is convex. Also, from Property 1, $x_\theta \in F$. Therefore, $f(x_\theta) = f^*$ and $x_\theta \in X^*$. Hence, the set of optimal solutions $X^*$ is convex.

2. The set of optimal solutions is convex.

• Consider optimal solution set $X^* = { x \in F \mid f(x) = f^* }, \quad f^* = \min_{x \in F} f(x)$. Take any two optimal solutions $x_1, x_2 \in X^*$. Then $f(x_1) = f(x_2) = f^*$. For any $\theta \in [0,1]$, consider $x_\theta = \theta x_1 + (1-\theta)x_2$. Since $f$ is convex, we have that $f(x_\theta) \le \theta f(x_1) + (1-\theta) f(x_2) = \theta f^* + (1-\theta) f^* = f^*$.

3. Any local optimum is also a global optimum.

• Let $x^* \in F$ be a local minimum, i.e., there exists $\epsilon > 0$ such that $f(x^*) \le f(x), \quad \forall x \in F \text{ with } |x - x^*| < \epsilon$. Since $f$ is convex and $F$ is convex, the first-order condition for convex functions applies that $\nabla f(x^*)^\top (x - x^*) \ge 0, \quad \forall x \in F$. From the theorem we proved earlier (first-order condition implies global minimum for convex functions on a convex set), this implies $x^*$ is a global minimum. Therefore, every local optimum is globally optimal.

4. If the objective function is strictly convex and a global optimum exists, then it is unique.

• Suppose $f$ is strictly convex and there exist two global optima $x_1 \neq x_2$ with $f(x_1) = f(x_2) = f^*$. Consider $x_\theta = \theta x_1 + (1-\theta) x_2$ for $\theta \in (0,1)$. Strict convexity of $f$ gives that $f(x_\theta) < \theta f(x_1) + (1-\theta) f(x_2) = f^*$. But $f^*$ is the global minimum, so $f(x_\theta) \ge f^*$, which is a contradiction. Hence, the global minimum is unique.