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.     

On the projected subgradient method for nonsmooth convex optimization in a Hilbert space

We consider the method for constrained convex optimization in a Hilbert space, consisting of a step in the direction opposite to an _k -subgradient of the objective at a current iterate, followed by an orthogonal projection onto the feasible set. The normalized stepsizes _k are exogenously given, satisfying _{k=0 k} = , _{k=0 k} ² < , and _k is chosen so that _{k k} for some > 0. We prove that the sequence generated in this way is weakly convergent to a minimizer if the problem has solutions, and is unbounded otherwise. Among the features of our convergence analysis, we mention that it covers the nonsmooth case, in the sense that we make no assumption of differentiability off, and much less of Lipschitz continuity of its gradient. Also, we prove weak convergence of the whole sequence, rather than just boundedness of the sequence and optimality of its weak accumulation points, thus improving over all previously known convergence results. We present also convergence rate results. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Research of this author was partially supported by CNPq grant nos. 301280/86 and 300734/95-6.     

Necessary conditions for constrained optimization problems with semicontinuous and continuous data

We consider nonsmooth constrained optimization problems with semicontinuous and continuous data in Banach space and derive necessary conditions without constraint qualification in terms of smooth subderivatives and normal cones. These results, in different versions, are set in reflexive and smooth Banach spaces.

     

Convergence of the Augmented Lagrangian Method for Nonlinear Optimization Problems over Second-Order Cones

The paper analyzes the rate of local convergence of the augmented Lagrangian method for nonlinear second-order cone optimization problems. Under the constraint nondegeneracy condition and the strong second order sufficient condition, we demonstrate that the sequence of iterate points generated by the augmented Lagrangian method locally converges to a local minimizer at a linear rate, whose ratio constant is proportional to 1/τ with penalty parameter τ not less than a threshold . Importantly and interestingly enough, the analysis does not require the strict complementarity condition. Supported by the National Natural Science Foundation of China under Project 10771026 and by the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry.     

Multicriteria analysis in decision making under information uncertainty

This paper presents results of research related to multicriteria decision making under information uncertainty. The Bellman–Zadeh approach to decision making in a fuzzy environment is utilized for analyzing multicriteria optimization models (X,M models) under deterministic information. Its application conforms to the principle of guaranteed result and provides constructive lines in obtaining harmonious solutions on the basis of analyzing associated maxmin problems. This circumstance permits one to generalize the classic approach to considering the uncertainty of quantitative information (based on constructing and analyzing payoff matrices reflecting effects which can be obtained for different combinations of solution alternatives and the so-called states of nature) in monocriteria decision making to multicriteria problems. Considering that the uncertainty of information can produce considerable decision uncertainty regions, the resolving capacity of this generalization does not always permit one to obtain unique solutions. Taking this into account, a proposed general scheme of multicriteria decision making under information uncertainty also includes the construction and analysis of the so-called X,R models (which contain fuzzy preference relations as criteria of optimality) as a means for the subsequent contraction of the decision uncertainty regions. The paper results are of a universal character and are illustrated by a simple example.     

An effective and simple heuristic for the set covering problem

This paper investigates the development of an effective heuristic to solve the set covering problem (SCP) by applying the meta-heuristic Meta-RaPS (Meta-heuristic for Randomized Priority Search). In Meta-RaPS, a feasible solution is generated by introducing random factors into a construction method. Then the feasible solutions can be improved by an improvement heuristic. In addition to applying the basic Meta-RaPS, the heuristic developed herein integrates the elements of randomizing the selection of priority rules, penalizing the worst columns when the searching space is highly condensed, and defining the core problem to speedup the algorithm. This heuristic has been tested on 80 SCP instances from the OR-Library. The sizes of the problems are up to 1000 rows × 10,000 columns for non-unicost SCP, and 28,160 rows × 11,264 columns for the unicost SCP. This heuristic is only one of two known SCP heuristics to find all optimal/best known solutions for those non-unicost instances. In addition, this heuristic is the best for unicost problems among the heuristics in terms of solution quality. Furthermore, evolving from a simple greedy heuristic, it is simple and easy to code. This heuristic enriches the options of practitioners in the optimization area.     

