tag:blogger.com,1999:blog-8781383461061929571.post2815776527683251743..comments2024-03-14T09:08:19.035-04:00Comments on OR in an OB World: Solving a Multidimensional NLP via Line SearchPaul A. Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-8781383461061929571.post-71100881465074378532021-07-13T11:33:40.558-04:002021-07-13T11:33:40.558-04:00You can use bisection (which may be faster than a ...You can use bisection (which may be faster than a fixed step approach) to find the lower bound *if* you have a feasible value you can use as the upper limit of the search interval. You cannot use bisection is you are starting with an interval where both endpoints are infeasible (because, after checking the midpoint, you would have no idea which half interval to keep). So you need a feasible value of $q_1$ before you do anything else. I suppose you could randomly generate values of $q_1$ in the initial interval until you got a feasible one, then use bisection (twice) to get feasible lower and upper limits.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-47740923163274501132021-07-12T19:36:10.897-04:002021-07-12T19:36:10.897-04:00Thank you for the detailed explanation. Overall me...Thank you for the detailed explanation. Overall method is clear to me. I would like to clarify one point regarding the interval of uncertainty. <br /><br />In the R code, I note that you assume a step size of 0.1 and keep increasing the value of q1 by this amount until you find a feasible value. That code calls findQ2() function which in turn calls findX(). To find the upper bound, you use bisection method with a bracket of [q1min,100] to find a root for q1. <br /><br />I do not understand why different methods are used for lower and upper bounds. Can the bisection method be used to find the lower bound as well for q1? <br /> Marryhttps://stackexchange.com/users/20573714/marrynoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-6540808923071281852021-07-08T20:07:23.681-04:002021-07-08T20:07:23.681-04:00Hi,
(1) I start out by setting upper limits of 10...Hi,<br /><br />(1) I start out by setting upper limits of 100 for $q_1$ and $q_2$, snatched out of thin air. In practice, the context of the model (what $q_1$ and $q_2$ stand for) would hopefully let you set reasonable upper bounds. To get an initial lower bound for $q_1$, I find the maximum value of the left side of (1). In the R code, I assume the $p_i$ are nonnegative, in which case the left side is maxed out when all $x_i=1$. I then solve (1) to get a value for $q_1$, which is the smallest possible choice for $q_1$. Neither the lower nor upper bound is automatically feasible, so I do a line search up from the lower bound and a separate line search down from the upper bound to get the lowest and highest values of $q_1$ than are feasible.<br /><br />(2) The objective function for golden section is $q_1 + q_2$, the original objective function.<br /><br />(3) At each step of the golden section search, we get a new candidate value for $q_1$. I call the findQ2() function to find the corresponding value of $q_2$. That function in turn calls findX(), which solves an LP to get $x$. So there is an LP solution at each step of the GS search.<br /><br />I hope that clarifies things.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-77481053532991317202021-07-08T19:31:24.429-04:002021-07-08T19:31:24.429-04:00I happens to be the one who asked the question on ...I happens to be the one who asked the question on OR StackExchange. I didn't realise that you have written a blog here. I think you are being modest when you say "low-tech" solution. To me it looks like a very elegant solution. Using your assumption for β, I get the same answer with Couenne solver. I see that you have given your R code as well but I don’t understand R. I can follow the code up to the point you solve the LP to find x, and then you find a lower bound for q1. If I may ask some questions on the method:<br />(1) What bracketing interval you assume to find feasible values for q1 using line search when setting the (feasible) lower bound and upper bound? <br />(2) What is the objective function for the golden search? Is it given by LHS – RHS of (1) that you minimize?<br />(3) Are you iteratively solving the LP based on candidate solutions for q1 and q2 until you hit the minimum based on Golden Search?<br />Marryhttps://stackexchange.com/users/20573714/marrynoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-47520627970031298792021-01-31T17:36:23.066-05:002021-01-31T17:36:23.066-05:00Thanks for pointing that out. It's fixed now.Thanks for pointing that out. It's fixed now.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-22424583056002302232021-01-31T17:24:40.276-05:002021-01-31T17:24:40.276-05:00Small typo in (2). Pretty sure that the index unde...Small typo in (2). Pretty sure that the index under the 3rd summation should be i, not n. Anonymousnoreply@blogger.com