0
$\begingroup$

Here is an optimization problem I'm trying to solve:

Objective function to be minimized:

$$ f(x) = -\sum_{i=1}^{n}(x_{i}+a_{i})\bigg[1-\exp\bigg(-\frac{x_ib_i}{x_i+a_i}\bigg)\bigg] $$ where the constants: $$ a_{i},b_{i} \ge 0 $$ are positive for all $i$.

Constraints: $$ x_{i} \ge 0 $$ $$ \sum_{x=1}^{n}x_{i} \le A $$ (A is a positive constant)

I have tried solving this in python and matlab using built-in solvers. It works well, however the problem is that the constants order of magnitude is very large (also largely different among them, so can't normalize) and the solvers do not output correct results for these values. I am trying to solve this in a programming language using gradient descent, which I read it is suitable for such occasions (even with the risk of stopping into a local minima if the function is not convex). I've read the theory about gradient descent which makes sense.

However I also read that since I have constraints, I have to project my space on them. I am not sure how exactly I can do this. Can anyone give any suggestions and advice? Thanks!

$\endgroup$
0
$\begingroup$

You can add a slack variable $x_{n+1}\geq 0$ such that $x_1+\dots +x_{n+1} = A$. Then you can apply the projected gradient method $$x^{k+1} = P_C(x^k - \alpha \nabla f(x^k)),$$ where in every iteration you need to project onto the set $C = \{x\in\mathbb{R}^{n+1}_{+}\colon x_1+\dots + x_{n+1} = A\}$. The set $C$ is called the simplex and the projection onto it is more or less explicit: it needs only sorting of the coordinates, and thus requires $O(n\log n)$ operations. There are many versions of such algorithms, here is one of them Fast Projection onto the Simplex and the $l_1$ Ball by L. Condat.

Since $C$ is a very important set in applications, it has been already implemented for various languages.

$\endgroup$

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.