Semidefinite programming for min–max problems and games

We consider two min–max problems (1) minimizing the supremum of finitely many rational functions over a compact basic semi-algebraic set and (2) solving a 2-player zero-sum polynomial game in randomized strategies with compact basic semi-algebraic sets of pure strategies. In both problems the optimal value can be approximated by solving a hierarchy of semidefinite relaxations, in the spirit of the moment approach developed in Lasserre (SIAM J Optim 11:796–817, 2001; Math Program B 112:65–92, 2008). This provides a unified approach and a class of algorithms to compute Nash equilibria and min–max strategies of several static and dynamic games. Each semidefinite relaxation can be solved in time which is polynomial in its input size and practice on a sample of experiments reveals that few relaxations are needed for a good approximation (and sometimes even for finite convergence), a behavior similar to what was observed in polynomial optimization.     

Max–max,max–min,min–max and min–min knapsack problems with a parametric constraint

4OR - Max–max, max–min, min–max and min–min optimization problems with a knapsack-type constraint containing a single numerical parameter are studied. The goal is to present...     

Min–max and min–max regret versions of combinatorial optimization problems: A survey

Min–max and min–max regret criteria are commonly used to define robust solutions. After motivating the use of these criteria, we present general results. Then, we survey complexity results for the min–max and min–max regret versions of some combinatorial optimization problems: shortest path, spanning tree, assignment, min cut, min s–t cut, knapsack. Since most of these problems are NP-hard, we also investigate the approximability of these problems. Furthermore, we present algorithms to solve these problems to optimality.     

A weighted max–min model for fuzzy goal programming

After Narasimhan's pioneering study of applying fuzzy set theory to goal programming in 1980, many achievements in the field have been recorded. Most of them followed the max–min approach. However, when objectives have different levels of importance, only the weighted additive model of Tiwari et al. seems to be applicable. However, the shortcoming of the additive model is that the summation of quasiconcave functions may not be quasiconcave. This study proposes a novel weighted max–min model for fuzzy goal programming (FGP) and for fuzzy multiple objective decision-making. The proposed model adapts well to even the most complicated membership functions. Numerical examples demonstrate that the proposed model can be effectively incorporated with other approaches to FGP and is superior to the weighted additive approach.     

A majorization–minimization algorithm for split feasibility problems

The classical multi-set split feasibility problem seeks a point in the intersection of finitely many closed convex domain constraints, whose image under a linear mapping also lies in the intersection of finitely many closed convex range constraints. Split feasibility generalizes important inverse problems including convex feasibility, linear complementarity, and regression with constraint sets. When a feasible point does not exist, solution methods that proceed by minimizing a proximity function can be used to obtain optimal approximate solutions to the problem. We present an extension of the proximity function approach that generalizes the linear split feasibility problem to allow for non-linear mappings. Our algorithm is based on the principle of majorization–minimization, is amenable to quasi-Newton acceleration, and comes complete with convergence guarantees under mild assumptions. Furthermore, we show that the Euclidean norm appearing in the proximity function of the non-linear split feasibility problem can be replaced by arbitrary Bregman divergences. We explore several examples illustrating the merits of non-linear formulations over the linear case, with a focus on optimization for intensity-modulated radiation therapy.     

A continuation–domain decomposition algorithm for bifurcation problems

We study numerical solution branches of certain parameter-dependent problems defined on compact domains with various boundary conditions. The finite differences combined with the domain decomposition method are exploited to discretize the partial differential equations. We propose efficient numerical algorithms for solving the associated linear systems and for the detection of bifurcation points. Sample numerical results are reported. This revised version was published online in August 2006 with corrections to the Cover Date.     

A projected–gradient interior–point algorithm for complementarity problems

