3
$\begingroup$

In order to find the local minima of a scalar function $f(x)$, where $x \in \mathbb{R}^N$, I know we can use the projected gradient descent method if I want to ensure a constraint $x\in C$:

$$y_{k+1}=x_k-\alpha_k \nabla_xp(x)$$ $$x_{k+1} = \arg \min_{x \in C} \|y_{k+1}-x\|$$ where $\alpha_k$ is the step size and $\nabla_xp(x)$ is the gradient of $p(x)$.

Furthermore, the generalized gradient descent method helps to find local minima if $f(x)=g(x)+h(x)$ were $g$ is convex and differentiable and $h$ is convex but not necessarily differentiable.

My question is: How can I compute a gradient descent approach for the following optimization problem?

$$\min_{\sum_{i=1}^N \Delta_i =0} f\left(g(\Delta)-c||\Delta||_1\right)$$ where the scalar function $f(x), x\in\mathbb{R}$ is convex and differentiable, $g(\Delta),\Delta\in\mathbb{R}^N$ is convex and differentiable but - LASSO-style - the $L_1$ Norm $||\Delta||_1$ is not everywhere differentiable. The condition requires that the elements of $\Delta$ sum up to 0, $c >0$ is just a scalar.

Edit (to illustrate my current state of knowledge):

  1. I am aware of the ISTA algorithm, therefore without the constraint and the wrapping-function $f$, finding a minimum for $z_1(\Delta) =g(\Delta)-c||\Delta||$ could be done by choosing $$\Delta_k = \arg\min_\Delta \left( \frac{1}{2_t} ||\Delta-(\Delta_{k-1} - t_k \nabla f(\Delta_{k-1})||^2 +c||\Delta_1|| \right) \\ =p_{c t_k}(\Delta_{k-1} - t_k \nabla f(\Delta_{k-1}))$$ with $$p_{c t_k} (x)_i= (|x|_i - ct_k)^+ sgn(x_i).$$

  2. With respect to the constraint I do not think performing projected gradient descent $x_{k+1} = \pi(\Delta_{k+1}))$ with $\pi(\Delta) = (I_N-\iota\iota'/N )\Delta$ is a reliable approach after rephrasing the optimization problem as an unconstrained optimization: $$\min_{\Delta \in\mathbb{R}^{N-1}} f \left( g(\Delta,-\sum_{i=1} ^{N-1} \Delta_i)-c\left(\sum_{i=1}^{N-1}|\Delta_i|+|\sum_{i=1} ^{N-1} \Delta_i|\right) \right).$$ Instead, the proximity operator $p_t (z) = \arg \min _{\Delta'\iota = 0} \frac{1}{2t} ||\Delta - z|| ^2 +c||\Delta||_1$ is needed (this is at least my understanding, feel free to comment if this is wrong).

$\endgroup$
  • $\begingroup$ can you show your attempt at finding the prox operator? $\endgroup$ – LinAlg Oct 28 '16 at 16:51
  • $\begingroup$ Thanks for your comment @LinAlg! I edited the question. $\endgroup$ – muffin1974 Oct 28 '16 at 17:40

Your Answer

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

Browse other questions tagged or ask your own question.