0

The problem I have is to optimize a vector $x = [x_1, x_2, x_3, \ldots, x_n]$ where the value of $x$ can be either $0$ or within the interval of $[x_\min, 1]$ where $x_\min$ is some parameter than will be somewhere between $0$ and $1$. The objective function is differentiable and all that, so I can get gradients no problem.

Note that the $x$ vector can potentially have more than $100,000$ elements, so I can't just full factorial brute force it like I could if $x$ had only $3$ elements or something. If I only had a $3$ elements, I'd just run the optimization $8$ times with all possible domain combinations.

I'll also note that it's not necessarily critical that all values lie exactly within the intervals that I'm aiming for. If I can optimize such that values in between $0$ and $x_\min$ are really close to either $0$ or $x_\min$ and I can just bump it up or down for the final solution, I'm okay with that.

Anyone know any ways to tackle this problem?

Kuzja
  • 450
  • 4
  • 12
Matt McConaha
  • 1

1 Answers1

2

Decision variables $x$ that can assume values: $x=0$ or $x \in [L,U]$, are called "semi-continuous". Some linear (and quadratic) mixed integer programming (MIP) solvers support this directly (just tell it the variable type is semi-continuous). Otherwise we can formulate this using additional binary variables $\delta$: $$ \begin{align} & L \delta \le x \le U \delta\\ & \delta \in \{0,1\} \end{align} $$ These constructs are quite popular. E.g. in portfolio optimization semi-continuous variables are used to prevent very small positions (which have a relatively large transaction cost).

If your model is otherwise nonlinear, this would make it a MINLP (Mixed Integer Nonlinear Programming) model. There are readily available solvers for this class of models. MINLP solvers typically do much better than complete enumeration. Having $n=1e5$ variables makes your model rather large, but I would say it is not hopeless.

Erwin Kalvelagen
  • 4,267