]> On the treatment of jump discontinuities in nonlinear programs

On the treatment of jump discontinuities in nonlinear programs

by Stephan K.H. Seidl

Version 3, Thu, 16 Jul 2015 12:08:56 +0200


Abstract

The present work shows a technique for getting rid of jump discontinuities in nonlinear programs. Functions in nonlinear programs that contain jump discontinuities are firstly expressed with the help of the step() function. The resulting step() function values are further replaced by linear and, if such a function consists of more than one jump discontinuity, also quadratic expressions constructed from sign() functions. The sign() function values are then provided via additional variables defined by additional equalities that contain abs() functions, which in turn are finally made available through linear equalities with nonnegative auxiliary variables that are aligned by means of special penalties. At least the formulation of the latter part is also known under the name Mathematical Programs with Equilibrium Constraints (MPEC). The presented technique at all works as long as the prerequisites to replace the abs() functions are given. The elimination of one jump discontinuity here requires three additional variables, two additional equality constraints where one of them is linear and the other quadratic, six additional linear inequality constraints, and one additional quadratic penalty. The technique has successfully been applied to solve TP 87 in [7].


To do

It has still to be checked that the stuff that is called Mathematical Programs with Equilibrium Constraints in [2] is the same as the one with the corresponding name in [4], or, that the regarding material in [2] at least belongs to a subtopic [4] deals with. Studying [4] should also give a deeper insight to clarify whether the presented approach here works always or only under certain conditions that are not obvious upon ordinary considerations. In short, I have to read the book someday.

For the representation, this page uses MathJax, a set of JavaScript scripts to process the mathematics. MathJax is configured here such that all of us see the formulæ typesetting based on the same fonts. Good. On the other side, it seems that currently only some of us are able to print the present document in an acceptable manner, except with the X Window System window dumping utility, xwd, of course. Those who run a browser that says about itself Mozilla/5.0 (X11; Linux; rv:31.1.1) Gecko/20140101 Firefox/31.1.1 Iceweasel/31.1.1 belong to the lucky ones. That browser generates a perfect PDF file from the text here.


Change log

For the change log click Changelog.
Comments, bug reports, and better ideas are welcome.


Acknowledgements

I am grateful to John D. Hedengren, Provo UT, for providing MPEC related model files through the Internet, taken as the starting point for the present work.


References

[1] A. Griewank: On stable piecewise linearization and generalized algorithmic differentiation.
Optimization Methods & Software,
http://dx.doi.org/10.1080/10556788.2013.796683 (2013)
[2] J. D. Hedengren: APMonitor Documentation: MPEC Examples.
http://www.apmonitor.com/wiki/index.php/Apps/MpecExamples/
[3] W. Hock and K. Schittkowski: Test Examples for Nonlinear Programming Codes.
Vol 187 of Lecture Notes in Economics and Mathematical Systems (Springer 1981)
[4] Z.-Q. Luo, J.-S. Pang and D. Ralph: Mathematical Programs with Equilibrium Constraints.
(Cambridge University Press, 1996) ISBN 0-521-57290-8
[5] K. Schittkowski: Test Examples for Nonlinear Programming Codes:
All Problems from the Hock-Schittkowski-Collection.
http://www.ai7.uni-bayreuth.de/test_problem_coll.pdf (2009)
[6] K. Schittkowski: An Updated Set of 306 Test Problems for Nonlinear
Programming with Validated Optimal Solutions, User's Guide.
http://www.ai7.uni-bayreuth.de/test_problems.pdf and
http://www.ai7.uni-bayreuth.de/test_probs_src.zip, file PROB.FOR (2011)
[7] S. K. H. Seidl: Revised Hock & Schittkowski Models for Automatable Test Scenarios.
http://www.stfmc.de/fmc/rhs/x/tlf.html (2014)

Introduction