1
$\begingroup$

I am not currently unfamiliar with a numerical optimization, so I am studying them. What I am wondering is that I'd like to optimize a certain function with the following constraints by using gradient descent algorithm.

\begin{align} & \min\limits_{x}f(x) \\ & \text{subject to }\sum_{i} x_{i}=1 \quad \text{and} \quad x_{i} \geq 0 \end{align}

where the function $f$ is non-convex function. Is there any method to do optimization efficiently?

$\endgroup$
  • $\begingroup$ Welcome to MSE! Please show your attempts. $\endgroup$ – Culver Kwan Aug 17 '19 at 7:18
  • 2
    $\begingroup$ You can use the projected gradient method. At each iteration, you will have to project onto the probability simplex, but it is possible to do that efficiently. You can also use an accelerated version of the projected gradient method, such as FISTA. $\endgroup$ – littleO Aug 17 '19 at 7:20
  • $\begingroup$ What is your $f$. At a point it is easy to parametrize the directions preserving the constraints. $\endgroup$ – reuns Aug 17 '19 at 8:46
  • $\begingroup$ Please, add more context. Why SD method? Is the dimension of $x$ is so high that using quasi-Newton is expensive? Do you know anything more about $f$ except "non-convex"? $\endgroup$ – A.Γ. Aug 17 '19 at 8:52
  • $\begingroup$ @littleO Thanks for good directions. $\endgroup$ – JH Back Aug 19 '19 at 2:42
1
$\begingroup$

You can transform it to a Lagrangian function and minimize this function with the algorithm. Or find the first and/or second derivative and go for bisection or newton methods.

$\endgroup$
  • $\begingroup$ Thanks for your comment. $\endgroup$ – JH Back Aug 19 '19 at 2:48

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.