Geometric programming

Authors: Wenjun Zhu, Sam Olsen (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

Let $x_{1}$ ... $x_{n}$ denote $n$ real positive variables,

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, $a_{i}$ ε R

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.

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
• $1+x$ and $2x^{7}$ are posynomials, since it is the maximum of two posynomials, $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.

Feasibility Analysis

For the generalized geometric programming problem to be feasible, the constants need to be mutually consistent. where:

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

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

Determining the feasibility needs to be found before optimization. If these conditions are not met, then it might be useful to find: $x*$, the closest point to feasibility. If that is the case, the following format is provided:

Minimize $s_{1}...s_{m}$

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

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

$f_{i}(x)\geqslant 1$, $i$ = 1,...,m

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: $1\leqslant {x}\leqslant 4$,

$x^{2}\leqslant {y^{2}}$,

$x/y^{3}=3$

The equivalent standard form GP is as follows:

Minimize $f_{0}(x,y)=x^{-1}y$

Subject to: $x^{-1}\leqslant 1$,

${(1/4)}x\leqslant 1$,

${x^{2}}{y^{-2}}\leqslant 1$,

${(1/3)}xy^{-3}=1$

Transform Non-convex Optimization Problems to Convex Optimization problem

The non-convex non-linear programming is as follows:

Minimize $f_{0}(x_{1},x_{2})={x_{1}}{x_{2}}$

Subject to: $({x_{1}}^{2}/{x_{2}}^{2})\leqslant {{x_{1}}^{0.6}}$,

$x_{1}\geqslant 0$,

$x_{2}\geqslant 0$

The reformulation process using exponential transformation, from non-convex optimization problem to convex optimization problem, is as follows:

Let $x_{1}=e^{u_{1}}$, $x_{2}=e^{u_{2}}$, then the objective function becomes:

$f_{0}(e^{u_{1}},e^{u_{2}})=e^{({u_{1}}+{u_{2}})}$

The first constraint of the problem becomes:

=> $e^{2({u_{1}}-{u_{2}})}\leqslant {e^{{0.6}u_{1}}}$

=> $2({u_{1}}-{u_{2}})\leqslant {0.6{u_{1}}}$

=> ${u_{1}}-{u_{2}}\leqslant {0.3{u_{1}}}$

The second constraint of the problem becomes:

=> $e^{u_{1}}\geqslant 0$

${u_{1}}$ is unbounded.

The third constraint of the problem becomes:

=> $e^{u_{2}}\geqslant 0$

${u_{2}}$ is unbounded.

Substitute the new reformulation into the original problem, the new problem becomes:

Minimize $f_{0}(e^{u_{1}},e^{u_{2}})=e^{({u_{1}}+{u_{2}})}$

Subject to: ${u_{1}}-{u_{2}}\leqslant {0.3{u_{1}}}$,

${u_{1}}$, ${u_{2}}$ are unbounded.

This is a convex non-linear programming problem.

Applications

Power Control

Transmitter power control in communication system is one of the typical applications of geometric programming. The objective of the problem is to minimize the total power of the transmitters subject to transmitter power limits and the signal to interference and noise ratio (SINR) of many receiver/transmitter pairs. This application demonstrates that the GP formulation allows us to handle the more general case in which the receiver interference power is any posynomial function of the powers.

Optimal Doping Profile

Doping profile in semiconductor device engineering is another typical application of geometric programming. The objective of the problem is to choose the best doping profile (also called the acceptor impurity concentration) to obtain a transistor with favorable properties. There are many factors that affect the properties of a transistor. One of the critical measures of the favorable properties of a transistor is its base transit time, which determines how fast the transistor is. Therefore, the goal is to choose the doping profile to minimize the base transit time, subject to doping profile limits, doping gradient, and initial/final doping profile values.

FloorPlanning

The floor planning problem is a generalized geometric programming problem instead of a geometric programming problem. However, any generalized geometric programming problem can be mechanically transferred to any geometric programming problem. The objective of the problem is to minimize the "bounding box" area that can include all the required objects, subject to the area of the individual object and the aspect ratio of the individual object.

Digital Circuit

Digital Gate Sizing

The digital gate sizing problem is a generalized geometric programming problem instead of a geometric programming problem. However, any generalized geometric programming problem can be mechanically transferred to any geometric programming problem. The objective of the problem is to minimize the worst-case delay of the digital signal traveling along any path through the circuit, subject to limits on the total area and power. The problem can be demonstrated as follows: To the right there is a Digital Circuit with the critical path highlighted in red. Every IC component is given power, area, resistance, and capacitance values. Using the 3 different component types: AND, OR, NOT, the total power, total area, total resistance, and total capacitance are fond for each component type. The Minimum delay, is the summation of the multiplication for each components total resistance and capacitance, with relations to bounded area and power.

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. Because of convexification, geometric programming is used to solve and analyze various large-scale applications, and it is used to convert computationally intractable optimization problems to computationally tractable optimization problems.