On penalty methods for minimax problems

Penalty algorithms for constrained minimax problems typically involve a sequence of unconstrained approximates which is pointwise monotone in each variable. This paper generalizes convergence results for a wider class of algorithms while imposing conditions which are close to being minimal.Sponsored in part by a grant from the Norwegian Council of Scientific and Technological Research.     

A direct method of linearization for continuous minimax problems

We consider the problem of minimizing a nondifferentiable function that is the pointwise maximum over a compact family of continuously differentiable functions. We suppose that a certain convex approximation to the objective function can be evaluated. An iterative method is given which uses as successive search directions approximate solutions of semi-infinite quadratic programming problems calculated via a new generalized proximity algorithm. Inexact line searches ensure global convergence of the method to stationary points.This work was supported by Project No. CPBP-02.15/2.1.1.     

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.     

On a class of non-smooth dynamical systems: a sufficient condition for smooth versus non-smooth solutions

In this paper we present a possible classification of the elements of a class of dynamical systems, whose underlying mathematical models contain non-smooth components. For this purpose a sufficient condition is introduced. To illustrate and motivate this classification, three nontrivial and realistic examples are considered.     

A direct method for accurate solution and gradient computations for elliptic interface problems

Numerical Algorithms - Recently, an augmented IIM (Li et al. SIAM J. Numer. Anal. 55, 570–597 2017) has been developed and analyzed for some interface problems. The augmented IIM can provide...     

Single-level reformulations of a specific non-smooth bilevel programming problem and their applications

Optimization Letters - We study a bilevel programming problem (BLPP) with a maximin lower level problem which is non-smooth and sometimes even non-convex. We reformulate such a non-smooth BLPP as a...     

On solutions of minimax test problems for special capacities

Summary Solutions to minimax test problems between neighbourhoods generated by specially defined capacities are discussed. The capacities are superpositions of probability measures and concave functions, so the paper covers most of the earlier results of Huber and Rieder concerning minimax testing between -contamination and total variation neighbourhoods. It is shown that the Neyman-Pearson lemma for 2-alternating capacities, proved by Huber and Strassen, can be applied to test problems between noncompact neighbourhoods of probability measures. It turns out that the Radon-Nikodym derivative between the special capacities is usually a nondecreasing function of the truncated likelihood ratio of some probability measures.     

On minimax eigenvalue problems via constrained optimization

In this paper, we consider the problem of minimizing the maximum eigenvalues of a matrix. The aim is to show that this optimization problem can be transformed into a standard nonlinearly constrained optimization problem, and hence is solvable by existing software packages. For illustration, two examples are solved by using the proposed method.     

On the need for special purpose algorithms for minimax eigenvalue problems

It has been recently reported that minimax eigenvalue problems can be formulated as nonlinear optimization problems involving smooth objective and constraint functions. This result seems very appealing since minimax eigenvalue problems are known to be typically nondifferentiable. In this paper, we show, however, that general purpose nonlinear optimization algorithms usually fail to find a solution to these smooth problems even in the simple case of minimization of the maximum eigenvalue of an affine family of symmetric matrices, a convex problem for which efficient algorithms are available.This work was supported in part by NSF Engineering Research Centers Program No. NSFD-CDR-88-03012 and NSF Grant DMC-84-20740. The author wishes to thank Drs. M. K. H. Fan and A. L. Tits for their many useful suggestions.     

On the lexicographic minimax approach to location problems

When locating public facilities, the distribution of travel distances among the service recipients is an important issue. It is usually tackled with the minimax (center) solution concept. The minimax solution concept, despite the most commonly used in the public sector location models, is criticized as it does not comply with the major principles of the efficiency and equity modeling. In this paper we develop a concept of the lexicographic minimax solution (lexicographic center) being a refinement of the standard minimax approach to location problems. We show that the lexicographic minimax approach complies with both the Pareto-optimality (efficiency) principle (crucial in multiple criteria optimization) and the principle of transfers (essential for equity measures) whereas the standard minimax approach may violate both these principles. Computational algorithms are developed for the lexicographic minimax solution of discrete location problems.     

On the accurate identification of active set for constrained minimax problems

In this paper, the problem of identifying the active constraints for constrained nonlinear programming and minimax problems at an isolated local solution is discussed. The correct identification of active constraints can improve the local convergence behavior of algorithms and considerably simplify algorithms for inequality constrained problems, so it is a useful adjunct to nonlinear optimization algorithms. Facchinei et al. [F. Facchinei, A. Fischer, C. Kanzow, On the accurate identification of active constraints, SIAM J. Optim. 9 (1998) 14-32] introduced an effective technique which can identify the active set in a neighborhood of a solution for nonlinear programming. In this paper, we first improve this conclusion to be more suitable for infeasible algorithms such as the strongly sub-feasible direction method and the penalty function method. Then, we present the identification technique of active constraints for constrained minimax problems without strict complementarity and linear independence. Some numerical results illustrating the identification technique are reported.     

