Geometric programming

Authors: Wenjun Zhu(wz274), Sam Olsen(sgo23) (SYSEN5800, FALL 2021)

Introduction

A geometric programming (GP) is a family of non-linear optimization problems. Geometric programming optimization problems are typically not convex optimization problems. However, geometric programming optimization problems can be transformed from non-convex optimization problems to convex optimization problems given by their special properties. The convexification for geometric programming optimization problems is implemented by a mathematical transformation of the objective function and constraint functions and a change of decision variables. Though a number of practical problems are not equivalent to geometric programming, geometric programming is generally considered an effective solution for practical problems and it is used to well approximate and analyze various large-scale applications. Typical applications include but are not limited to optimizing power control in communication systems , optimizing doping profile in semiconductor device engineering , optimizing electronic component sizing in IC design , and optimizing aircraft design in aerospace engineering .

Theory/Methodology

Monomial function

A monomial function, or a monomial, is defined as:

$f(x)$ = $cx_{1}^{a_{1}}$$x_{2}^{a_{2}}$...$x_{n}^{a_{n}}$

where $c$ > 0, $f(x)$ is a function: $R^{n}\rightarrow R$ with domain $R_{++}^{n}$

The exponents $a_{i}$ of a monomial can be any real numbers, including fractional or negative, but the coefficient $c$ can only be positive .

Posynomial function

Posynomial

A posynomial function, or a posynomial, is defined as: $f(x)$ = $\sum _{k=1}^{K}$$c_{k}x_{1}^{a_{1k}}$$x_{2}^{a_{2k}}$...$x_{n}^{a_{nk}}$

where $c_{k}$ > 0,

This is a function of sum of monomial functions defined in the above section 2.1 .

Generalized Posynomial

A generalized posynomial function, or a general posynomial, is defined as a function $f(x_{i})$ of positive variables $x_{i}$ if it can be formed from posynomials using the operations of addition, multiplication, positive (fractional) power, and maximum .

For example:

$f(x)=(h_{1}(x)+h_{2}(x))^{6}(h_{3}(x)+10)$

where $h_{1}(x)=0.9x^{2}$,

$h_{2}(x)=4{x}^{6}$,

$h_{3}(x)=max(1+x,2x^{7})$

$f(x)$ is a generalized posynomial function and it can be seen as follows:

• $0.9x^{2}$ is a posynomial so $h_{1}(x)$ is a posynomial function
• $4x^{6}$ is a posynomial so $h_{2}(x)$ is a posynomial function
• $max(1+x,2x^{7})$ is a generalized posynomial so $h_{3}(x)$ is a generalized posynomial function
• $f(x)$ is expressed by addition, multiplication, and positive (fractional) power from $h_{1}(x)$, $h_{2}(x)$, $h_{3}(x)$ functions

Therefore $f(x)$ is a generalized posynomial function.

Definition

The standard form of Geometric Programming optimization is to minimize the objective function which must be posynomial. The inequality constraints can only have the form of a posynomial less than or equal to one, and the equality constraints can only have the form of a monomial equal to one.

Standard Form

Minimize $f_{0}(x)$

Subject to: $f_{i}(x)\leqslant 1$, $i$ = 1,...,m,

$g_{i}(x)=1$, $i$ = 1,...,p,

$x_{i}>0$, $i$ = 1,...,q,

where $f_{i}(x)$ are posynomial functions, $g_{i}(x)$ are monomials, and $x_{i}$ are the decision variables.

Generalized Geometric Programming Form

Minimize $f_{0}(x)$

Subject to: $f_{i}(x)\leqslant 1$, $i$ = 1,...,m,

$g_{i}(x)=1$, $i$ = 1,...,p,

where $f_{i}(x)$ are generalized posynomial functions, $g_{i}(x)$ are monomials, and $x_{i}$ are the decision variables.

Since any posynomial is also a generalized posynomial, any geometric programming is also generalized geometric programming.

Generalized geometric programming can be converted to equivalent geometric programming by different mathematical transformations.

Numerical Examples

Transform a non-standard form GP to standard form GP

The non-standard form GP is as follows:

Minimize $f_{0}(x,y)=x/y$

Subject to: $x\leqslant 4$,

$x+2y\leqslant 1$,

$xy=1$,

$x>0$,

$y>0$

The equivalent standard form GP is as follows:

Minimize $f_{0}(x,y)=x^{2}y^{3}+3x+2xy$

Subject to: $x^{5}+2y^{6}+1\leqslant 1$,

$x+2y\leqslant 1$,

$xy=1$,

$x>0$,

$y>0$

Transform Non-convex Optimization Problems to Convex Optimization problem

The non-convex mixed integer non-linear programming (MINLP) is as follows:

Minimize $f_{0}(x_{1},x_{2},x_{3})=16(x_{1})^{2}(x_{2})^{2}+3(x_{2})^{3}(x_{3})^{4}$

Subject to: $x^{5}+2y^{6}+1\leqslant 1$,

$x+2y\leqslant 1$,

$xy=1$,

$x>0$,

$y>0$

The reformulation of the MINLP above, from non-convex optimization problem to convex optimization problem, is as follows:

Minimize $f_{0}(x_{1},x_{2},x_{3})=16(x_{1})^{2}(x_{2})^{2}+3(x_{2})^{3}(x_{3})^{4}$

Subject to: $x^{5}+2y^{6}+1\leqslant 1$,

$x+2y\leqslant 1$,

$xy=1$,

$x>0$,

$y>0$

Conclusion

In general, geometric programming is a simple but powerful family of non-linear optimization problems. Though geometric programming optimization problems are typically not convex optimization problems, they can be transformed to convex optimization problems by multiple convexification techniques. This makes the optimization problems more tractable. Because of this special property, geometric programming is one of the best ways to solve and analyze various large-scale applications.