Survey of linear programming for standard and nonstandard Markovian control problems. Part I: Theory

This paper gives an overview of linear programming methods for solving standard and nonstandard Markovian control problems. Standard problems are problems with the usual criteria such as expected total (discounted) rewards and average expected rewards; we also discuss a particular class of stochastic games. In nonstandard problems there are additional considerations as side constraints, multiple criteria or mean-variance tradeoffs. In a second companion paper efficient linear programing algorithms are discussed for some applications.     

Controlled Markov processes on the infinite planning horizon: Weighted and overtaking cost criteria

Stochastic control problems for controlled Markov processes models with an infinite planning horizon are considered, under some non-standard cost criteria. The classical discounted and average cost criteria can be viewed as complementary, in the sense that the former captures the short-time and the latter the long-time performance of the system. Thus, we study a cost criterion obtained as weighted combinations of these criteria, extending to a general state and control space framework several recent results by Feinberg and Shwartz, and by Krass et al. In addition, a functional characterization is given for overtaking optimal policies, for problems with countable state spaces and compact control spaces; our approach is based on qualitative properties of the optimality equation for problems with an average cost criterion.Research partially supported by the Engineering Foundation under grant RI-A-93-10, in part by the National Science Foundation under grant NSF-INT 9201430, and in part by a grant from the AT&T Foundation.Research partially supported by the Air Force Office of Scientific Research under Grant F49620-92-J-0045, and in part by the National Science Foundation under Grant CDR-8803012.     

The asymptotic behavior of nonlinear semigroups and invariant means

Various first-order sufficient optimality criteria for continuous-time nonlinear programming problems with nonlinear equality and inequality constraints are established under generalized convexity assumptions, and applications of these criteria to optimal control and continuous-time fractional programming problems are briefly discussed.     

Semiparametric proper efficiency principles and duality models for constrained multiobjective fractional optimal control problems containing arbitrary norms

Semiparametric necessary and sufficient proper efficiency conditions are established for a class of constrained multiobjective fractional optimal control problems with linear dynamics, containing arbitrary norms. Moreover, utilizing these proper efficiency results, eight semiparametric duality models are formulated and appropriate duality theorems are proved. These proper efficiency and duality criteria contain, as special cases, similar results for several classes of unorthodox optimal control problems with multiple, fractional, and conventional objective functions, which are particular cases of the main problem considered in this paper.     

An algorithm for solving a multiple criteria optimal control problem

An algorithm for finding agood solution for a multiple criteria optimal control problem is given. The criteria are assumed to be ordered according to their importance to the decision-maker. The algorithm consists of successive solutions of single criterion optimal control problems. Other criteria are taken into account by adding constraints to the problem in a systematic manner.     

Concave Programming in Control Theory

We show in the present paper that many open and challenging problems in control theory belong the the class of concave minimization programs. More precisely, these problems can be recast as the minimization of a concave objective function over convex LMI (Linear Matrix Inequality) constraints. As concave programming is the best studied class of problems in global optimization, several concave programs such as simplicial and conical partitioning algorithms can be used for the resolution. Moreover, these global techniques can be combined with a local Frank and Wolfe feasible direction algorithm and improved by the use of specialized stopping criteria, hence reducing the overall computational overhead. In this respect, the proposed hybrid optimization scheme can be considered as a new line of attack for solving hard control problems.Computational experiments indicate the viability of our algorithms, and that in the worst case they require the solution of a few LMI programs. Power and efficiency of the algorithms are demonstrated for a realistic inverted-pendulum control problem.Overall, this dedication reflects the key role that concavity and LMIs play in difficult control problems.     

Proper efficiency and duality for a class of constrained multiobjective fractional optimal control problems containing arbitrary norms

We establish necessary and sufficient conditions for properly efficient solutions of a class of nonsmooth nonconvex optimal control problems with multiple fractional objective functions, linear dynamics, and nonlinear inequality constraints on both the state and control variables. Subsequently, we utilize these proper efficiency criteria to construct two multiobjective dual problems and prove appropriate duality theorems. Also, we specialize and discuss these results for a particular case of our principal problem which contains square roots of positivesemidefinite quadratic forms. As special cases of the main proper efficiency and duality results, this paper also contains similar results for control problems with multiple, fractional, and ordinary objective functions.     

