1
$\begingroup$

I am trying to maximize the following function (variable: $\theta$, a vector ($\theta_1$,...,$\theta_K$). most likely $K\leq5$

$$ \begin{aligned} F(\theta, c_0, c_1) = &P_{\theta}(T_0 > c_0, \max T_i >c_1, \min T_i <-c_1) \\ &+ \sum_{S \subset \{1,2,.,K\},\\ 1\leq |S|\leq K-1} P_{\theta}(T_0 > c_0, \min_{i\in S} |T_i| >c_1, \max_{i \in \bar{S}} |T_i| \leq c_1) \\ &\mspace{100mu}\mathcal{I}(\max_{i\in S} |\theta_i| \leq \min_{i\in \bar{S}} |\theta_i|) \end{aligned} $$

where $T_i$ is normally distributed with mean $\theta_i$ and variance 1. $T_0 = \sum_{1<= i<j <=K} (T_i-T_j)^2$

So basically this function is First, a sum of Gaussian integrals which I don't believe has any closed form. Second, discontinuous due to the multiplication of indicator $\mathcal{I}(\max_{i\in S} |\theta_i| \leq \min_{i\in \bar{S}} |\theta_i|)$

My approach now: use quasi-Monte Carlo to numerically calculate the integral. Use simulated annealing to optimize.

Seems quite clumsy. Is there a better way to do this?

$\endgroup$
  • $\begingroup$ It's currently hard to read your function definition, since brackets aren't matched and the mentioned integration/expectation calculation does not appear in the formula. Could you clean up the formatting? $\endgroup$ – Geoffrey Irving Mar 4 '14 at 5:28
  • $\begingroup$ Just cleaned up. I forgot to mention that all $\theta_i$ will be non-negative. This function is piece-wise continuous. For example, when K=2, it is continuous on $\theta_1>\theta_2>0$, on $\theta_1=\theta_2$, and on $\theta_2>\theta_1>0$. I could optimize the function on each of the three regions. However, as K increases, this will be very time-consuming. $\endgroup$ – user3075021 Mar 4 '14 at 19:29
2
$\begingroup$

It's not possible to optimize rigorously a discontinuous objective function without resorting to all sorts of trickery.

If you know where all of the discontinuities are, you can subdivide your problem into a collection of problems, all of which have continuous objective functions. Hopefully, this collection is small; otherwise, it is intractable.

If you don't know where all of the discontinuities are, in some cases, you can use automatic differentiation-like tools to detect where they are, and if they are step discontinuities, it's possible to construct relaxed optimization problems and solve them in a branch-and-bound procedure. This sort of algorithm has exponential time complexity in the number of decision variables, and requires lots of infrastructure (automatic differentiation, the ability to calculate convex and concave relaxations).

Most deterministic algorithms require that a function be Lipschitz continuous, at minimum. Stochastic algorithms like simulated annealing are probably a good practical compromise in situations where you need an answer, have severe time constraints, and aren't picky about the quality of your answer (i.e., it has to be "good enough"). If the set of discontinuities is a set of measure zero (which I suspect holds in a lot of situations), then any stochastic method will almost surely avoid those discontinuities.

$\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.