3
$\begingroup$

Consider the function $f : [0,1]^n \to [0,\infty)$ defined as $$ f(x_1,\dots,x_n) = \sum_{(z_1,\dots,z_n) \in \{0,1\}^n} g(z_1,\dots,z_n) \cdot \left[\prod_{i=1}^n x_i^{z_i} \cdot (1-x_i)^{1-z_i}\right] $$ where $g(z_1,\dots,z_n) \geq 0$ for every $(z_1,\dots,z_n) \in \{0,1\}^n$. Note that the summation consists of $2^n$ terms. My objective is to solve the following problem: \begin{equation} \begin{aligned} \min_{x_1,\dots,x_n} \quad & f(x_1,\dots,x_n), \\ \textrm{s.t.} \quad & (x_1,\dots,x_n) \in \{y \in \mathbb R^n \mid y_1 \in [a_{1},1],\dots,y_n \in [a_{n},1]\} \end{aligned} \tag{1} \label{prob} \end{equation} where $0 \leq a_i < 1$ for each $i$. In other words, the decision variables $x_1,\dots,x_n$ are constrained to be within an $n$-dimensional hyperrectangle that is a subset of an $n$-dimensional hypercube. To solve the problem in \eqref{prob}, my strategy was to convert it into the standard form for a geometric program and then pass it to a solver. However, the main difficulty in doing so is that the literature that I have found on geometric programming constrain $g(z_1,\dots,z_n)$ to be strictly positive for every $(z_1,\dots,z_n) \in \{0,1\}^n$, while in my case, it can be $0$ for some $(z_1,\dots,z_n) \in \{0,1\}^n$. Therefore, $f$ is not strictly a posynomial. Any suggestions on how to proceed?


Update

Based on the definitions given here, it seems that this isn't really a problem, as the summation in $f$ can be split as \begin{align} f(x_1,\dots,x_n) &= \sum_{\substack{(z_1,\dots,z_n) \in \{0,1\}^n \\ g(z_1,\dots,z_n) \neq 0}} g(z_1,\dots,z_n) \cdot \left[\prod_{i=1}^n x_i^{z_i} \cdot (1-x_i)^{1-z_i}\right] \\ &+ \sum_{\substack{(z_1,\dots,z_n) \in \{0,1\}^n \\ g(z_1,\dots,z_n) = 0}} g(z_1,\dots,z_n) \cdot \left[\prod_{i=1}^n x_i^{z_i} \cdot (1-x_i)^{1-z_i}\right] \\ &= \sum_{\substack{(z_1,\dots,z_n) \in \{0,1\}^n \\ g(z_1,\dots,z_n) \neq 0}} g(z_1,\dots,z_n) \cdot \left[\prod_{i=1}^n x_i^{z_i} \cdot (1-x_i)^{1-z_i}\right] \end{align} However, I wonder if there is a better way to approach this problem in the first place, so I'm keeping this question open.

$\endgroup$
5
  • $\begingroup$ How is this any kind of generalized geometric program? Aside from being nonnegative, Your $g(x_1,...,x_n)$ could be anything. With such a general $g$, this is not necessarily transformable into a convex optimization problem. In the link you provide, the $c_k$ are constants, not functions of the optimization variables - that is a crucial and "deal-breaking" difference. $\endgroup$ Sep 6, 2023 at 23:08
  • $\begingroup$ @MarkL.Stone Note that I wrote "$g(z_1,\dots,z_n)$" and not "$g(x_1,\dots,x_n)$" when defining $f$. $g$ is not a function of the decision variables $x_1,\dots,x_n$. $\endgroup$
    – mhdadk
    Sep 6, 2023 at 23:16
  • $\begingroup$ I misread $z_i$ as $x_o$. There's no problem if some g = 0, because that's the same as the term not being in the sum. So the objective is a posynomial and the problem is a geometric program. $\endgroup$ Sep 7, 2023 at 0:43
  • $\begingroup$ @MarkL.Stone thanks a lot for confirming this. This is unrelated to my main question, but I'm not sure how to show that the term $$\prod_{i=1}^n x_i^{z_i} \cdot (1-x_i)^{1-z_i}$$ in the summation above is a monomial in $x_1,\dots,x_n$. Any suggestions? $\endgroup$
    – mhdadk
    Sep 7, 2023 at 1:27
  • $\begingroup$ A variable raised to a power is a monomial. A product of monomials is a monomial. $\endgroup$ Sep 7, 2023 at 10:04

2 Answers 2

3
$\begingroup$

