Weak and Strong Optimality Conditions for Constrained Control Problems with Discontinuous Control

In recent years, sufficient optimality criteria and solution stability in optimal control have been investigated widely and used in the analysis of discrete numerical methods. These results were concerned mainly with weak local optima, whereas strong optimality has been considered often as a purely theoretical aspect. In this paper, we show via an example problem how weak the weak local optimality can be and derive new strong optimality conditions. The criteria are suitable for practical verification and can be applied to the case of discontinuous controls with changes in the set of active constraints.     

Optimality equations and sensitive optimality in bounded Markov decision processes 1

This paper consider Markov decision processes with countable state space, compact action spaces and a bounded reward function. Under some recurrence and connectedness condition, including the simultaneous Döblin condition, we prove the existence of bounded solutions of the optimality equations which arise for the multichain case in connection with the average reward criterion and sensitive optimality criteria, and we give a characterization of the sets of n-average optimal decision rules.     

On sufficient second order optimality conditions in multiobjective optimization

A second order sufficient optimality criterion is presented for a multiobjective problem subject to a constraint given just as a set. To this aim, we first refine known necessary conditions in such a way that the sufficient ones differ by the replacement of inequalities by strict inequalities. Furthermore, we show that no relationship holds between this criterion and a sufficient multipliers rule, when the constraint is described by inequalities and equalities. Finally, improvements of this criterion for the unconstrained case are presented, stressing the differences with single-objective optimization     

Statistical verification of optimality conditions for stochastic programs with recourse

Statistically motivated algorithms for the solution of stochastic programming problems typically suffer from their inability to recognize optimality of a given solution algorithmically. Thus, the quality of solutions provided by such methods is difficult to ascertain. In this paper, we develop methods for verification of optimality conditions within the framework of Stochastic Decomposition (SD) algorithms for two stage linear programs with recourse. Consistent with the stochastic nature of an SD algorithm, we provide termination criteria that are based on statistical verification of traditional (deterministic) optimality conditions. We propose the use of bootstrap methods to confirm the satisfaction of generalized Kuhn-Tucker conditions and conditions based on Lagrange duality. These methods are illustrated in the context of a power generation planning model, and the results are encouraging.This work was supported in part by Grant No. AFOSR-88-0076 from the Air Force Office of Scientific Research and Grant No. DDM-89-10046 from the National Science Foundation.     

Proximity theorems of discrete convex functions

A proximity theorem is a statement that, given an optimization problem and its relaxation, an optimal solution to the original problem exists in a certain neighborhood of a solution to the relaxation. Proximity theorems have been used successfully, for example, in designing efficient algorithms for discrete resource allocation problems. After reviewing the recent results for L-convex and M-convex functions, this paper establishes proximity theorems for larger classes of discrete convex functions, L₂-convex functions and M₂-convex functions, that are relevant to the polymatroid intersection problem and the submodular flow problem.Mathematics Subject Classification (2000): 90C27, 05B35     

Overtaking optimality for controlled Markov-modulated diffusions

This article concerns controlled Markov-modulated diffusions (also known as piecewise diffusions or switching diffusions or diffusions with Markovian switchings). Our main objective is to give conditions for the existence and characterization of overtaking optimal policies. To this end, first, we use fact that the average reward Hamilton–Jacobi–Bellman equation gives that the family of the so-called canonical control policies is nonempty. Then, within this family, we search policies with some special feature, for instance, canonical policies that in addition maximize the bias, which turn out to be overtaking optimal.     

Nondifferentiability Detection and Dimensionality Reduction in Minisum Multifacility Location Problems

The minisum multifacility location problem is regarded as hard to solve, due to nondifferentiabilities whenever two or more facilities coincide. Recently, several authors have published conditions for the coincidence of facilities. In the present paper, these conditions are extended to more general location problems and improved with respect to new sufficient coincidence conditions for location problems with mixed asymmetric gauges. Some of these conditions are formulated only in terms of the given weights and certain values from a preprocessing step.     

Using box indices in supporting comparison in multiobjective optimization

Because of the conflicting nature of criteria or objectives, solving a multiobjective optimization problem typically requires interaction with a decision maker who can specify preference information related to the objectives in the problem in question. Due to the difficulties of dealing with multiple objectives, the way information is presented plays a very important role. Questions posed to the decision maker must be simple enough and information shown must be easy to understand. For this purpose, visualization and graphical representations can be useful and constitute one of the main tools used in the literature. In this paper, we propose to use box indices to represent information related to different solution alternatives of multiobjective optimization problems involving at least three objectives. Box indices are an intelligible and easy to handle way to represent data. They are based on evaluating the solutions in a natural and rough enough scale in order to let the decision maker easily recognize the main characteristics of a solution at a glance and to facilitate comparison of two or more solutions in an easily understandable way.     

二机器流水作业排序问题全部最优解的结构

排序问题F2||Cmax,Johnson条件只是最优解的充分条件，不是必要的．本文绘出一个充分必要条件，由此得到生成全部最优解的算法．主要理论是基于一种序论方法．     

Efficient weight vectors from pairwise comparison matrices

