2
$\begingroup$

I want to optimize the following function:

$$ argmin_{x} f(x) = g(x) + h(x) $$

, where I can get $\nabla_xg(x)$, but cannot calculate $\nabla_xh(x)$.

The derivative-free method, such as the Hill climbing method, works well, but I wonder whether I can make use of $\nabla_xg(x)$.

Improve this question
$\endgroup$
2
  • $\begingroup$ This question is far too general. Look at the trivial case $g \equiv 0$. $\endgroup$
    – Dieter Kadelka
    Commented Mar 8, 2022 at 7:41
  • 3
    $\begingroup$ @DieterKadelka I do not fully agree (see my answer), although I also see that a bit more detail would have been helpful. $\endgroup$
    – Dirk
    Commented Mar 8, 2022 at 11:08

1 Answer 1

Reset to default
2
$\begingroup$

Problems of this type may be solved with splitting methods. One very popular case if the proximal gradient method. If $h$ is convex and lower-semicontinuous and if you are able to caluculate the proximal map, namely $$\operatorname{prox}_{\lambda h}(x) = \operatorname{argmin}_y \tfrac12\|y-x\|_2^2 + \lambda h(y)$$ you can iterate $$x^{k+1} = \operatorname{prox}_{\lambda h}(x^k - \lambda\nabla g(x^k)).$$ If $g$ is convex and $\nabla g$ is Lipschitz continuous with constant $L$ this iteration will converge to a solution if $0<\lambda < 2/L$. There are extensions for non-convex problems as well…

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for your answer! Actually, $h(x)$ is black-box, so I think I cannot calculate the proximal map... $\endgroup$
    – Koukyosyumei
    Commented Mar 8, 2022 at 14:20
  • $\begingroup$ Well, in this case I don't know any method that can take advantage of a gradient of a part of the objective… $\endgroup$
    – Dirk
    Commented Mar 8, 2022 at 14:45

You must log in to answer this question.

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