Separable linear programs

83 Views Asked by At

Assume, we have two distinct LPs:

\begin{equation*} \begin{aligned} & \text{min}_{x_1} & & c_1^Tx_1 \\ & \text{subject to} & & A_1x_1 = b \\ & & & x_1 \geq 0 \\ \end{aligned} \end{equation*}

and

\begin{equation*} \begin{aligned} & \text{min}_{x_2} & & c_2^Tx_2 \\ & \text{subject to} & & A_2x_2 = b \\ & & & x_2 \geq 0 \\ \end{aligned} \end{equation*}

I'd like to know for given solutions of the above LPs whether it is possible to find the solution of the following LP systematically;

\begin{equation*} \begin{aligned} & \text{min}_{x_1,x_2} & & c_1^Tx_1 + c_2^Tx_2 \\ & \text{subject to} & & A_1x_1 + A_2x_2 = b \\ & & & x_1, x_2 \geq 0 \\ \end{aligned} \end{equation*}

1

There are 1 best solutions below

3
On BEST ANSWER

I edited my answer according to your extended questions.

1) You asked whether there is a connection between the linear programs: There is a strong connection. Let's look at the dual linear programs \begin{equation*} \begin{aligned} & \text{max} & & b^Ty \\ & \text{subject to} & & A_1^Ty \leq c_1, \end{aligned}\quad \begin{aligned} & \text{max} & & b^Ty \\ & \text{subject to} & & A_2^Ty \leq c_2, \end{aligned} \end{equation*} and \begin{equation*} \begin{aligned} & \text{max} & & b^Ty \\ & \text{subject to} & & A_1^Ty \leq c_1\\ & & & A_2^Ty \leq c_2. \end{aligned} \end{equation*} Hence, by strong duality, the optimal value of your third linear program is the optimal value of the intersection of the sets of dual feasible solutions.

2) Let me also answer your extended question.

It is useful to introduce the notion of support functions. The support function of a convex set $S\subseteq\mathbb{R}^d$ is defined as $h_S(b) = \sup_{x\in S} b^Tx$. In the case of a closed convex polyhedron $P=\{x\mid Ax \leq c\}$ the value of the support function $h_P(b)$ is given as the optimal value of the linear program \begin{gather*} \text{max } b^Tx\quad\text{s.t. }Ax \leq c. \end{gather*} Let's look at the dual programs again. Further let us define the polyhedra $P_1=\{ y \mid A_1^Ty \leq c_1\}$ and $P_2=\{y \mid A_2^Ty \leq c_2\}$. Now we may restate your question as whether it is possible to compute the value of the support function $h_{P_1\cap P_2}(b)$ given the values $h_{P_1}(b)$ and $h_{P_2}(b)$ only.

Clearly, the inequality \begin{gather*} h_{P_1\cap P_2}(b) \leq \min(h_{P_1}(b), h_{P_2}(b)) \end{gather*} holds. Moreover, in general, the equality \begin{gather*} h_{P_1\cap P_2}(b) = \inf_{a\in\mathbb{R}^d} h_{P_1}(b-a)+h_{P_2}(a) \end{gather*} holds (Rockafellar, Variational Analysis). This equality is not easily computable, especially not from the given two values only.

In contrast to the negative result above, there are several other operations on polyhedra which can be easily computed from the value of the support functions, e.g.\ the closed convex hull: \begin{gather*} h_{\text{clconv}(P_1\cup P_2)}(b) = \max(h_{P_1}(b), h_{P_2}(b)), \end{gather*} or the Minkowski sum: \begin{gather*} h_{P_1+P_2}(b) = h_{P_1}(b) + h_{P_2}(b). \end{gather*} For more information on support functions, you may google for ``reachability analysis using support functions'' (Le Guernic, Girard, Frehse, ...)