Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The optimization problem is:

maximize $$\min(\sum\limits_{i=1}^N \log\left(a_{1,i}+\frac{b_{1,i}}{c_{1,i}+d_{1,i}x_i}\right),\sum\limits_{i=1}^N \log\left(a_{2,i}+\frac{b_{2,i}}{c_{2,i}+d_{2,i}x_i}\right))$$ subject to $x_i\ge0, i=1,...,N$ and $\sum\limits_{i=1}^N x_i=C$, where $x_i$ are variables, $a_{1,i}, b_{1,i}, c_{1,i}, d_{1,i}, a_{2,i}, b_{2,i}, c_{2,i}, d_{2,i}$ and $C$ are constants.

Kuhn–Tucker conditions can only optimize one $\sum$ alone. but I don't know how to handle optimization problem involving $\min$ operation as above. Could you please tell me what method can I employ to solve it (I would greatly appreciate if you can refer me to a textbook containing exposition of the method)? Thank you very much!

share|improve this question
add comment

2 Answers 2

up vote 4 down vote accepted

A common transformation when faced with a problem of this type:

$${\rm maximize} \min (f(x), g(x))$$

is to instead solve the equivalent problem

$${\rm maximize} \ \ \ z $$ subject to $$ z\le f(x); z\le g(x).$$

This can be helpful, for instance, in making the problem more tractable for some numerical optimization methods (if they are better at handling inequality constraints rather than complicated objective).

Many other transformations are possible; for instance, you can replace the inequality constraints above with equality constraints via slack variables. For a discussion of transformations of optimization problems, I recommend Section 4.1.3 of Boyd and Vandenberghe (free PDF here). Actually, I recommend the whole book.

share|improve this answer
    
I see. Thank you very much for the enlightening answer! –  zzzhhh Jul 4 '12 at 9:23
add comment

Also if $C > 0$ by replacing $x_i$ with $x_i/C$ you have simplex constrain for your problem. Common approach to simplex constraint is iteratively projecting solution of unconstrained problem on simplex. There are some efficient algorithms for projection on simplex (for example http://arxiv.org/abs/1101.6081 ). For similar methods you can google projected gradient methods. However you may (or may not depending on the parameters) problem with convexity (you problem likely is not convex) and singularities. "Branch and bound" heuristics may help here ( http://en.wikipedia.org/wiki/Branch_and_bound )

share|improve this answer
add comment

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.