Minimize the following problem:

$$\min_{x\in \mathbb{R}^n}\max_{i=1 \dots m}\{\langle\nabla f_i({\overline{x}}),x-\overline{x}\rangle\}+\sigma\|x-\overline{x}\|^2 \tag 1,$$

with $F:\mathbb{R}^n\to \mathbb{R}^m, F(x)=(f_{1}(x), \dots,f_{m}(x))$.

I was solving this problem, but I could not finish, could someone please help me ?, this is part of my solution:

Solve problem (1) is equivalent to solve \begin{align} \min\limits_{x,z}&\quad z&\hspace{4cm} (2)& \\ \text{s.t}& \quad \langle \nabla f_i({\overline{x}}),x-\overline{x}\rangle+\sigma\|x-\overline{x}\|^2 \leq z&& \end{align} the Langragian dual problem associated with $(2)$ is:

$$\max_{\mu\geq 0}q(\mu)\tag 3,$$ with $$q(\mu)=\inf L(x,z,\mu)$$ and $$L(x,z,\mu)= z+\sum_{i=1}^m\mu_i(\langle \nabla f_i({\overline{x}}),x-\overline{x}\rangle+\sigma\|x-\overline{x}\|^2-z)$$. the problem (3) is equivalent to solve $$\max_{\mu\geq 0} \min_{x,z}\left(1-\sum\limits_{i=1}^m \mu_i\right)z + \sum \limits_{i=1}^m \mu_i(\langle\nabla f_i(\overline{x}),x-\overline{x}\rangle + \sigma\|x-\overline{x}\|^2), $$ $$(x^\ast,z^\ast)=\operatorname*{arg min}_{x,z} \left(1-\sum\limits_{i=1}^m \mu_i\right)z+\sum_{i=1}^m \mu_i(\langle \nabla f_i(\overline{x}),x-\overline{x}\rangle + \sigma\|x-\overline{x}\|^2),$$ $$\nabla_{x,z} L(x^\ast,z^\ast,\mu^\ast)=0$$ this is $$\begin{pmatrix} \sum\limits_{i=1}^m\mu_i^\ast\nabla f_i(\overline{x}) + \sum\limits_{i=1}^m 2\mu_i^\ast \sigma(x^\ast-\overline{x}) \\ 1-\sum\limits_{i=1}^m\mu_i^\ast \\ \end{pmatrix}=\begin{pmatrix} 0\\ 0 \end{pmatrix}$$ This problem has a solution when: $$\sum\limits_{i=1}^{m}\mu_{1}=1$$ and $$x^{\ast}=-\frac{\sum\limits_{i=1}^m\mu_i\nabla f_i(\overline{x})}{2\sigma\sum\limits_{i=1}^m\mu_i}+\overline{x}$$ $$x^{\ast}=-\frac{\sum\limits_{i=1}^m\mu_i\nabla f_i(\overline{x})}{2\sigma} + \overline{x}.$$ I do not know what else to do, what would be the solution to my original problem? and what would be the value of $z^{\ast}$?

  • $\begingroup$ Proper notation is $\langle \nabla f_i(\overline{x}),x-\overline{x}\rangle,$ not $< \nabla f_i({\overline{x}}),x-\overline{x}>.$ I changed that and some other things. $\endgroup$ – Michael Hardy Aug 7 '18 at 0:12
  • 1
    $\begingroup$ This is a standard formulation of a search direction problem (similar to a trust region approach). It might be easier to solve using von Neumann's minimax theorem (or some variant). $\endgroup$ – copper.hat Aug 7 '18 at 0:37

Let $C = \operatorname{co} \{ \nabla f_k( \bar{x} ) \}$ and observe that $C$ is a compact convex set. Note that the problem is equivalent to $\min_h \max_{\xi \in C} \langle \xi, h \rangle + \sigma \|h\|^2$.

A little work shows that a solution must lie in a compact convex set (because of the $\|h\|^2$ term) and the map $(h,\xi) \to \langle \xi, h \rangle + \sigma \|h\|^2$ is convex in $h$ and concave (in fact, linear) in $\xi$.

We can apply von Neumann's minimax theorem to exchange the $\min, \max$ to get $\max_{\xi \in C} \min_h \langle \xi, h \rangle + \sigma \|h\|^2$.

We see that the inner problem has a unique solution $\xi = -2 \sigma h$, and so the problem reduces to $\max_{\xi \in C} -{1 \over 4 \sigma} \|\xi \|^2 = - {1 \over 4 \sigma} \min_{\xi \in C} \|\xi \|^2$.

In particular, the solution is given by the unique point of minimal norm in $C$.

Adjusting $\sigma$ has an effect similar to a step size, except that increasing $\sigma$ has a similar effect to reducing the stepsize.


Let $\Delta_m$ be the $m$-simplex and note that the maximum of a linear function on $\Delta_m$ is attained on a vertex (this is elementary, and dates back to Nash). Thus $$\max_{i} \langle \nabla f_i(\bar{x}), x-\bar{x}\rangle = \max_{z \in \Delta_m}\langle \nabla F(\bar{x})^T(x-\bar{x}),z\rangle = \max_{z \in \Delta_m}\langle x-\bar{x},\nabla F(\bar{x})z\rangle. $$ Thus by Sion's minimax theorem, one has

$$ \begin{split} \min_{x \in \mathbb R^n}\max_{i} \langle \nabla f_i(\bar{x}), x-\bar{x}\rangle + \frac{\sigma}{2}\|x-\bar{x}\|_2^2 &= \min_{x \in \mathbb R^n}\max_{z \in \Delta_m}\langle x-\bar{x},\nabla F(\bar{x})z\rangle\\ &= \max_{z \in \Delta_m}\min_{x \in \mathbb R^n}\langle x-\bar{x},\nabla F(\bar{x})z\rangle + \frac{\sigma}{2}\|x-\bar{x}\|_2^2\\ &= \max_{z \in \Delta_m} \langle -\frac{1}{\sigma}\nabla F(\bar{x})z,\nabla F(\bar{x})z\rangle + \frac{\sigma}{2}\|\frac{1}{\sigma}\nabla F(\bar{x})\|_2^2\\ &= \max_{z \in \Delta_m} -\frac{1}{2\sigma}\|\nabla F(\bar{x})z\|_2^2 = -\frac{1}{2\sigma}\min_{u \in C}\|u\|_2^2, \end{split} $$

where $C := \{z_i\nabla f_i(\bar{x}) | z \in \Delta_m\} =: \operatorname{co}(\nabla F(\bar{x})$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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