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.     

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.     

A truncated aggregate smoothing Newton method for minimax problems

Aggregate function is a useful smoothing function to the max-function of some smooth functions and has been used to solve minimax problems, linear and nonlinear programming, generalized complementarity problems, etc. The aggregate function is a single smooth but complex function, its gradient and Hessian calculations are time-consuming. In this paper, a truncated aggregate smoothing stabilized Newton method for solving minimax problems is presented. At each iteration, only a small subset of the components in the max-function are aggregated, hence the number of gradient and Hessian calculations is reduced dramatically. The subset is adaptively updated with some truncating criterions, concerning only with computation of function values and not their gradients or Hessians, to guarantee the global convergence and, for the inner iteration, locally quadratic convergence with as few computational cost as possible. Numerical results show the efficiency of the proposed algorithm.     

Linear bilevel programs with multiple objectives at the upper level

Bilevel programming has been proposed for dealing with decision processes involving two decision makers with a hierarchical structure. They are characterized by the existence of two optimization problems in which the constraint region of the upper level problem is implicitly determined by the lower level optimization problem. Focus of the paper is on general bilevel optimization problems with multiple objectives at the upper level of decision making. When all objective functions are linear and constraints at both levels define polyhedra, it is proved that the set of efficient solutions is non-empty. Taking into account the properties of the feasible region of the bilevel problem, some methods of computing efficient solutions are given based on both weighted sum scalarization and scalarization techniques. All the methods result in solving linear bilevel problems with a single objective function at each level.     

Solving knapsack sharing problems with general tradeoff functions

A knapsack sharing problem is a maximin or minimax mathematical programming problem with one or more knapsack constraints (an inequality constraint with all non-negative coefficients). All knapsack sharing algorithms to date have assumed that the objective function is composed of single variable functions called tradeoff functions which are strictly increasing continuous functions. This paper develops optimality conditions and algorithms for knapsack sharing problems with any type of continuous tradeoff function including multiple-valued and staircase functions which can be increasing, decreasing, unimodal, bimodal, or even multi-modal. To do this, optimality conditions are developed for a special type of multiple-valued, nondecreasing tradeoff function called an ascending function. The optimal solution to any knapsack sharing problem can then be found by solving an equivalent problem where all the tradeoff functions have been transformed to ascending functions. Polynomial algorithms are developed for piecewise linear tradeoff functions with a fixed number of breakpoints. The techniques needed to construct efficient algorithms for any type of tradeoff function are discussed.     

Smoothing methods for nonsmooth, nonconvex minimization

We consider a class of smoothing methods for minimization problems where the feasible set is convex but the objective function is not convex, not differentiable and perhaps not even locally Lipschitz at the solutions. Such optimization problems arise from wide applications including image restoration, signal reconstruction, variable selection, optimal control, stochastic equilibrium and spherical approximations. In this paper, we focus on smoothing methods for solving such optimization problems, which use the structure of the minimization problems and composition of smoothing functions for the plus function (x)₊. Many existing optimization algorithms and codes can be used in the inner iteration of the smoothing methods. We present properties of the smoothing functions and the gradient consistency of subdifferential associated with a smoothing function. Moreover, we describe how to update the smoothing parameter in the outer iteration of the smoothing methods to guarantee convergence of the smoothing methods to a stationary point of the original minimization problem.     

Pattern search methods for finite minimax problems

In this paper, we propose pattern search methods for finite minimax problems. Due to the nonsmoothness of this class of problems, we convert the original problem into a smooth one by using a smoothing technique based on the exponential penalty function of Kort and Bertsekas, which technique depends on a smoothing parameter that control the approximation to the finite minimax problems. The proposed methods are based on a sampling of the smooth function along a set of suitable search directions and on an updating rule for the step-control parameter. Under suitable conditions, we get the global convergence results despite the fact that pattern search methods do not have explicit information concerning the gradient and consequently are unable to enforce explicitly a notion of sufficient feasible decrease.     

Efficiency and Optimality in Minisum,Minimax 0-1 Programming Problems

Inspired by an increasing interest in multicriteria 0-1 programming problems in general and by a recent result on the reducibility of minimax to minisum problems in particular, we consider properties of efficient and optimal solutions to two-criteria (minisum and minimax) 0-1 programming problems with any constraint set.A solution procedure is suggested for solving problems whose objective functions are a convex combination of these criteria. The solution properties are illustrated with examples mainly within the context of locational decision problems.     

Using modified maximum regret for finding a necessarily efficient solution in an interval MOLP problem

The current research concerns multiobjective linear programming problems with interval objective functions coefficients. It is known that the most credible solutions to these problems are necessarily efficient ones. To solve the problems, this paper attempts to propose a new model with interesting properties by considering the minimax regret criterion. The most important property of the new model is attaining a necessarily efficient solution as an optimal one whenever the set of necessarily efficient solutions is nonempty. In order to obtain an optimal solution of the new model, an algorithm is suggested. To show the performance of the proposed algorithm, numerical examples are given. Finally, some special cases are considered and their characteristic features are highlighted.     

