0
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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}

$\endgroup$
2
  • 1
    $\begingroup$ Hello, cvanaret. Thanks a lot for your feedback. I can't believe I forget to take the Langragian route. Also, I checked your nature pics online. Great shots! $\endgroup$
    – Jxson99
    Jan 9, 2022 at 23:51
  • 1
    $\begingroup$ You're welcome @Jxson99! Thanks for the kind words :) $\endgroup$ Jan 10, 2022 at 10:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .