Exponential transformation: Difference between revisions

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search
No edit summary
No edit summary
Line 4: Line 4:
== Introduction ==
== 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 <ref> 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 </ref>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.
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 <ref> 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 </ref> 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 ==
== Theory & Methodology ==
Line 46: Line 46:




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. <ref> 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 </ref>
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. <ref> 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 </ref> <ref> 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 </ref>


== Example of Convexification application in MINLP ==
== Example of Convexification application in MINLP ==
Line 52: Line 52:




Proof of convexity with positive definite test of Hessian


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>:


https://www.princeton.edu/~chiangm/gp.pdf
Proof of convexity of  with positive definite test of Hessian


pROOF THAT CHANGING IT DOESNT CHANGE THE BOUNDS OF THE PROBLEM https://link.springer.com/content/pdf/10.1023/A:1021708412776.pdf


== Current Applications ==
== Current Applications ==

Revision as of 16:28, 27 November 2021

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 [1] 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 [2] :

where and

A transformation of is applied [3]

The transformed function is presented as:


Numerical Example

Reformulating to exponents

Substituting

Simplifying by exponent properties

Further linearization with natural logarithm


Applications

Exponential transformation can be used for convexification of any Geometric NLP or 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. [4] [5]

Example of Convexification application in MINLP

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

Proof of convexity of with positive definite test of Hessian


Current Applications

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 NLP/MINLP and obtain a global solution to the problem. However, this approach can only be applied given certain parameters are met. 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