Exponential transformation

Author: Daphne Duvivier, Daniela Gil, Jacqueline Jackson, Sinclaire Mills, Vanessa Nobre (SYSEN 5800, Fall 2021)

Introduction

Exponential transformations are simple algebraic transformations of monomial functions through a variable substitution with an exponential variable. In computational optimization, exponential transformations are used for convexification of geometric programming constraints nonconvex optimization problems. The constraints for geometric programs are posynomial functions which are characterized by being positive polynomials.

Exponential transformation creates a convex function without changing the decision space of the problem. This is done through a simple substitution of continuous variables with a natural exponent and simplifying binary variables by removing the exponents due to the binary nature of the variable. The transformation can then be verified using the Hessian positive definite test to confirm that it is now a convex function.

Using exponential transformations, the overall time to solve a Nonlinear Programming (NLP) or a Mixed Integer Nonlinear Programming (MINLP) problem is reduced and simplifies the solution space enough to utilize conventional NLP/MINLP solvers. This can be seen used in various real world optimization problem applications to simplify the solution space as real world applications have extensive quantities of constraints and variables.

Theory & Methodology

Exponential transformation is an algebraic transformation applied to geometric programs.

In non linear programming an exponential transformation are used for geometric programs which are composed of posynomial functions in the optimization function and constraints.

A posynomial function which can also be referred to as a posynomial is defined as a positive polynomial function.

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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) = \sum_{k=1}^N c_k{x_1}^{a_{1k}}{x_2}^{a_{2k}}....{x_n}^{a_{nk}} }

where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_k \geq 0 } and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_n \geq0 }

A transformation of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_n = e^u_i } is applied

The transformed function is presented as:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(u) = \sum_{k=1}^N c_k{{e}^{{u_1}{a_{1k}}}{e}^{{u_2}{a_{2k}}}....{e}^{{u_n}{a_{nk}}}} }

Exponential transformation can be applied to geometric programs. A geometric program is a mathematical optimization problem where the objective function is a posynomial which is minimized. For Geometric programs in standard form the objective must be a posynomial and the constraints must be posynomials Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \leq 1 } or monomials equal to 1.

Geometric Programs in standard form is represented by:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \min & \quad f_0(x) \\ s.t. & \quad f_i(x) \leq 1 & i = 1,....,m \\ & \quad g_i(x) = 1 & i = 1,....,p \end{align}}

Where f_0 is a posynomial function, f_i(x) is a posynomial function and g_i(x) is a monomial function.

Exponential Transformation in Computational Optimization

Exponential transformation can be used for convexification of any Geometric MINLP that meets the criteria for a geometric program. In a geometric program the approach to solving efficiently is taken by transforming the optimization problem into a convex nonlinear problem. This is done by turning the problem into a nonlinear convex optimization problem through exponential transformation. Using the exponential substitution detailed above, all continuous variables in the function are transformed while binary variables are not transformed. Through exponential transformation the constraints of a geometric program are also convex.

In a special case binary exponential transformation can also be applied where binary variables are linearized since their possible allocation is 0 or 1. Binary exponential transformation can be done by using the following replacement Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {y^n} is substituted by y }

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. this creates a convex under estimator approach to the problem.

Also as presented by Li and Biswal, the bounds of the problem are not altered through exponential transformation.

Numerical Example

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {\frac{x_1^3}{x_2^4}} + {x_1^2} + {\sqrt[3]{x_2^2}} \leq 4}

Reformulating to exponents

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {x_1^3}*{x_2^{-4}} + {x_1^2} + {x_2^{\frac{2}{3}}} \leq 4 }

Substituting Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1 = e^{u_1}, x_2 = e^{u_2} }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {e^{{3}{u_1}}}*{e^{{-4}{u_2}}} + {e^{{2}{u_1}}} + {{e^{u_2}}^{\frac{2}{3}}} \leq 4 }

Simplifying by exponent properties

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {e^{3{u_1} - 4{u_2}}} + {e^{{2}{u_1}}} + {{e^{{\frac{2}{3}}{u_2}}}} \leq 4 }

Example of Convexification Application in MINLP

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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \min & \quad Z = 5{x_1^2}{x_2^8} + 2{x_1} + \frac{x_2^3} + 5{y_1} + 2 {y_2^2} \\ s.t. & \quad {x_1} \leq 7{x_2^{0.2}} \\ & \quad 2{x_1^3} - y_1^2 \leq 1 \\ & \quad x_1 \geq 0 \\ & \quad x_2 \leq 4 \\ & \quad y_1 = 0,1 \quad y_2 = 0,1 \end{align} }

Using the exponential transformation to continuous variables Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1, x_2 } by substituting Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1 = e^{u_1}} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_2 = e^{u_2} } described the problem becomes the following:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \min & \quad Z = 5{e^{2{u_1}}}{e^{8{u_2}}} + 2{e^{u_1}}{e^{2u_2}} + \frac{e^{{u_2}{3}}} + 5{y_1} + 2 {y_2^2} \\ s.t. & \quad {e^{u_1}} \leq 7{e^{0.2{u_2}}} \\ & \quad 2{e^{3{u_1}}} - y_1^2 \leq 1 \\ & \quad e^{u_1} \geq 0 \\ & \quad e^{u_2} \leq 4 \\ & \quad y_1 = 0,1 \quad y_2 = 0,1 \end{align}}

