Static Optimality and Dynamic Search-Optimality in Lists and Trees

Adaptive data structures form a central topic of on-line algorithms research. The area of Competitive Analysis began with the results of Sleator and Tarjan showing that splay trees achieve static optimality for search trees, and that Move-to-Front is constant competitive for the list update problem [ST1], [ST2]. In a parallel development, powerful algorithms have been developed in Machine Learning for problems of on-line prediction [LW], [FS]. This paper is inspired by the observation made in [BB] that if computational decision-making costs are not considered, then these ``weighted experts'' techniques from Machine Learning allow one to achieve a 1+ε ratio against the best static object in hindsight for a wide range of data structure problems. In this paper we give two results. First, we show that for the case of lists , we can achieve a 1+ε ratio with respect to the best static list in hindsight, by a simple efficient algorithm. This algorithm can then be combined with existing results to achieve good static and dynamic bounds simultaneously. Second, for trees, we show a (computationally in efficient) algorithm that achieves what we call ``dynamic search optimality'': dynamic optimality if we allow the on-line algorithm to make free rotations after each request. We hope this to be a step towards solving the longstanding open problem of achieving true dynamic optimality for trees.     

Strategic stability in linear-quadratic differential games with nontransferable payoffs

We address the problem of strategically supported cooperation for linear-quadratic differential games with nontransferable payoffs. As an optimality principle, we study Pareto-optimal solutions. It is assumed that players use a payoff distribution procedure guaranteeing individual rationality of a cooperative solution over the entire game horizon. We prove that under these conditions a Pareto-optimal solution can be strategically supported by an ε-Nash equilibrium. An example is considered.     

Stochastic Optimal Control of Risk Processes with Lipschitz Payoff Functions

This paper studies the stochastic optimal control problem of finding optimal dividend policies of an insurance company in discrete time with the use of general Lipschitz payoff functions involving indicators of profitability and risk. To construct positional optimal controls and to evaluate the performance indicators, the dynamic programming method is validated. The convergence rate of the successive approximation method in finding generally unbounded Bellman functions is estimated. The Pareto-optimal set of the problem is numerically approximated by so-called barrier-proportional control strategies.     

Optimal periodic control: The π test revisited

The paper examines second-order conditions for both steady-state and dynamic optimality in a periodic control problem. It centers on the π condition of Bittanti, Fronza, and Guardabassi [2] and has three main objectives: 1) to form a π "test" for a somewhat more general problem than considered in [2]; 2) to point out that certain auxiliary conditions must be added if the results of [2] are to be valid; and 3) to explore more fully the relationships between second-order conditions for steady-state optimality and second-order conditions for optimality in the dynamic problem.     

相空间坐标受限时的最优控制问题

对于相空间坐标受限的最优控制问题,P.B.加姆克列利德泽等得到了控制最优性的必要条件(即熟知的极大值原理)和衔接点处的“跳跃条件”.但是文献[1]中所用的数学工具不是初等的,推证过程也较繁长,不易为工程技术界所理解.本文在应用文献[1]中某些分析的基础上,采用文献[2,3]中的方法处理这一问题,作法较为简单,而且除了得到[1]中的结论外,还可得到一些新的结果,例如,文中所得到的某些充分条件以及对于线性系统“小范围”最优性的必要充分条件等.     

Static Optimality and Dynamic Search-Optimality in Lists and Trees

Abstract. Adaptive data structures form a central topic of on-line algorithms research. The area of Competitive Analysis began with the results of Sleator and Tarjan showing that splay trees achieve static optimality for search trees, and that Move-to-Front is constant competitive for the list update problem [ST1], [ST2]. In a parallel development, powerful algorithms have been developed in Machine Learning for problems of on-line prediction [LW], [FS]. This paper is inspired by the observation made in [BB] that if computational decision-making costs are not considered, then these ``weighted experts' techniques from Machine Learning allow one to achieve a 1+ε ratio against the best static object in hindsight for a wide range of data structure problems. In this paper we give two results. First, we show that for the case of lists , we can achieve a 1+ε ratio with respect to the best static list in hindsight, by a simple efficient algorithm. This algorithm can then be combined with existing results to achieve good static and dynamic bounds simultaneously. Second, for trees, we show a (computationally in efficient) algorithm that achieves what we call ``dynamic search optimality': dynamic optimality if we allow the on-line algorithm to make free rotations after each request. We hope this to be a step towards solving the longstanding open problem of achieving true dynamic optimality for trees.     