Interior–point algorithms are among the most efficient techniques for solving complementarity problems. In this paper, a procedure for globalizing interior–point algorithms by using the maximum stepsize is introduced. The algorithm combines exact or inexact interior–point and projected–gradient search techniques and employs a line–search procedure for the natural merit function associated with the complementarity problem. For linear problems, the maximum stepsize is shown to be acceptable if the Newton interior–point search direction is employed. Complementarity and optimization problems are discussed, for which the algorithm is able to process by either finding a solution or showing that no solution exists. A modification of the algorithm for dealing with infeasible linear complementarity problems is introduced which, in practice, employs only interior–point search directions. Computational experiments on the solution of complementarity problems and convex programming problems by the new algorithm are included.     

Reference variable methods of solving min–max optimization problems

In this paper, reference variable methods are proposed for solving nonlinear Minmax optimization problems with unconstraint or constraints for the first time, it uses reference decision vectors to improve the methods in Vincent and Goh (J Optim Theory Appl 75:501–519, 1992) such that its algorithm is convergent. In addition, a new method based on KKT conditions of min or max constrained optimization problems is also given for solving the constrained minmax optimization problems, it makes the constrained minmax optimization problems a problem of solving nonlinear equations by a complementarily function. For getting all minmax optimization solutions, the cost function f(x, y) can be constrained as M ₁ < f(x, y) < M ₂ by using different real numbers M ₁ and M ₂. To show effectiveness of the proposed methods, some examples are taken to compare with results in the literature, and it is easy to find that the proposed methods can get all minmax optimization solutions of minmax problems with constraints by using different M ₁ and M ₂, this implies that the proposed methods has superiority over the methods in the literature (that is based on different initial values to get other minmax optimization solutions).     

A smoothing projected Newton-type algorithm for semi-infinite programming

This paper presents a smoothing projected Newton-type method for solving the semi-infinite programming (SIP) problem. We first reformulate the KKT system of the SIP problem into a system of constrained nonsmooth equations. Then we solve this system by a smoothing projected Newton-type algorithm. At each iteration only a system of linear equations needs to be solved. The feasibility is ensured via the aggregated constraint under some conditions. Global and local superlinear convergence of this method is established under some standard assumptions. Preliminary numerical results are reported. Qi’s work is supported by the Hong Kong Research Grant Council. Ling’s work was supported by the Zhejiang Provincial National Science Foundation of China (Y606168). Tong’s work was done during her visit to The Hong Kong Polytechnic University. Her work is supported by the NSF of China (60474070) and the Technology Grant of Hunan (06FJ3038). Zhou’s work is supported by Australian Research Council.     

A smoothing-out technique for min—max optimization

In this paper, we suggest approximations for smoothing out the kinks caused by the presence of max or min operators in many non-smooth optimization problems. We concentrate on the continuous-discrete min—max optimization problem. The new approximations replace the original problem in some neighborhoods of the kink points. These neighborhoods can be made arbitrarily small, thus leaving the original objective function unchanged at almost every point ofR ⁿ . Furthermore, the maximal possible difference between the optimal values of the approximate problem and the original one, is determined a priori by fixing the value of a single parameter. The approximations introduced preserve properties such as convexity and continuous differentiability provided that each function composing the original problem has the same properties. This enables the use of efficient gradient techniques in the solution process. Some numerical examples are presented.     

On the resolution of certain discrete univariate max–min problems

Graph coloring is a classical NP-hard combinatorial optimization problem with many practical applications. A broad range of heuristic methods exist for tackling the graph coloring problem: from fast greedy algorithms to more time-consuming metaheuristics. Although the latter produce better results in terms of minimizing the number of colors, the former are widely employed due to their simplicity. These heuristic methods are centralized since they operate by using complete knowledge of the graph. However, in real-world environmets where each component only interacts with a limited number of other components, the only option is to apply decentralized methods. This paper explores a novel and simple algorithm for decentralized graph coloring that uses a fixed number of colors and iteratively reduces the edge conflicts in the graph. We experimentally demonstrate that, for most of the tested instances, the new algorithm outperforms a recent and very competitive algorithm for decentralized graph coloring in terms of coloring quality. In our experiments, the fixed number of colors used by the new algorithm is controlled in a centralized manner.     