Pairwise comparison matrices are frequently applied in multi-criteria decision making. A weight vector is called efficient if no other weight vector is at least as good in approximating the elements of the pairwise comparison matrix, and strictly better in at least one position. A weight vector is weakly efficient if the pairwise ratios cannot be improved in all non-diagonal positions. We show that the principal eigenvector is always weakly efficient, but numerical examples show that it can be inefficient. The linear programs proposed test whether a given weight vector is (weakly) efficient, and in case of (strong) inefficiency, an efficient (strongly) dominating weight vector is calculated. The proposed algorithms are implemented in Pairwise Comparison Matrix Calculator, available at pcmc.online.     

Weight determination for consistently ranking alternatives in multiple criteria decision analysis

One of the most difficult tasks in multiple criteria decision analysis (MCDA) is determining the weights of individual criteria so that all alternatives can be compared based on the aggregate performance of all criteria. This problem can be transformed into the compromise programming of seeking alternatives with a shorter distance to the ideal or a longer distance to the anti-ideal despite the rankings based on the two distance measures possibly not being the same. In order to obtain consistent rankings, this paper proposes a measure of relative distance, which involves the calculation of the relative position of an alternative between the anti-ideal and the ideal for ranking. In this case, minimizing the distance to the ideal is equivalent to maximizing the distance to the anti-ideal, so the rankings obtained from the two criteria are the same. An example is used to discuss the advantages and disadvantages of the proposed method, and the results are compared with those obtained from the TOPSIS method.     

Empirical Bayes Procedures for Selecting the Best Population with Multiple Criteria

Consider k (k 2) populations whose mean _i and variance _i ² are all unknown. For given control values ₀ and ₀ ² , we are interested in selecting some population whose mean is the largest in the qualified subset in which each mean is larger than or equal to ₀ and whose variance is less than or equal to ₀ ² . In this paper we focus on the normal populations in details. However, the analogous method can be applied for the cases other than normal in some situations. A Bayes approach is set up and an empirical Bayes procedure is proposed which has been shown to be asymptotically optimal with convergence rate of order O(ln² n/n). A simulation study is carried out for the performance of the proposed procedure and it is found satisfactory.     

Bayesian planning of step‐stress accelerated degradation tests under various optimality criteria

Step‐stress accelerated degradation testing (SSADT) has become a common approach to predicting lifetime for highly reliable products that are unlikely to fail in a reasonable time under use conditions or even elevated stress conditions. In literature, the planning of SSADT has been widely investigated for stochastic degradation processes, such as Wiener processes and gamma processes. In this paper, we model the optimal SSADT planning problem from a Bayesian perspective and optimize test plans by determining both stress levels and the allocation of inspections. Large‐sample approximation is used to derive the asymptotic Bayesian utility functions under 3 planning criteria. A revisited LED lamp example is presented to illustrate our method. The comparison with optimal plans from previous studies demonstrates the necessity of considering the stress levels and inspection allocations simultaneously.     

On stopped decision processes with discrete time parameter

A non-stationary stopped decision process is investigated under rather weak convergence assumptions on the expected total rewards. Sufficient conditions are given for the approximation of the maximal conditional expected rewards from infinite stage play by the maximal conditional expected rewards from finite stage play. General criteria of optimality are derived. The results are essentially based on two lemmas given in this paper. The existence of optimal plans is established using results of non-stationary dynamic programming.     

Constructive method for solving a linear minimax problem of optimal control

In this paper, we propose a constructive method for solving a linear minimax problem of optimal control. Following the Gabasov-Kirillova approach, we introduce the concept of so-called support control. After establishing an optimality criterion for the support control, we describe a scheme for reducing the initial infinite-dimensional problem to a finite-dimensional one, which can be solved numerically by the methods of linear programming. At the end, we give an illustrative example.     

Stability and accuracy functions for a multicriteria Boolean linear programming problem with parameterized principle of optimality “from Condorcet to Pareto”

A multicriteria Boolean programming problem with linear cost functions in which initial coefficients of the cost functions are subject to perturbations is considered. For any optimal alternative, with respect to parameterized principle of optimality “from Condorcet to Pareto”, appropriate measures of the quality are introduced. These measures correspond to the so-called stability and accuracy functions defined earlier for optimal solutions of a generic multicriteria combinatorial optimization problem with Pareto and lexicographic optimality principles. Various properties of such functions are studied and maximum norms of perturbations for which an optimal alternative preserves its optimality are calculated. To illustrate the way how the stability and accuracy functions can be used as efficient tools for post-optimal analysis, an application from the voting theory is considered.     

A refinement of an optimality criterion and its application to parametric programming

We consider semi-infinite linear minimization problems and prove a refinement of an optimality condition proved earlier by the author. This refinement is used to derive a sufficient condition for strong uniqueness of a minimal point. As an application, we show that these strongly unique minimal points depend (pointwise) Lipschitz-continuously on the parameter of the minimization problem. Finally, we consider numerical algorithms for semi-infinite optimization problems and we apply the above results to derive error estimates for these algorithms.     

Throughput and delay optimality of power-of-d choices in inhomogeneous load balancing systems

It is well-known that the power-of-d choices routing algorithm maximizes throughput and is heavy-traffic optimal in load balancing systems with homogeneous servers. However, if the servers are heterogeneous, throughput optimality does not hold in general. We find necessary and sufficient conditions for throughput optimality of power-of-d choices when the servers are heterogeneous, and we prove that almost the same conditions are sufficient to show heavy-traffic optimality. Additionally, we generalize the sufficient condition for throughput optimality to a larger class of routing policies.