Real-time optimization of a hydroelectric power plant

An optimal control problem modelling a hydroelectric power plant was developed and discussed by Hj. Wacker and his co-workers in [1]. In the present paper, this problem is treated within a more general framework of “non-differentiable” optimal control problems. Necessary conditions of optimality are derived and it is proven that the restricted class of controls considered in [1] indeed contains the optimal control. Furthermore, a decoupling technique is established that allows the full problem to be split into several small subproblems. Based on the new results, an efficient algorithm is developed. This algorithm allows the optimal control to be computed for more general problems with greater accuracy and for a longer time period. Numerical results are given both for the model described in [1] and for the more refined model presented in this paper.     

On certain approaches to optimization of control processes. II

We consider a general approach to constructing efficient iterative procedures with extension and localization principles, sufficient optimality conditions, and global estimates. We pay special attention to new constructive methods based on the minimax control improvement principle of V.F. Krotov. As an in-depth example, we solve the optimization problem for a therapeutic process. This is the second of two papers devoted to approximate control optimization; it continues the first one [1], which proposed a general scheme for solving the said problem and considered in detail the stage of finding the initial approximation.     

Incentive- and compulsion-based cooperative approach in water resources quality management

Simulating control systems for water resources quality is considered. A hierarchical approach to organization of these systems and hierarchical control methods are taken as the basis. Moving from non-cooperative to cooperative relations is proved to be reasonable. A new way to distribute the payoff in the cooperative game is proposed for the problem of water resources quality control. Typical examples are given to illustrate various optimality principles in the cooperative game.     

Some principles of coordinated decision making in distributed systems

Conclusion The proposed approach leads to flexible decision support algorithms and procedures that easily adapt to changing requirements. The application of the proposed principles is illustrated in [12] with the object of allowing for the specific features of the problem and accelerating convergence of distributed decision support systems. The application of these principles to the construction of various control procedures and decision support scheme is demonstrated in [13–19]. At the present time, in connection with active transition to the market and operation in a rapidly changing reality, we can expect an increase in demand for algorithms, procedures, and schemes that divide the domains of competence, sharply delineate the domains of responsibility, and clearly separate the fields of action of the “center” and the “periphery” [11]. The need for such procedures will also be felt in financial management support [26–27] and in macro/micro economic modeling and forecasting [20–26]. This is due to the fact that in our rapidly changing world we are often unable to identify several separate criteria for optimization. We are often forced to look for a decision which is admissible by a whole range of formal and informal criteria and is stable under small perturbations of both the criteria and the external conditions [28–30]. Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 161–175, March–April, 1996.     

On Optimal Detectors in Multiuser Detection Problems

The paper is a supplement to [1]. Conditions under which asymptotically optimal detectors are linear are found. It is shown also that if, in contrast to [1], we consider not the Bayesian but minimax statement of the problem with unknown coefficients, then optimal detectors are linear (moreover, nonasymptotically). A geometrical meaning of Theorem 1 from [1] is explained, and it is shown that the theorem follows from some general results [2, 3] on hypotheses testing. It is also shown that some results of [4] follow from [1, Theorem 1].     

Robust controller synthesis using the maximum entropy design equations

This note presents an application of the optimality conditions obtained in [1] for dynamic compensation in the presence of state-, control-, and measurement-dependent noise. By solving these equations, which represent a fundamental generalization of standard steady-state LQG theory, a series of increasingly robust control designs is obtained for the example considered in [2].     

