0

$$ \begin{equation} \begin{aligned} & \underset{x,y}{\text{minimize}} & & f_0(x,y) \label{eq:6}\\ & \text{subject to} & & f_1(x)\geq 0, \label{eq:7} \\ & & & f_2(y)=0,\\ & & & x \in \{0,1\}^n, y\in\mathbb{R}^n. \label{eq:9} \end{aligned} \end{equation} $$

where $f_0(x)$ and $f_1(x)$ are linear functions. The function $f_2(x)$ is a monomial of the form $$ f_2(y)=-c+\prod_{i=1}^ny_i, $$ for some $c>0$.

How can I solve the following problem? Is it a geometric programming problem? What is the name of this problem and is there any tool to solve it?

zebda
  • 39

2 Answers2

2

I will answer it so I can have more space for explain myself.

If $y_i>0$ you can apply $\log$ on $c=\prod^{n}_{i=1} y_i$ and obtain $\log c=\sum^n_{i=1}\log y_i$.

Now call $w_i = \log y_i$, then the constraint become $\log c=\sum^n_{i=1} w_i$, which is a linear constraint. Since $c$ is a parameter you can have $k = \log c$ being a parameter as well.

If you are able to change your objective function, \begin{align} f_0(x,y) = \sum_{i=1}^n a_i y_i + \sum^n_{i=1}b_i x_i \end{align} in order to fit $w_i$ in the place of $y_i$, you could find some $\widetilde{a}_i$ such that \begin{align} f_0(x,y) = \sum_{i=1}^n \widetilde{a}_i w_i + \sum^n_{i=1}b_i x_i \end{align} Then, this would yield a mixed-integer programming. Note that minimizing $w_i$ imply minimizing $y_i$.


Alternatively, if you can not change your parameter $a_i$ in the objective function. Consider that you have \begin{align} f_0(x,y) = \sum_{i=1}^n a_i y_i + \sum^n_{i=1}b_i x_i \end{align} if $w_i = \log y_i$ then $y_i = e^{w_i}$. Therefore \begin{align} f_0(x,y) = \sum_{i=1}^n a_i e^{w_i} + \sum^n_{i=1}b_i x_i \end{align} Which is a nonlinear but convex objective function.

The problem becomes a convex constrained Mixed Integer Convex Programming with linear constraints which can be solved easily. Which can be solved to global optimality with BONMIN (free and also available in NEOS Solver).

1

If coefficients in f0 and f1 are positive, all variables are positive, and you frame the $y$ constraints as $c = \prod_{i=1}^n y_i$ then yes. But you're better off with Marco's solution above: use a mixed-integer linear programming solver, which you can find for any programming language you like.

If you do want to solve geometric programs, take a look at GPkit. No mixed-integer support yet, but we're working on it.

Ned
  • 11