# Geometric programming (GP) ¶

Go back

This is some sort of constrained optimization, but the only constraint is that all values are strictly positives. Usually, that's some function looking like that

$\min_{x \gt 0,\ \ y \gt 0} g(X) = ... + ... + ...$

Having m terms and n variables (and X is the vector of variables).

## Steps ¶

Matrix

Create a matrix $M_{m,n}$ so we will have m rows and n columns. A value such as $a_{i,j}$ is the power of the j-nth variable in the i-nth term.

• 0 if not found
• 1 if no power
• -n if the variable is under a fraction bar
• n else

System

Write a system of equations using the matrix. A column of your matrix is a row of the system. Each row of your matrix is a variable delta_i where i is the row number. Each line of the system is equal to 0.

$\sum\limits_{i=1}^{m} \alpha_{ij}\delta_{i} = 0$

Then add another equation: the sum of all deltas is 1. And solve and find all deltas.

Find the solution $$\nu$$ (nu)

Simply evaluate this equation with the values that you found. Note that $c_i$ stands for the coefficient of the i-nth term.

$\nu(\delta)=\prod\limits_{i=1}^{m} \big( \frac{c_{i}}{\delta_{i}}\big)^{\delta_{i}}$

Check it's a critical point

System of equations, for each term m, you write the term equals to $\nu(\delta) * delta_i$

You solve the system, and will have x*, y*, ... Then as you could guess, try to check if these values in your gradient are giving you a vector of zeros.

## Example ¶

Apply the steps on

$\min_{x \gt 0,\ \ y \gt 0} g(x, y) = 8x + \frac{y}{x}+ \frac{1}{y}$

Create the matrix

$\begin{pmatrix} 1 & 0 \\ -1 & 1 \\ 0 & -1 \end{pmatrix}$

The first line is 1 (x power is 1) and 0 (y not found) in 8x.

System

We got 2 equations (the last two) since we had 2 columns and 3 deltas since we got 3 lines in our matrix.

$\begin{split}\left\lbrace\begin{array}{l} \delta_{i}>0 \,\,\forall i=1,2,3 \\ \delta_{1} + \delta_{2} + \delta_{3} = 1 \\ \delta_{1} - \delta_{2} =0 \\ \delta_{2} - \delta_{3} =0 \\ \end{array}\right.\end{split}$

The 3rd line is 1 delta1 -1 delta2 + 0 delta3 since we got (1,-1,0) in our first column.

Let's solve this

$\begin{cases} (1) & \delta_{1} = \delta_{2} \ so\ \ \delta_{2} = \delta_{1} \\ (2) & \delta_{2} = \delta_{3}\\ but & \delta_{1} + \delta_{2} + \delta_{3} = 1\\ so\ (3) & \delta_{2} + \delta_{2} + \delta_{2} = 1\\ (4) & 3 \delta_{2} = 1 \\ (5) & \delta_{2} = 1/3 \\ so & \delta_{1} = \delta_{2} = \delta_{3} = 1/3 \\ \end{cases}$

Find the solution

$\nu(\delta)= (\frac{8}{\frac{1}{3}}) ^ {\frac{1}{3}} * (\frac{1}{\frac{1}{3}}) ^ {\frac{1}{3}} * (\frac{1}{\frac{1}{3}}) ^ {\frac{1}{3}} * = 24 ^ {\frac{1}{3}} * 3 ^ {\frac{1}{3}} * 3 ^ {\frac{1}{3}} = 8 ^ {\frac{1}{3}} * 3 ^ {\frac{1}{3} + \frac{1}{3} + \frac{1}{3}} = 8 ^ {\frac{1}{3}} * 3 = 2 * 3 = 6$

Critical point?

\begin{split}\left\lbrace\begin{array}{l} 8x = 2 \\ \\ \frac{y}{x} = 2 \\ \\ \frac{1}{y} = 2 \end{array}\right.\end{split}

Note that 2 is equals to 6 (sol) * 1/3 (delta_i). We got

$\begin{cases} x*=2/8=1/4\\ y*=1/2 \end{cases}$

$\begin{split}\nabla f(X) = \begin{pmatrix} 8 - y/x^2 \\ 1/x - 1/y^2 \\\end{pmatrix}\end{split}$
$\begin{cases} 8 - (1/2)/(1/4)^2 = 0 \\ 1/(1/4) - 1/(1/2)^2 = 0 \end{cases}$
$\begin{split}Hf(X) = \begin{pmatrix} 2y/x^3 & -1/x^2 \\ -1/x^2 & 2/y^3 \\ \end{pmatrix}\end{split}$