There's no problem if some $g(z_1,...,z_n) = 0$, because that's the same as the terms which have a zero $g(z_1,...,z_n)$ not being in the sum (objective function). So the objective is a posynomial, and the optimization problem is a geometric program.

The objective function is a posynomial because it is the sum of monomials. Each term in the sum is a monomial because a variable raised to a power is a monomial, and a product of monomials is a monomial.

$\endgroup$
2
$\begingroup$

Just want to add some clarifications to @MarkL.Stone's answer. The function $$g(x) = \prod_{i=1}^n x_i^{z_i} \cdot (1-x_i)^{1-z_i} \tag{1}$$ is not a monomial in $x_1,\dots,x_n$. The reason is that, according to section 1.2 in the paper Disciplined Geometric Programming (2019) by A. Agrawal, S. Diamond, and S. Boyd,

A function is log-log affine if and only if it is a monomial

That is (see section 2.1 in the same paper), a function $f : D \to \mathbb R_+$, where $\mathbb R_+$ is the set of positive reals and $D \subseteq \mathbb R^n_+$, is a monomial if $$ \forall x_1,x_2 \in D, \forall t \in [0,1], f\left(x_1^t \circ x_2^{1-t}\right) = f(x_1)^t \cdot f(x_2)^{1-t} $$ where $\circ$ denotes elementwise product and $x^t = (x_1^t,\dots,x_n^t)$ denotes elementwise exponentiation. In the case of $(1)$, we have \begin{align} g(x_1)^t &= \prod_{i=1}^n x_{1i}^{tz_i} \cdot (1-x_{1i})^{t(1-z_i)} \\ g(x_2)^{1-t} &= \prod_{i=1}^n x_{2i}^{(1-t)z_i} \cdot (1-x_{2i})^{(1-t)(1-z_i)} \\ g(x_1)^t \cdot g(x_2)^{1-t} &= \prod_{i=1}^n x_{1i}^{tz_i} \cdot x_{2i}^{(1-t)z_i} \cdot (1-x_{1i})^{t(1-z_i)} \cdot (1-x_{2i})^{(1-t)(1-z_i)} \end{align} but \begin{align} g\left(x_1^t \circ x_2^{1-t}\right) &= \prod_{i=1}^n (x_{1i}^t \cdot x_{2i}^{1-t})^{z_i} \cdot (1-(x_{1i}^t \cdot x_{2i}^{1-t}))^{1-z_i} \\ &= \prod_{i=1}^n x_{1i}^{tz_i} \cdot x_{2i}^{(1-t)z_i} \cdot (1-(x_{1i}^t \cdot x_{2i}^{1-t}))^{1-z_i} \\ &\neq g(x_1)^t \cdot g(x_2)^{1-t} \end{align} However, if we introduce the variable $y_i = 1 - x_i$ for each $i = 1,\dots,n$ with the equality constraint $x_i + y_i = 1$ for each $i$, then the following function is a monomial in $(x,y)$: $$ h(x,y) = \prod_{i=1}^n x_i^{z_i} \cdot y_i^{1-z_i} \tag{2} $$ We can check if $h(x,y)$ is a monomial in $(x,y)$ using the same definition above: \begin{align} h(x_1,y_1)^t &= \prod_{i=1}^n x_{1i}^{tz_i} \cdot y_{1i}^{t(1-z_i)} \\ h(x_2,y_2)^{1-t} &= \prod_{i=1}^n x_{2i}^{(1-t)z_i} \cdot y_{2i}^{(1-t)(1-z_i)} \\ h(x_1,y_1)^t \cdot h(x_2,y_2)^{1-t} &= \prod_{i=1}^n x_{1i}^{tz_i} \cdot x_{2i}^{(1-t)z_i} \cdot y_{1i}^{t(1-z_i)} \cdot y_{2i}^{(1-t)(1-z_i)} \end{align} and \begin{align} h\left(x_1^t \circ x_2^{1-t},y_1^t \circ y_2^{1-t}\right) &= \prod_{i=1}^n x_{1i}^{tz_i} \cdot x_{2i}^{(1-t)z_i} \cdot y_{1i}^{(1-z_i)t} \cdot y_{2i}^{(1-t)(1-z_i)} \\ &= h(x_1,y_1)^t \cdot h(x_2,y_2)^{1-t} \end{align}

$\endgroup$
1
  • 1
    $\begingroup$ Thanks. I did take a liberty as you have described with $(1-x_i)$. $\endgroup$ Sep 20, 2023 at 23:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.