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.

     

A local min-orthogonal method for finding multiple saddle points

The purpose of this paper is twofold. The first is to remove a possible ill-posedness related to a local minimax method developed in SIAM J. Sci. Comput. 23 (2001) 840-865, SIAM J. Sci. Comput. 24 (2002) 840-865 and the second is to provide a local characterization for nonminimax type saddle points. To do so, a local L-⊥ selection is defined and a necessary and sufficient condition for a saddle point is established, which leads to a min-orthogonal method. Those results exceed the scope of a minimax principle, the most popular approach in critical point theory. An example is given to illustrate the new theory. With this local characterization, the local minimax method in SIAM J. Sci. Comput. 23 (2001) 840-865, SIAM J. Sci. Comput. 24 (2002) 840-865 is generalized to a local min-orthogonal method for finding multiple saddle points. In a subsequent paper, this approach is applied to define a modified pseudo gradient (flow) of a functional for finding multiple saddle points in Banach spaces.     

Saddle points and scalarizing sets in multiple objective linear programming

The main purpose of this paper is to study saddle points of the vector Lagrangian function associated with a multiple objective linear programming problem. We introduce three concepts of saddle points and establish their characterizations by solving suitable systems of equalities and inequalities. We deduce dual programs and prove a relationship between saddle points and dual solutions, which enables us to obtain an explicit expression of the scalarizing set of a given saddle point in terms of normal vectors to the value set of the problem. Finally, we present an algorithm to compute saddle points associated with non-degenerate vertices and the corresponding scalarizing sets.     

Lagrange optimality system for a class of nonsmooth convex optimization

In this paper, we revisit the augmented Lagrangian method for a class of nonsmooth convex optimization. We present the Lagrange optimality system of the augmented Lagrangian associated with the problems, and establish its connections with the standard optimality condition and the saddle point condition of the augmented Lagrangian, which provides a powerful tool for developing numerical algorithms: we derive a Lagrange–Newton algorithm for the nonsmooth convex optimization, and establish the nonsingularity of the Newton system and the local convergence of the algorithm.     

Primal-dual subgradient methods for convex problems

In this paper we present a new approach for constructing subgradient schemes for different types of nonsmooth problems with convex structure. Our methods are primal-dual since they are always able to generate a feasible approximation to the optimum of an appropriately formulated dual problem. Besides other advantages, this useful feature provides the methods with a reliable stopping criterion. The proposed schemes differ from the classical approaches (divergent series methods, mirror descent methods) by presence of two control sequences. The first sequence is responsible for aggregating the support functions in the dual space, and the second one establishes a dynamically updated scale between the primal and dual spaces. This additional flexibility allows to guarantee a boundedness of the sequence of primal test points even in the case of unbounded feasible set (however, we always assume the uniform boundedness of subgradients). We present the variants of subgradient schemes for nonsmooth convex minimization, minimax problems, saddle point problems, variational inequalities, and stochastic optimization. In all situations our methods are proved to be optimal from the view point of worst-case black-box lower complexity bounds.     

Minimax designs for linear regression models with bias in a reproducing kernel Hilbert space in a discrete set

Consider the design problem for estimation and extrapolation in approximately linear regression models with possible misspecification. The design space is a discrete set consisting of finitely many points, and the model bias comes from a reproducing kernel Hilbert space. Two different design criteria are proposed by applying the minimax approach for estimating the parameters of the regression response and extrapolating the regression response to points outside of the design space. A simulated annealing algorithm is applied to construct the minimax designs.These minimax designs are compared with the classical D-optimal designs and all-bias extrapolation designs. Numerical results indicate that the simulated annealing algorithm is feasible and the minimax designs are robust against bias caused by model misspecification.     

精确罚函数和极小极大问题

在这篇文章中我们研究了对于不等式约束的非线性规划问题如何根据极小极大问题的鞍点来找精确罚问题的解。对于一个具有不等式约束的非线性规划问题,通过罚函数,我们构造出一个极小极大问题,应用交换“极小”或“极大”次序的策略,证明了罚问题的鞍点定理。研究结果显示极小极大问题的鞍点是精确罚问题的解。     

Hyperbolic smoothing function method for minimax problems

