Continuous minimax optimization using modal intervals

Many real life problems can be stated as a continuous minimax optimization problem. Well-known applications to engineering, finance, optics and other fields demonstrate the importance of having reliable methods to tackle continuous minimax problems. In this paper a new approach to the solution of continuous minimax problems over reals is introduced, using tools based on modal intervals. Continuous minimax problems, and global optimization as a particular case, are stated as the computation of semantic extensions of continuous functions, one of the key concepts of modal intervals. Modal intervals techniques allow to compute, in a guaranteed way, such semantic extensions by means of an efficient algorithm. Several examples illustrate the behavior of the algorithms in unconstrained and constrained minimax problems.     

A simplex social spider algorithm for solving integer programming and minimax problems

In this paper, we propose a new hybrid social spider algorithm with simplex Nelder-Mead method in order to solve integer programming and minimax problems. We call the proposed algorithm a Simplex Social Spider optimization (SSSO) algorithm. In the the proposed SSSO algorithm, we combine the social spider algorithm with its powerful capability of performing exploration, exploitation, and the Nelder-Mead method in order to refine the best obtained solution from the standard social spider algorithm. In order to investigate the general performance of the proposed SSSO algorithm, we test it on 7 integer programming problems and 10 minimax problems and compare against 10 algorithms for solving integer programming problems and 9 algorithms for solving minimax problems. The experiments results show the efficiency of the proposed algorithm and its ability to solve integer and minimax optimization problems in reasonable time.     

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.     

An Algorithm Based on Active Sets and Smoothing for Discretized Semi-Infinite Minimax Problems

We present a new active-set strategy which can be used in conjunction with exponential (entropic) smoothing for solving large-scale minimax problems arising from the discretization of semi-infinite minimax problems. The main effect of the active-set strategy is to dramatically reduce the number of gradient calculations needed in the optimization. Discretization of multidimensional domains gives rise to minimax problems with thousands of component functions. We present an application to minimizing the sum of squares of the Lagrange polynomials to find good points for polynomial interpolation on the unit sphere in ℝ³. Our numerical results show that the active-set strategy results in a modified Armijo gradient or Gauss-Newton like methods requiring less than a quarter of the gradients, as compared to the use of these methods without our active-set strategy. Finally, we show how this strategy can be incorporated in an algorithm for solving semi-infinite minimax problems.     

非凸极小极大问题的优化算法与复杂度分析

非凸极小极大问题是近期国际上优化与机器学习、信号处理等交叉领域的一个重要研究前沿和热点,包括对抗学习、强化学习、分布式非凸优化等前沿研究方向的一些关键科学问题都归结为该类问题。国际上凸-凹极小极大问题的研究已取得很好的成果,但非凸极小极大问题不同于凸-凹极小极大问题,是有其自身结构的非凸非光滑优化问题,理论研究和求解难度都更具挑战性,一般都是NP-难的。重点介绍非凸极小极大问题的优化算法和复杂度分析方面的最新进展。     

Relaxation-based algorithms for minimax optimization problems with resource allocation applications

We consider minimax optimization problems where each term in the objective function is a continuous, strictly decreasing function of a single variable and the constraints are linear. We develop relaxation-based algorithms to solve such problems. At each iteration, a relaxed minimax problem is solved, providing either an optimal solution or a better lower bound. We develop a general methodology for such relaxation schemes for the minimax optimization problem. The feasibility tests and formulation of subsequent relaxed problems can be done by using Phase I of the Simplex method and the Farkas multipliers provided by the final Simplex tableau when the corresponding problem is infeasible. Such relaxation-based algorithms are particularly attractive when the minimax optimization problem exhibits additional structure. We explore special structures for which the relaxed problem is formulated as a minimax problem with knapsack type constraints; efficient algorithms exist to solve such problems. The relaxation schemes are also adapted to solve certain resource allocation problems with substitutable resources. There, instead of Phase I of the Simplex method, a max-flow algorithm is used to test feasibility and formulate new relaxed problems.Corresponding author.Work was partially done while visiting AT&T Bell Laboratories.     

Memetic particle swarm optimization

We propose a new Memetic Particle Swarm Optimization scheme that incorporates local search techniques in the standard Particle Swarm Optimization algorithm, resulting in an efficient and effective optimization method, which is analyzed theoretically. The proposed algorithm is applied to different unconstrained, constrained, minimax and integer programming problems and the obtained results are compared to that of the global and local variants of Particle Swarm Optimization, justifying the superiority of the memetic approach.     

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.     

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.     

A hybrid algorithm for linearly constrained minimax problems

Many real life problems can be stated as a minimax problem, such as economics, finance, management, engineering and other fields, which demonstrate the importance of having reliable methods to tackle minimax problems. In this paper, an algorithm for linearly constrained minimax problems is presented in which we combine the trust-region methods with the line-search methods and curve-search methods. By means of this hybrid technique, it avoids possibly solving the trust-region subproblems many times, and make better use of the advantages of different methods. Under weaker conditions, the global and superlinear convergence are achieved. Numerical experiments show that the new algorithm is robust and efficient.     

Intelligent Initialization and Adaptive Thresholding for Iterative Matrix Completion: Some Statistical and Algorithmic Theory for Adaptive-Impute

