Exponential transformation: Difference between revisions

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search
No edit summary
m (Added min to Latex)
Line 1: Line 1:
Author: Daphne Duvivier, Daniela Gil, Jacqueline Jackson, Sinclaire Mills, Vanessa Nobre (SYSEN 5800, Fall 2021)
Author: Daphne Duvivier, Daniela Gil, Jacqueline Jackson, Sinclaire Mills, Vanessa Nobre (SYSEN 5800, Fall 2021)


== Introduction ==
== Introduction ==


Exponential transformations are simple algebraic transformation of monomial functions through a variable substitution with an exponential variable.  
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 (posynominal) nonconvex optimization problems.  
In computational optimization exponential transformations are used for convexification of geometric programming constraints (posynominal) nonconvex optimization problems.  
Line 12: Line 10:


Through the use of exponential transformation the time to solve an Non-linear program (NLP) or a Mixed integer non-linear program (MINLP) is reduced by allowing the use of a global solve. Many current applications use exponential transformation to simplify solution spaces and allow for solving with normal NLP/MINLP solvers.  
Through the use of exponential transformation the time to solve an Non-linear program (NLP) or a Mixed integer non-linear program (MINLP) is reduced by allowing the use of a global solve. Many current applications use exponential transformation to simplify solution spaces and allow for solving with normal NLP/MINLP solvers.  


== Theory & Methodology ==
== Theory & Methodology ==
Line 23: Line 19:
Geometric Programs take the form of:
Geometric Programs take the form of:


<math> min f_0(x) </math>
<math> min\quad f_0(x)</math>
<math> s.t. f_i(x) \leq 1  i = 1,....,m </math>
<math> s.t.\quad f_i(x) \leq 1  i = 1,....,m </math>
<math> s.t. g_i(x) = 1  i = 1,....,p </math>
<math> s.t.\quad g_i(x) = 1  i = 1,....,p </math>


convexification of a non-inferior frontier - based on having a differentiable objective function  https://link.springer.com/content/pdf/10.1023/A:1021708412776.pdf  
convexification of a non-inferior frontier - based on having a differentiable objective function  https://link.springer.com/content/pdf/10.1023/A:1021708412776.pdf  
Line 70: Line 66:
The following MINLP problem can take a Covexification approach using exponential transformation:
The following MINLP problem can take a Covexification approach using exponential transformation:


min <math> Z = 5{x_1^2}{x_2^8} + 2{x_1} + \frac{x_2^3} + 5{y_1} + 2 {y_2^2} </math>
<math>min\quad Z = 5{x_1^2}{x_2^8} + 2{x_1} + \frac{x_2^3} + 5{y_1} + 2 {y_2^2} </math>


s.t.  
s.t.  
Line 86: Line 82:
Using the exponential transformation to continuous variables <math>x_1, x_2, x_3 </math>  by substituting <math> x_1 = e^{u_1} and x_2 = e^{u_2} </math> described the problem becomes the following:
Using the exponential transformation to continuous variables <math>x_1, x_2, x_3 </math>  by substituting <math> x_1 = e^{u_1} and x_2 = e^{u_2} </math> described the problem becomes the following:


min <math> 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} </math>
<math>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} </math>


s.t
s.t
Line 102: Line 98:
With additional logarithmic simplification through properties of natural logarithm:
With additional logarithmic simplification through properties of natural logarithm:


min <math> 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} </math>
<math>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} </math>


s.t
s.t
Line 142: Line 138:




In the example above the hessian is defined as:
In the example above, the Hessian is defined as:


<math>  
<math>  
Line 165: Line 161:


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


==Conclusion==
==Conclusion==

Revision as of 15:55, 13 December 2021

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 (posynominal) nonconvex optimization problems.

Exponential transformation creates a convex function without changing the decision space of the problem. [1] The transformation can then be verified using the Hessian positive definite test to confirm that it is now a convex function.

Through the use of exponential transformation the time to solve an Non-linear program (NLP) or a Mixed integer non-linear program (MINLP) is reduced by allowing the use of a global solve. Many current applications use exponential transformation to simplify solution spaces and allow for solving with normal NLP/MINLP solvers.

Theory & Methodology

Exponential transformation can be applied to geometric programs

A geometric program is a mathematical optimization problem

Geometric Programs take the form of:

convexification of a non-inferior frontier - based on having a differentiable objective function https://link.springer.com/content/pdf/10.1023/A:1021708412776.pdf

this would apply to any polynomial. A posynomial is defined as define polynomials:

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

where and

A transformation of is applied [3]

The transformed function is presented as:


Exponential transformation in Computational Optimization

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. Using the exponential substitution detailed above all continuous variables in the function are transformed while binary variables are not transformed.

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. [4] Also presented by Li and Biswal the bounds of the problem are not altered through exponential transformation. [5]


Simple Numerical Example

Reformulating to exponents

Substituting

Simplifying by exponent properties

Example of Convexification application in MINLP

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

s.t.

Using the exponential transformation to continuous variables by substituting described the problem becomes the following:

s.t

With additional logarithmic simplification through properties of natural logarithm:

s.t

Where is unbounded due to logarithmic of 0 being indefinite.

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 [6]:

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" [7] can be used. This tests the Hessian defined as:

to test that

where

for all

for functions the Hessian is defined as:


In the example above, the Hessian is defined as:

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, due to the closeness with logarithmic transformation usually a combination of the approaches are used in practical solutions.

Global optimization of heat exchanger network synthesis problems with and without the isothermal mixing assumption:

  • 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. [8]


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


Quadratic Geometric Programming Economics: 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. (Add jump metric) Geometric Programming transformation can be further explored through logarithmic transformation to address convexification.

References

  1. Li, D., Biswal, M.P. Exponential Transformation in Convexifying a Noninferior Frontier and Exponential Generating Method. Journal of Optimization Theory and Applications 99, 183–199 (1998). https://doi.org/10.1023/A:1021708412776
  2. Boyd, S., Kim, SJ., Vandenberghe, L. et al. A tutorial on geometric programming. Optim Eng 8, 67 (2007). https://doi.org/10.1007/s11081-007-9001-7
  3. Grossmann, I.E. Review of Nonlinear Mixed-Integer and Disjunctive Programming Techniques. Optimization and Engineering 3, 227–252 (2002). https://doi.org/10.1023/A:1021039126272
  4. Boyd, S., Kim, SJ., Vandenberghe, L. et al. A tutorial on geometric programming. Optim Eng 8, 67 (2007). https://doi.org/10.1007/s11081-007-9001-7
  5. Li, D., Biswal, M.P. Exponential Transformation in Convexifying a Noninferior Frontier and Exponential Generating Method. Journal of Optimization Theory and Applications 99, 183–199 (1998). https://doi.org/10.1023/A:1021708412776
  6. Chiang, Mung. (2005). Geometric Programming for Communication Systems. 10.1561/9781933019574; https://www.princeton.edu/~chiangm/gp.pdf
  7. T.F. Edgar, D.M. Himmelblau, L.S. Lasdon, Optimization of Chemical Processes. McGraw-Hill, 2001.
  8. Template:Cite journal

Template:Reflist