Timeline for Maximizing a piecewise-linear convex function
Current License: CC BY-SA 4.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 11, 2021 at 7:50 | history | edited | Rodrigo de Azevedo | CC BY-SA 4.0 |
added 113 characters in body
|
| Mar 11, 2021 at 7:43 | comment | added | lovasoa | or.stackexchange.com/questions/5894/… | |
| Mar 11, 2021 at 7:15 | comment | added | Rodrigo de Azevedo | I suppose you can flag your own question and request that it be moved. Or, you can re-post there and cross-link them, so that if it is answered in one site, people on the other site will know. | |
| Mar 11, 2021 at 7:05 | comment | added | lovasoa | Ok, I'll do that. Is there a way to move a question from one site to another, or should I delete it here and create a new one there ? | |
| Mar 10, 2021 at 19:30 | comment | added | Rodrigo de Azevedo | Exactly. The number of branches does grow exponentially with the number of variables, but it should grow according to $2^n$, whereas in your example, if one is sloppy, it grows according to $2^{2n}$. Isn't the existence of problems whose average-case instances are infeasible that makes cryptography possible? In my humble opinion, you should move this question to or.stackexchange.com which is where the experts on combinatorial optimization are. | |
| Mar 10, 2021 at 19:19 | comment | added | lovasoa | The number of branches grows exponentially with the number of variables, and I don't think it's possible to solve billions of linear programs in a reasonable amount of time. What are the smarter ways of doing it ? I can determine whether the objective is concave: it is not :p | |
| Mar 10, 2021 at 19:14 | history | edited | Rodrigo de Azevedo | CC BY-SA 4.0 |
added 40 characters in body
|
| Mar 10, 2021 at 19:09 | comment | added | Rodrigo de Azevedo | Every $\min$ / $\max$ introduces a Boolean variable. Thus, in your example, you have $2^4 = 16$ "branches". The maximum of each of these branches can be found via LP. Lastly, find the $\max$ of the $16$ maxima. There are smarter ways of doing it. If you can determine whether the objective to be maximized is concave, it is much easier. | |
| Mar 10, 2021 at 17:44 | history | edited | Rodrigo de Azevedo |
edited tags
|
|
| Mar 10, 2021 at 17:23 | history | edited | lovasoa | CC BY-SA 4.0 |
added 122 characters in body
|
| Mar 10, 2021 at 8:27 | comment | added | lovasoa | Yes, the objective function is piecewise linear and all the variables are bounded, so the objective has a finite maximum. | |
| Mar 9, 2021 at 22:45 | history | edited | lovasoa | CC BY-SA 4.0 |
deleted 1 character in body
|
| Mar 9, 2021 at 22:41 | comment | added | lovasoa | Yes, exactly, the feasible region is not convex. So the question is: what is the canonical way of solving such problems ? | |
| Mar 9, 2021 at 20:38 | comment | added | Rodrigo de Azevedo | When $c^- > c^+$, you can solve the problem because it is convex. When $c^- < c^+$, the problem is non-convex. | |
| Mar 9, 2021 at 20:37 | history | edited | Rodrigo de Azevedo | CC BY-SA 4.0 |
edited title
|
| Mar 9, 2021 at 20:31 | comment | added | Rodrigo de Azevedo | I would write $c_+$ instead, since $c^+$ is a bit too close to $c$ transposed. | |
| Mar 9, 2021 at 20:30 | history | edited | Rodrigo de Azevedo | CC BY-SA 4.0 |
added 1 character in body
|
| Mar 9, 2021 at 16:49 | history | edited | lovasoa |
edited tags
|
|
| Mar 9, 2021 at 16:42 | review | First posts | |||
| Mar 9, 2021 at 18:18 | |||||
| Mar 9, 2021 at 16:39 | history | asked | lovasoa | CC BY-SA 4.0 |