# Geometric program

A mathematical program of the form

$LaTeX: \min P_0(x) : P_k(x) \le 1, \; x > 0,$

where each $LaTeX: P_k$ is a posynomial (k=0,...,m). Conventionally, the monomials are indexed sequentially, so that the posynomials appear as:

$LaTeX: P_{0} = \sum_{i=1}^{N_0} c_{i} \prod_{j} x_{j}^{a_{i,j}}$
$LaTeX: P_{1} = \sum_{i=N_0 + 1}^{N_1} c_{i} \prod_{j} x_j^{a_{i,j}}$
$LaTeX: \vdots$
$LaTeX: P_m = \sum_{i=N_{m-1} + 1}^{N_m} c_i \prod_j x_j^{a_{i,j}}$

For example, consider:

$LaTeX: \min 1/y^3 + 5y/z^2: x, y, z > 0, \; 1/(xyz) \le 1, \; x/y + z/x \le 1.$

Then, $LaTeX: n=3$ (variables), $LaTeX: m=2$ (constraints), $LaTeX: N_0=2$ (monomials in objective), $LaTeX: N_1=3$ ($LaTeX: N_0 + 1$ monomial in constraint 1), and $LaTeX: N_2 = 5$ ($LaTeX: N_1 + 2$ monomials in constraint 2).

The exponent matrix is the $LaTeX: N_m \times n$ matrix whose i-th row contains the exponents of the variables in the i-th monomial. The example has 5 rows and 3 columns:

$LaTeX: A = \left[ \begin{array}{rrr}

 0 & 0 & -3 \\ 0 & 1 & -2 \\ -1 & -1 & -1 \\ 1 & -1 & 0 \\ -1 & 0 & 1 \end{array} \right]

$

The degree of difficulty is the number of terms in all posynomials ($LaTeX: N_m$) minus the number of independent variables (one less than the rank of exponent matrix). In the above example, the rank of $LaTeX: A$ is 3, so the degree of difficulty is 5-3-1 = 1. If the last constraint were not present, only the first three rows comprise the exponent matrix, and its rank is 2. In that case, the degree of difficulty is 0. (Using the <a href="second.php?page=duals.html#Geometric">geometric dual</a>, the solution reduces to solving a system of linear equations, which is what motivates the terminology.)

Also see superconsistent.

Since its inception, the posynomial form has been extended to signomials. In that case, the duality need not be strong, as there can be a duality gap. The general, or signomial, geometric program is of the form:

$LaTeX: \min P_0(x) - Q_0(x): x > 0, \; P_k(x) - Q_k(x) \le 1$

for $LaTeX: i=1,\ldots,m$, where $LaTeX: P_k$ and $LaTeX: Q_k$ are posynomials ($LaTeX: k=0,\dots,m$).