Over the past decade, various matrix completion algorithms have been developed. Thresholded singular value decomposition (SVD) is a popular technique in implementing many of them. A sizable number of studies have shown its theoretical and empirical excellence, but choosing the right threshold level still remains as a key empirical difficulty. This article proposes a novel matrix completion algorithm which iterates thresholded SVD with theoretically justified and data-dependent values of thresholding parameters. The estimate of the proposed algorithm enjoys the minimax error rate and shows outstanding empirical performances. The thresholding scheme that we use can be viewed as a solution to a nonconvex optimization problem, understanding of whose theoretical convergence guarantee is known to be limited. We investigate this problem by introducing a simpler algorithm, generalized- softImpute, analyzing its convergence behavior, and connecting it to the proposed algorithm.     

A scenario aggregation algorithm for the solution of stochastic dynamic minimax problems

In this paper, we present a scenario aggregation algorithm for the solution of the dynamic minimax problem in stochastic programming. We consider the case where the joint probability distribution has a known finite support. The algorithm applies the Alternating Direction of Multipliers Method on a reformulation of the minimax problem using a double duality framework. The problem is solved by decomposition into scenario sub-problems, which are deterministic multi-period problems. Convergence properties are deduced from the Alternating Direction of Multipliers. The resulting algorithm can be seen as an extension of Rockafellar and Wets Progressive Hedging algorithm to the dynamic minimax context.     

A nonmonotone line search based algorithm for distribution center location selected

The minimax optimization model introduced in this paper is an important model which has received some attention over the past years. In this paper, the application of minimax model on how to select the distribution center location is first introduced. Then a new algorithm with nonmonotone line search to solve the non-decomposable minimax optimization is proposed. We prove that the new algorithm is global Convergent. Numerical results show the proposed algorithm is effective.     

A lexicographic minimax algorithm for multiperiod resource allocation

Resource allocation problems are typically formulated as mathematical programs with some special structure that facilitates the development of efficient algorithms. We consider a multiperiod problem in which excess resources in one period can be used in subsequent periods. The objective minimizes lexicographically the nonincreasingly sorted vector of weighted deviations of cumulative activity levels from cumulative demands. To this end, we first develop a new minimax algorithm that minimizes the largest weighted deviation among all cumulative activity levels. The minimax algorithm handles resource constraints, ordering constraints, and lower and upper bounds. At each iteration, it fixes certain variables at their lower bounds, and sets groups of other variables equal to each other as long as no lower bounds are violated. The algorithm takes advantage of the problem's special structure; e.g., each term in the objective is a linear decreasing function of only one variable. This algorithm solves large problems very fast, orders of magnitude faster than well known linear programming packages. (The latter are, of course, not designed to solve such minimax problems efficiently.) The lexicographic procedure repeatedly employs the minimax algorithm described above to solve problems, each of the same format but with smaller dimension.     

Minimax problems of discrete optimization invariant under majority operators

A special class of discrete optimization problems that are stated as a minimax modification of the constraint satisfaction problem is studied. The minimax formulation of the problem generalizes the classical problem to realistic situations where the constraints order the elements of the set by the degree of their feasibility, rather than defining a dichotomy between feasible and infeasible subsets. The invariance of this ordering under an operator is defined, and the discrete minimization of functions invariant under majority operators is proved to have polynomial complexity. A particular algorithm for this minimization is described.     

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.     

An Algorithm for the Global Optimization of a Class of Continuous Minimax Problems

We propose an algorithm for the global optimization of continuous minimax problems involving polynomials. The method can be described as a discretization approach to the well known semi-infinite formulation of the problem. We proceed by approximating the infinite number of constraints using tools and techniques from semidefinite programming. We then show that, under appropriate conditions, the SDP approximation converges to the globally optimal solution of the problem. We also discuss the numerical performance of the method on some test problems. Financial support of EPSRC Grant GR/T02560/01 gratefully acknowledged.     

Corrected sequential linear programming for sparse minimax optimization

We present a new algorithm for nonlinear minimax optimization which is well suited for large and sparse problems. The method is based on trust regions and sequential linear programming. On each iteration a linear minimax problem is solved for a basic step. If necessary, this is followed by the determination of a minimum norm corrective step based on a first-order Taylor approximation. No Hessian information needs to be stored. Global convergence is proved. This new method has been extensively tested and compared with other methods, including two well known codes for nonlinear programming. The numerical tests indicate that in many cases the new method can find the solution in just as few iterations as methods based on approximate second-order information. The tests also show that for some problems the corrective steps give much faster convergence than for similar methods which do not employ such steps.Research supported partly by The Nordic Council of Ministers, The Icelandic Science Council, The University of Iceland Research Fund and The Danish Science Research Council.     

Existence and uniqueness of solution for quasi-equilibrium problems and fixed point problems on complete metric spaces with applications

In this paper, we presented new and important existence theorems of solution for quasi-equilibrium problems, and we show the uniqueness of its solution which is also a fixed point of some mapping. We also show that this unique solution can be obtained by Picard’s iteration method. We also get new minimax theorem, and existence theorems for common solution of fixed point and optimization problem on complete metric spaces. Our results are different from any existence theorems for quasi-equilibrium problems and minimax theorems in the literatures.     

一类无约束离散Minimax问题的区间调节熵算法

In this paper,a class of unconstrained discrete minimax problems is described,in which the objective functions are in C^1. The paper deals with this problem by means of taking the place of maximum-entropy function with adjustable entropy function. By constructing an interval extension of adjustable entropy function and some region deletion test rules, a new interval algorithm is presented. The relevant properties are proven, The minimax value and the localization of the minimax points of the problem can be obtained by this method. This method can overcome the flow problem in the maximum-entropy algorithm. Both theoretical and numerical results show that the method is reliable and efficient.