Timeline for Maximizing the minimum of piecewise linear functions in high dimensional space
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 15, 2011 at 15:27 | vote | accept | Jeff | ||
| Aug 14, 2011 at 15:55 | comment | added | Brian Borchers | Yes, that's the basic idea. However, you can be more inteligent in picking your branching variables- look for an x(i) that is involved in the active constraint associated with your current x rather than splitting on a random dimension. | |
| Aug 14, 2011 at 0:00 | comment | added | Jeff | Branch-and-bound sounds like the right approach, but it's new to me. Does the following sound right? For a particular (21-dimensional) rectangular subset $S$ of the domain, 1) Branch by splitting $S$ in half on a dimension selected at random. 2) Find a lower bound by evaluating the objective function on a few points in $S$ selected at random. 3) Find an upper bound by taking $\max_i \{\max_{x_i \in S} a_i + \|x_i - b_i\|_\infty \}$. Suitable $x_i$ will be found on the edge of $S$ farthest from $b_i$. Many thanks. | |
| Aug 12, 2011 at 22:59 | history | answered | Brian Borchers | CC BY-SA 3.0 |