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.

$\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
    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
    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
    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
    Sep 16, 2015 at 22:16

1 Answer 1

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.