0
$\begingroup$

I have a nonlinear optimization problem of the form :

$$ \begin{align} & \underset{ \mathbf{x} }{ \text{ maximize } } & & f(\mathbf{x}) \\ & \text{ subject to } & & g(\mathbf{x}) \leqslant 0,\\ & & & x_{ i } \in \{ 0,\cdots,r \}. \forall i \end{align} $$

where $g(\mathbf{x})$ is a nonlinear function. I did the transfomation $x_i=\log y_i$ and make the problem a linear programming problem as:

$$ \begin{align} & \underset{ \mathbf{y} }{ \text{ maximize } } & & f(\mathbf{y}) \\ & \text{ subject to } & & g(\mathbf{y}) \leqslant 0,\\ & & & y_{ i } \in \{ 1,,\cdots,e^r \}. \forall i \end{align} $$

How to model this problem in a solver ? Specifically, how to write the constraint $y_{ i } \in \{ 1,,\cdots,e^r \}$ in a solver ?

$\endgroup$
  • 1
    $\begingroup$ It looks like your constraint $y_i \in \{e^0, e^1, ..., e^r\}$ restricts your variables to a discrete set. So, it is not a linear programming problem (it is still non-convex, at best an integer linear program, provided the $f$ and $g$ functions are linear in the variables). If the functions are indeed linear, it may be useful to relax the problem to a linear program via the relaxed interval constraints $y_i \in [1, e^r]$ for all $i$. $\endgroup$ – Michael Nov 6 '15 at 23:27
  • $\begingroup$ But can we guarantee that the relaxed problem still gives the optimal solution? $\endgroup$ – drzbir Nov 6 '15 at 23:39
  • $\begingroup$ The relaxed problem may not give an optimal solution. It will give an upper bound. $\endgroup$ – Michael Nov 7 '15 at 5:10
  • $\begingroup$ Thank you. So there is no way to solve the problem optimally? Are there any solvers available? $\endgroup$ – drzbir Nov 7 '15 at 23:56
  • $\begingroup$ One way to solve optimally is to try all of the (finite) number of possible solution options. There is no polynomial time way of solving. There are general integer linear program solvers available that may help and may be a bit more efficient than trying all possibilities. Note: I do not see where your title of "countable subset of $\mathbb{R}$" comes into this problem. Perhaps you meant "finite subset of $\mathbb{R}$." $\endgroup$ – Michael Nov 8 '15 at 21:55

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.