what method can I employ to solve this optimization problem which involves \min? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T18:28:30Z http://mathoverflow.net/feeds/question/101293 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/101293/what-method-can-i-employ-to-solve-this-optimization-problem-which-involves-min what method can I employ to solve this optimization problem which involves \min? zzzhhh 2012-07-04T08:17:08Z 2012-08-08T08:04:07Z <p>The optimization problem is:</p> <p>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.</p> <p>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!</p> http://mathoverflow.net/questions/101293/what-method-can-i-employ-to-solve-this-optimization-problem-which-involves-min/101295#101295 Answer by David Ketcheson for what method can I employ to solve this optimization problem which involves \min? David Ketcheson 2012-07-04T09:06:39Z 2012-07-04T17:43:13Z <p>A common transformation when faced with a problem of this type:</p> <p>$${\rm maximize} \min (f(x), g(x))$$</p> <p>is to instead solve the equivalent problem</p> <p>$${\rm maximize} \ \ \ z$$ subject to $$z\le f(x); z\le g(x).$$</p> <p>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).</p> <p>Many other transformations are possible; for instance, you can replace the inequality constraints above with equality constraints via <em>slack variables</em>. For a discussion of transformations of optimization problems, I recommend Section 4.1.3 of Boyd and Vandenberghe (<a href="http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf" rel="nofollow">free PDF here</a>). Actually, I recommend the whole book.</p> http://mathoverflow.net/questions/101293/what-method-can-i-employ-to-solve-this-optimization-problem-which-involves-min/104263#104263 Answer by mirror2image for what method can I employ to solve this optimization problem which involves \min? mirror2image 2012-08-08T08:04:07Z 2012-08-08T08:04:07Z <p>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 <a href="http://arxiv.org/abs/1101.6081" rel="nofollow">http://arxiv.org/abs/1101.6081</a> ). 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 ( <a href="http://en.wikipedia.org/wiki/Branch_and_bound" rel="nofollow">http://en.wikipedia.org/wiki/Branch_and_bound</a> )</p>