Mathematical programs with vanishing constraints: critical point theory

We study mathematical programs with vanishing constraints (MPVCs) from a topological point of view. We introduce the new concept of a T-stationary point for MPVC. Under the Linear Independence Constraint Qualification we derive an equivariant Morse Lemma at nondegenerate T-stationary points. Then, two basic theorems from Morse Theory (deformation theorem and cell-attachment theorem) are proved. Outside the T-stationary point set, continuous deformation of lower level sets can be performed. As a consequence, the topological data (such as the number of connected components) then remain invariant. However, when passing a T-stationary level, the topology of the lower level set changes via the attachment of a q-dimensional cell. The dimension q equals the stationary T-index of the (nondegenerate) T-stationary point. The stationary T-index depends on both the restricted Hessian of the Lagrangian and the number of bi-active vanishing constraints. Further, we prove that all T-stationary points are generically nondegenerate. The latter property is shown to be stable under C ²-perturbations of the defining functions. Finally, some relations with other stationarity concepts, such as strong, weak, and M-stationarity, are discussed.     

Morse theory for periodic solutions of hamiltonian systems and the maslov index

In this paper we prove Morse type inequalities for the contractible 1-periodic solutions of time dependent Hamiltonian differential equations on those compact symplectic manifolds M for which the symplectic form and the first Chern class of the tangent bundle vanish over π₂ (M). The proof is based on a version of infinite dimensional Morse theory which is due to Floer. The key point is an index theorem for the Fredholm operator which plays a central role in Floer homology. The index formula involves the Maslov index of nondegenerate contractible periodic solutions. This Maslov index plays the same role as the Morse index of a nondegenerate critical point does in finite dimensional Morse theory. We shall use this connection between Floer homology and Maslov index to establish the existence of infinitely many periodic solutions having integer periods provided that every 1-periodic solution has at least one Floquet multiplier which is not equal to 1.     

One-parameter families of optimization problems: Equality constraints

In this paper, we introduce generalized critical points and discuss their relationship with other concepts of critical points [resp., stationary points]. Generalized critical points play an important role in parametric optimization. Under generic regularity conditions, we study the set of generalized critical points, in particular, the change of the Morse index. We focus our attention on problems with equality constraints only and provide an indication of how the present theory can be extended to problems with inequality constraints as well.     

A symplectic perspective on constrained eigenvalue problems

The Maslov index is a powerful tool for computing spectra of selfadjoint, elliptic boundary value problems. This is done by counting intersections of a fixed Lagrangian subspace, which designates the boundary conditions, with the set of Cauchy data for the differential operator. We apply this methodology to constrained eigenvalue problems, in which the operator is restricted to a (not necessarily invariant) subspace. The Maslov index is defined and used to compute the Morse index of the constrained operator. We then prove a constrained Morse index theorem, which says that the Morse index of the constrained problem equals the number of constrained conjugate points, counted with multiplicity, and give an application to the nonlinear Schrödinger equation.     

Index computations in Rabinowitz Floer homology

In this note we study two index questions. In the first we establish the relationship between the Morse indices of the free time action functional and the fixed time action functional. The second is related to Rabinowitz Floer homology. Our index computations are based on a correction term which is defined as follows: around a nondegenerate Hamiltonian orbit lying in a fixed energy level a well-known theorem says that one can find a whole cylinder of orbits parametrized by the energy. The correction term is determined by whether the periods of the orbits are increasing or decreasing as one moves up the orbit cylinder. We also provide an example to show that, even above the Ma?é critical value, the periods may be increasing thus producing a jump in the Morse index of the free time action functional in relation to the Morse index of the fixed time action functional.     

Algorithms for bound constrained quadratic programming problems

