Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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_{imin} \leq a_i \leq a_{imax}$ 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$.

share|improve this question
    
Actually, your example of a minimizing function doesn't necessarily work. Suppose the additional constraint is $1 \le 100a_1 + a_2 \le 2$. Then $a_1$ is minimized at $(0,1)$, but your minimizing function $L = 10a_1 + a_2$ is minimized at $(0.01,0)$ instead. In general, a single scalar minimizing function will not work except in the limit of $L = a_1 + \epsilon a_2 + \epsilon^2 a_3 + \cdots$ as $\epsilon \rightarrow 0$. –  Rahul Sep 19 '10 at 16:41
    
I don't this as a counterexample. Ngu didn't require $a_1>a_2$ but he 'preferred' it (if it is required $a_1>a_2$ it should become a constraint). He formed $L$ and if the solution $(0.01,0)$ was unacceptable then he hasn't selected $a_1$ to be important enough. For example perhaps $L=100a_1+a_2$ would have better. –  alext87 Sep 19 '10 at 17:30
    
@alext87, I think you misunderstand my point, my point is that if there are two sets of values of $(a_1, a_2)$ that satisfy the constraint, then a smaller $a_1$ is preferred. So, if both $(3,4)$ and $(4,3)$ satisfy the constraint, then $(3,4)$ should be selected as answer. –  Graviton Sep 20 '10 at 1:09
    
@Rahul, I've updated the question. Hope it clarifies the matter. You have any suggestion? –  Graviton Sep 20 '10 at 1:13

3 Answers 3

up vote 5 down vote accepted

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.

share|improve this answer
    
+1: This proof is so much better than my lumbering attempt. –  Rahul Sep 21 '10 at 6:34
    
@jomy, thanks. How to solve this kind of problem? –  Graviton Sep 21 '10 at 9:29
    
@hui. I haven't seen this type of problem before. But how about this: first solve an optimization problem that minimizes $a_1$ given the constraints. This is a standard problem. Let the minimum value of $a_1$ achieved be $a_1^*$. Then solve the problem of minimizing $a_2$ with the original constraints plus the additional constraint $a_1=a_1^*$. And so on. –  Jyotirmoy Bhattacharya Sep 21 '10 at 14:33
    
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 for a general $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. –  Jyotirmoy Bhattacharya Sep 22 '10 at 0:19

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.

share|improve this answer
    
@Rahul, OK. If using a minimizing function cannot do the job, what are the other methods of attacks you can suggest? –  Graviton Sep 20 '10 at 6:06
    
@Ngu Soon Hui: Without knowing more about the form of your constraint, the best I can propose is just what is suggested by my first paragraph above: first minimize $a_1$, then find the set of feasible points with this value of $a_1$; if this set is a singleton, you're done, else recurse, minimizing $a_2$ on this set and so on. –  Rahul Sep 20 '10 at 6:53
    
@Rahul, the solution you suggest seems more like a brute force approach than any other thing else. I can't minimize $a_1$ unless I loop over every combination of $a_i$ and find the sets of $a_i$ that yields minimum $a_i$. This is clearly not scalable. –  Graviton Sep 20 '10 at 7:03
    
@Ngu Soon Hui, I'm not sure why you say that. You can minimize $a_1$ using whatever optimization procedure you were going to use for minimizing $L$, by setting $L = a_1$. Then you may be able to use knowledge of the constraints to determine whether other feasible points may have the same $a_1$. This is the tricky part, for which I don't know a general solution; that's why I didn't include this in my answer. It will really depend on the form of your constraints, of which you have not told us anything (is $f$ linear? quadratic? convex? completely arbitrary?). –  Rahul Sep 20 '10 at 8:13
    
But once you have the new set of solutions, you only have to recurse on $a_2$ first, then $a_3$, and so on. You don't ever have to consider all $n!$ possible combinations of $a_i$s. Perhaps I'm misunderstanding you, or my earlier comment was not clear, but it's difficult to explain things completely in this comment section. –  Rahul Sep 20 '10 at 8:15

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

share|improve this answer
    
@alex87, so how do I select $\lambda_n$, beyond the condition that $\lambda_i>\lambda_{i+1}$ ? –  Graviton Sep 19 '10 at 14:06
    
Well that is down to you. $\lambda_i$ indicates the level of importance YOU give to the variable $a_i$ to be small. You used words such as 'better' and so this needs to be quantified through the variables $\lambda_i$. –  alext87 Sep 19 '10 at 14:24
    
I just thought in case you are confused. This method doesn't ensure that $a_i>a_{i+1}$, if you want this then add it to the constraints and you have a feasiblity problem. An example would be $\lambda_i=n-i$ (though I don't know your level of important). –  alext87 Sep 19 '10 at 14:37
    
I have updated the question, hope it clarifies. All the talk about importance is to make sure that if there are multiple sets of values that satisfy the constraint, the values that has minimum $a_1$ is selected. I guess your answer doesn't reflect this. Sorry for not making my question clear in the first place. –  Graviton Sep 20 '10 at 1:15
    
Upvoted for pointing out a general direction –  Graviton Sep 21 '10 at 1:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.