A generalized min–max theorem for functionals of strongly indefinite sign

We consider non-linear Schrödinger equations of the following type: $$\begin{aligned} \left\{ \begin{array}{l} -\Delta u(x) + V(x)u(x)-q(x)|u(x)|^\sigma u(x) = \lambda u(x), \quad x\in \mathbb{R }^N \\ u\in H^1(\mathbb{R }^N)\setminus \{0\}, \end{array} \right. \end{aligned}$$ where $N\ge 1$ and $\sigma >0$ . We will concentrate on the case where both $V$ and $q$ are periodic, and we will analyse what happens for different values of $\lambda $ inside a spectral gap $]\lambda ^-,\lambda ^+[$ . We derive both the existence of multiple orbits of solutions and the bifurcation of solutions when $\lambda \nearrow \lambda ^+$ . Thereby we use the corresponding energy function ${I_\lambda }$ and we derive a new variational characterization of multiple critical levels for such functionals: in this way we get multiple orbits of solutions. One main advantage of our new view on some specific critical values $c_0(\lambda )\le c_1(\lambda )\le \cdots \le c_n(\lambda )\le \cdots $ is a multiplicity result telling us something about the number of critical points with energies below $c_n(\lambda )$ , even if for example two of these values $c_i(\lambda )$ and $c_j(\lambda )$ ( $0\le i<j\le n$ ) coincide. Let us close this summary by mentioning another main advantage of our variational characterization of critical levels: we present our result in an abstract setting that is suitable for other problems and we give some hints about such problems (like the case corresponding to a Coulomb potential $V$ ) at the end of the present paper.     

A method of adding–removing knots for solving smoothing problems with obstacles

We study a method of adding–removing knots that has been proposed in the literature for solving the smoothing problem with obstacles. The method uses the coefficients of natural splines in the expansion by radial basis functions. We present examples of cycling and counterexamples to possible use of some ideas. We also give some sufficient conditions for finiteness of the method.     

A primal–dual simplex algorithm for bi-objective network flow problems

In this paper we develop a primal–dual simplex algorithm for the bi-objective linear minimum cost network flow problem. This algorithm improves the general primal–dual simplex algorithm for multi-objective linear programs by Ehrgott et al. (J Optim Theory Appl 134:483–497, 2007). We illustrate the algorithm with an example and provide numerical results.     

Thresholded covering algorithms for robust and max–min optimization

In a two-stage robust covering problem, one of several possible scenarios will appear tomorrow and require to be covered, but costs are higher tomorrow than today. What should you anticipatorily buy today, so that the worst-case cost (summed over both days) is minimized? We consider the \(k\) -robust model where the possible scenarios tomorrow are given by all demand-subsets of size \(k\) . In this paper, we give the following simple and intuitive template for \(k\) -robust covering problems: having built some anticipatory solution, if there exists a single demand whose augmentation cost is larger than some threshold, augment the anticipatory solution to cover this demand as well, and repeat. We show that this template gives good approximation algorithms for \(k\) -robust versions of many standard covering problems: set cover, Steiner tree, Steiner forest, minimum-cut and multicut. Our \(k\) -robust approximation ratios nearly match the best bounds known for their deterministic counterparts. The main technical contribution lies in proving certain net-type properties for these covering problems, which are based on dual-rounding and primal–dual ideas; these properties might be of some independent interest. As a by-product of our techniques, we also get algorithms for max–min problems of the form: “given a covering problem instance, which \(k\) of the elements are costliest to cover?” For the problems mentioned above, we show that their \(k\) -max–min versions have performance guarantees similar to those for the \(k\) -robust problems.     

Outer limits of subdifferentials for min–max type functions

Abstract

We generalize the outer subdifferential construction suggested by Cánovas, Henrion, López and Parra for max type functions to pointwise minima of regular Lipschitz functions. We also answer an open question about the relation between the outer subdifferential of the support of a regular function and the end set of its subdifferential posed by Li, Meng and Yang.