Exercise 1.13 (Linear fractional programming)

Question

Consider the problem
$$
\begin{array}{cl}
	ext { minimize } & \dfrac{\mathbf{c}^{\prime} \mathbf{x}+d}{\mathbf{f}^{\prime} \mathbf{x}+g} \
	ext { subject to } & \mathbf{A x} \leq \mathbf{b} \
& \mathbf{f}^{\prime} \mathbf{x}+g>0
\end{array}
$$
Suppose that we have some prior knowledge that the optimal cost belongs to an interval $[K, L]$. Provide a procedure, that uses linear programming as a subroutine, and that allows us to compute the optimal cost within any desired accuracy. Hint: Consider the problem of deciding whether the optimal cost is less than or equal to a certain number.

Elu Thingol · Accepted Answer

Consider the problem of deciding whether the optimal cost is less than or equal to a certain threshold $\alpha \in [K,L]$:

$$\dfrac{\mathbf{c}^{\prime} \mathbf{x}+d}{\mathbf{f}^{\prime} \mathbf{x}+g} \leq \alpha.$$

Naturally, we want to find out how low we can take $\alpha$:

\begin{equation*}
\begin{array}{llll}
	ext{minimize} \quad &\alpha\
	ext{subject to} \quad
&\mathbf{c}^{\prime} \mathbf{x}+d \leq \alpha (\mathbf{f}^{\prime} \mathbf{x}+g)\
&\mathbf{A x} \leq \mathbf{b} \
& \mathbf{f}^{\prime} \mathbf{x}+g>0
\end{array}
\end{equation*}

We can implement the following search algorithm by fixing $\alpha$ lower and lower at each iteration and checking whether the feasible set of the above optimization problem is nonempty:

$$\begin{bmatrix} \mathbf{c}^{\prime}  - \alpha \mathbf{f} \ \mathbf{A} \ -\mathbf{f} \end{bmatrix} \mathbf{x} \leq \begin{bmatrix} \alpha g - d \ \mathbf{b} \ g \end{bmatrix}.$$

Fix a desired accuracy $\epsilon > 0$ after which the algorithm should stop. At each step, we will narrow down the interval $\alpha^* \in [K,L]$ to a smaller interval $\alpha^* \in [k,l]$:

\begin{minted}{python}
l := L
k := K
while l-k > eps:
   alpha := (l-k) / 2
   solve system of inequalities
   if x* exists:
       u := alpha
   else:
       l := alpha
\end{minted}

Since we are halving $[k,l]$ at each iteration, the number of iterations must be $\left\lceil \log_2\dfrac{L-K}{\epsilon}ightceil$.

Elu Thingol · Answer

extbf{(Alternative solution)} Consider a non-linear transformation defined by

\begin{equation}
\mathbf{y} \leftrightarrow \dfrac{1}{\mathbf{f}'\mathbf{x}+g} \cdot \mathbf{x}; \qquad t \leftrightarrow \dfrac{1}{\mathbf{f}'\mathbf{x}+g}.
\label{transformation}
\end{equation}

This transformation maps each feasible solution $\mathbf{x}$ of the fractional optimization problem to a pair $\begin{bmatrix} \mathbf{y} \ t \end{bmatrix}$. Performing a change of variables in our optimization problem using this transformation results in the following linear optimization problem:

\begin{equation*}
\begin{array}{llll}
	ext{minimize} \quad &\mathbf{c}^{\prime}\mathbf{y} + td\
	ext{subject to} \quad
&\mathbf{A y} - t\mathbf{b}\leq \mathbf{0} \
& \mathbf{f}^{\prime} \mathbf{y}+tg=1\
& t \geq 0
\end{array}
\end{equation*}

Notice that the transformation defined in \eqref{transformation} is invertible, and it is easy to verify that the inverse transformation $\mathbf{x} \leftrightarrow \mathbf{y} / t$ maps each feasible solution of the fractional optimization problem to a feasible solution of the linear optimization problem. Thus, the fractional optimization problem is feasible if and only if the linear optimization problem is feasible. Furthermore, every feasible solution $\mathbf{x}^*$ of the fractional optimization problem gives the same optimal cost as the corresponding solution $\begin{bmatrix} \mathbf{y}^{*} \ t^{*} \end{bmatrix}$ of the linear optimization problem:

$$\dfrac{\mathbf{c}^{\prime} \mathbf{x}^{*}+d}{\mathbf{f}^{\prime} \mathbf{x}^{*}+g}
= \dfrac{1}{\mathbf{f}^{\prime} \mathbf{x}^{*}+g} \mathbf{c}^{\prime} \mathbf{x}^{*} + 
\dfrac{1}{\mathbf{f}^{\prime} \mathbf{x}^{*}+g} d = \mathbf{c}^{\prime}\mathbf{y}^{*} + t^{*}d.$$

Thus, both optimization problems have the same optimal cost.

Exercise 1.13 (Linear fractional programming)

Answers

Comments

Comments

Exercise 1.13 (Linear fractional programming)

Answers

Comments

Comments

Add answer