On the complexity of the exchange algorithm for minimax optimization problems

We present an exchange algorithm for the solution of minimax optimization problems involving convex functions. For a certain class of functions, the complexity of this algorithm is shown to be either linear in the number of functions, or at least squared in that number.     

Nonmonotone line search for minimax problems

It was recently shown that, in the solution of smooth constrained optimization problems by sequential quadratic programming (SQP), the Maratos effect can be prevented by means of a certain nonmonotone (more precisely, three-step or four-step monotone) line search. Using a well-known transformation, this scheme can be readily extended to the case of minimax problems. It turns out however that, due to the structure of these problems, one can use a simpler scheme. Such a scheme is proposed and analyzed in this paper. Numerical experiments indicate a significant advantage of the proposed line search over the Armijo search.This research was supported in part by NSF Engineering Research Centers Program No. NSFD-CDR-88-03012, by NSF Grant No. DMC-88-15996, and by a grant from the Westinghouse Corporation.     

A dual algorithm for minimax problems

In this paper, a dual algorithm, based on a smoothing function of Bertsekas (1982), is established for solving unconstrained minimax problems. It is proven that a sequence of points, generated by solving a sequence of unconstrained minimizers of the smoothing function with changing parametert, converges with Q-superlinear rate to a Kuhn-Tucker point locally under some mild conditions. The relationship between the condition number of the Hessian matrix of the smoothing function and the parameter is studied, which also validates the convergence theory. Finally the numerical results are reported to show the effectiveness of this algorithm.     

Stochastic approximation algorithm for minimax problems

A stochastic approximation algorithm for minimax optimization problems is analyzed. At each iterate, it performs one random experiment, based on which it computes a direction vector. It is shown that, under suitable conditions, it a.s. converges to the set of points satisfying necessary optimality conditions. The algorithm and its analysis bring together ideas from stochastic approximation and nondifferentiable optimization.     

Nonmonotone algorithm for minimax optimization problems

Many real life problems can be stated as a minimax optimization problem, such as the problems in economics, finance, management, engineering and other fields. In this paper, we present an algorithm with nonmonotone strategy and second-order correction technique for minimax optimization problems. Using this scheme, the new algorithm can overcome the difficulties of the Maratos effect occurred in the nonsmooth optimization, and the global and superlinear convergence of the algorithm can be achieved accordingly. Numerical experiments indicate some advantages of this scheme.     

An algebra for piecewise-linear minimax problems

A piecewise-linear function whose definition involves the operator max and min may be reformulated as a ‘sum-of-partial-fractions’ by use of an algebraic structure $\text{J}$ and so may be ‘rationalized’ to become a ‘quotient-of-polynomials’ in the notation of $\text{J}$ We show that these ‘partial fractions’ and ‘polynomials’ have algebraic properties closely analogous to those of their counterparts in traditional elementary algebra: in particular an analogue of the fundamental theorem of algebra holds. These formal properties lead to straightforward procedures for finding maxima and minima of such functions.     

An existence result for non-smooth vibro-impact problems

We are interested in mechanical systems with a finite number of degrees of freedom submitted to frictionless unilateral constraints. We consider the case of a convex, non-smooth set of admissible positions given by , ν?1, and we assume inelastic shocks at impacts. We propose a time-discretization of the measure differential inclusion which describes the dynamics and we prove the convergence of the approximate solutions to a limit motion which satisfies the constraints. Moreover, if the geometric properties ensuring continuity on data hold at the limit, we show that the transmission of velocities at impacts follows the inelastic shocks rule.     

Standard bi-quadratic optimization problems and unconstrained polynomial reformulations

A so-called Standard Bi-Quadratic Optimization Problem (StBQP) consists in minimizing a bi-quadratic form over the Cartesian product of two simplices (so this is different from a Bi-Standard QP where a quadratic function is minimized over the same set). An application example arises in portfolio selection. In this paper we present a bi-quartic formulation of StBQP, in order to get rid of the sign constraints. We study the first- and second-order optimality conditions of the original StBQP and the reformulated bi-quartic problem over the product of two Euclidean spheres. Furthermore, we discuss the one-to-one correspondence between the global/local solutions of StBQP and the global/local solutions of the reformulation. We introduce a continuously differentiable penalty function. Based upon this, the original problem is converted into the problem of locating an unconstrained global minimizer of a (specially structured) polynomial of degree eight.