# 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?

\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$$.
$$\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$$).
\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}