Exercise 3.28 (Convexity constraint)

Question

Consider a linear programming problem in standard form with a bounded feasible set. Furthermore, suppose that we know the value of a scalar $U$ such that any feasible solution satisfies $x_{i} \leq U$, for all $i$. Show that the problem can be transformed into an equivalent one that contains the constraint $\sum_{i=1}^{n} x_{i}=1$.

Elu Thingol · Accepted Answer

The trick is to notice that from $x_i \leq U$ for all $i = 1,\ldots,n$, it follows that $\sum_{i=1}^{n}x_i \leq nU$. Introducing a new slack variable $x_{n+1}$ and dividing all variables by $nU$, we can formulate an equivalent optimization problem in $\mathfrak{R}^{n+1}$.

\begin{proof} Consider the following original optimization problem and its converted version:
\begin{equation*}
  \begin{array}{ll}
    \text {minimize }   & \mathbf{c}^{\prime}\mathbf{x} \
    \text {subject to } & \mathbf{A}\mathbf{x} = \mathbf{b} \
                        & \mathbf{x} \geq \mathbf{0}\
                        &\
  \end{array}
  \qquad\qquad
  \begin{array}{ll}
    \text {minimize }   & \tilde{\mathbf{c}}^{\prime}\tilde{\mathbf{x}}\
    \text {subject to } & \tilde{\mathbf{A}}\tilde{\mathbf{x}} = \tilde{\mathbf{b}} \
                        &\sum_{i=1}^{n+1}\tilde{x}_i = 1\
                        & \tilde{\mathbf{x}} \geq \mathbf{0},
  \end{array}
\end{equation*}

where $\tilde{\mathbf{c}}:= \begin{bmatrix} nU \cdot \mathbf{c} \ 0 \end{bmatrix}$, $\tilde{\mathbf{A}} := \begin{bmatrix} \mathbf{A} \ 0 \end{bmatrix}$ and $\tilde{\mathbf{b}} := \dfrac{1}{nU}\mathbf{b}$. We argue that both optimization problems are equivalent.

\begin{itemize}
\item We first show that, for every feasible solution of the original problem, we can construct a feasible solution of the modified problem with an objective value equal to or lower than. Let $\mathbf{x}$ be a feasible solution to the original problem. Define

$$\tilde{\mathbf{x}} := \begin{bmatrix} \dfrac{1}{nU}\mathbf{x}\[7.5pt] \displaystyle 1 - \dfrac{1}{nU}\sum_{i=1}^{n}x_i\end{bmatrix} \in \mathfrak{R}^{n+1}.$$

Then trivial linear algebra shows that $\tilde{\mathbf{x}}$ is feasible for the modified problem, and we also have $\mathbf{c}^{\prime}\mathbf{x} = \tilde{\mathbf{c}}^{\prime}\tilde{\mathbf{x}}$.
\item For the other direction, simply project the feasible solution $\tilde{\mathbf{x}}\in\mathfrak{R}^{n+1}$ of the modified problem onto $\mathfrak{R}^n$ and get a feasible solution $\mathbf{x}$ of the original problem with the same objective value.
\end{itemize}
\end{proof}

Exercise 3.28 (Convexity constraint)

Answers

Comments

Exercise 3.28 (Convexity constraint)

Answers

Comments

Add answer