Exponential transformation

Author: Daphne Duvivier (dld237), Daniela Gil (dsg254), Jacqueline Jackson (jkj49), Sinclaire Mills (sm2795), Vanessa Nobre (vmn28) Fall 2021

Introduction

Exponential transformations are simple algebraic transformation of monomial functions through a variable substitution with an exponential variable. They are used for convexification of geometric programming constraints (posynominal) nonconvex optimization problems. This transformation creates a convex function without changing the decision space of the problem and reducing the time to solve an NLP/MINLP, in some cases linearization can be achieved through exponential transformation as seen in the example below.

Theory & Methodology

Exponential transformation begins with a posynominal (Positive and Polynomial) noncovex function of the form  :

$f(x)=\sum _{k=1}^{N}c_{k}{x_{1}}^{a_{1}k}{x_{2}}^{a_{2}k}....{x_{n}}^{a_{n}k}$

where $c_{k}\geq 0$ and $x_{n}\geq 0$

A transformation of $x_{n}=e_{i}^{u}$ is applied

The transformed function is presented as:

$f(u)=\sum _{k=1}^{N}c_{k}{{e}^{{u_{1}}{a_{1}k}}{e}^{{u_{2}}{a_{2}k}}....{e}^{{u_{n}}{a_{n}k}}}$

Numerical Example

${\frac {x_{1}^{3}}{x_{2}^{4}}}+{x_{1}^{2}}+{\sqrt[{3}]{x_{2}^{2}}}\leq 4$

Reformulating to exponents

${x_{1}^{3}}*{x_{2}^{-4}}+{x_{1}^{2}}+{x_{2}^{\frac {2}{3}}}\leq 4$

Substituting $x_{1}=e^{u_{1}},x_{2}=e^{u_{2}}$

${{e^{u_{1}}}^{3}}*{{e^{u_{2}}}^{-4}}+{{e^{u_{1}}}^{2}}+{{e^{u_{2}}}^{\frac {2}{3}}}\leq 4$

Simplifying by exponent properties

${e^{3{u_{1}}-4{u_{2}}}}+{e^{{2}{u_{1}}}}+{e^{{\frac {2}{3}}{u_{2}}}}\leq 4$

Further linearization with natural logarithm

$({{3}{u_{1}}-{4}{u_{2}}})+{2}{u_{1}}+{\frac {2}{3}}{u_{2}}\leq \ln 4$

Applications

Exponential transformation can be used for convexification of any Geometric MINLP that meet the criteria of equation (1). This is done by turning the problem into a nonlinear convex optimization problem through exponential transformation.

Additionally as presented in Theorem 1 and accompanying proof in "Global optimization of signomial geometric programming using linear relaxation" by P. Shen, K. Zhang, given that a function is being minimized it shows that after transformation all points on the transformed function are feasible in the original function and all objective values in the transformed function are the same or less than the original function. Also presented by Li and Biswal the bounds of the problem are not altered through exponential transformation.

Example of Convexification application in MINLP

The following MINLP problem can take a Covexification approach using exponential transformation:

min Failed to parse (unknown function "\math"): {\displaystyle Z = {5{x_1^2}{x_2^8} + 2{x1}{x_3^2} + {\frac{x_2^3}{x_3}] + 5{y_1} + 2 {y_2^2} <\math> The transformed objective function can be show to be convex through the positive-definite test of the Hessian, for the example above the Hessian is as follows <ref> Chiang, Mung. (2005). Geometric Programming for Communication Systems. 10.1561/9781933019574; https://www.princeton.edu/~chiangm/gp.pdf </ref>: Proof of convexity of with positive definite test of Hessian <math> \begin{bmatrix} X & X \\ X & Y \end{bmatrix} }

Current Applications

Currently various applications of exponential transformation can be seen in published journal articles and industry practices, due to the closeness with logarithmic transformation usually a combination of the approaches are used in practical solutions.

Electrical Engineering Application: http://home.eng.iastate.edu/~cnchu/pubs/j08.pdf

Quadratic Geometric Programming Ecconomics: https://link.springer.com/content/pdf/10.1007/BF02591746.pdf

Conclusion

Exponential transformation is a useful method to convexify Geometric MINLP and obtain a global solution to the problem. Exponential transformation does not alter the bounds of the problem and allows for a convex objective function and constraints given that the conditions described under the Theory and methodology section are satisfied. Geometric Programming transformation can be further explored through logarithmic transformation to address convexification.