Exponential transformation

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

Introduction

An exponential transformation is a simple algebraic transformation of a monomial function through variable substitution with an exponential variable. In computational optimization, exponential transformations are used for convexification of geometric programming constraints in nonconvex optimization problems.

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 simplification of binary variables through removal of the exponent. The transformation is verified to be convex if the Hessian, denoted by $H(x)$, is proven to be positive-definite.

By using exponential transformations, not only is the overall time to solve a Nonlinear Programming (NLP) or a Mixed Integer Nonlinear Programming (MINLP) problem reduced, but we can also simplify the solution space enough to utilize conventional NLP/MINLP solvers. Various real world optimization problems apply this transformation to simplify the solution space consisting of extensive quantities of constraints and variables.

Theory, Methodology, and Algorithmic Discussions

Theory

Exponential transformations are most commonly applied to geometric programs. A geometric program is a mathematical optimization problem where the objective function is a posynomial being minimized. Posynomial functions are defined as positive polynomials.

The standard form of a geometric program is represented by:

${\begin{aligned}\min &\quad f_{0}(x)\\s.t.&\quad f_{i}(x)\leq 1\quad i=1,....,m\\&\quad g_{i}(x)=1\quad i=1,....,p\end{aligned}}$

Where $f_{0}(x)$ is a posynomial function, $f_{i}(x)$ is a posynomial function and $g_{i}(x)$ is a monomial function.

To verify a geometric program is represented in its standard form, the following conditions must be true:

1. Objective function $f_{0}(x)$ is a posynomial.
2. Inequality constraints $f_{i}(x)$ must be posynomials less than or equal to 1.
3. Equality constraints $g_{i}(x)$ must be monomials equal to 1.

In this definition, monomials differ from the usual algebraic definition where the exponents must be nonnegative integers. For this application, exponents can be any positive number inclusive of fractions and negative exponents.

Methodology

Exponential transformation begins with a posynomial noncovex function as depicted below. A posynomial begins with $x_{1},...,x_{n}$ where $x_{n}$ are real non-negative variables.

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

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

A transformation is applied in which $x_{n}$ is replaced with the natural logarithm base exponential $e^{u_{n}}$. The transformed function after substitution is presented as:

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

Properties of the exponent can be used to further simplify the transformation above, resulting in the sum of the exponents with a natural logarithm base.

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

In order to prove the convexity of the final transformed function, the positive-definite test of the Hessian is used as defined in Optimization of Chemical Processes . The Hessian is defined as the following:

$H(x)=H=\nabla ^{2}f(x)={\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}}$

to test that

$Q(x)\geq 0$ where $Q(x)=x^{T}Hx$ for all $x\neq 0$.

Exponential Transformation in Computational Optimization

Exponential transformation can be used for convexification of any MINLP that meets the criteria for a geometric program. Using the exponential substitution detailed above, all continuous variables in the function are transformed while binary variables are not transformed. This transformation can also be applied to constraints to ensure convexification throughout the entire problem.

In a special case, binary exponential transformation can also be applied where binary variables are linearized. Binary exponential transformation can be done by using the following replacement: ${y^{n}}$ is substituted by $y$.

Additionally, 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. Note that the bounds of the problem are not altered through exponential transformation.

Numerical Example

To provide an example, we begin with a simple nonconvex problem:

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

Step 1: Convert the problem into standard form by reformulating radicals, fractions, etc. into exponents.

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

Step 2: Substitute all instances of $x_{n}$ with $e^{u_{n}}$.

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

Step 3: Simplify by applying exponent properties.

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

Example of Convexification in MINLP

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

${\begin{aligned}\min &\quad Z=5{x_{1}^{2}}{x_{2}^{8}}+2{x_{1}}+{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}\in \left\{0,1\right\}\quad y_{2}\in \left\{0,1\right\}\end{aligned}}$

Step 1: Apply the exponential transformation to continuous variables $x_{1}$ and $x_{2}$ by substituting $x_{1}=e^{u_{1}}$ and $x_{2}=e^{u_{2}}$.

${\begin{aligned}\min &\quad Z=5{e^{2{u_{1}}}}{e^{8{u_{2}}}}+2{e^{u_{1}}}{e^{2u_{2}}}+{e^{{3}{u_{2}}}}+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}\in \left\{0,1\right\}\quad y_{2}\in \left\{0,1\right\}\end{aligned}}$

Step 2: Simplify using the properties of exponents. (i.e. Combining the products of exponential terms as the sum of exponents with the same base)

${\begin{aligned}\min &\quad Z=5{e^{2{u_{1}}+{8{u_{2}}}}}+2{e^{u_{1}}}+{e^{{2u_{2}}+{3}{u_{2}}}}+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}\in \left\{0,1\right\}\quad y_{2}\in \left\{0,1\right\}\end{aligned}}$

Where $u_{1}$ is unbounded due to logarithmic of 0 being indefinite.

Step 3: Simplify binary variables by substituting ${y_{1}}^{2}$ with ${y_{1}}$ and ${y_{2}}^{2}$ with ${y_{2}}$.

${\begin{aligned}\min &\quad Z=5{e^{2{u_{1}}}}{e^{8{u_{2}}}}+2{e^{u_{1}}}{e^{2u_{2}}}+{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}\in \left\{0,1\right\}\quad y_{2}\in \left\{0,1\right\}\end{aligned}}$

Convexity Check

For the example above, the Hessian of the transformed matrix is as follows:

${\begin{bmatrix}{\partial ^{2}Z(u) \over \partial u_{1}^{2}}&{\partial ^{2}Z(u) \over \partial u_{1}\partial u_{2}}\\{\partial ^{2}Z(u) \over \partial u_{2}\partial u_{1}}&{\partial ^{2}Z(u) \over \partial u_{2}^{2}}\\\end{bmatrix}}$

Step 1: Solve for each partial derivative.

${\begin{aligned}{\partial Z(u) \over \partial u_{1}}=10{e^{2{u_{1}}}}{e^{8{u_{2}}}}+2{e^{u_{1}}}{e^{2u_{2}}}\qquad &{\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^{3u_{2}}}\\{\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}}}\qquad &{\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^{3u_{2}}}\\{\partial ^{2}Z(u) \over \partial u_{1}\partial u_{2}}=80{e^{2{u_{1}}}}{e^{8{u_{2}}}}+4{e^{u_{1}}}{e^{2u_{2}}}\qquad &{\partial ^{2}Z(u) \over \partial u_{2}\partial u_{1}}=80{e^{2{u_{1}}}}{e^{8{u_{2}}}}+4{e^{u_{1}}}{e^{2u_{2}}}\end{aligned}}$

Step 2: Construct Hessian matrix, $H(x)$, from second derivatives.

$H(x)={\begin{bmatrix}20{e^{2{u_{1}}}}{e^{8{u_{2}}}}+2{e^{u_{1}}}{e^{2u_{2}}}\qquad &80{e^{2{u_{1}}}}{e^{8{u_{2}}}}+4{e^{u_{1}}}{e^{2u_{2}}}\\80{e^{2{u_{1}}}}{e^{8{u_{2}}}}+4{e^{u_{1}}}{e^{2u_{2}}}\qquad &320{e^{2{u_{1}}}}{e^{8{u_{2}}}}+8{e^{u_{1}}}{e^{2u_{2}}}+9{e^{3u_{2}}}\end{bmatrix}}$

Because the second derivatives consist only of exponential equations and the exponential expression $e^{x}$ is convex everywhere, the H(x) is proven to be 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 prerequisite conditions described are satisfied. Geometric programming transformation can be further explored through logarithmic transformation to address convexification.