Multitime Dynamic Programming for Curvilinear Integral Actions

This paper justifies dynamic programming PDEs for optimal control problems with performance criteria involving curvilinear integrals. The main novel feature, relative to the known theory, is that the multitime dynamic programming PDEs are now connected to the multitime maximum principle. For the first time, an interesting and useful connection between the multitime maximum principle and the multitime dynamic programming is given, characterizing the optimal control by means of a PDE system that may be viewed as a multitime feedback law.     

A Survey of Reachability and Controllability for Positive Linear Systems

This paper is a survey of reachability and controllability results for discrete-time positive linear systems. It presents a variety of criteria in both algebraic and digraph forms for recognising these fundamental system properties with direct implications not only in dynamic optimization problems (such as those arising in inventory and production control, manpower planning, scheduling and other areas of operations research) but also in studying properties of reachable sets, in feedback control problems, and others. The paper highlights the intrinsic combinatorial structure of reachable/controllable positive linear systems and reveals the monomial components of such systems. The system matrix decomposition into monomial components is demonstrated by solving some illustrative examples.     

分组测试与迫进控制标准

1引言 在第二次世界大战期间,珍珠港事件发生后,美国为了反击德国法西斯挑起的侵略战争,多次进行大规模的征兵活动．在征兵活动中,需要对大量报名入伍者进行健康检查,看其身体是否符合入伍的条件．其中一项健康检查的内容是血液抗体检测,通过血液抗体检测,查出梅毒的携带者．当时,由于被检测者数量巨大,部队又急需补充兵员,检测时间紧、任务重,这就需要找到一种科学的检测方法,用尽可能少的测试次数检测出所有病毒携带者,这一问题后来称为搜索坏硬币的最优化问题．在这个问题中,被检测者抽象为硬币,血液不带病毒者抽象为标准硬币,血液带病毒者抽象为伪硬币,检测的设备称为装置．如何用特定性能的若干台装置,以尽可能少的测试次数从由硬币组成的集合中检测出全部伪硬币,是一个有很强实际背景的最优化问题,正因为如此,近一段时间组合搜索中的伪硬币问题一直受到人们的广泛关注．     

Continuous-Time Mean-Variance Portfolio Selection: A Stochastic LQ Framework

This paper is concerned with a continuous-time mean-variance portfolio selection model that is formulated as a bicriteria optimization problem. The objective is to maximize the expected terminal return and minimize the variance of the terminal wealth. By putting weights on the two criteria one obtains a single objective stochastic control problem which is however not in the standard form due to the variance term involved. It is shown that this nonstandard problem can be ``embedded' into a class of auxiliary stochastic linear-quadratic (LQ) problems. The stochastic LQ control model proves to be an appropriate and effective framework to study the mean-variance problem in light of the recent development on general stochastic LQ problems with indefinite control weighting matrices. This gives rise to the efficient frontier in a closed form for the original portfolio selection problem. Accepted 24 November 1999     

Simplicially-Constrained DC Optimization over Efficient and Weakly Efficient Sets

We formulate optimization problems over efficient and weakly efficient sets as DC problems over a simplex in the criteria space. This formulation allows developing a decomposition algorithm using an adaptive simplex subdivision and a convex envelope function for solving both problems. Randomly generated problems up to the size of 150 decision variables and 7 criteria are solved.     

Sufficient criteria are necessary for monotone control volume methods

Control volume methods are prevailing for solving the potential equation arising in porous media flow. The continuous form of this equation is known to satisfy a maximum principle, and it is desirable that the numerical approximation shares this quality. Recently, sufficient criteria were derived guaranteeing a discrete maximum principle for a class of control volume methods. We show that most of these criteria are also necessary. An implication of our work is that no linear nine-point control volume method can be constructed for quadrilateral grids in 2D that is exact for linear solutions while remaining monotone for general problems.     

Conditions for the absence of cycles of the second kind in continuous and discrete systems with cylindrical phase space

Continuous and discrete indirect control systems with periodic vector nonlinearities are considered. One of the key problems concerning the asymptotic behavior of such systems is studied, namely, the existence of cycles in a cylindrical phase space. Multiparameter frequency-algebraic criteria for the absence in a cylindrical phase space of a system of cycles with given frequency are obtained.     

