/sci/ - Science & Math

>>11376745
Suppose I have a vector [math]x \in \mathbb{R}^d[/math]. Let [math]x \vert_{A} \in \mathbb{R}^{|A|}[/math] denote the restriction of [math]x[/math] onto the support of indices [math]A \subseteq \{ 1, \ldots, d \}[/math]. I am interested in the quantity [eqn]S = \sum_{k=1}^m || x\vert_{A_k} ||_2 = \sum_{k=1}^m \sqrt{\sum_{j \in A_k} x_j^2}, [/eqn] where I have partitioned [math]\{ 1, \ldots, d \} = \bigsqcup_{k=1}^m A_k [/math], i.e. [math]A_k \cap A_{k'} = \varnothing[/math] for [math]k \neq k'[/math], and to avoid trivial partitions, suppose all [math]|A_k| > 0[/math]. Note that I have chosen a "standard basis" in which to express my vector elements, i.e. [math]x = (x_1, \ldots, x_d)[/math].

I have two questions, one of which should be trivial but I'm too brainlet to formally prove right now, and the other being a bit more conceptual.

1) What is the minimum value of this quantity, minimized over all possible partitions? This means that I allow [math]m[/math], the number of sets in my partition, to vary, as well as the actual choice of partitioning the indices. I suspect that it's just [math]m=1[/math] due to the concavity of [math]\sqrt{\ \cdot \ }[/math], but I'm not 100% sure.

2) Suppose I have some constraints on what partitions are allowable, and I want to minimize over these constraints. For instance, this may be some esoteric constraint on the indices which may be grouped together (e.g. each [math]A_k[/math] can only contain all odd or all even indices, or the sum of all indices in [math]A_k[/math] must be less than some constant (these are not the actual constraints I'm looking at, they're just examples of what I mean)). How would I go about implementing such a minimization procedure? I often see terms like "semi-definite program" and "linear program" thrown around, but I don't really know how to determine whether my problem (including constraints) falls into one of these nice, tractable settings.