In this article, an approach for solving finite minimax problems is proposed. This approach is based on the use of hyperbolic smoothing functions. In order to apply the hyperbolic smoothing we reformulate the objective function in the minimax problem and study the relationship between the original minimax and reformulated problems. We also study main properties of the hyperbolic smoothing function. Based on these results an algorithm for solving the finite minimax problem is proposed and this algorithm is implemented in general algebraic modelling system. We present preliminary results of numerical experiments with well-known nonsmooth optimization test problems. We also compare the proposed algorithm with the algorithm that uses the exponential smoothing function as well as with the algorithm based on nonlinear programming reformulation of the finite minimax problem.     

On mountain pass type algorithms

We consider constructive proofs of the mountain pass lemma, the saddle point theorem and a linking type theorem. In each, an initial “path” is deformed by pushing it downhill using a (pseudo) gradient flow, and, at each step, a high point on the deformed path is selected. Using these high points, a Palais–Smale sequence is constructed, and the classical minimax theorems are recovered. Because the sequence of high points is more accessible from a numerical point of view, we investigate the behavior of this sequence in the final two sections. We show that if the functional satisfies the Palais–Smale condition and has isolated critical points, then the high points form a Palais–Smale sequence, and—passing to a subsequence—the high points will in fact converge to a critical point.     

Convergence analysis of a minimax method for finding multiple solutions of hemivariational inequality in Hilbert space

In 2013, a minimax method for finding saddle points of locally Lipschitz continuous functional was designed (Yao Math. Comp. 82 2087–2136 2013). The method can be applied to numerically solve hemivariational inequality for multiple solutions. Its subsequence and sequence convergence results in functional analysis were established in the same paper. But, since these convergence results do not consider discretization, they are not convergence results in numerical analysis. In this paper, we point out what approximation problem is, when this minimax method is used to solve hemivariational inequality and the finite element method is used in discretization. Computation of the approximation problem is discussed, numerical experiment is carried out and its global convergence is verified. Finally, as element size goes to zero, convergence of solutions of the approximation problem to solutions of hemivariational inequality is proved.     

Interior penalty functions and duality in linear programming

Logarithmic additive terms of barrier type with a penalty parameter are included in the Lagrange function of a linear programming problem. As a result, the problem of searching for saddle points of the modified Lagrangian becomes unconstrained (the saddle point is sought with respect to the whole space of primal and dual variables). Theorems on the asymptotic convergence to the desired solution and analogs of the duality theorems for the arising optimization minimax and maximin problems are formulated.     

Characterizations for Optimality Conditions of General Robust Optimization Problems

In this paper, by virtue of the image space analysis, the general scalar robust optimization problems under the strictly robust counterpart are considered, among which, the uncertainties are included in the objective as well as the constraints. Besides, on the strength of a corrected image in a new type, an equivalent relation between the uncertain optimization problem and its image problem is also established, which provides an idea to tackle with minimax problems. Furthermore, theorems of the robust weak alternative as well as sufficient characterizations of robust optimality conditions are achieved on the frame of the linear and nonlinear (regular) weak separation functions. Moreover, several necessary and sufficient optimality conditions, especially saddle point sufficient optimality conditions for scalar robust optimization problems, are obtained. Finally, a simple example for finding a shortest path is included to show the effectiveness of the results derived in this paper.     

Eigenvalue Problems for Hemivariational Inequalities

We consider a semilinear eigenvalue problem with a nonsmooth potential (hemivariational inequality). Using a nonsmooth analog of the local Ambrosetti–Rabinowitz condition (AR-condition), we show that the problem has a nontrivial smooth solution. In the scalar case, we show that we can relax the local AR-condition. Finally, for the resonant λ?=?λ ₁ problem, using the nonsmooth version of the local linking theorem, we show that the problem has at least two nontrivial solutions. Our approach is variational, using minimax methods from the nonsmooth critical point theory.     

Nonsmooth Steepest Descent Method by Proximal Subdifferentials in Hilbert Spaces

In this paper, we first study a nonsmooth steepest descent method for nonsmooth functions defined on a Hilbert space and establish the corresponding algorithm by proximal subgradients. Then, we use this algorithm to find stationary points for those functions satisfying prox-regularity and Lipschitz continuity. As an application, the established algorithm is used to search for the minimizer of a lower semicontinuous and convex function on a finite-dimensional space. A convergence theorem, as an extension and improvement of the existing converging result for twice continuously differentiable convex functions, is also presented therein.     