Summary We present an algorithm which combines standard active set strategies with the gradient projection method for the solution of quadratic programming problems subject to bounds. We show, in particular, that if the quadratic is bounded below on the feasible set then termination occurs at a stationary point in a finite number of iterations. Moreover, if all stationary points are nondegenerate, termination occurs at a local minimizer. A numerical comparison of the algorithm based on the gradient projection algorithm with a standard active set strategy shows that on mildly degenerate problems the gradient projection algorithm requires considerable less iterations and time than the active set strategy. On nondegenerate problems the number of iterations typically decreases by at least a factor of 10. For strongly degenerate problems, the performance of the gradient projection algorithm deteriorates, but it still performs better than the active set method.Work supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research of the U.S. Department of Energy under Contract W-31-109-Eng-38     

Fundamental Theorems of Morse Theory for Optimization on Manifolds with Corners

This note extends the fundamental theorems of Morse theory for stable stationary solutions to optimization problems on manifolds with corners.     

On regular minimax optimization

We consider functions of maximum type (max functions for short), subject to (in)equality constraints. The space dimension is finite, and the maximum is taken over a compact manifold with boundary. Effective local minimization algorithms based on Newton's method can be derived in the case where a local minimum is nondegenerate (in a two-level sense). In fact, nondegeneracy refers on the one hand to a local (implicit) reduction of the original max function to another one, where the maximum is taken over a finite set. On the other hand, it refers to strict complementarity and nondegeneracy of the underlying quadratic form with respect to the reduced stationary situation. As the main goal, we show that the set ofn-parameter families of functions, for which the stationary points of the corresponding max function are nondegenerate, constitutes an open and dense subset in the space of alln-parameter families (the topology used takes derivatives up to second order into account). An application to approximation problems of Chebyshev type is presented.     

Spectral Flow,Maslov Index and Bifurcation of Semi-Riemannian Geodesics

We give a functional analytical proof of the equalitybetween the Maslov index of a semi-Riemannian geodesicand the spectral flow of the path of self-adjointFredholm operators obtained from the index form. This fact, together with recent results on the bifurcation for critical points of strongly indefinite functionals imply that each nondegenerate and nonnull conjugate (or P-focal)point along a semi-Riemannian geodesic is a bifurcation point.In particular, the semi-Riemannian exponential map is notinjective in any neighborhood of a nondegenerate conjugate point,extending a classical Riemannian result originally due to Morse and Littauer.     

A DIRECT-based approach exploiting local minimizations for the solution of large-scale global optimization problems

In this paper we propose a new algorithm for solving difficult large-scale global optimization problems. We draw our inspiration from the well-known DIRECT algorithm which, by exploiting the objective function behavior, produces a set of points that tries to cover the most interesting regions of the feasible set. Unfortunately, it is well-known that this strategy suffers when the dimension of the problem increases. As a first step we define a multi-start algorithm using DIRECT as a deterministic generator of starting points. Then, the new algorithm consists in repeatedly applying the previous multi-start algorithm on suitable modifications of the variable space that exploit the information gained during the optimization process. The efficiency of the new algorithm is pointed out by a consistent numerical experimentation involving both standard test problems and the optimization of Morse potential of molecular clusters.     

Instability analysis of saddle points by a local minimax method

The objective of this work is to develop some tools for local instability analysis of multiple critical points, which can be computationally carried out. The Morse index can be used to measure local instability of a nondegenerate saddle point. However, it is very expensive to compute numerically and is ineffective for degenerate critical points. A local (weak) linking index can also be defined to measure local instability of a (degenerate) saddle point. But it is still too difficult to compute. In this paper, a local instability index, called a local minimax index, is defined by using a local minimax method. This new instability index is known beforehand and can help in finding a saddle point numerically. Relations between the local minimax index and other local instability indices are established. Those relations also provide ways to numerically compute the Morse, local linking indices. In particular, the local minimax index can be used to define a local instability index of a saddle point relative to a reference (trivial) critical point even in a Banach space while others failed to do so.

     

On the Regularity for Stationary Harmonic Maps

We prove a compactness theorem for k-indexed stationary harmonic maps, and show a regularity theorem for this kind of maps which says that the singular set of a k-indexed stationary harmonic map is of Hausdorff dimension at most m-3.     

Geometrical Decomposition of the Free Loop Space on a Manifold with Finitely Many Closed Geodesics

