Criteria and dimension reduction of linear multiple criteria optimization problems

Two of the main approaches in multiple criteria optimization are optimization over the efficient set and utility function program. These are nonconvex optimization problems in which local optima can be different from global optima. Existing global optimization methods for solving such problems can only work well for problems of moderate dimensions. In this article, we propose some ways to reduce the number of criteria and the dimension of a linear multiple criteria optimization problem. By the concept of so-called representative and extreme criteria, which is motivated by the concept of redundant (or nonessential) objective functions of Gal and Leberling, we can reduce the number of criteria without altering the set of efficient solutions. Furthermore, by using linear independent criteria, the linear multiple criteria optimization problem under consideration can be transformed into an equivalent linear multiple criteria optimization problem in the space of linear independent criteria. This equivalence is understood in a sense that efficient solutions of each problem can be derived from efficient solutions of the other by some affine transformation. As a result, such criteria and dimension reduction techniques could help to increase the efficiency of existing algorithms and to develop new methods for handling global optimization problems arisen from multiple objective optimization.     

投入产出反问题的优化模型及算法

本文从反问题的角度讨论了修订直接消耗系数的几种优化方法，通过引入“投入产出反问题”的概念，建立了拉格朗日优化，二次规划，熵优化等三个优化模型，同时给出了算法和算例，并且比较了各种方法的计算结果。     

Minimizing total tardiness in a scheduling problem with a learning effect

Minimizing of total tardiness is one of the most studied topics on single machine problems. Researchers develop a number of optimizing and heuristic methods to solve this NP-hard problem. In this paper, the problem of minimizing total tardiness is examined in a learning effect situation. The concept of learning effects describes the reduction of processing times arising from process repetition. A 0–1 integer programming model is developed to solve the problem. Also, a random search, the tabu search and the simulated annealing-based methods are proposed for the problem and the solutions of the large size problems with up to 1000 jobs are found by these methods. To the best of our knowledge, no works exists on the total tardiness problem with a learning effect tackled in this paper.     

Non-linear stability of a general class of differential equation methods

For a class of methods sufficiently general as to include linear multistep and Runge-Kutta methods as special cases, a concept known as algebraic stability is defined. This property is based on a non-linear test problem and extends existing results on Runge-Kutta methods and on linear multistep and one-leg methods. The algebraic stability properties of a number of particular methods in these families are studied and a generalization is made which enables estimates of error growth to be provided for certain classes of methods.     

分块平方和分解

本文定义了分块平方和可分解多项式的概念.粗略地说,它是这样一类多项式,只考虑其支撑集(不考虑系数)就可以把它的平方和分解问题等价地转换为较小规模的同类问题(换句话说,相应的半正定规划问题的矩阵可以分块对角化).本文证明了近年文献中提出的两类方法—分离多项式(split polynomial)和最小坐标投影(minimal coordinate projection)—都可以用分块平方和可分解多项式来描述,证明了分块平方和可分解多项式集在平方和多项式集中为零测集.     

Numerical Applications of the Scaling Concept

We present a survey of recent developments in the applications of the scaling concept to numerical analysis. In addition, we report on some relevant topics not covered in existing surveys. Therefore, the present work updates and complements the existing surveys on the subject concerned.Applications of the scaling concept are useful in the numerical treatment of both ordinary and partial differential problems. Applications to boundary-value problems governed by ordinary differential equations are mainly related to their transformation into initial-value problems. Within this context, special emphasis is placed on systems of governing equations, eigenvalue, and free boundary-value problems. An error analysis for a truncated boundary formulation of the Blasius problem is also reported. As far as initial-value problems governed by ordinary differential equations are concerned, we discuss the development of adaptive mesh methods. Applications to partial differential problems considered herein are related to the construction of finite-difference schemes for conservations laws, the solution structure of the Riemann problem, rescaling schemes and adaptive schemes for blow-up problems.In writing this paper, our aim was to promote further and more important numerical applications of the scaling concept. Meanwhile, the pertinent bibliography is highlighted and is available on internet as the BIB file sc-gita.bib from the anonymous ftp area at the URL ftp://dipmat.unime.it/pub/papers/fazio/surveys.     

Leader–Follower Dynamic Game of New Product Diffusion