Bifurcation problems in nonlinear parametric programming

The nonlinear parametric programming problem is reformulated as a closed system of nonlinear equations so that numerical continuation and bifurcation techniques can be used to investigate the dependence of the optimal solution on the system parameters. This system, which is motivated by the Fritz John first-order necessary conditions, contains all Fritz John and all Karush-Kuhn-Tucker points as well as local minima and maxima, saddle points, feasible and nonfeasible critical points. Necessary and sufficient conditions for a singularity to occur in this system are characterized in terms of the loss of a complementarity condition, the linear dependence of the gradients of the active constraints, and the singularity of the Hessian of the Lagrangian on a tangent space. Any singularity can be placed in one of seven distinct classes depending upon which subset of these three conditions hold true at a solution. For problems with one parameter, we analyze simple and multiple bifurcation of critical points from a singularity arising from the loss of the complementarity condition, and then develop a set of conditions which guarantees the unique persistence of a minimum through this singularity. The research of this author was supported by National Science Foundation through NSF Grant DMS-85-10201 and by the Air Force Office of Scientific Research through instrument number AFOSR-ISSA-85-00079.     

Generalized Newton’s method based on graphical derivatives

This paper concerns developing a numerical method of the Newton type to solve systems of nonlinear equations described by nonsmooth continuous functions. We propose and justify a new generalized Newton algorithm based on graphical derivatives, which have never been used to derive a Newton-type method for solving nonsmooth equations. Based on advanced techniques of variational analysis and generalized differentiation, we establish the well-posedness of the algorithm, its local superlinear convergence, and its global convergence of the Kantorovich type. Our convergence results hold with no semismoothness and Lipschitzian assumptions, which is illustrated by examples. The algorithm and main results obtained in the paper are compared with well-recognized semismooth and B-differentiable versions of Newton’s method for nonsmooth Lipschitzian equations.     

An approximate bundle method for solving nonsmooth equilibrium problems

We present an approximate bundle method for solving nonsmooth equilibrium problems. An inexact cutting-plane linearization of the objective function is established at each iteration, which is actually an approximation produced by an oracle that gives inaccurate values for the functions and subgradients. The errors in function and subgradient evaluations are bounded and they need not vanish in the limit. A descent criterion adapting the setting of inexact oracles is put forward to measure the current descent behavior. The sequence generated by the algorithm converges to the approximately critical points of the equilibrium problem under proper assumptions. As a special illustration, the proposed algorithm is utilized to solve generalized variational inequality problems. The numerical experiments show that the algorithm is effective in solving nonsmooth equilibrium problems.     

SEMILINEAR HEMIVARIATIONAL INEQUALITIES WITH STRONG RESONANCE AT INFINITY

A semilinear elliptic equation with strong resonance at infinity and with a nonsmooth potential is studied. Using nonsmooth critical point theory and developing some abstract minimax principles which complement and extend results in the literature, two results on existence are obtained.     

Nonconvex energy functions,related eigenvalue hemivariational inequalities on the sphere and applications

The present paper deals with a new type of eigenvalue problems arising in problems involving nonconvex nonsmooth energy functions. They lead to the search of critical points (e.g. local minima) for nonconvex nonsmooth potential functions which in turn give rise to hemivariational inequalities. For this type of variational expressions the eigenvalue problem is studied here concerning the existence and multiplicity of solutions by applying a critical point theory appropriate for nonsmooth nonconvex functionals.     

Construction of a minimax solution for an eikonal-type equation

A formula for a minimax (generalized) solution of the Cauchy-Dirichlet problem for an eikonal-type equation is proved in the case of an isotropic medium providing that the edge set is closed; the boundary of the edge set can be nonsmooth. A technique of constructing a minimax solution is proposed that uses methods from the theory of singularities of differentiable mappings. The notion of a bisector, which is a representative of symmetry sets, is introduced. Special points of the set boundary—pseudovertices—are singled out and bisector branches corresponding to them are constructed; the solution suffers a “gradient catastrophe” on these branches. Having constructed the bisector, one can generate the evolution of wave fronts in smoothness domains of the generalized solution. The relation of the problem under consideration to one class of time-optimal dynamic control problems is shown. The efficiency of the developed approach is illustrated by examples of analytical and numerical construction of minimax solutions.