what method can I employ to solve this optimization problem which involves \min? - MathOverflow

what method can I employ to solve this optimization problem which involves \min?

2012-07-04T08:17:08Z

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!

Answer by David Ketcheson for what method can I employ to solve this optimization problem which involves \min?

2012-07-04T09:06:39Z

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.

Answer by mirror2image for what method can I employ to solve this optimization problem which involves \min?

2012-08-08T08:04:07Z

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 )