Understanding duality when objective function contain a function of the decision variable.
Let $P_1$ be the following optimization problem.
\begin{align} P_1: \min \ & cx + y \\ \text{s.t.} \ & Ax \geq b \ \end{align}
where $A$ is a real-valued matrix $\in \mathbb{R}^{m \times n}$, $x,y \in \mathbb{R}^n$.
Regardless of $x$, I understand this problem is unbounded in $y$. Therefore, there is no dual. However, what happens if we say that $y = f(x)$, where $f$ is a linear function? This results in a slightly modified problem I will refer to as $P_2$.
\begin{align} P_2: \min \ & cx + f(x) \\ \text{s.t.} \ & Ax \geq b \ \end{align}
Can I say $P_2$ is bounded and feasible? If so, what would the dual be?
To take the dual, I'd start with
\begin{align} D_1: \max \ & \sum_{i = 1}^m y_i\\ \text{s.t.} \ & y^TA = \textbf{?}\ \end{align}
Since $x$, in this problem, is not sign-constrained, the respective constraint in the dual problem is an equality. However
1. What do I equate $\mathbf{y^TA}$ to?
2. What is going to be the constraint to for the primal term $\mathbf{f(x)}$?
Thank you.
Here is your primal:
\begin{align}
P: \min_x \ & c^T x + f(x) \\
\text{s.t.} \ & A x \geq b \
\end{align}
Let $y \ge 0$ be the dual variable associated with $A x \geq b$.
Write the Lagrangian:
$\mathcal{L}(x, y) = c^T x + f(x) - y^T (A x - b)$.
Differentiate wrt $x$ and set to 0:
$\frac{\partial \mathcal{L}}{\partial x}(x, y) = c + \nabla f(x) - A^T y = 0$.
Therefore the Lagrangian can be written: $\mathcal{L}(x, y) = c^T x + f(x) - (c^T + \nabla f(x)^T) x + y^T b = f(x) - \nabla f(x)^T x + y^T b$.
Note: if $f$ is linear in $x$, the first two terms vanish and you're left with $y^T b$ ($= b^T y$).
Therefore the dual can be written:
\begin{align}
D: \max_y \ & b^T y + f(x) - \nabla f(x)^T x \\
\text{s.t.} \ & A^T y = c + \nabla f(x) \\
& y \ge 0
\end{align}