In Morse theory an isolated degenerate critical point can be resolved into a finite number of nondegenerate critical points by perturbing the totally degenerate part of the Morse function inside the domain of a generalized Morse chart. Up to homotopy we can admit pertubations within the whole characteristic manifold. Up to homotopy type a relative CW-complex is attached, which is the product of a big relative CW-complex, representing the degenerate part, and a small cell having the dimension of the Morse index.     

Generalized Kojima–Functions and Lipschitz Stability of Critical Points

In this paper we consider systems of equations which are defined by nonsmooth functions of a special structure. Functions of this type are adapted from Kojima's form of the Karush–Kuhn–Tucker conditions for C²—optimization problems. We shall show that such systems often represent conditions for critical points of variational problems (nonlinear programs, complementarity problems, generalized equations, equilibrium problems and others). Our main purpose is to point out how different concepts of generalized derivatives lead to characterizations of different Lipschitz properties of the critical point or the stationary solution set maps.     

Smoothing by mollifiers. Part II: nonlinear optimization

This article complements the paper (Jongen, Stein, Smoothing by mollifers part I: semi-infinite optimization J Glob Optim doi:), where we showed that a compact feasible set of a standard semi-infinite optimization problem can be approximated arbitrarily well by a level set of a single smooth function with certain regularity properties. In the special case of nonlinear programming this function is constructed as the mollification of the finite min-function which describes the feasible set. In the present article we treat the correspondences between Karush–Kuhn–Tucker points of the original and the smoothed problem, and between their associated Morse indices.      

A trust region affine scaling method for bound constrained optimization

We study a new trust region affine scaling method for general bound constrained optimization problems. At each iteration, we compute two trial steps. We compute one along some direction obtained by solving an appropriate quadratic model in an ellipsoidal region. This region is defined by an affine scaling technique. It depends on both the distances of current iterate to boundaries and the trust region radius. For convergence and avoiding iterations trapped around nonstationary points, an auxiliary step is defined along some newly defined approximate projected gradient. By choosing the one which achieves more reduction of the quadratic model from the two above steps as the trial step to generate next iterate, we prove that the iterates generated by the new algorithm are not bounded away from stationary points. And also assuming that the second-order sufficient condition holds at some nondegenerate stationary point, we prove the Q-linear convergence of the objective function values. Preliminary numerical experience for problems with bound constraints from the CUTEr collection is also reported.     

Smoothing by mollifiers. Part I: semi-infinite optimization

We show that a compact feasible set of a standard semi-infinite optimization problem can be approximated arbitrarily well by a level set of a single smooth function with certain regularity properties. This function is constructed as the mollification of the lower level optimal value function. Moreover, we use correspondences between Karush–Kuhn–Tucker points of the original and the smoothed problem, and between their associated Morse indices, to prove the connectedness of the so-called min–max digraph for semi-infinite problems.      

Proof of a Conjecture by Deutsch, Li, and Swetits on Duality of Optimization Problems

A conjecture of Deutsch, Li, and Swetits on duality relationships among three optimization problems is shown to hold true. The proof relies on a reformulation of one of the problems in a suitable product space, to which then a version of the classical Fenchel duality theorem applies.     

Conjugacy of Morse Functions on Surfaces with Values on a Straight Line and Circle

We investigate the conjugacy of Morse functions on closed surfaces. By using cellular decompositions of surfaces, we formulate a criterion for the conjugacy of Morse functions. We establish a criterion for the conjugacy of mappings into a circle with nondegenerate critical points.     

On the Use of Augmented Lagrangians in the Solution of Generalized Semi-Infinite Min-Max Problems

We present an approach for the solution of a class of generalized semi-infinite optimization problems. Our approach uses augmented Lagrangians to transform generalized semi-infinite min-max problems into ordinary semi-infinite min-max problems, with the same set of local and global solutions as well as the same stationary points. Once the transformation is effected, the generalized semi-infinite min-max problems can be solved using any available semi-infinite optimization algorithm. We illustrate our approach with two numerical examples, one of which deals with structural design subject to reliability constraints.