On minimax optimization problems

We give a short proof that in a convex minimax optimization problem ink dimensions there exist a subset ofk + 1 functions such that a solution to the minimax problem with thosek + 1 functions is a solution to the minimax problem with all functions. We show that convexity is necessary, and prove a similar theorem for stationary points when the functions are not necessarily convex but the gradient exists for each function.     

Smooth sample average approximation of stationary points in nonsmooth stochastic optimization and applications

Inspired by a recent work by Alexander et al. (J Bank Finance 30:583–605, 2006) which proposes a smoothing method to deal with nonsmoothness in a conditional value-at-risk problem, we consider a smoothing scheme for a general class of nonsmooth stochastic problems. Assuming that a smoothed problem is solved by a sample average approximation method, we investigate the convergence of stationary points of the smoothed sample average approximation problem as sample size increases and show that w.p.1 accumulation points of the stationary points of the approximation problem are weak stationary points of their counterparts of the true problem. Moreover, under some metric regularity conditions, we obtain an error bound on approximate stationary points. The convergence result is applied to a conditional value-at-risk problem and an inventory control problem.      

Asymptotic Stability of a Stationary Flowing Regime of an Ideal Incompressible Fluid

We give sufficient conditions for asymptotic stability of a stationary solution to a flowing problem of a homogeneous incompressible fluid through a given planar domain. We consider a planar problem for the Euler equation and boundary conditions for the curl and the normal component of the velocity; moreover, the latter is given on the whole boundary of the flow domain and the curl is given only on the inlet part of the boundary. We establish asymptotic stability of a stationary flow (in linear approximation), assuming it to have no rest points and to satisfy some smallness condition which means that the perturbations leave the flow domain before they become to affect the main flow. In particular, we prove asymptotic stability for an arbitrary stationary flow in a rectangular canal close to the Couette flow without rest points. Moreover, we show that stability of the main flow in the L ₂-norm under curl perturbations implies its stability in higher-order norms depending, for example, on the derivatives of the curl.     

A smoothing sample average approximation method for stochastic optimization problems with CVaR risk measure

This paper is concerned with solving single CVaR and mixed CVaR minimization problems. A CHKS-type smoothing sample average approximation (SAA) method is proposed for solving these two problems, which retains the convexity and smoothness of the original problem and is easy to implement. For any fixed smoothing constant ε, this method produces a sequence whose cluster points are weak stationary points of the CVaR optimization problems with probability one. This framework of combining smoothing technique and SAA scheme can be extended to other smoothing functions as well. Practical numerical examples arising from logistics management are presented to show the usefulness of this method.     

Convergence Analysis of a Class of Penalty Methods for Vector Optimization Problems with Cone Constraints

In this paper, we consider convergence properties of a class of penalization methods for a general vector optimization problem with cone constraints in infinite dimensional spaces. Under certain assumptions, we show that any efficient point of the cone constrained vector optimization problem can be approached by a sequence of efficient points of the penalty problems. We also show, on the other hand, that any limit point of a sequence of approximate efficient solutions to the penalty problems is a weekly efficient solution of the original cone constrained vector optimization problem. Finally, when the constrained space is of finite dimension, we show that any limit point of a sequence of stationary points of the penalty problems is a KKT stationary point of the original cone constrained vector optimization problem if Mangasarian–Fromovitz constraint qualification holds at the limit point.This work is supported by the Postdoctoral Fellowship of Hong Kong Polytechnic University.     

New Constrained Optimization Reformulation of Complementarity Problems

We suggest a reformulation of the complementarity problem CP(F) as a minimization problem with nonnegativity constraints. This reformulation is based on a particular unconstrained minimization reformulation of CP(F) introduced by Geiger and Kanzow as well as Facchinei and Soares. This allows us to use nonnegativity constraints for all the variables or only a subset of the variables on which the function F depends. Appropriate regularity conditions ensure that a stationary point of the new reformulation is a solution of the complementarity problem. In particular, stationary points with negative components can be avoided in contrast to the reformulation as unconstrained minimization problem. This advantage will be demonstrated for a class of complementarity problems which arise when the Karush–Kuhn–Tucker conditions of a convex inequality constrained optimization problem are considered.     

THE MITRA‐WAN FORESTRY MODEL: A DISCRETE‐TIME OPTIMAL CONTROL PROBLEM