Simple Sequential Quadratically Constrained Quadratic Programming Feasible Algorithm with Active Identification Sets for Constrained Minimax Problems

In this paper, the nonlinear minimax problems with inequality constraints are discussed. Based on the idea of simple sequential quadratically constrained quadratic programming algorithm for smooth constrained optimization, an alternative algorithm for solving the discussed problems is proposed. Unlike the previous work, at each iteration, a feasible direction of descent called main search direction is obtained by solving only one subprogram which is composed of a convex quadratic objective function and simple quadratic inequality constraints without the second derivatives of the constrained functions. Then a high-order correction direction used to avoid the Maratos effect is computed by updating the main search direction with a system of linear equations. The proposed algorithm possesses global convergence under weak Mangasarian–Fromovitz constraint qualification and superlinear convergence under suitable conditions with the upper-level strict complementarity. At last, some preliminary numerical results are reported.     

Bounded knapsack sharing

A bounded knapsack sharing problem is a maximin or minimax mathematical programming problem with one or more linear inequality constraints, an objective function composed of single variable continuous functions called tradeoff functions, and lower and upper bounds on the variables. A single constraint problem which can have negative or positive constraint coefficients and any type of continuous tradeoff functions (including multi-modal, multiple-valued and staircase functions) is considered first. Limiting conditions where the optimal value of a variable may be plus or minus infinity are explicitly considered. A preprocessor procedure to transform any single constraint problem to a finite form problem (an optimal feasible solution exists with finite variable values) is developed. Optimality conditions and three algorithms are then developed for the finite form problem. For piecewise linear tradeoff functions, the preprocessor and algorithms are polynomially bounded. The preprocessor is then modified to handle bounded knapsack sharing problems with multiple constraints. An optimality condition and algorithm is developed for the multiple constraint finite form problem. For multiple constraints, the time needed for the multiple constraint finite form algorithm is the time needed to solve a single constraint finite form problem multiplied by the number of constraints. Some multiple constraint problems cannot be transformed to multiple constraint finite form problems.     

求连续minimax问题整体解的区间算法

1 引 言 Minimax问题是一类重要的数学规划问题,它来源于实际并有极广泛的应用([1],[2]).用区间数学方法求解 minimax问题已取得了一些成果.文[1]对由 C2类函数构成的无约束连续 minimax问题进行了研究,建立了相应的区间算法,文[6]～[11]分别讨论和建立了无约束和不等式约束的离散minimax问题的区间算法.文[12]、[13]则讨论了最坏     

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.     

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.     

一类非光滑优化问题的区间算法

1引言 考虑下面离散minimax问题x∈X~(o)≤i≤m min max{f_i(x)},(1.1)     

求广义几何规划全局最优解的线性化方法

对广义几何规划问题(GGP)提出了一个确定型全局优化算法，这类优化问题能广泛应用于工程设计和非线性系统的鲁棒稳定性分析等实际问题中，使用指数变换及对目标函数和约束函数的线性下界估计，建立了GGP的松弛线性规划(RLP)，通过对RLP可行域的细分以及一系列RLP的求解过程，从理论上证明了算法能收敛到GGP的全局最优解，对一个化学工程设计问题应用本文算法，数值实验表明本文方法是可行的。     

Reducibility of minimax to minisum 0–1 programming problems

We consider 0–1 programming problems with a minimax objective function and any set of constraints. Upon appropriate transformations of its cost coefficients, such a minimax problem can be reduced to a linear minisum problem with the same set of feasible solutions such that an optimal solution to the latter will also solve the original minimax problem.Although this reducibility applies for any 0–1 programming problem, it is of particular interest for certain locational decision models. Among the obvious implications are that an algorithm for solving a p-median (minisum) problem in a network will also solve a corresponding p-center (minimax) problem.It should be emphasized that the results presented will in general only hold for 0–1 problems due to intrinsic properties of the minimax criterion.     

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.     

极大熵方法与二次规划子问题的显式解

本文对混合约束极大极小问题的目标函数与约束分别用熵函数来逼近,讨论了逼近问题的二次规划子问题的搜索方向的显式形式,并给出了极大极小问题和多目标规划的二次规划予问题的显式解。将所得结果用于相应的算法中,可提高算法的有效性。     

Efficient solution generation for multiple objective linear programming based on extreme ray generation method

In this paper we consider solution generation method for multiple objective linear programming problems. The set of efficient or Pareto optimal solutions for the problems can be regarded as global information in multiple objective decision making situation. In the past three decades as solution generation techniques various conventional algorithms based on simplex-like approach with heavy computational burden were developed. Therefore, the development of novel and useful directions in efficient solution generation method have been desired. The purpose of this paper is to develop theoretical results and computational techniques of the efficient solution generation method based on extreme ray generation method that sequentially generates efficient points and rays by adding inequality constraints of the polyhedral feasible region.