Geometric programming: Why are the constraints defined to be less than/equal to 1?

Question

In a simple convex optimisation problem, the standard form is given by \begin{align}\min_{\bf x}&\qquad f({\bf x})\\\text{s.t.}&\qquad g_i({\bf x})\le 0,\quad i=1,\cdots,m\\&\qquad h_j({\bf x})=0,\quad j=1,\cdots,p\end{align} with ${\bf x}\in\Bbb R^n$ being the vector of variables to be optimised.

By changing the RHS of the constraints, we obtain a geometric optimisation problem, whose standard form is given by \begin{align}\min_{\bf x}&\qquad f({\bf x})\\\text{s.t.}&\qquad g_i({\bf x})\le 1,\quad i=1,\cdots,m\\&\qquad h_j({\bf x})=1,\quad j=1,\cdots,p\end{align} with ${\bf x}\in\Bbb R^n$ being the vector of variables to be optimised. This has the additional restrictions that $f,g_i$ are posynomials and $h_j$ are simple monomials.

Questions

1. Why is it so common to have 1 as the RHS of the constraints? That is, is there anything significant/geometrically convenient about it or is it by convention? For example, in a simple LP, the constraint is of the form $A{\bf x}\le \bf b$ and not usually written as $A{\bf x}{\bf b}^{-1}\le 1$.

2. Suppose that we replace 1 by the more general set of constraints \begin{cases}g_i({\bf x})\le a_i,\quad i=1,\cdots,m\\h_j({\bf x})=b_j,\quad j=1,\cdots,p.\end{cases} What is the terminology for this generalised problem?

Answer 1

Some of the reasons are convention (and the reason $1$ is the convention is that after substituting $x_i = e^{y_i}$ and taking logs of both sides, we get a convex program where all right-hand sides are $0$). But the primary practical reason to put the constraints in a standard form - that is, $g_i(\mathbf x) \le 1$ - is that then the dual of a geometric program is slightly more convenient to state.

I'm going to be lazy and link to my own notes on the geometric programming dual. The dual geometric program is described on the first page. The description is, uh, kind of long. The example at the bottom of page $3$ might be more helpful.

There is a dual variable $\delta_i$ for each term $C_i x_1^{\alpha_{i1}} x_2^{\alpha_{i2}} \dotsm x_m^{\alpha_{im}}$ that appears in the geometric program, wherever it appears: in the objective function, or in one of the constraints. The key point to highlight for your question is that, provided your geometric program is in standard form, the dual objective function has a $\left(\frac{C_i}{\delta_i}\right)^{\delta_i}$ factor.

If we're working with a geometric program that's not in standard form, and the $i^{\text{th}}$ term comes from a constraint with right-hand side $B$, then this factor should look like $\left(\frac{C_i/B}{\delta_i}\right)^{\delta_i}$ instead. Effectively, we are forced to divide through by $B$ before we can take the dual.

---

I would still consider programs that have the more general constraints of the form $\text{posynomial} \le B$ (for $B>0$) to be geometric programs. They're not in standard form, but depending on what you're about to do with them, you may not care.

In fact, we could even allow the right-hand side to be any monomial with a positive coefficient. For example, the constraint $$x_1^2 + x_2^2 \le x_3^2$$ is not any harder to deal with. The reason, of course, is that we can divide through by such a monomial to get a posynomial constraint $$x_1^2 x_3^{-2} + x_2^2 x_3^{-2} \le 1$$ in standard form. I would still call programs with such constraints geometric programs, though somewhat less neatly stated ones.

Answer 2

$\log 1 = 0$ could explain that: take $\log$ of both sides.

Edit: I have now looked and found this in "A tutorial on geometric programming", Stephen Boyd · Seung-Jean Kim · Lieven Vandenberghe · Arash Hassibi.

Look on p. 73 equation (6), and the paragraph which precedes it:

The conversion of a GP to a convex problem is based on a logarithmic change of variables, and a logarithmic transformation of the objective and constraint functions. In place of the original variables $x_i$, we use their logarithms, $y_i = \log x_i$ (so $x_i = e^{y_i}$). Instead of minimizing the objective $f_0$, we minimize its logarithm $\log f_0$. We replace the inequality constraints $f_i \le 1$ with $\log f_i \le 0$, and the equality constraints $g_i = 1$ with $\log g_i = 0$. This results in the problem \begin{align}\text{minimize}&\qquad f_0(e^y)\\\text{subject to}&\qquad\log f_i(e^y)\le 0,\quad i=1,\cdots,m\\&\qquad\log g_i(e^y)=0,\quad i=1,\cdots,p\tag6\end{align} with variables $y=(y_1,\cdots,y_n)$.

As for the RHS not being 1, that is still basically a Geometric Program, which can be converted to standard form by dividing both the LHS and RHS by the RHS. That is addressed in the first paragraph of section 2.3 on p. 71 of the link:

Several extensions are readily handled. If $f$ is a posynomial and $g$ is a monomial, then the constraint $f(x) \le g(x)$ can be handled by expressing it as $f(x)/g(x) \le 1$ (since $f/g$ is posynomial). This includes as a special case a constraint of the form $f(x) \le a$, where $f$ is posynomial and $a > 0$. In a similar way if $g_1$ and $g_2$ are both monomial functions, then we can handle the equality constraint $g_1(x) = g_2(x)$ by expressing it as $g_1(x)/g_2(x) = 1$ (since $g_1/g_2$ is monomial).