Optimizing macroeconomic policy: A review of approaches and applications

In this paper the main approaches to optimizing macroeconomic policy problems are reviewed. These include the classical approaches of Tinbergen, Theil and Frisch as well as several mathematical programming methods, such as linear programming, goal programming, interactive multiple criteria optimization, and methods of optimal control. In addition, several applications are described. Finally, the usefullness and suitability of these approaches to solving macroeconomic policy problems in practice is discussed.     

Minimizing maximum tardiness and number of tardy jobs on parallel machines subject to minimum flow-time

This paper considers the problems of scheduling jobs on parallel identical machines where an optimal schedule is defined as one that gives the smallest maximum tardiness (or the minimum number of tardy jobs) among the set of schedules with optimal total flow-time (the sum of the completion times of all jobs). We show that these problems are unary NP-Hard, develop lower bounds for these two secondary criteria problems, and describe heuristic algorithms for their solution. Results of a computational study show that the proposed heuristic algorithms are quite effective and efficient in solving these hierarchical criteria scheduling problems.     

Measuring the relative balance of DMUs

In basic Data Envelopment Analysis (DEA) models, the weights of performance criteria are endogenously determined, assigning to each decision-making unit (DMU) its best possible efficiency score. This property is widely considered to be a major strength of the method, but it is also a source of considerable problems concerning performance assessment and performance control. Such problems result from the possibility of zero-value weights that exclude criteria from the evaluation. Unlike approaches that deal with this issue by incorporating value judgments into the analysis, we suggest a complementary balance score that is derived from the given data set. This score evaluates the extent to which a DMU avoids concentration on only some of the crucial performance criteria. One of the possible decisions resulting from a balance analysis is to reduce the set of DMUs considered to serve as benchmarks. For this case, a modified CCR–O model is presented.     

Controllability and observability in the problem of stabilizing steady motions of non-holonomic mechanical systems with cyclic coordinatest

The approach to the solution of stabilization problems for steady motions of holonomic mechanical systems [1, 2] based on linear control theory, combined with the theory of critical cases of stability theory, is used to solve the analogous problems for non-holonomic systems. It is assumed that the control forces may affect both cyclic and positional coordinates, where the number r of independent control inputs may be considerably less than the number n of degrees of freedom of the system, unlike in many other studies (see, e.g., [3–5]), in which as a rule r = n. Several effective new criteria of controllability and observability are formulated, based on reducing the problem to a problem of less dimension. Stability analysis is carried out for the trivial solution of the complete non-linear system, closed by a selected control. This analysis is a necessary step in solving the stabilization problem for steady motion of a non-holonomic system (unlike holonomic systems), since in most cases such a system is not completely controllable.     

A Goal Programming model of the reference point method

Real-life decision problems are usually so complex they cannot be modeled with a single objective function, thus creating a need for clear and efficient techniques of handling multiple criteria to support the decision process. The most commonly used technique is Goal Programming. It is clear and appealing, but in the case of multiobjective optimization problems strongly criticized due to its noncompliance with the efficiency (Pareto-optimality) principle. On the other hand, the reference point method, although using similar control parameters as Goal Programming, always generates efficient solutions. In this paper, we show how the reference point method can be modeled within the Goal Programming methodology. It allows us to simplify implementations of the reference point method as well as shows how Goal Programming with relaxation of some traditional assumptions can be extended to a multiobjective optimization technique meeting the efficiency principle.     

Geometric conditions for Kuhn–Tucker sufficiency of global optimality in mathematical programming

We present geometric criteria for a feasible point that satisfies the Kuhn–Tucker conditions to be a global minimizer of mathematical programming problems with or without bounds on the variables. The criteria apply to multi-extremal programming problems which may have several local minimizers that are not global. We establish such criteria in terms of underestimators of the Lagrangian of the problem. The underestimators are required to satisfy certain geometric property such as the convexity (or a generalized convexity) property. We show that the biconjugate of the Lagrangian can be chosen as a convex underestimator whenever the biconjugate coincides with the Lagrangian at a point. We also show how suitable underestimators can be constructed for the Lagrangian in the case where the problem has bounds on the variables. Examples are given to illustrate our results.