On optimal parameter selection

Pontryagin's results on optimal parameter selection problems [1, p. 193] have been found to contain some errors, as reported in Boltyanskii [2, p. 263] and Hofer and Sagirow [4]. In this note, it is shown that Boltyanskii's results (on optimal parameters) are easily derived from Gamkrelidze's general maximum principle [3], which, in contrast to the former, also yields an explicit solution to the problem in certain special cases.     

Team decision theory and information structures in optimal control problems--Part I

Information structures of organizations are studied and applied to problems of dynamic team decisions. For a causal system it is shown that there is a partially ordered precedence relation existing among the decision makers. The team decision problem with linear information structure and quadratic payoff function is dealt with. The primitive random variables are assumed to be jointly Gaussian. The optimal solutions for the teams in which precedents' information is available for the followers are obtained. It is shown that the well-known linear-quadratic-Gaussian stochastic control problem and static team decision problem are special cases of the structure considered.     

Application of statistical information criteria for optimal fuzzymodel construction

Theoretical studies have shown that fuzzy models are capable of approximating any continuous function on a compact domain to any degree of accuracy. However, constructing a good fuzzy model requires finding a good tradeoff between fitting the training data and keeping the model simple. A simpler model is not only easily understood, but also less likely to overfit the training data. Even though heuristic approaches to explore such a tradeoff for fuzzy modeling have been developed, few principled approaches exist in the literature due to the lack of a well-defined optimality criterion. In this paper, we propose several information theoretic optimality criteria for fuzzy models construction by extending three statistical information criteria: 1) the Akaike information criterion [AIC] (1974); 2) the Bhansali-Downham information criterion [BDIC] (1977); and 3) the information criterion of Schwarz (1978) and Rissanen (1978) [SRIC]. We then describe a principled approach to explore the fitness-complexity tradeoff using these optimality criteria together with a fuzzy model reduction technique based on the singular value decomposition (SVD). The role of these optimality criteria in fuzzy modeling is discussed and their practical applicability is illustrated using a nonlinear system modeling example     

Control constraints, abnormality, and improved performance by periodic control

Second-order conditions for steady-state optimality and nonoptimality in a periodic control problem are presented. The main result is a generalization of the π test, a second-order sufficient condition for improved performance by periodic control. Earlier results are generalized in two distinct ways: 1) the control constraint set is only assumed to be convex (and, hence, possibly nonopen) thus allowing the optimal steady-slate control to be an element of the control constraint set boundary; and 2) auxiliary normality conditions are eliminated. Proofs of the results are based upon second-order necessary, conditions for nonlinear programming and optimal control obtained recently in [43] and [44].     

Grouped sweeping scheduling for DASD-based multimedia storage management

This paper presents a new formulation of DASD (direct access storage device) disk arm scheduling schemes for multimedia storage management. The formulation, referred to as grouped sweeping scheduling (GSS), provides a framework for minimizing the buffer space required in the retrieval of multimedia streams. In GSS, the set ofn media streams that are to be served concurrently is divided intog groups. Groups are served in fixed order and streams within each group are served in an elevator-like SCAN scheme. Hence, the fixed order (FIFO) and SCAN schemes are special cases of GSS wheng=n andg=1, respectively. In this paper an optimization problem is formulated in which the buffer requirement is minimized with respect to the two design parameters:g and the size of the service unit, i.e. the number of blocks accessed in each service cycle. This formulation initially assumes that all media streams have the same playout requirements. A procedure of complexityO(1) is developed in computing the optimum solution to this problem. The proof of optimality and comparisons between the optimized GSS scheme and FIFO and SCAN are also presented. The paper also discusses the effect of disk arrays in the GSS formulation and issues related to operating GSS in a dynamic setting where streams arrive and depart in random order. Finally, the GSS scheme is extended to support heterogeneous media streams where each stream may have its own playout requirement.This paper extends earlier results that were presented at NOSDAV'92 [1] and Multimedia'93 [2].     