The objective of this paper is to study optimal pricing strategies in a duopoly, under an asymmetric information structure, where the appropriate solution concept is the feedback Stackelberg equilibrium. In order to take into account effects such as imitation (e.g., word of mouth) and saturation, the demand (state equation) is assumed to depend on past cumulative sales, market potential, and both players' prices. We assume also that the unit production cost decreases with cumulative production (learning effects). Each player maximizes his total discounted profit over the planning horizon.The problem is formulated as a two-player discrete-time finite-horizon game. Existence results are first obtained under rather mild conditions. Since the solution of this problem is intractable by analytical methods, we use a numerical approach. Thus, we design a numerical algorithm for the computation of feedback Stackelberg equilibria and use it to obtain strategies in various representative cases. The numerical results presented are intented to give some insights into the optimal pricing strategies in the context of an asymmetrical feedback information structure.     

Geometry of a five link mechanism with two degrees of freedom

The paper is devoted to the solution of straight and inverse geometrical tasks of five link mechanism with two degrees of freedom. The solution of the mentioned problem is very important in order to determine kinematic parameters of actuators. The problem can be divided into two parts. The first part is considered when we are given the coordinates of the output link of the mechanism and the necessity arises of determining the angles of rotation of actuators. On the other hand, it is very important to determine the position of the output link when the angles of rotation of the actuators are known. Here we consider that the mechanism is composed only of five classes of rotating kinematic pairs and the actuators are situated at the junctions of frames and links of the examined mechanism. The solution of the said problem is based on utilization of homogenous coordinates. On the basis of the obtained equations of motion, one can calculate the trajectories of motion of the output link as well angles of rotation of the actuators by taking into consideration preliminary given kinematic parameters of the mechanism. Here we also obtain equations for calculating values of speed and acceleration of the links of the mechanism. The calculations differ from known methods in simplicity and high performance, which would be useful for programming actuators mounted in the joints of the linkage.     

With a focus on ‘Grundvorstellungen’ Part 1: a theoretical integration into current concepts

Current comparative studies such as PISA assess individual achievement in an attempt to grasp the concept of competence. Working with mathematics is then put into concrete terms in the area of application. Thereby, mathematical work is understood as a process of modelling: At first, mathematical models are taken from a real problem; then the mathematical model is solved; finally the mathematical solution is interpreted with a view to reality and the original problem is validated by the solution. During this cycle the main focus is on the transition between reality and the mathematical level. Mental objects are necessary for this transition. These mental objects are described in the German didactic with the concept of Grundvorstellungen'. In the delimitation to related educational constructs, ‘Grundvorstellungen’ can be described as mental models of a mathematical concept.     

Transformation of Time-Delay Systems to a Form with Zero Dynamics

The problem of transforming a controlled linear stationary system of differential equations with commensurable time delays into a canonical form with zero dynamics is considered. This problem has been well studied for ODE systems and is closely related to the concept of a relative degree. In this paper, the results are extended to time-delay systems.     

Finite-difference methods for one-dimensional hyperbolic conservation laws

This article contains a survey of some important finite-difference methods for one-dimensional hyperbolic conservation laws. Weak solutions of hyperbolic conservation laws are introduced and the concept of entropy stability is discussed. Furthermore, the Riemann problem for hyperbolic conservation laws is solved. An introduction to finite-difference methods is given for which important concepts such as, e.g., conservativity, stability, and consistency are introduced. Godunov-type methods are elaborated for general systems of hyperbolic conservation laws. Finally, flux limiter methods are developed for the scalar nonlinear conservation law. © 1994 John Wiley & Sons, Inc.     

Optimal guaranteed control of delay systems

A linear problem of optimal guaranteed control of a delay system is considered in which geometric constraints on control actions and terminal constraints on states are present. A new concept of a state of the problem that represents a finite-dimensional vector is introduced. Three kinds of optimal feedback are defined. We describe methods for implementing open-loop and closable optimal feedbacks. They are based on a fast dual method for the correction of optimal programs. The results are illustrated by examples.     

Duality for constrained multifacility location problems with mixed norms and applications

A dual problem is developed for the constrained multifacility minisum location problems involving mixed norms. General optimality conditions are also obtained providing new algorithms based on the concept of partial inverse of a multifunction. These algorithms which are decomposition methods, generate sequences globally converging to a primal and a dual solution respectively. Numerical results are reported.     

A New Pareto Optimal Solution in a Lagrange Decomposable Multi-Objective Optimization Problem

