Piecewise affine approximation of a convex function

Question

I am working on the following exercise:

Let $A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m, c \in \mathbb{R}^n$. Let further $f: \mathbb{R}^n \rightarrow \mathbb{R}$ be a differentiable convex function. We are interested in the following non-linear optimization problem:

$$\min_x f(x) \quad \text{ subject to } \quad Ax=b, x \ge 0 \qquad (P)$$

We assume that the feasible set is bounded. Let $s$ be the optimal value of the problem $(P)$. For $x_1, \ldots, x_N \in \mathbb{R}^n$ we define

$$f_N(x) := \max_{i = 1, \ldots, N} \bigg\{ f(x_i) + \nabla f(x_i) \cdot (x - x_i) \bigg\}$$

and we consider the problem

$$\min_x f_N(x) \quad \text{ subject to } \quad Ax=b, x \ge 0 \qquad (P_N).$$

Show the following:

1. For all $x\in \mathbb{R}$ holds $f(x) \ge f_N(x)$.
2. Reformulate $(P_N)$ as a LP in canonical form $\min c^Tx \text{ s.t. } Ax=b, x\ge0$.
3. Let $x^*$ be a solution to $(P_N)$. Show that $f_N(x^*) \le s \le f(x^*)$.

My Attempt: For 1) it is enough to recall that for convex functions holds for all $x,y \in \mathbb{R}$:

$$f(x)-f(y) \ge \nabla f(y) \cdot (x-y).$$

For 3) we note that $s \le f(x^*)$ is clear, since $s$ is assumed to be a solution of $(P)$.

However, I do not see how to prove the part $f_N(x^*) \le s$ from 3) and I have no idead about point 2). Could you help me?

Answer 1

Let $X$ denote the (common) feasible set for the problems $(P)$ and $(P_N)$. Denote by $x_0\in X$ a minimizer of $(P)$, i.e. $f(x_0)=s$. Consider Part (3). By Part (1), we know that $f_N(x_0) \le f(x_0)$. Since $x^*$ is defined to be a solution for $(P_N)$, it holds that $f_N(x^*) \le f_N(x)$ for all $x\in X$, and therefore in particular, since $x_0$ is optimal (and therefore feasible) for $(P)$ it must be that $f_N(x^*) \le f_N(x_0)$. Putting our inequalities together we find that \begin{equation*} f_N(x^*) \le f(x_0) = s, \end{equation*} as desired. As you mentioned, the inequality $s=f(x_0)=\le f(x^*)$ is obvious due to the optimality of $x_0$ and the feasibility of $x^*$ for $(P)$.

For Part (b), we seek to solve the problem \begin{align*} &\text{minimize}&& f_N(x)=\max_{i\in\{1,2,\dots,N\}} (f(x_i) + \nabla f(x_i)^\top(x-x_i)) \\ &\text{subject to}&& Ax = b, ~ x\ge 0. \end{align*} Introduce the epigraphic variable $t$ such that $f_N(x)\le t$. Then, the constraint $f_N(x)\le t$ is equivalent to $f(x_i)+\nabla f(x_i)^\top(x-x_i) \le t$ for all $i\in\{1,2,\dots,n\}$. Hence, our problem becomes \begin{align*} &\text{minimize}&& t \\ &\text{subject to}&&Ax=b, ~ x\ge 0, \\ &&& f(x_i) + \nabla f(x_i)^\top (x-x_i) ~ \text{for all $i\in\{1,2,\dots,N\}$}, \end{align*} where the optimization variable is now $z=(x,t)\in\mathbb{R}^n\times\mathbb{R}$. Since the objective is linear in $z$ and all constraints are affine in $z$, the above problem is a linear program. I leave it to you to convert it into canonical form.