3
$\begingroup$

I have a problem, which has $n$ variables. Let's call these variables as $a_1$, $a_2$, $a_3$ ... $a_n$. Each of these variables have their own range (i.e, $a_{i\min} \leq a_i \leq a_{i\max}$ for all $i$). And most importantly, each $a_n$ is ranked in terms of importance. Without a loss of generality one can assume that that $a_1$ is more important than $a_2$, which in turn is more important than $a_3$, and so on. This means that as long as the constraint is satisfied, it is better to have a smaller $a_1$ compare to have a smaller $a_2$, and a smaller $a_3$ is better compare to a smaller $a_4$

These variables are required to fulfill one ( yes, just one!!) constraint function

$$F_{\min} \leq f(a_1,a_2,a_3, .... a_n) \leq F_{\max}$$

The question now is, how to construct a minimizing function that satisfy the above condition? If I have two variables ($a_1$ and $a_2$), and both of them are between or equal to 0 and 9, then I can easily write the minimizing function as

$L=10a_1 + a_2$

given that $a_1$ is more important than $a_2$.

But for complicated case, I am a bit confused.

Edit: Maybe I should clarify further. My point is, for the above case, if $a_1=3, a_2=4$ and $a_1=4, a_2=3$ both satisfy the constraint equation, $a_1=3, a_2=4$ should be selected. So how to construct $L$ in this case to reflect the situation?

Edit 2 : Referring to the answer by Rahul, it seems that it is not possible to formulate such a minimizing function. Is there other methods of attack I can use?

Edit 3: alext87 answer is a good start, it contains general guidelines on how to proceed. But I want a hard, quantitative rule that tells me how to select for $lambda_i$ for all $i$.

  • 0
    @Rahul, I've updated the question. Hope it clarifies the matter. You have any suggestion?2010-09-20

3 Answers 3

5

The kind of ordering you specify is known to economists as 'lexicographic preferences'. There is no objective function which can represent these preferences. Here is an outline of the proof for two variables:

Assume on the contrary that there is such a function $f(x,y)$. It must be the case for any $x$ that

$f(x,0) < f(x,1),$

so we can find a rational number, say $q(x)$ such that

$f(x,0) < q(x) < f(x,1) $

Now if $x < y$, then

$q(x) < f(x,1) < f(y,0) < q(y)$

So, $q(\cdot)$ is a one-to-one mapping from the set of real numbers into the set of rational numbers which is impossible since the set of real numbers is uncountable while the set of rational numbers is countable.

  • 0
    Realized that this solution had already been pointed out by Rahul in the comments to his answers. I agree with him that this problem is going to be very hard $f$or a $g$eneral $f$. Also, if we take your preferences literally then there is no point in doing the second and later optimizations unless you have an exact solution for the first optimization since even the smallest improvement in the first optimization would beat any improvements you could make in the later optimizations.2010-09-22
2

I think my point in the comments was not taken, so I'll elaborate here and make this a proper answer. As far as I understand, you want to find the feasible point with the smallest $a_1$. If there is more than one such point, you want to find the one among them with the smallest $a_2$, and so on.

There is no such objective function that will work for all constraints $f$. Taking your example $L = 10x + y$ (I've renamed the variables as it'll make things easier later), I can choose the constraint to be $f(x,y) = 100x + y \in [1,2]$, making the feasible set to be a convex quadrilateral with vertices at $(0.01,0)$, $(0.02,0)$, $(0,1)$, and $(0,2)$. Now by your criteria you would like to choose the point $(0,1)$ as it minimizes $x$, but if you work out the values of $L$, you'll find that it is instead minimized at $(0.01,0)$. So the objective function you could "easily write" does not give you the desired solution.

In general, suppose $L$ is a function that gives you the desired solution for all constraints. Pick two values $x_1 < x_2$ and consider two corresponding "slices" of the domain $S_1 = \{(x_1,y) : y_{\min} \le y \le y_{\max}\}$ and $S_2 = \{(x_2,y) : y_{\min} \le y \le y_{\max}\}$. Then $L$ attains strictly lower values on $S_1$ than on $S_2$, because all points in $S_1$ are preferred over all points in $S_2$. On the other hand, $L$ must increase by a nonzero amount over $S_1$ itself, because L(x_1,y_{\max}) > L(x_1,y_{\min}); call the difference $\Delta L(x_1)$. So, L(x_2,y_{\min}) > L(x_1,y_{\max}) = L(x_1,y_{\min}) + \Delta L(x_1). This is the key point — if x_2 > x_1, L(x_2,y_{\min}) > L(x_1,y_{\min}) + \Delta L(x_1) — that is, keeping $y$ fixed, moving along $x$ by any arbitrarily small amount must cause a finite increase in $L$ independent of how little you move.

From here, the proof is easy to wrap up. There are uncountably many $x$s in $[x_{\min},x_{\max}]$, yet $L(x,y_{\min})$ must increase by a positive amount $\Delta L(x)$ at each $x$. So $L(x_{\max},y_{\min}) \ge L(x_{\min},y_{\min}) + \sum_x \Delta L(x)$, but this is impossible because the sum of uncountably many positive numbers must diverge.

  • 0
    Upvoted for explaining how hard is in writing a minimizing function in this case.2010-09-21
1

You can turn this into an optimization problem. For each $a_i$ set up a parameter $\lambda_i$, where $\lambda_i$ you determine to be the importance of the variable being small. For example as $a_i$ is more important to be small than $a_{i+1}$ you will select \lambda_i>\lambda_{i+1}. Then solve the following problem.

$\min \lambda_1a_1+\ldots+\lambda_na_n$

subject to

$F_{\text{min}}\leq f(a_1,a_2,\ldots,a_n)\leq F_{\text{max}}$

and

$a_{imin}\leq a_i\leq a_{imax}$ for all i

  • 0
    Upvoted for poi$n$ting out a general direction2010-09-21