Exercise 1.13 (Linear fractional programming)

Consider the problem

 minimize  c′x + d f′x + g  subject to Ax ≤b f′x + g > 0

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.

Answers

Consider the problem of deciding whether the optimal cost is less than or equal to a certain threshold α ∈ [K,L]:

c′x + d f′x + g ≤ α.

Naturally, we want to find out how low we can take α:

minimize α subject toc′x + d ≤ α(f′x + g) Ax ≤b f′x + g > 0

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

[ c′− αf A −f ]x ≤ [αg − d b g ].

Fix a desired accuracy 𝜖 > 0 after which the algorithm should stop. At each step, we will narrow down the interval α∗∈ [K,L] to a smaller interval α∗∈ [k,l]:

l := L 
k := K 
while l-k > eps: 
   alpha := (l-k) / 2 
   solve system of inequalities 
   if x* exists: 
       u := alpha 
   else: 
       l := alpha

Since we are halving [k,l] at each iteration, the number of iterations must be ⌈log ⁡ 2L − K 𝜖 ⌉.

User profile picture
2022-02-11 10:07
Comments

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

y ↔ 1 f′x + g ⋅x;t ↔ 1 f′x + g.
(1)

This transformation maps each feasible solution x of the fractional optimization problem to a pair [y t ]. Performing a change of variables in our optimization problem using this transformation results in the following linear optimization problem:

minimize c′y + td subject toAy − tb ≤0 f′y + tg = 1 t ≥ 0

Notice that the transformation defined in (1) is invertible, and it is easy to verify that the inverse transformation x ↔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 x∗ of the fractional optimization problem gives the same optimal cost as the corresponding solution [y∗ t∗ ] of the linear optimization problem:

c′x∗ + d f′x∗ + g = 1 f′x∗ + gc′x∗ + 1 f′x∗ + gd = c′y∗ + t∗d.

Thus, both optimization problems have the same optimal cost.

User profile picture
2022-02-11 11:06
Comments