In this paper, we present some new properties of the Mitra‐Wan forestry model written as a discrete‐time optimal control problem. For this problem, the set of stationary states is characterized. For the optimal long‐run management, we consider the following optimality criteria: average optimality, good control policies, bias optimality, and overtaking optimality. We establish relationships between these criteria and show that the value of average optimal policies is constant and equals the value in the optimal stationary state.     

Einige unstetige stochastische Prozesse

Summary Stochastic processes of the following type are considered. At random time points, the variablex(t) jumps fromy tox, say. The heightsx–y of the jumps have a given distributionG ^*(x–y) that may depend ony ort. Between the jumps,x(t) is a solution to a given differential equationdx/dt=x(x, t). We look for the distributionF(x, t) ofx at timet>0,F(x, 0) being given. In the stationary case, stable distributions are investigated.If there is a lower boundaryx ₀ and ifF(x ₀)>0, the problem is similar to the queueing problem. We solve it in the stationary case with integral equations of the Volterra type. Other problems can be transformed to differential equations for the moment generating functions. These equations are partial in the non stationary and ordinary in the stationary case.     

Elimination of bounds in optimization problems by transforming variables

The problem of minimizing a nonlinear objective function ofn variables, with continuous first and second partial derivatives, subject to nonnegativity constraints or upper and lower bounds on the variables is studied. The advisability of solving such a constrained optimization problem by making a suitable transformation of its variables in order to change the problem into one of unconstrained minimization is considered. A set of conditions which guarantees that every local minimum of the new unconstrained problem also satisfies the first-order necessary (Kuhn—Tucker) conditions for a local minimum of the original constrained problem is developed. It is shown that there are certain conditions under which the transformed objective function will maintain the convexity of the original objective function in a neighborhood of the solution. A modification of the method of transformations which moves away from extraneous stationary points is introduced and conditions under which the method generates a sequence of points which converges to the solution at a superlinear rate are given.     

Long range percolation in stationary point processes

We consider a continuum percolation model in ?d, d ? 1 in which any two points of a stationary point process are connected with a probability which decays exponentially in the distance between the points. We give sufficient conditions for the (non)-existence of a phase transition. We also give examples of processes which show that it is impossible to write down a theorem which relates the critical parameter value of a process to its density. Finally, we show that uniqueness of the infinite cluster is still valid in this general setting. © 1993 John Wiley & Sons, Inc.     

Regularity for critical points of a non local energy

We study the regularity of critical points of an energy which stems from micromagnetism theory. First we show that in dimension two critical points are smooth in B ² . In the three dimensional case we prove that the stationary critical points of the energy are smooth except in a subset of one dimensional Hausdorff measure zero. The particularity of this work is the non local character of one term of the energy. Received July 10, 1995 / Accepted April 15, 1996     

On the approximate augmented Lagrangian for nonlinear symmetric cone programming

This paper studies the approximate augmented Lagrangian for nonlinear symmetric cone programming. The analysis is based on some results under the framework of Euclidean Jordan algebras. We formulate the approximate Lagrangian dual problem and study conditions for approximate strong duality results and an approximate exact penalty representation. We also show, under Robinson’s constraint qualification, that the sequence of stationary points of the approximate augmented Lagrangian problems converges to a stationary point of the original nonlinear symmetric cone programming.     

A smooth penalty approach and a nonlinear multigrid algorithm for elliptic MPECs

An optimal control problem governed by an elliptic variational inequality of the first kind and bilateral control constraints is studied. A smooth penalization technique for the variational inequality is applied and convergence of stationary points of the subproblems to an E-almost C-stationary point of the limit problem is shown. The subproblems are solved using a full approximation multigrid scheme (FAS) and alternatively a multigrid method of the second kind for which a convergence result is given. An overall algorithmic concept is provided and its performance is discussed by means of examples.     

An Interval Analysis Approach to the EM Algorithm

Abstract

The EM algorithm is widely used in incomplete-data problems (and some complete-data problems) for parameter estimation. One limitation of the EM algorithm is that, upon termination, it is not always near a global optimum. As reported by Wu (1982), when several stationary points exist, convergence to a particular stationary point depends on the choice of starting point. Furthermore, convergence to a saddle point or local minimum is also possible. In the EM algorithm, although the log-likelihood is unknown, an interval containing the gradient of the EM q function can be computed at individual points using interval analysis methods. By using interval analysis to enclose the gradient of the EM q function (and, consequently, the log-likelihood), an algorithm is developed that is able to locate all stationary points of the log-likelihood within any designated region of the parameter space. The algorithm is applied to several examples. In one example involving the t distribution, the algorithm successfully locates (all) seven stationary points of the log-likelihood.     

