Geometric program

From Glossary

Jump to: navigation, search

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}
</p>
<pre>  0 &  0 & -3 \\
  0 &  1 & -2 \\
 -1 & -1 & -1 \\
  1 & -1 &  0 \\
 -1 &  0 &  1
  \end{array} \right]
</pre>
<p>

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).


Views
Personal tools