In this paper a committee decision-making process of a convex Lagrange decomposable multi-objective optimization problem, which has been decomposed into various subproblems, is studied. Each member of the committee controls only one subproblem and attempts to select the optimal solution of this subproblem most desirable to him, under the assumption that all the constraints of the total problem are satisfied. This procedure leads to a new solution concept of a Lagrange decomposable multi-objective optimization problem, called a preferred equilibrium set. A preferred equilibrium point of a problem, for a committee, may or may not be a Pareto optimal point of this problem. In some cases, a non-Pareto optimal preferred equilibrium point of a problem, for a committee, can be considered as a special type of Pareto optimal point of this problem. This fact leads to a generalization of the Pareto optimality concept in a problem.     

<Emphasis Type="Bold">R</Emphasis><Emphasis Type="SmallCaps">UBIS</Emphasis>: a bipolar-valued outranking method for the choice problem

The main concern of this article is to present the R UBIS method for tackling the choice problem in the context of multiple criteria decision aiding. Its genuine purpose is to help a decision maker to determine a single best decision alternative. Methodologically we focus on pairwise comparisons of these alternatives which lead to the concept of bipolar-valued outranking digraph. The work is centred around a set of five pragmatic principles which are required in the context of a progressive decision aiding methodology. Their thorough study and implementation in the outranking digraph lead us to define a choice recommendation as an extension of the classical digraph kernel concept.      

Bi-criteria evolution strategy in estimating weights from the AHP ratio-scale matrices

The problem of deriving weights from ratio-scale matrices in an analytic hierarchy process (AHP) is addressed by researchers worldwide. There are various ways to solve the problem that are generally grouped into simple matrix and optimization methods. All methods have received criticism regarding the accuracy of derived weights, and different criteria are in use to compare the weights obtained from different methods. Because the set of Pareto non-dominated solutions (weights) is unknown and for inconsistent matrices is indefinite, a bi-criterion optimization approach is proposed for manipulating such matrices. The problem-specific evolution strategy algorithm (ESA) is implemented for a robust stochastic search over a feasible indefinite solution space. The fitness function is defined as a scalar vector function composed of the common error measure, i.e. the Euclidean distance and a minimum violation error that accounts for no violation of the rank ordering. The encoding scheme and other components of the search engine are adjusted to preserve the imposed constraints related to the required normalized values of the weights. The solutions generated by the proposed approach are compared with solutions obtained by five well-known prioritization techniques for three judgment matrices taken from the literature. In these and other test applications, the prioritization method that uses the entitled weights estimation by evolution strategy algorithm (WEESA) appears to be superior to other methods if only two, the most commonly used methods, are applied: the Euclidean distance and minimum violation exclusion criteria.     

Partial linearization methods in nonlinear programming

In this paper, we characterize a class of feasible direction methods in nonlinear programming through the concept of partial linearization of the objective function. Based on a feasible point, the objective is replaced by an arbitrary convex and continuously differentiable function, and the error is taken into account by a first-order approximation of it. A new feasible point is defined through a line search with respect to the original objective, toward the solution of the approximate problem. Global convergence results are given for exact and approximate line searches, and possible interpretations are made. We present some instances of the general algorithm and discuss extensions to nondifferentiable programming.The author wishes to thank Drs. K. Holmberg, T. Larsson, and A. Migdalas for their helpful comments.     

Solving the optimal network problem

A heuristic method for solving the optimal network problem is proposed and shown to yield high quality results. Solution methods based on Branch-and-Bound techniques are also considered in some detail. The effects of making various approximations, when calculating lower bounds, is discussed and the concept of forced moves introduced.The various methods are applied to a series of problems which include networks with link construction cost not proportional to length and with trip demands tij not all equal.     

Balance function for the optimal control problem

The balance-function concept for transforming constrained optimization problems into unconstrained optimization problems, for the purpose of finding numerical iterative solutions, is extended to the optimal control problem. This function is a combination orbalance between the penalty and Lagrange functions. It retains the advantages of the penalty function, while eliminating its numerical disadvantages. An algorithm is developed and applied to an orbit transfer problem, showing the feasibility and usefulness of this concept.These results are part of the author's doctoral thesis written under Professors H. Lo and D. Alspaugh of Purdue University.     

一类带时间窗车辆分配问题的贪婪算法

本文对一类带时间窗的车辆分配问题进行了分析,引入了车辆任务的概念,并将问题转化为车辆与车辆任务的匹配问题,同时制订了运输任务选择和车辆选择的贪婪策略,并在此基础上设计了车辆分配问题的贪婪算法,最后通过实例验证了算法的有效性。