1
$\begingroup$

Let $ \{F_{i}\} $ be a finite set of linear functionals on a convex compact subset $B\subset\mathbb{R}^{n}$ such that each $F_i$ is $k$-local (acts on $k\ll n$ variables only).
Assume $F=\sum_{i}F_{i}$ gets a minimum at some $v\in B$.

Can we always find another family $F_i'$ of $k'$-local functionals acting on $B$ (for some "small" $k'$) such that each $F_i'$ has a minimum at $v$ (that is, $F'=\sum_{i}F'_{i}$ is frustration free)?

Alternatively: what can I say about the set $A_{k,v}$ of all finite sums of $k$-local functionals of which $v$ is a minimum? $A_{k,v}$ is convex so I would be interested in understanding its extreme points. I suppose they have something to do with frustration free functionals but I'm not sure.

Improve this question
$\endgroup$
4
  • $\begingroup$ Yes: Define $F_i'(x)=0$ for all $i$ and all $x \in B$. Then indeed each $F_i'$ has a minimum at $v \in B$ for all $i$. $\endgroup$
    – Michael
    Commented Sep 16, 2015 at 21:49
  • $\begingroup$ I think the problem should be reformulated as: Can we always find a $k'$-local function $G:B\rightarrow \mathbb{R}$ (for some "small" $k'$) such that $v$ is the unique minimizer of $G(x)$ over $x \in B$? $\endgroup$
    – Michael
    Commented Sep 16, 2015 at 21:55
  • $\begingroup$ Another related question, assuming $v$ is on the boundary of $B$, is: Define $\mathcal{Y}$ as the set of all unit vectors $y$ such that $y^Tx \leq 0$ for all "feasible directions" $x$ that point out of the vector $v$ (so that $v + \delta x \in B$ for all sufficiently small $\delta>0$). Can we find a vector $y \in \mathcal{Y}$ that has at most $k'$ nonzero entries? $\endgroup$
    – Michael
    Commented Sep 16, 2015 at 22:09
  • $\begingroup$ Note that the structure $F_i$ being $k$-local seems meaningless, since any linear function $F(x)$ can be written as a sum of $1$-local functions: $F(x) = c + \sum_{i=1}^N a_i x_i$. $\endgroup$
    – Michael
    Commented Sep 16, 2015 at 22:16

1 Answer 1

Reset to default
1
$\begingroup$

As written it doesn't seem like this should happen very often. For example take $B$ to be a set with a smooth boundary, such as the $n$-disc and suppose that the sum $F$ is not the zero function. Then $F$ has a unique minimizer $v\in B$. Furthermore any unit vector $v$ can arise in this way for some $F$ (the $F_i$ don't seem to be involved in any way). Then any linear functional $F_i'(x) = c_i^T x$ with the same minimizer satisfies $F_i' = -\alpha_i v$ for some $\alpha_i \geq 0$. But $v$ could be arbitrary, and so particularly not local.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .