Timeline for Explicit upper and lower bounds for a certain support function
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 4, 2023 at 18:31 | vote | accept | Drew Brady | ||
| Dec 1, 2023 at 23:17 | answer | added | icecuber | timeline score: 3 | |
| Nov 10, 2023 at 4:01 | comment | added | Drew Brady | Of course, one can also drop the constraint $\sum_i b_i^2 \leq 1$, which leads to an upper bound of $t (\max_i a_i)$. | |
| Nov 10, 2023 at 3:59 | comment | added | Drew Brady | That approach leads to an upper bound of $\sqrt{\sum a_i^2}$. It is not sharp unless $\sum_i \sqrt{a_i} \leq t \sqrt[4]{\sum_i a_i^2}$. There are vectors that do not satisfy this inequality when $1 < t < d^{3/4}$. | |
| Nov 10, 2023 at 3:11 | comment | added | Thomas Kojar | If you drop the square-root-constraint in terms $t$, then you basically have a inequality matrix constraint $$\sum b_{i}^{2}=bIb\leq 1,$$ for the identity matrix $I$, which is standard in textbooks in nonlinear programing like the one by Boyd and Vandenberghe web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf. So this less-constrained optimization problem can give you an upper bound. | |
| Nov 10, 2023 at 3:06 | comment | added | Thomas Kojar | Are you looking for any particular bounds for some problem? Lower bounds are much easier because you just have to make choices that satisfy the constraints eg. setting $b_{1}=1$ and the rest $b_{i}=0$ and to get a lower bound by $a_{1}$. | |
| Nov 10, 2023 at 2:42 | history | edited | Drew Brady | CC BY-SA 4.0 |
edited body
|
| Nov 10, 2023 at 1:03 | comment | added | Drew Brady | This doesn't really seem to help too much. The dual problem is somewhat challenging to handle as well. | |
| Nov 10, 2023 at 1:00 | comment | added | Thomas Kojar | I would also try solving the penalized unconstrained version i.e. $$max \sum a_i b_i+c\min(0,1-\sum b_i^2)+c\min(0,t-\sum \sqrt{b_i})$$ and then taking $c\to +\infty$. (see penalized version with inequality constraints in warin.ca/ressources/books/…). | |
| Nov 10, 2023 at 0:50 | comment | added | Thomas Kojar | did you try the KKT-conditions and duality? Duality at least gives an upper bound. | |
| Nov 10, 2023 at 0:41 | comment | added | Drew Brady | Comment: Of course for such upper and lower bounds, one can simply take $f_t$. I am hoping for something more explicit. (I realize this is loosely formulated, so I leave it open to interpretation and will accept anything that is more explicit than the current variational representation.) | |
| Nov 10, 2023 at 0:39 | history | asked | Drew Brady | CC BY-SA 4.0 |