Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm currently working on a problem that involves a two-stage linear program (LP). For simplicity, I refer to the LP in first stage as LP$_1$, and the LP in the second stage as LP$_2$. The relationship between the LPs in this problem is that the feasible region of LP$_2$ depends on the optimal solution of LP$_1$.

I am wondering whether anything can be said about the relationship between the norm of optimal value to LP$_2$ and the norm of another parameter that intuitively represents the "slope" between the optimal value of LP$_2$ and the optimal solution of LP$_1$.

My explanation is a little confusing, so I've written it as formally as possible below.

Formulation

  • Let $\widehat{x}$ be an $(N_x \times 1)$ vector that represents the optimal solution to LP$_1$. We assume that this value is fixed.

  • Let $Q(\widehat{x})$: $\mathbb{R}^{N_x}\rightarrow \mathbb{R}$ be a function that represents the optimal cost of LP$_2$ in terms of $\widehat{x}$, the optimal solution to LP$_1$

  • Let $\nabla Q(\widehat{x})$ represents the subgradient of the function $Q$ at $\widehat{x}$. This term essentially represents the "slope" between the optimal objective value of LP$_2$ and the optimal solution to LP$_1$.

We express the primal of LP$_2$ as,

\begin{alignat}{4} \begin{aligned} z_{primal} = &\min_{y} & c^\text{T} y & \\ &\mbox{ s.t.} & A y & \geq b - W\widehat{x} \\ & & y & \geq 0 \end{aligned} \end{alignat}

And express the dual of LP$_2$ as,

\begin{alignat}{2} \begin{aligned} z_{dual} = &\max_{\lambda} & ( b - & W\widehat{x} )^\text{T} \lambda\\ &\mbox{ s.t.} &A\lambda & \leq c \\ & & \lambda & \geq 0 \end{aligned} \end{alignat}

We assume that a optimal solution exists for both the primal and the dual, so that $Q(\widehat{x}) = z_{primal} = z_{dual}$ by duality. We also the dual formulation can be used to show that $\nabla Q(\widehat{x}) = \lambda^\text{T} W$.

Then,

\begin{alignat}{1} \begin{aligned} z_{primal} &= z_{dual} \\ Q(\widehat{x}) &= z_{dual} \\ Q(\widehat{x}) &= (b - W\widehat{x})^\text{T} \lambda \\ Q(\widehat{x}) &= b^\text{T}\lambda - (W\widehat{x})^\text{T} \lambda \\ Q(\widehat{x}) &= b^\text{T}\lambda - \lambda^\text{T} (W\widehat{x}) \\ Q(\widehat{x}) &= b^\text{T}\lambda - \lambda^\text{T} W \widehat{x} \\ Q(\widehat{x}) &= b^\text{T} \lambda - \nabla Q(\widehat{x}) \widehat{x} \\ |Q(\widehat{x})| &= |b^\text{T}\lambda - \nabla Q(\widehat{x})\widehat{x} | \end{aligned} \end{alignat}

At this point, I'm wondering whether it is fair to say that $|Q(\widehat{x})|$ is "roughly proportional" to $|\nabla Q(\widehat{x})|$. If so, why? If not, why not? In addition, I'm wondering whether anything at all can be said about the relationship between these two values as the problem is currently formulated.

share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.