A smooth method for the finite minimax problem

We consider unconstrained minimax problems where the objective function is the maximum of a finite number of smooth functions. We prove that, under usual assumptions, it is possible to construct a continuously differentiable function, whose minimizers yield the minimizers of the max function and the corresponding minimum values. On this basis, we can define implementable algorithms for the solution of the minimax problem, which are globally convergent at a superlinear convergence rate. Preliminary numerical results are reported.This research was partially supported by the National Research Program on Metodi di ottimizzazione per le decisioni, Ministero dell'Università e della Ricerca Scientifica e Tecnologica, Italy.     

Second-Order Duality for Nondifferentiable Minimax Programming Involving Generalized Type I Functions

We apply the optimality conditions of nondifferentiable minimax programming to formulate a general second-order Mond-Weir dual to the nondifferentiable minimax programming involving second-order pseudo-quasi Type I functions. We establish also weak, strong, and strict converse duality theorems.Research supported by the Council of Scientific and Industrial Research, New Delhi, India, Research Scheme-25 (0132)/04/EMR-II.     

极大极小问题的广义投影算法

研究了无约束极大极小问题.通过引入一个可微的辅助函数,利用广义投影技术产生下降搜索方向,结合Armjio非精确线搜索建立了一个广义梯度投影算法.在初始点任意的条件下,证明了算法的全局收敛性.     

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.     

Variable Programming: A Generalized Minimax Problem. Part II: Algorithms

In this part of the two-part series of papers, algorithms for solving some variable programming (VP) problems proposed in Part I are investigated. It is demonstrated that the non-differentiability and the discontinuity of the maximum objective function, as well as the summation objective function in the VP problems constitute difficulty in finding their solutions. Based on the principle of statistical mechanics, we derive smooth functions to approximate these non-smooth objective functions with specific activated feasible sets. By transforming the minimax problem and the corresponding variable programming problems into their smooth versions we can solve the resulting problems by some efficient algorithms for smooth functions. Relevant theoretical underpinnings about the smoothing techniques are established. The algorithms, in which the minimization of the smooth functions is carried out by the standard quasi-Newton method with BFGS formula, are tested on some standard minimax and variable programming problems. The numerical results show that the smoothing techniques yield accurate optimal solutions and that the algorithms proposed are feasible and efficient.This work was supported by the RGC grant CUHK 152/96H of the Hong Kong Research Grant Council.     

Variable Programming: A Generalized Minimax Problem. Part I: Models and Theory

In this two-part series of papers, a new generalized minimax optimization model, termed variable programming (VP), is developed to solve dynamically a class of multi-objective optimization problems with non-decomposable structure. It is demonstrated that such type of problems is more general than existing optimization models. In this part, the VP model is proposed first, and the relationship between variable programming and the general constrained nonlinear programming is established. To illustrate its practicality, problems on investment and the low-side-lobe conformal antenna array pattern synthesis to which VP can be appropriately applied are discussed for substantiation. Then, theoretical underpinnings of the VP problems are established. Difficulties in dealing with the VP problems are discussed. With some mild assumptions, the necessary conditions for the unconstrained VP problems with arbitrary and specific activated feasible sets are derived respectively. The necessary conditions for the corresponding constrained VP problems with the mild hypotheses are also examined. Whilst discussion in this part is concentrated on the formulation of the VP model and its theoretical underpinnings, construction of solution algorithms is discussed in Part II.This work was supported by the RGC grant CUHK 152/96H of the Hong Kong Research Grant Council.     

广义拟凹映射和向量极小极大不等式

引入z-广义c-拟凹向量映射,研究它和广义KKM映射的等价性,应用这些结果改进了-Ky Fan向量极小极大不等式,并且获得了一强向量极小极大不等式．     

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.     

Algorithms for a class of nondifferentiable problems

A nonlinear programming problem with nondifferentiabilities is considered. The nondifferentiabilities are due to terms of the form min(f ₁(x),...,f _n(x)), which may enter nonlinearly in the cost and the constraints. Necessary and sufficient conditions are developed. Two algorithms for solving this problem are described, and their convergence is studied. A duality framework for interpretation of the algorithms is also developed.This work was supported in part by the National Science Foundation under Grant No. ENG-74-19332 and Grant No. ECS-79-19396, in part by the U.S. Air Force under Grant AFOSR-78-3633, and in part by the Joint Services Electronics Program (U.S. Army, U.S. Navy, and U.S. Air Force) under Contract N00014-79-C-0424.     

A Generalized Conjugate Gradient Algorithm

We present modifications of the generalized conjugate gradient algorithm of Liu and Storey for unconstrained optimization problems (Ref. 1), extending its applicability to situations where the search directions are not defined. The use of new search directions is proposed and one additional condition is imposed on the inexact line search. The convergence of the resulting algorithm can be established under standard conditions for a twice continuously differentiable function with a bounded level set. Algorithms based on these modifications have been tested on a number of problems, showing considerable improvements. Comparisons with the BFGS and other quasi-Newton methods are also given.     

