I have a simple LP of the form:
\begin{align*} \text{maximize } & c^Tx\\ \text{s.t. } &A_1x = b_1 \\ &A_2x \le b_2 \\ &x\ge0 \end{align*}
with $x\in R^n$, $A_1 \in R^{m\times n}$, $A_2 \in R^{l\times n}$, $b_1 \in R^{m}$, and $b_2 \geq 0 \in R^{l}$.
Let's introduce the dual variables relative to the constraints defined above.
- $y_1$ for the equality constraint
- $y_2$ for the inequality constraint
Assume now that we know the values of the following: $A_1$, $b_1$, $A_2$, $y_1^*$, $(c^Tx)^*$ (we don't know $x^*$ but only the optimal cost value).
How can we determine $b2$ such that the optimal solution to the corresponding primal and dual problems have value $(c^Tx)^*$ and dual variable $y_1^*$, respectively?
Here what I have done so far. First, I have written the associated dual problem:
\begin{align*} \text{minimize } & \lambda_1^Tb_1 + \lambda_2^Tb_2\\ \text{s.t. } &A_1^T\lambda_1 + A_2^T\lambda_2 >= c \\ &\lambda_2\ge0 \end{align*}
Here the problem is that both $\lambda_2$ as well as $b_2$ are, in our case, unknown (optimization variables). However, we know that:
- both variables in the bilinear term $\lambda_2^Tb_2$ are non-negative
- the term $b_2$ appears only in the bilinear term mentioned above
- strong duality holds so that the optimal cost of the dual is equal to the optimal of the primal (that we know)
These conditions allow us (do they?) to introduce the auxilary variable z_i=$\lambda_{2, i}b_{2, i} \leq \lambda_{2, i}b_{i, max}$ $\forall i \in R^l$. I have a natural bound, $b_{i, max}$, for each component of $b_2$. Putting all of this together we obtain:
\begin{align*} \text{minimize } & 1^Tz + \lambda_1^Tb_1\\ \text{s.t. } & 1^Tz + \lambda_1^Tb_1 >= (c^Tx)^* \\ &A_1^T\lambda_1 + A_2^T\lambda_2 >= c \\ &\lambda_2\ge0 \\ & z \leq \lambda_2b_{max} \end{align*}
If all I have done is correct this would allow us to solve in $z$, $\lambda_2$ and the obtain each component $b_{2, i}$ as:
$$ b_{2, i} = z_i/\lambda_{2, i}$$
where $b_{2, i}$ will be undetermined whenever $\lambda_{2, i} = 0$.
I have implemented this but the solution seems completely off. What I am doing wrong?