Variable neighborhood search for the cost constrained minimum label spanning tree and label constrained minimum spanning tree problems

Given an undirected graph whose edges are labeled or colored, edge weights indicating the cost of an edge, and a positive budget B, the goal of the cost constrained minimum label spanning tree (CCMLST) problem is to find a spanning tree that uses the minimum number of labels while ensuring its cost does not exceed B. The label constrained minimum spanning tree (LCMST) problem is closely related to the CCMLST problem. Here, we are given a threshold K on the number of labels. The goal is to find a minimum weight spanning tree that uses at most K distinct labels. Both of these problems are motivated from the design of telecommunication networks and are known to be NP-complete [15].In this paper, we present a variable neighborhood search (VNS) algorithm for the CCMLST problem. The VNS algorithm uses neighborhoods defined on the labels. We also adapt the VNS algorithm to the LCMST problem. We then test the VNS algorithm on existing data sets as well as a large-scale dataset based on TSPLIB [12] instances ranging in size from 500 to 1000 nodes. For the LCMST problem, we compare the VNS procedure to a genetic algorithm (GA) and two local search procedures suggested in [15]. For the CCMLST problem, the procedures suggested in [15] can be applied by means of a binary search procedure. Consequently, we compared our VNS algorithm to the GA and two local search procedures suggested in [15]. The overall results demonstrate that the proposed VNS algorithm is of high quality and computes solutions rapidly. On our test datasets, it obtains the optimal solution in all instances for which the optimal solution is known. Further, it significantly outperforms the GA and two local search procedures described in [15].     

Optimal Adaptive Control—Contradiction in Terms or a Matter of Choosing the Right Cost Functional?

Approaching the problem of optimal adaptive control as ldquooptimal control made adaptive,rdquo namely, as a certainty equivalence combination of linear quadratic optimal control and standard parameter estimation, fails on two counts: numerical (as it requires a solution to a Riccati equation at each time step) and conceptual (as the combination actually does not possess any optimality property). In this note, we present a particular form of optimality achievable in Lyapunov-based adaptive control. State and control are subject to positive definite penalties, whereas the parameter estimation error is penalized through an exponential of its square, which means that no attempt is made to enforce the parameter convergence, but the estimation transients are penalized simultaneously with the state and control transients. The form of optimality we reveal here is different from our work in [Z. H. Li and M. Krstic, ldquoOptimal design of adaptive tracking controllers for nonlinear systems,rdquo Automatica, vol. 33, pp. 1459-1473, 1997] where only the terminal value of the parameter error was penalized. We present our optimality concept on a partial differential equation (PDE) example-boundary control of a particular parabolic PDE with an unknown reaction coefficient. Two technical ideas are central to the developments in the note: a nonquadratic Lyapunov function and a normalization in the Lyapunov-based update law. The optimal adaptive control problem is fundamentally nonlinear and we explore this aspect through several examples that highlight the interplay between the non-quadratic cost and value functions.     

Bias Reduction in Variational Regularization

The aim of this paper was to introduce and study a two-step debiasing method for variational regularization. After solving the standard variational problem, the key idea is to add a consecutive debiasing step minimizing the data fidelity on an appropriate set, the so-called model manifold. The latter is defined by Bregman distances or infimal convolutions thereof, using the (uniquely defined) subgradient appearing in the optimality condition of the variational method. For particular settings, such as anisotropic \(\ell ^1\) and TV-type regularization, previously used debiasing techniques are shown to be special cases. The proposed approach is, however, easily applicable to a wider range of regularizations. The two-step debiasing is shown to be well-defined and to optimally reduce bias in a certain setting. In addition to visual and PSNR-based evaluations, different notions of bias and variance decompositions are investigated in numerical studies. The improvements offered by the proposed scheme are demonstrated, and its performance is shown to be comparable to optimal results obtained with Bregman iterations.