Optimal Infinite-Horizon Multicriteria Feedback Control of Stationary Systems with Minimax Objectives and Bounded Disturbances

This article presents a methodology for exploring the solution surface in a class of multicriteria infinite-horizon closed-loop optimal control problems with bounded disturbances and minimax objectives. The maximum is taken with respect to both time and all sequences of disturbances; that is, the value of a criterion is the maximal stage cost for the worst possible sequence of disturbances. It is assumed that the system and the cost functions are stationary. The proposed solution method is based on reference point approach and inverse mapping from the space of objectives into the space of control policies and their domains in state space.     

Minimax approach to structural optimization problems

The problem of determining the shape of an elastic body which is optimal for a whole class of loads is formulated. Its general solution scheme, based on a minimax approach, is indicated. The optimization problem of an elastic beam is studied for both the simply supported case and the cantilevered case, and some specific properties of the optimal shape are determined.The author is grateful to Professor A. I. Lurie, Professor F. L. Chernousko, and Professor G. S. Shapiro for useful discussions of the results.     

On Minimax Fractional Optimality and Duality with Generalized Convexity

In this paper, we establish several sufficient optimality conditions for a class of generalized minimax fractional programming. Based on the sufficient conditions, a new dual model is constructed and duality results are derived. Our study naturally unifies and extends some previously known results in the framework of generalized convexity and dual models. Mathematics Subject Classifications: 90C25, 90C32, 90C47.     

Spherical Minimax Location Problem

This paper presents an algorithm for determining a minimax location to service demand points that are equally weighted and distributed over a sphere. The norm under consideration is geodesic. The algorithm presented here is based on enumeration and has a polynomial time complexity.     

Portfolio Selection Problem with Minimax Type Risk Function

The investor's preference in risk estimation of portfolio selection problems is important as it influences investment strategies. In this paper a minimax risk criterion is considered. Specifically, the investor aims to restrict the standard deviation for each of the available stocks. The corresponding portfolio optimization problem is formulated as a linear program. Hence it can be implemented easily. A capital asset pricing model between the market portfolio and each individual return for this model is established using nonsmooth optimization methods. Some numerical examples are given to illustrate our approach for the risk estimation.     

Testing Parallel Variable Transformation

This paper studies performance of the parallel variable transformation (PVT) algorithm for unconstrained nonlinear optimization through numerical experiments on a Fujitsu VPP500, one of the most up-to-date vector parallel computers. Special attention is paid to a particular form of the PVT algorithm that is regarded as a generalization of the block Jacobi algorithm that allows overlapping of variables among processors. Implementation strategies on the VPP500 are described in detail and results of numerical experiments are reported.     

一般约束极大极小优化问题一个强收敛的广义梯度投影算法

该文考虑求解带非线性不等式和等式约束的极大极小优化问题,借助半罚函数思想,提出了一个新的广义投影算法.该算法具有以下特点:由一个广义梯度投影显式公式产生的搜索方向是可行下降的;构造了一个新型的最优识别控制函数;在适当的假设条件下具有全局收敛性和强收敛性.最后,通过初步的数值试验验证了算法的有效性.     

一般无约束优化问题的广义拟牛顿法

对一般目标函数极小化问题的拟牛顿法及其全局收敛性的研究,已经成为拟牛顿法理论中最基本的开问题之一．本文对这个问题做了进一步的研究,对无约束优化问题提出一类新的广义拟牛顿算法,并结合Goldstein线搜索证明了算法对一般非凸目标函数极小化问题的全局收敛性．     

Convergence and Error Bound of a Method for Solving Variational Inequality Problems via the Generalized D-Gap Function

The variational inequality problem (VIP) can be reformulated as an unconstrained minimization problem through the generalized D-gap function. Recently, a hybrid Newton-type method was proposed by Peng and Fukushima for minimizing a special form of the generalized D-gap function. In this paper, the hybrid Newton-type algorithm is extended to minimize the general form g of the generalized D-gap function. It is shown that the algorithm has nice convergence properties. Under some reasonable conditions, it is proved that the algorithm is locally and globally convergent. Moreover, it is proved that the function g has bounded level sets for strongly monotone VIP. An error bound of the algorithm is obtained.     

On the Use of Augmented Lagrangians in the Solution of Generalized Semi-Infinite Min-Max Problems

We present an approach for the solution of a class of generalized semi-infinite optimization problems. Our approach uses augmented Lagrangians to transform generalized semi-infinite min-max problems into ordinary semi-infinite min-max problems, with the same set of local and global solutions as well as the same stationary points. Once the transformation is effected, the generalized semi-infinite min-max problems can be solved using any available semi-infinite optimization algorithm. We illustrate our approach with two numerical examples, one of which deals with structural design subject to reliability constraints.