In mathematical terms, optimization is the problem of minimizing (or maximizing) a prescribed function, the objective function, while obeying a number of equality and inequality constraints Depending on the area of definition of these functions, one can differentiate various classes of optimization problems, continuous problems, discrete problems, and mixed-integer problems.
The full version of the abstract is here.
M. Kieffer, M. C. Markót, H. Schichl, and E. Walter,
Verified global optimization for estimating the parameters of nonlinear models,
Chapter 7 in
Modeling, Design, and Simulation of Systems with Uncertainties,
Volume 3 of the Springer Series Mathematical Engineering
(Rauh, Andreas; Auer, Ekaterina (Eds.)), 2011.
pdf file (290K),
Nonlinear parameter estimation is usually achieved via the minimization
of some possibly non-convex cost function. Interval analysis provides tools for the
guaranteed characterization of the set of all global minimizers of such a cost function
when a closed-form expression for the output of the model is available or when
this output is obtained via the numerical solution of a set of ordinary differential
equations. However, cost functions involved in parameter estimation are usually
challenging for interval techniques, if only because of multi-occurrences of the parameters
in the formal expression of the cost. This paper addresses parameter estimation
via the verified global optimization of quadratic cost functions. It introduces
tools instrumental for the minimization of generic cost functions. When a closedform
expression of the output of the parametric model is available, significant improvements
may be obtained by a new box exclusion test and by careful manipulations
of the quadratic cost function. When the model is described by ODEs, some of
the techniques available in the previous case may still be employed, provided that
sensitivity of the model output with respect to the parameters are available.
Vu Xuan-Ha, H. Schichl, and D. Sam-Haroud,
Interval Propagation and Search on Directed Acyclic Graphs for
Numerical Constraint Solving,
Journal of Global Optimization, 45 (4), 499-531 (2009).
pdf file (725K),
The fundamentals of interval analysis on directed acyclic graphs (DAGs) for global
optimization and constraint propagation have recently been proposed in Schichl and
Neumaier (J. Global Optim. 33, 541?562, 2005). For representing numerical problems,
the authors use DAGs whose nodes are subexpressions and whose directed edges are
computational flows. Compared to tree-based representations [Benhamou et al.
Proceedings of the International Conference on Logic Programming (ICLP?99), pp. 230-244.
Las Cruces, USA (1999)], DAGs offer the essential advantage of more accurately handling
the influence of subexpressions shared by several constraints on the overall system during
propagation. In this paper we show how interval constraint propagation and search on
DAGs can be made practical and efficient by: (1) flexibly choosing the nodes on which
propagations must be performed, and (2) working with partial subgraphs of the initial
DAG rather than with the entire graph. We propose a new interval constraint propagation
technique which exploits the influence of subexpressions on all the constraints together
rather than on individual constraints. We then show how the new propagation technique
can be integrated into branch-and-prune search to solve numerical constraint satisfaction
problems. This algorithm is able to outperform its obvious contenders, as shown by the
experiments.
H. Schichl and A. Neumaier,
Transposition theorems and qualification-free optimality conditions,
SIAM J. Optimization, 17, 1035-1055 (2006).
ps.gz file (166K),
pdf file (197K)
downloading/printing problems?
New theorems of the alternative for polynomial constraints (based on
the Positivstellensatz from real algebraic geometry) and for linear
constraints (generalizing the transposition theorems of Motzkin and
Tucker) are proved.
Based on these, two Karush-John optimality conditions -- holding
without any constraint qualification -- are proved for single- or
multi-objective constrained optimization problems. The first condition
applies to polynomial optimization problems only, and gives for the
first time necessary and sufficient global optimality conditions for
polynomial problems. The second condition applies to smooth
local optimization problems and strengthens known local conditions.
If some linear or concave constraints are present, the new version
reduces the number of constraints for which a constraint qualification
is needed to get the Kuhn-Tucker conditions.
M. Kunzinger, H. Schichl, R. Steinbauer, and J. A. Vickers,
Global Gronwall Estimates for Integral Curves on Riemannian Manifolds,
Rev. Mat. Complut. 19/1 (2006), 133-137,
ps.gz file (167K),
pdf file (152K)
downloading/printing problems?
We prove several Gronwall-type estimates for the distance of
integral curves of smooth vector fields on a Riemannian manifold.
X.-H. Vu, H. Schichl and D. Sam-Haroud,
Using Directed Acyclic Graphs to Coordinate Propagation and Search for Numerical Constraint Satisfaction Problems,
In Proceedings of the 16th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2004), pages 72-81, Florida, USA, November 2004.
pdf file (527K)
ps.gz file (566K)
downloading/printing problems?
Given the fundamentals of interval analysis on DAGs for global optimization
and constraint propagation, we show in this paper how constraint propagation
on DAGs can be made efficient and practical by:
(i) working on partial DAG representations; and
(ii) enabling the flexible choice of the interval inclusion functions during
propagation. We then propose a new simple algorithm which coordinates
constraint propagation and exhaustive search for solving numerical constraint
satisfaction problems. The experiments carried out on different problems
show that the new approach outperforms previously available propagation
techniques by an order of magnitude or more in speed, while being roughly
the same quality w.r.t. enclosure properties.
H. Schichl and A. Neumaier,
Exclusion regions for systems of equations,
SIAM J. Numer. Anal. 42 (2004), 383--408.
pdf file (826K)
downloading/printing problems?
Branch and bound methods for finding all zeros of a nonlinear
system of equations in a box frequently have the difficulty
that subboxes containing no solution cannot be easily eliminated
if there is a nearby zero outside the box. This has the effect
that near each zero, many small boxes are created by repeated
splitting, whose processing may dominate the total work spent
on the global search.
This paper discusses the reasons for the occurrence of this so-called
cluster effect, and how to reduce the cluster effect by defining
exclusion regions around each zero found, that are guaranteed
to contain no other zero and hence can safely be discarded.
Such exclusion regions are traditionally constructed using
uniqueness tests based on the Krawczyk operator or the Kantorovich
theorem. These results are reviewed; moreover, refinements are
proved that significantly enlarge the size of the exclusion region.
Existence and uniqueness tests are also given.
H. Schichl,
Global Optimization in the COCONUT project,
in Proceedings of the Dagstuhl Seminar "Numerical Software
with Result Verification", Springer Lecture Notes in Computer Science
2991, Springer, Berlin, 2004.
ps.gz file (909K),
pdf file (381K)
downloading/printing problems?
In this article, a solver platform for global optimization is
presented, as it is developed in the COCONUT project. After a
short introduction, a short description is given of the basic
algorithmic concept and of all relevant components, the strategy
engine, inferenence engines, and the remaining modules. A compact
description of the search graph and its nodes and of the internal
model representation using directed acyclic graphs (DAGs) completes
the presentation.
H. Schichl,
Models and the History of Modeling,
Chapter 2, pp. 25-36 in: Modeling Languages in Mathematical Optimization
(J. Kallrath, ed.),
Kluwer, Boston 2004.
ps.gz file (213K),
pdf file (207K),
downloading/printing problems?
After a very fast tour through 30,000 years of modeling history,
I will describe the basic ingredients to models in general, and to
mathematical models in particular.
H. Schichl,
Theoretical Concepts and Design of Modeling Languages,
Chapter 4, pp. 45-62 in: Modeling Languages in Mathematical Optimization
(J. Kallrath, ed.),
Kluwer, Boston 2004.
ps.gz file (222K),
pdf file (222K),
downloading/printing problems?
Here, I will present the basic design features of
modeling languages, turning our attention to algebraic modeling
languages. Later I will introduce an important class of
optimization problems --- global optimization, and
illustrate the difficulties in constructing models for such
problems.
H. Schichl and A. Neumaier,
The NOP-2 Modeling Language,
Chapter 15, pp. 279-292 in: Modeling Languages in Mathematical Optimization
(J. Kallrath, ed.),
Kluwer, Boston 2004.
ps.gz file (192K),
pdf file (174K),
downloading/printing problems?
We present a short overview over
the modeling language NOP-2 for specifying
general optimization problems, including constrained local or global
nonlinear programs and constrained single and multistage stochastic
programs. The proposed language is specifically designed to
represent the internal (separable and repetitive) structure of the
problem.
H. Schichl, A. Neumaier and S. Dallwig,
The NOP-2 modeling language,
Ann. Oper. Research 104 (2001), 281-312.
dvi.gz file (32K),
ps.gz file (97K),
pdf file (179K),
downloading/printing problems?
An enhanced version NOP-2 of the NOP language
for specifying global optimization problems is described.
Because of its additional features,
NOP-2 is comparable to other modeling languages like AMPL and GAMS,
and allows the user to define a wide range of problems arising in real
life applications such as global constrained (and even stochastic)
optimization programs.
NOP-2 permits named variables, parameters, indexing, loops, relational
operators, extensive set operations, matrices and tensors, and
parameter arithmetic.
The main advantage that makes NOP-2 look and feel considerably
different from other modeling languages is the display of the internal
analytic structure of the problem. It is fully flexible for interfacing
with solvers requiring special features such as automatic
differentiation or interval arithmetic.
A.Cap and H. Schichl,
Parabolic Geometries and Canonical Cartan Connections,
Hokkaido Math. J.,
29, 3 (2000), 453-505
ps.gz file (47K),
pdf file (74K),
downloading/printing problems?
Also available as ESI preprint 450.
Let $G$ be a (real or complex) semisimple Lie group, whose
Lie algebra $\mathfrak{g}$ is endowed with a so called $|k|$--grading,
i.e. a grading of the form $\mathfrak{g}=\mathfrak{g}_{-k}\oplus\dots\oplus
\mathfrak{g}_k$, such that no simple factor of $G$ is of type $A_1$. Let $P$
be the subgroup corresponding to the subalgebra $\mathfrak{p}=
\mathfrak{g}_0\oplus\dots\oplus\mathfrak{g}_k$. The aim of this paper is to
clarify the geometrical meaning of Cartan connections corresponding to the pair
$(G,P)$ and to study basic properties of these geometric
structures.
Let $G_0$ be the (reductive) subgroup of $P$ corresponding to the
subalgebra $\mathfrak{g}_0$. A principal $P$--bundle $E$ over a smooth
manifold $M$ endowed with a (suitably normalized) Cartan connection
$\omega\in\Omega^1(E,\mathfrak{g})$ automatically gives rise to a filtration of
the tangent bundle $TM$ of $M$ and to a reduction to the structure
group $G_0$ of the associated graded vector bundle to the filtered
vector bundle $TM$. We prove that in almost all cases the principal
$P$ bundle together with the Cartan connection is already uniquely
determined by this underlying structure (which can be easily
understood geometrically), while in the remaining cases one has to
make an additional choice (which again can be easily interpreted
geometrically) to determine the bundle and the Cartan connection.
A. Neumaier, S. Dallwig, W. Huyer and H. Schichl,
New techniques for the construction of residue potentials for protein
folding,
pp. 212-224 in:
Algorithms for Macromolecular Modelling (P. Deuflhard et al., eds.),
Lecture Notes Comput. Sci. Eng. 4, Springer, Berlin 1999.
download
P.W. Michor and H. Schichl,
No slices on the space of generalized connections,
Acta Math. Univ. Comenianiae,
66, 2 (1997), 221-228
ps.gz file (68K),
downloading/printing problems?
Also available as ESI preprint 453.
On a fiber bundle without structure group the action of the
gauge group (the group of all fiber respecting diffeomorphisms)
on the space of (generalized) connections is shown to admit no slices.
S. Dallwig, A. Neumaier and H. Schichl,
GLOPT - A Program for Constrained Global Optimization,
pp. 19-36 in:
I. Bomze et al., eds.,
Developments in Global Optimization,
Kluwer, Dordrecht 1997.
ps.gz file (100K),
pdf file (183K),
downloading/printing problems?
GLOPT is a Fortran77 program for global minimization of a
block-separable objective function subject to bound constraints and
block-separable constraints. It finds a nearly globally optimal point
that is near a true local minimizer. Unless there are several local
minimizers that are nearly global, we thus find a good approximation
to the global minimizer.
GLOPT uses a branch and bound technique to split the problem recursively
into subproblems that are either eliminated or reduced in their size.
This is done by an extensive use of the block separable structure of
the optimization problem.
In this paper we discuss a new reduction technique for boxes and
new ways for generating feasible points of constrained nonlinear
programs. These are implemented as the first stage of our GLOPT project.
The current implementation of GLOPT uses neither derivatives nor
simultaneous information about several constraints. Numerical results
are already encouraging. Work on an extension using curvature
information and quadratic programming techniques is in progress.
A.Cap and H. Schichl,
Characteristic Classes for A-bundles,
"Proc. of the Winter School on Geometry and Physics, Srni
1994" Supp. ai Rend. Circolo. Math. Palermo, II,
39, (1996), 57-71
ps.gz file (102K),
pdf file (205K),
downloading/printing problems?
We consider locally trivial bundles over smooth manifolds, whose
fibers are finitely generated projective modules over a convenient
algebra $A$. For such a bundle $E\to X$ and a bounded reduced cyclic
cocycle $c$ on $A$ we construct a sequence $\chi_c^k(E)$ of de--Rham
cohomology classes on $X$, which are an analog of the classical Chern
character. We show that these classes depend only on the cohomology
class of $c$ and behave natural under various constructions.
A.Cap and H. Schichl and J. Vanzura,
On Twisted Tensor Products of Algebras,
Commun. Algebra,
23, 12 (1995), 4701-4735
ps.gz file (47K),
pdf file (74K),
downloading/printing problems?
Also available as ESI preprint 163.
The problems considered in this paper are motivated by
non-commutative geometry.
Starting from two unital algebras $A$ and $B$ over a commutative ring
$\mathbb{K}$ we describe all triples $(C,i_A,i_B)$, where $C$ is a unital
algebra and $i_A$ and $i_B$ are inclusions of $A$ and $B$ into $C$
such that the canonical linear map $(i_A,i_B):A\otimes B\to C$ is a
linear isomorphism. We discuss possibilities to construct
differential forms and modules over $C$ from differential forms and
modules over $A$ and $B$, and give a description of deformations of
such structures using cohomological methods.
A.Cap and P.W. Michor and H. Schichl,
A quantum group like structure on non commutative 2-tori,
Letters in Math. Phys.,
28, (1993), 251-255
ps.gz file (39K),
pdf file (89K),
downloading/printing problems?
Also available as ESI preprint 6.
In this paper we show that in the case of non commutative two tori
one gets in a natural way simple structures which have analogous
formal properties as Hopf algebra structures but with a deformed
multiplication on the tensor product.
H. Schichl,
VGTL (Vienna Graph Template Library) Version 1.0, Reference Manual,
Technical Report,
Appendix to "Upgraded State of the Art Techniques implemented as Modules",
Deliverable D13 of the COCONUT project (July 2003),
Version 1.1 (October 2003), 323 pages,
pdf file (3114K),
html,
downloading/printing problems?
This technical report contains the complete commented class reference
of the Vienna Graph Template Library.
H. Schichl,
VDBL (Vienna Database Library) Version 1.0, Reference Manual,
Technical Report,
Appendix to "Upgraded State of the Art Techniques implemented as Modules",
Deliverable D13 of the COCONUT project (July 2003), 163 pages,
pdf file (1565K),
html,
downloading/printing problems?
This technical report contains the complete commented class reference
of the Vienna Graph Template Library.
H. Schichl,
The COCONUT API Version 2.32, Reference Manual,
Technical Report,
[Version 2.13 (July 2003)],
Appendix to "Specification of new and improved representations",
Deliverable D5 v2 of the COCONUT project (November 2003), 510 pages,
pdf file (5981K),
html,
downloading/printing problems?
This technical report contains the complete class reference
of the COCONUT API.
C. Maheshwari, A. Neumaier, and H. Schichl,
Convexity and concavity detection,
Technical Report,
in "New Techniques as Modules", Deliverable D12 of the COCONUT project
(July 2003), pages 61-67,
ps file (422K),
downloading/printing problems?
This technical report contains the mathematical background of some techniques
for automatic convexity detection in expressions.
H. Schichl,
An introduction to the Vienna Database Library,
Technical Report,
in "Upgraded State of the Art Techniques implemented as Modules",
Deliverable D13 of the COCONUT project (July 2003), pages 29-31,
ps file (237K),
downloading/printing problems?
This technical report contains a short introduction to the VDBL
(Vienna Database Library), one of the basic libraries
of the COCONUT API.
H. Schichl,
Changes and new features in API 2.x,
Technical Report,
upgrade of Deliverable D6
in "Upgraded State of the Art Techniques implemented as Modules",
Deliverable D13 of the COCONUT project (July 2003), pages 30-37,
ps file (259K),
downloading/printing problems?
This technical report contains the changes of the interface definitions
between the various module classes, the evaluators, and the base classes
for modules from COCONUT API Version 1 to Version 2, as well as the changes
to file structure and additional operator type definitions in the internal
model representation.
H. Schichl,
UWien Evaluators,
Technical Report,
in "Upgraded State of the Art Techniques implemented as Modules",
Deliverable D13 of the COCONUT project (July 2003), pages 41-52,
ps file (264K),
downloading/printing problems?
This technical report contains descriptions of all evaluators (automatic
differentiaton,...) implemented in the COCONUT API.
H. Schichl,
UWien Basic Splitter, BestPoint, CheckBox, Check Infeasibility, Check Number,
Exclusion boxes using Karush-John conditions, Karush-John conditions generator,
Linear relaxation generator using slopes, Simple Convexity,
Template for description of modules,
TU Darmstadt module DONLP2-INTV (with P. Spellucci),
Technical Report,
in "Upgraded State of the Art Techniques implemented as Modules",
Deliverable D13 of the COCONUT project (July 2003),
pages 51-53, 61-69, 75-80, 83-86, 92-93, 106-107,
ps file (283K),
downloading/printing problems?
This technical report contains the descriptions of the implemented inference
engines (solver modules) for the COCONUT API.
H. Schichl,
Management Modules,
Technical Report,
in "Set of Combination Algorithms for State of the Art Modules",
Deliverable D14 of the COCONUT project (July 2003), pages 7-16,
ps file (353K),
downloading/printing problems?
This technical report contains descriptions of all management modules
graph and database handling,...) implemented in the COCONUT API.
H. Schichl,
Report Modules,
Technical Report,
in "Set of Combination Algorithms for State of the Art Modules",
Deliverable D14 of the COCONUT project (July 2003), pages 17-22,
ps file (346K),
downloading/printing problems?
This technical report contains descriptions of all report modules
output generation,...) implemented in the COCONUT API.
H. Schichl, O. Shcherbina, Andrzej Pownuk
External Converters,
Technical Report,
in "Set of Combination Algorithms for State of the Art Modules",
Deliverable D14 of the COCONUT project (July 2003), pages 23-40,
ps file (553K),
downloading/printing problems?
This technical report contains descriptions of all external converters
from and to modeling languages and high level languages (C, Fortran 90),
and other global optimization algorithms.
I do not send out paper copies of my manuscripts; but here are some hints of how to make your own copy.
To uncompress the files obtained you need the GNU program gunzip.
Some browsers seem to save *.dvi.gz files as *.dvi, so that one thinks one has a dvi-file while one actually may still have to do a gunzip. And some other browsers appear to do an automatic gunzip, while leaving the file name with the suffix .gz! In both cases, the file needs to be renamed appropriately for further processing.
See The gzip homepage or Compression for gunzip, dvi.exe or TeX Facilities or LaTeX Home Page for a dvi-viewer, Ghostscript for the popular free postscript viewer, and
Help for printing PostScript Files.
If you still have difficulties obtaining or printing one of the papers above, please tell me details about the difficulties you encountered.
Hermann Schichl (Hermann.Schichl@esi.ac.at)