I want to maximize $$\Phi_g(w):=\sum_{i\in I}\sum_{j\in I}\int\lambda({\rm d}x)\int\lambda({\rm d}y)\left(w_i(x)p(x)q_j(y)\wedge w_j(y)p(y)q_i(x)\right)\sigma_{ij}(x,y)|g(x)-g(y)|^2$$ over all choices of $w=\left(w_1,\ldots,w_{|I|}\right)$ subject to $$\sum_{i\in I}w_i=1\tag1.$$ I guess this is usually solved by the method of Lagrange multipliers, but the shape of the integrand seems to be problematic. What can we do?

If this problem is too hard, are we at least able to find a choice of $w$ yielding a sharp lower bound?

As usual, $a\wedge b:=\min(a,b)$. And it might be useful to rewrite $\Phi_g(w)$ using $2(a\wedge b)=a+b-|a-b|$.

The objects are defined as follows:

  • $(E,\mathcal E,\lambda)$ is a measure space
  • $I$ is a finite nonempty set
  • $p,q_i:E\to[0,\infty)$ are $\mathcal E$-measurable with $$\int p\:{\rm d}\lambda=\int q_i\:{\rm d}\lambda=1\tag2$$ for $i\in I$
  • $g\in L^2(p\lambda)$
  • $w_i:E\to[0,1]$ is $\mathcal E$-measurable with $$\{q_i=0\}\subseteq\{w_ip=0\}\tag3$$ for $i\in I$ with $$\{p\ne0\}\subseteq\left\{\sum_{i\in I}w_i=1\right\}\tag4$$
  • $\sigma_{ij}:E^2\to[0,\infty)$ is $\mathcal E^{\otimes2}$-measurable for $i,j\in I$ with $$\sigma_{ij}(x,y)=\sigma_{ji}(y,x)\;\;\;\text{for all }x,y\in E\text{ and }i,j\in I\tag5$$ and $$\sum_{j\in I}\int\lambda({\rm d}y)q_j(y)\sigma_{ij}(x,y)=1\tag6$$

I'm primarily interested in finding the choice of $w=\left(w_1,\ldots,w_{|I|}\right)$ maximizing $\Phi_g(w)$ and satisfying $(3)$ and $(4)$, but if it's easier to deal with feel free to assume $(1)$ instead of $(4)$.

EDIT: Let's elaborate on the hint given by dchatter. Let $$f:E^2\times{L^2(\lambda)}^I\to\mathbb R\;,\;\;\;((x,y),w)\sum_{i\in I}\sum_{j\in I}\left(w_i(x)p(x)q_j(y)\wedge w_j(y)p(y)q_i(x)\right)\sigma_{ij}(x,y)|g(x)-g(y)|^2.$$ To make everything as simple as possible, assume $I=\{1\}$ (we ignore that $(1)$ immediately implies that necessarily $w_1=1$). Then, as discussed here, $$\partial_wf((x,y),w_1)=\left.\begin{cases}\{\delta_x\}&\text{, if }w_1(x)<w_1(y)\frac{p(y)q_1(x)}{p(x)q_1(y)}\\\left\{c\delta_x+(1-c)\frac{p(y)q_1(x)}{p(x)q_1(y)}\delta_y:c\in[0,1]\right\}&\text{, if }w_1(x)=w_1(y)\frac{p(y)q_1(x)}{p(x)q_1(y)}\\\left\{\frac{p(y)q_1(x)}{p(x)q_1(y)}\delta_y\right\}&\text{, if }w_1(x)>w_1(y)\frac{p(y)q_1(x)}{p(x)q_1(y)}\end{cases}\right\}p(x)q_1(y)\sigma_{11}(x,y)|g(x)-g(y)|^2$$ for all $x,y\in E$ and $w_1\in L^2(\lambda)$, where $\delta_x$ denotes the evaluation functional on $\mathcal L^2(\lambda)$. In the paper of Clarke (Theorem 1 of Section 3), the author shows that $$\partial\Phi_g(w_1)\subseteq\int\lambda^{\otimes2}({\rm d}(x,y))\partial_wf((x,y),w_1)$$ (all derivatives have to be understood in the sense of Clarke's generalized gradient). That means, that for all $\varphi\in\partial F(w_1)$, there is a mapping $\Phi:E^2\to\partial_wf((x,y),w_1)\subseteq{L^2(\lambda)}'$ such that $(x,y)\mapsto\langle\Phi(x,y),v\rangle$ belongs to $L^1(\lambda^{\otimes2})$ and $$\langle\varphi,v\rangle=\int\lambda^{\otimes2}({\rm d}(x,y))\langle\Phi(x,y),v\rangle$$ for all $v\in L^2(\lambda)$. But I don't know how to proceed ...


1 Answer 1


Permit me to interpret your intention to "solve" your problem as "providing necessary conditions for optimality". Such a "solution" may be regarded as a first step towards "solving" the maximization problem.

The key issue with this maximization is the 'max' in the objective functional, but since it is Lipschitz continuous, I think the nonsmooth Lagrange multiplier rule in Clarke's 2013 text https://doi.org/10.1007/978-1-4471-4820-3, Chapter 10, Theorem 10.47, fits the bill. The same text contains several sufficient conditions for the existence of optimizers under nonsmooth (but Lipschitz continuous) in the later chapters.

  • $\begingroup$ You surely mean the $\min$ (not the $\max$) in the objective functional. $\endgroup$
    – 0xbadf00d
    Commented Sep 15, 2019 at 17:04
  • $\begingroup$ I've taken a quick look at the theorem in the book. Actually, I thought about a Lagrange multipliers approach before, but how exactly would we apply it here (which Banach/Hilbert space do we choose and how do we calculate the derivatives)? (My problems in applying the Lagrange multiplier approach led me to the search for a sharp lower bound for which the Lagrange multiplier approach is easier to apply, but I wasn't able to find a suitable bound yet.) $\endgroup$
    – 0xbadf00d
    Commented Sep 15, 2019 at 17:08
  • $\begingroup$ Standard manipulations are needed to make the max into a min, that's hardly an issue. You will need derivatives on Banach spaces, sure; this is again standard material in functional analysis textbooks. $\endgroup$
    – dchatter
    Commented Sep 15, 2019 at 19:08
  • $\begingroup$ I know how to calculate the Fréchet/Gâteaux derivative; that's not the problem. My problem is that the integrand is not everywhere differentiable (due to the occurrence of $\min$) and it seems quite complicated to derive a formula we can work with. If you know how to do it, this would be a great addendum to your answer. $\endgroup$
    – 0xbadf00d
    Commented Sep 15, 2019 at 19:15
  • $\begingroup$ My apologies for the delay. The concepts involved here are the Clarke generalized directional derivatives, limiting cones, and the like, and they're fine-tuned to handle Lipschitz nonsmoothness like the max; these constructions have been treated at length in Clarke's text that I mentioned. $\endgroup$
    – dchatter
    Commented Sep 17, 2019 at 16:16

Your Answer

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