2
$\begingroup$

Let's say we have a convex objective function $f(\textbf{x})$, with $\textbf{x}\in R^n$ which we want to minimise under a set of constraints. The problem is that calculating $f$ exactly is not possible and only stochastic approximations are available, which are computably expensive.

Luckily the gradient $\nabla f$ can also be approximated such that we can use a stochastic gradient descent method:

$$\textbf{x}^{(k+1)}=\mathbf{x}^{(k)}-\alpha^{(k)} \nabla f(\textbf{x})$$ where $\alpha^{(k)}$ is the step size and $\nabla f(\mathbf{x})$ is the approximated gradient of $f(\mathbf{x})$.


My question

This method is fast since it still converges even when the accuracy of the gradient is relatively low. But this will give an unconstrained solution, i.e., I will need that,

$$ x_j=0 \lor \alpha_j \le x_j \le \beta_j\quad \text{for all } \ \ j, \ \text{ and }\sum_j x_j \le 1 $$

where $\alpha_j$ and $\beta_j$ are minimum and maximum constraints such that $0<\alpha_j, \beta_j\le 1$.

Is there a way to use Mathematica's built in functions such as FindMinimum[] or Minimize[] to carry out a stochastic gradient descent (or any other method that will solve this problem).


Toy code

p = {.47, .53, .48, .31, .255, .27, .27, .311, .31, .466, .371, .304};
b = {2.5, 2, 2.2, 3.5, 4.33, 4, 4, 3.4, 3.4, 2.2, 2.7, 3.3};

z[o_, b_] := If[o == 1, b - 1, -1];
n = Length[p];
M = 10000;

outcomes = Transpose[Table[RandomVariate[MultinomialDistribution[1,{p[[i]], 1 - p[[i]]}], M], {i, n}]];

f[x_] := Block[{Y, R}, Mean[Reap[Do[Y = outcomes[[K]];R = 1 + Sum[z[Y[[i, 1]], b[[i]]] x[[i]], {i, n}]; Sow[-Log[R]];, {K, M}]][[2,1]]]]
$\endgroup$
  • 1
    $\begingroup$ Can you post your code, with approximated f, so that people have something to play around with? $\endgroup$ – aardvark2012 Sep 14 '17 at 8:06
  • 1
    $\begingroup$ No, there are no builtin functions for any of this. You'll need to implement it yourself. This is an interesting question (at least I'm personally interested), but it doesn't seem to be related to Mathematica. Maybe a better fit on scicomp.stackexchange.com ? $\endgroup$ – Szabolcs Sep 14 '17 at 8:08
  • $\begingroup$ BayesianMinimization attempts to find a good minimum using the smallest number of evaluations. Probably you can implement a Bayesian Optimization with Gradients. Probably by defining a good sampler. Actually I don't know much about this problem, so I may be saying something stupid. $\endgroup$ – rhermans Sep 14 '17 at 9:47
  • $\begingroup$ @Szabolcs Thank you for your reply, I thought as much but it couldn't hurt to ask. $\endgroup$ – user19218 Sep 14 '17 at 11:42
  • $\begingroup$ Your f[x] sometimes returns real values, sometimes returns Indeterminate, and sometimes complexes. You are going to need to fix that to have much hope of finding minima. $\endgroup$ – bill s Sep 14 '17 at 13:13

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.