Comparative analysis of the machine repair Problem with imperfect coverage and service pressure condition

In this paper we analyze the warm-standby M/M/R machine repair problem with multiple imperfect coverage which involving the service pressure condition. When an operating machine (or warm standby) fails, it may be immediately detected, located, and replaced with a coverage probability c by a standby if one is available. We use a recursive method to develop the steady-state analytic solutions which are used to calculate various system performance measures. The total expected profit function per unit time is derived to determine the joint optimal values at the maximum profit. We first utilize the direct search method to measure the various characteristics of the profit function followed by Quasi-Newton method to search the optimal solutions. Furthermore, the particle swarm optimization (PSO) algorithm is implemented to find the optimal combinations of parameters in the pursuit of maximum profit. Finally, a comparative analysis of the Quasi-Newton method with the PSO algorithm has demonstrated that the PSO algorithm provides a powerful tool to perform the optimization problem.     

On the structure of multiobjective combinatorial search space: MNK-landscapes with correlated objectives

The structure of the search space explains the behavior of multiobjective search algorithms, and helps to design well-performing approaches. In this work, we analyze the properties of multiobjective combinatorial search spaces, and we pay a particular attention to the correlation between the objective functions. To do so, we extend the multiobjective NK-landscapes in order to take the objective correlation into account. We study the co-influence of the problem dimension, the degree of non-linearity, the number of objectives, and the objective correlation on the structure of the Pareto optimal set, in terms of cardinality and number of supported solutions, as well as on the number of Pareto local optima. This work concludes with guidelines for the design of multiobjective local search algorithms, based on the main fitness landscape features.     

Robust nonlinear optimization with conic representable uncertainty set

The robust optimization methodology is known as a popular method dealing with optimization problems with uncertain data and hard constraints. This methodology has been applied so far to various convex conic optimization problems where only their inequality constraints are subject to uncertainty. In this paper, the robust optimization methodology is applied to the general nonlinear programming (NLP) problem involving both uncertain inequality and equality constraints. The uncertainty set is defined by conic representable sets, the proposed uncertainty set is general enough to include many uncertainty sets, which have been used in literature, as special cases. The robust counterpart (RC) of the general NLP problem is approximated under this uncertainty set. It is shown that the resulting approximate RC of the general NLP problem is valid in a small neighborhood of the nominal value. Furthermore a rather general class of programming problems is posed that the robust counterparts of its problems can be derived exactly under the proposed uncertainty set. Our results show the applicability of robust optimization to a wider area of real applications and theoretical problems with more general uncertainty sets than those considered so far. The resulting robust counterparts which are traditional optimization problems make it possible to use existing algorithms of mathematical optimization to solve more complicated and general robust optimization problems.     

Generalized Isotonic Regression

We present a new computational and statistical approach for fitting isotonic models under convex differentiable loss functions through recursive partitioning. Models along the partitioning path are also isotonic and can be viewed as regularized solutions to the problem. Our approach generalizes and subsumes the well-known work of Barlow and Brunk on fitting isotonic regressions subject to specially structured loss functions, and expands the range of loss functions that can be used (e.g., adding Huber loss for robust regression). This is accomplished through an algorithmic adjustment to a recursive partitioning approach recently developed for solving large-scale ?₂-loss isotonic regression problems. We prove that the new algorithm solves the generalized problem while maintaining the favorable computational and statistical properties of the l₂ algorithm. The results are demonstrated on both real and synthetic data in two settings: fitting count data using negative Poisson log-likelihood loss, and fitting robust isotonic regressions using Huber loss. Proofs of theorems and a MATLAB-based software package implementing our algorithm are available in the online supplementary materials.