With additional logarithmic simplification through properties of natural logarithm:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \min & \quad Z = 5{e^{2{u_1}}}{e^{8{u_2}}} + 2{e^{u_1}}{e^{2u_2}} + \frac{e^{{u_2}{3}}} + 5{y_1} + 2 {y_2^2} \\ s.t. & \quad u_1 \leq \ln 7 + 0.2{u_2} \\ & \quad 2{e^{3{u_1}}} - y_1^2 \leq 1 \\ & \quad {u_2} \leq \ln 4 \\ & \quad y_1 = 0,1 \quad y_2 = 0,1 \end{align}}

Where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u_1 } is unbounded due to logarithmic of 0 being indefinite.

Additionally simplifying further for binary variables by substituting Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {y_1}^2 with {y_1} and {y_2}^2 with {y_2} } since Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {y_2} } is either 0 or 1 and any exponents on the variable will not change the solution space:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \min & \quad Z = 5{e^{2{u_1}}}{e^{8{u_2}}} + 2{e^{u_1}}{e^{2u_2}} + \frac{e^{{u_2}{3}}} + 5{y_1} + 2 {y_2} \\ s.t. & \quad u_1 \leq \ln 7 + 0.2{u_2} \\ & \quad 2{e^{3{u_1}}} - y_1 \leq 1 \\ & \quad {u_2} \leq \ln 4 \\ & \quad y_1 = 0,1 \quad y_2 = 0,1 \end{align}}

The transformed objective function can be shown to be convex through the positive-definite test of the Hessian. In order to prove the convexity of the transformed functions, the positive definite test of Hessian is used as defined in Optimization of Chemical Processes . This tests the Hessian defined as:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(x) = H = \nabla^2f(x)}

to test that

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q(x)\geq 0 }

where

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q(x) = x^THx }

for all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \neq 0 }

For the example above, the Hessian is as follows :

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{bmatrix} {\partial^2 f \over \partial {x_1^2}} & {\partial^2 f \over \partial x_1\partial x_2} \\ {\partial^2 f \over \partial x_2\partial x_1} & {\partial^2 f \over \partial {x_2^2}} \end{bmatrix} }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} {\partial Z(u) \over \partial u_1} & = 10{e^{2{u_1}}}{e^{8{u_2}}} + 2{e^{u_1}}{e^{2u_2}} & \quad{\partial^2 Z(u) \over \partial u_1^2} = 20{e^{2{u_1}}}{e^{8{u_2}}} + 2{e^{u_1}}{e^{2u_2}} \\ {\partial Z(u) \over \partial u_2} & = 40{e^{2{u_1}}}{e^{8{u_2}}} + 4{e^{u_1}}{e^{2u_2}} + 3{e^{{3}{u_2}}} & \quad{\partial^2 Z(u) \over \partial u_2^2} = 320{e^{2{u_1}}}{e^{8{u_2}}} + 8{e^{u_1}}{e^{2u_2}} + 9{e^{{3}{u_2}}} \\ \end{align}}

In the example above, the Hessian is defined as:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{bmatrix} X & X \\ X & Y \end{bmatrix} }

Therefore, H(x) is positive-definite and strictly convex.

Applications

Currently, various applications of exponential transformation can be seen in published journal articles and industry practices. Many of these applications use exponential transformation to convexify their problem space. Due to the closeness with logarithmic transformation, usually a combination of the approaches is used in practical solutions.

Mechanical Engineering Applications

In the paper “Global optimization of heat exchanger network synthesis problems with and without the isothermal mixing assumption” a global optimization approach is explored for the synthesis of heat exchanger networks. As seen in eq(34) and (35) of the work by Björk and Westerlund, they employ an exponential transformation to convexify their optimization problem to employ a global optimization approach.

Electrical Engineering Application:

Applications for VLSI circuit performance optimization. In this application a special geometric program defined as unary geometric programs is presented. The unary geometric program is a posynomial as defined in the Theory & Methodology section. The unary geometric program is derived through a greedy algorithm which implements a logarithmic transformation within lemma 5. While this is not a specific exponential transformation example logarithmic transformations are within the same family and can also be used to convexify geometric programs.

Machining Economics:

Applications in economics can be seen through geometric programming approaches. Examples and applications include to analyze the life of cutting tools in machining. In this approach they use exponential transformations to convexify the problem.

Overall exponential transformations can be applied anywhere a geometric programming approach is taken to optimize the solution space. Some Applications may perform a logarithmic transformation instead of an exponential transformation.

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 within Theory & Methodology are satisfied. Geometric Programming transformation can be further explored through logarithmic transformation to address convexification.