Geometric interpretation of Hamiltonian cycles problem via singularly perturbed Markov decision processes

We consider the Hamiltonian cycle problem (HCP) embedded in a singularly perturbed Markov decision process (MDP). More specifically, we consider the HCP as an optimization problem over the space of long-run state-action frequencies induced by the MDP's stationary policies. We also consider two quadratic functionals over the same space. We show that when the perturbation parameter, ? is sufficiently small the Hamiltonian cycles of the given directed graph are precisely the maximizers of one of these quadratic functionals over the frequency space intersected with an appropriate (single) contour of the second quadratic functional. In particular, all these maximizers have a known Euclidean distance of z _m (?) from the origin. Geometrically, this means that Hamiltonian cycles, if any, are the points in the frequency polytope where the circle of radius z _m (?) intersects a certain ellipsoid.     

Upper Lipschitz behavior of solutions to perturbed. C1,1 programs

We analyze the local upper Lipschitz behavior of critical points, stationary solutions and local minimizers to parametric C ^1,1 programs. In particular, we derive a characterization of this property for the stationary solution set map without assuming the Mangasarian–Fromovitz CQ. Moreover, conditions which also ensure the persistence of solvability are given, and the special case of linear constraints is handled. The present paper takes pattern from [21] by continuing the approach via contingent derivatives of the Kojima function associated with the given optimization problem. Received: June 10, 1999 / Accepted: November 15, 1999?Published online July 20, 2000     

Multimodality analysis of a class of multistage allocation problems

Multiple optimum solutions of a multistage allocation problem, well-known to chemical engineers, are analyzed. The number of local optima becomes greater with a decrease in the initial-condition value of the first stage or with an increase in the total stage number. The fact that this behavior is closely related to the flat portion of the profile of a curvef(x), which determines the objective function, is revealed. A construction method by Aris is used to give an excellent insight into this behavior. Moreover, the construction curves ensure that all stationary points are found. Finally, a theorem to discriminate local optima from stationary points, without evaluating second-order derivatives, is presented.The authors would like to thank Dr. I. Hashimoto and Dr. H. Nishitani for valuable discussions. Computations were carried out with the assistance of Messrs. H. Unno, H. Nakano, Y. Era, and Y. Ueno. The authors are indebted to the computing centers of Osaka University, Kyoto University, and Nagoya University for the use of their facilities.     

An L2 finite element approximation for the incompressible Navier–Stokes equations

This paper utilizes the Picard method and Newton's method to linearize the stationary incompressible Navier–Stokes equations and then uses an LL* approach, which is a least-squares finite element method applied to the dual problem of the corresponding linear system. The LL* approach provides an L²-approximation to a given problem, which is not typically available with conventional finite element methods for nonlinear second-order partial differential equations. We first show that the proposed combination of linearization scheme and LL* approach provides an L²-approximation to the stationary incompressible Navier–Stokes equations. The validity of L²-approximation is proven through the analysis of the weak problem corresponding to the linearized Navier–Stokes equations. Then, the convergence is analyzed, and numerical results are presented.     

A quadratic approximation method for minimizing a class of quasidifferentiable functions

Summary An unconstrained nonlinear programming problem with nondifferentiabilities is considered. The nondifferentiabilities arise from terms of the form max [f ₁(x), ...,f _n (x)], which may enter nonlinearly in the objective function. Local convex polyhedral upper approximations to the objective function are introduced. These approximations are used in an iterative method for solving the problem. The algorithm proceeds by solving quadratic programming subproblems to generate search directions. Approximate line searches ensure global convergence of the method to stationary points. The algorithm is conceptually simple and easy to implement. It generalizes efficient variable metric methods for minimax calculations.     

Stationary points and equilibria

Almost all existence results in mathematical economics and game theory rely on some type of fixed point theorem. However, in many cases it is much easier to apply an equivalent stationary point theorem. In this survey paper we show for various general equilibrium and game-theoretical models the usefulness of the stationary point approach to prove existence of equilibrium. We also consider path following methods to find a stationary point and illustrate such methods by an example. Finally, we discuss some refinements of stationary points and their application to solve the problem of equilibrium selection.