Design with L-splines

We recently obtained a criterion to decide whether a given space of parametrically continuous piecewise Chebyshevian splines (i.e., splines with pieces taken from different Extended Chebyshev spaces) could be used for geometric design. One important field of application is the class of L-splines, that is, splines with pieces taken from the null space of some fixed real linear differential operator, generally investigated under the strong requirement that the null space should be an Extended Chebyshev space on the support of each possible B-spline. In the present work, we want to show the practical interest of the criterion in question for designing with L-splines. With this in view, we apply it to a specific class of linear differential operators with real constant coefficients and odd/even characteristic polynomials. We will thus establish necessary and sufficient conditions for the associated splines to be suitable for design. Because our criterion was achieved via a blossoming approach, shape preservation will be inherent in the obtained conditions. One specific advantage of the class of operators we consider is that hyperbolic and trigonometric functions can be mixed within the null space on which the splines are based. We show that this produces interesting shape effects.     

Optimal design of personalized prostate cancer therapy using Infinitesimal Perturbation Analysis

The standard treatment for advanced prostate cancer is hormone therapy in the form of continuous androgen suppression (CAS), which unfortunately frequently leads to resistance and relapse. An alternative scheme is intermittent androgen suppression (IAS), in which patients are submitted to cycles of treatment (in the form of androgen deprivation) and off-treatment periods in an alternating manner. In spite of extensive recent clinical experience with IAS, the design of ideal protocols for any given patient remains a challenge. The level of prostate specific antigen (PSA) is frequently monitored to determine when patients will be taken off therapy and when therapy will resume. In this work, we propose a threshold-based policy for optimal IAS therapy design that is parameterized by lower and upper PSA threshold values and is associated with a cost metric that combines clinically relevant measures of therapy success. We use a Stochastic Hybrid Automaton (SHA) model of prostate cancer evolution under IAS and perform Infinitesimal Perturbation Analysis (IPA) to adaptively adjust PSA threshold values so as to improve therapy outcomes. We also apply this methodology to clinical data from real patients, and obtain promising results and valuable insights for personalized IAS therapy design.     

Investigations of isotropy and homogeneity of spacetime in first-order logic

We investigate the logical connection between (spatial) isotropy, homogeneity of space, and homogeneity of time within a general axiomatic framework. We show that isotropy not only entails homogeneity of space, but also, in certain cases, homogeneity of time. In turn, homogeneity of time implies homogeneity of space in general, and the converse also holds true in certain cases.An important innovation in our approach is that formulations of physical properties are simultaneously empirical and axiomatic (in the sense of first-order mathematical logic). In this case, for example, rather than presuppose the existence of spacetime metrics – together with all the continuity and smoothness apparatus that would entail – the basic logical formulas underpinning our work refer instead to the sets of (idealised) experiments that support the properties in question, e.g., isotropy is axiomatised by considering a set of experiments whose outcomes remain unchanged under spatial rotation. Higher-order constructs are not needed.     

Reachability analysis of linear systems using support functions

This work is concerned with the algorithmic reachability analysis of continuous-time linear systems with constrained initial states and inputs. We propose an approach for computing an over-approximation of the set of states reachable on a bounded time interval. The main contribution over previous works is that it allows us to consider systems whose sets of initial states and inputs are given by arbitrary compact convex sets represented by their support functions. We actually compute two over-approximations of the reachable set. The first one is given by the union of convex sets with computable support functions. As the representation of convex sets by their support function is not suitable for some tasks, we derive from this first over-approximation a second one given by the union of polyhedrons. The overall computational complexity of our approach is comparable to the complexity of the most competitive available specialized algorithms for reachability analysis of linear systems using zonotopes or ellipsoids. The effectiveness of our approach is demonstrated on several examples.     

Endogenous effort in communication networks under strategic complementarity

This article examines individual incentives to produce information on communication networks. In our setting, efforts are strategic complements along communication paths with convex decay. We analyze the relationship between efforts and centrality on a set of networks which are unambiguous in terms of ordinal centrality. We first show that in both dominant and dominated equilibria central agents exert more effort. Second, we explore the issue of social coordination induced by our game.     

How behaviors spread in dynamic social networks

In this paper, we explore how decentralized local interactions of autonomous agents in a network relate to collective behaviors. Earlier work in this area has modeled social networks with fixed agent relations. We instead focus on dynamic social networks in which agents can rationally adjust their neighborhoods based on their individual interests. We propose a new connection evaluation theory, the Highest Weighted Reward (HWR) rule: agents dynamically choose their neighbors in order to maximize their own utilities based on rewards from previous interactions. We prove that, in the two-action pure coordination game, our system would stabilize to a clustering state in which all relationships in the network are rewarded with an optimal payoff. Our experiments verify this theory and also reveal additional interesting patterns in the network.     

Developing instructor support materials for an inquiry-oriented curriculum

The purpose of this paper is to describe the process of designing web-based instructor support materials for an inquiry oriented abstract algebra curriculum. First we discuss the ways in which the research literature influenced the design of the instructor support materials. Then we discuss the design-based research methods used to develop the instructor support materials, elaborating the ways in which the research phases of our work contributed to the design of the instructor support materials. This discussion includes specific examples of important insights from our research and precisely how these were incorporated into the support materials.     

基于改进的证据推理方法的多指标决策模型

对于一个多指标决策问题，证据理论可以通过构造辨识框架和基本概率分配函数、采取递归的证据合成方法。计算出原始数据在反映多个指标联合作用的情况下对不同判别结果的支持程度，并可以在信息复杂或数据不完整的条件下做出评估决策。本文首先建立基于证据推理的多指标评估问题的基本模型，然后引入了模糊数据方法以处理具有模糊概念或推理关系的复杂问题，同时还考虑了实际问题中可能出现加权证据或者相关证据的情况，其目的是为了建立一套具有实用性的、准确有效的多指标评估模型。文章最后设计一个风险评估的算例，分析了该方法的优点以及需要进一步完善之处。     

A comparison of three heuristics on a practical case of sub-daily staff scheduling

Sub-daily personnel planning, which is the focus of our work offers considerable productivity reserves for companies in certain industries, such as logistics, retail and call centres. However, it also creates complex challenges for the planning software. We compare particle swarm optimisation (PSO), the evolution strategy (ES) and a constructive agent-based heuristic on a set of staff scheduling problems derived from a practical case in logistics. All heuristics significantly outperform conventional manual full-day planning, demonstrating the value of sub-daily scheduling heuristics. PSO delivers the best overall results in terms of solution quality and is the method of choice, when CPU-time is not limited. The approach based on artificial agents is competitive with ES and delivers solutions of almost the same quality as PSO, but is vastly quicker. This suggests that agents could be an interesting method for real-time scheduling or re-scheduling tasks.     

Multicriterion Aerodynamic Shape Design Optimization and Inverse Problems Using Control Theory and Nash Games

Multicriterion design is gaining importance in aeronautics in order to cope with new needs of society. In the literature, contributions to single discipline and/or single-point design optimization abound. The goal of this paper is to introduce a new approach combining the adjoint method with a formulation derived from game theory for multipoint aerodynamic design problems. Transonic flows around lifting airfoils are analyzed via Euler computations. Airfoil shapes are optimized according to various aerodynamic criteria. The notion of player is introduced. In a competitive Nash game, each player attempts to optimize its own criterion through a symmetric exchange of information with others. A Nash equilibrium is reached when each player, constrained by the strategy of the others, cannot improve further its own criterion. Specific real and virtual symmetric Nash games are implemented to set up an optimization strategy for design under conflict. This work has benefited partially from the support of the National Science Foundation of China Grant NSFC-10372040 and Scientific Research Foundation (SRF) for Returned Overseas Chinese Scholars (ROCS) Grant 2003-091. The first author acknowledges the support of INRIA (Institut National de Recherche en Information et en Automatique), France.     

Boundedness of bilinear multipliers whose symbols have a narrow support

This work is devoted to studying the boundedness on Lebesgue spaces of bilinear multipliers on ? whose symbol is narrowly supported around a curve (in the frequency plane). We are looking for the optimal decay rate (depending on the width of this support) for exponents satisfying a sub-Hölder scaling. As expected, the geometry of the curve plays an important role, which is described. This has applications to the bilinear Bochner-Riesz problem (in particular, boundedness of multipliers whose symbol is the characteristic function of a set), as well as to the bilinear restriction-extension problem.     

Characterization and computation of control invariant sets for linear impulsive control systems

Impulsive control systems are suitable to describe and control a venue of real-life problems, going from disease treatment to aerospace guidance. The main characteristic of such systems is that they evolve freely in-between impulsive actions, which makes it difficult to guarantee its permanence in a given state-space region. In this work, we develop a method for characterizing and computing approximations to the maximal control invariant sets for linear impulsive control systems, which can be explicitly used to formulate a set-based model predictive controller. We approach this task using a tractable and non-conservative characterization of the admissible state sets, namely the states whose free response remains within given constraints, emerging from a spectrahedron representation of such sets for systems with rational eigenvalues. The so-obtained impulsive control invariant set is then explicitly used as a terminal set of a predictive controller, which guarantees the feasibly asymptotic convergence to a target set containing the invariant set. Necessary conditions under which an arbitrary target set contains an impulsive control invariant set (and moreover, an impulsive control equilibrium set) are also provided, while the controller performance are tested by means of two simulation examples.     

Stability analysis of probabilistic Boolean networks with switching topology

This paper investigates the set stability of probabilistic Boolean networks (PBNs) with switching topology. To deal with this problem, two novel concepts, set reachability and the largest invariant set family, are defined. By constructing an auxiliary system, the necessary and sufficient conditions for verifying set reachability are given and the calculation method for the largest invariant set family is obtained. Based on these two results, an equivalent condition of set stability is derived, which can be used to determine whether a PBN with switching topology can be stabilized to a given set. In addition, the design method of switching signal is proposed by combining the characteristic of the largest invariant set family, and a numerical example is reported to demonstrate the efficiency of presented approach.     

Sequence Independent Lifting for Mixed Integer Programs with Variable Upper Bounds

We investigate the convex hull of the set defined by a single inequality with continuous and binary variables with variable upper bound constraints. We extend the traditional flow cover inequality, and show that it is valid for a restriction of the set in which some variables are fixed. We also give conditions under which this inequality is facet-defining and, when it is not, we show how it can be lifted to obtain valid inequalities for the entire set using sequence independent lifting. In general, computing the lifting function is NP-hard, but under an additional restriction on the cover we obtain a closed form. Finally, we show how these results imply and extend known results about the single node fixed charge flow polyhedron. This material is based upon work supported by the National Science Foundation under Grant No. 0084826. Received: April 2004     

The transportation problem revisited—preprocessing before using the primal–dual algorithm

We give a necessary condition for the existence of a feasible solution for the transportation problem through a set of admissible cells, and an algorithm to find a set of admissible cells that satisfies the necessary condition. Either there exists a feasible solution through the admissible cells (which is therefore optimal since the complementary slackness conditions hold) or we could begin using the primal–dual algorithm (PDA) at this point. Our approach has two important advantages: Our O(mn) procedure for updating dual variables takes much less computing time than any procedure for solving a maximum flow problem in the primal phase of the PDA. We are never concerned by the degeneracy problem as we are not seeking basic solutions, but admissible cells. An example is presented for illustrating our approach. We finally provide computational results for a set of 30 randomly generated instances. Comparison of our method with the PDA reveals a real speed up.     

Regularity conditions via generalized interiority notions in convex optimization: New achievements and their relation to some classical statements

For the existence of strong duality in convex optimization regularity conditions play an indisputable role. In this article we mainly deal with regularity conditions formulated by means of different generalizations of the notion of interior of a set. The primal–dual pair we investigate is a general one expressed in the language of a perturbation function and by employing its Fenchel–Moreau conjugate. After providing an overview on the generalized interior-point conditions that exist in the literature we introduce several new ones formulated by means of the quasi-interior and quasi-relative interior. We underline the advantages of the new conditions vis-á-vis the classical ones and illustrate our investigations by numerous examples. We conclude this article by particularizing the general approach to the classical Fenchel and Lagrange duality concepts.     

最小顶点覆盖问题的加权分治算法

最小顶点覆盖问题是组合优化中经典NP-Hard问题之一,其在实际问题中有着广泛的应用。加权分治技术是算法设计和复杂性分析中的新技术,该技术主要用于对分支降阶的递归算法进行复杂性分析,其核心思想可以理解为依据问题不同的特征设置一组相应的权值,以求降低该算法最坏情况下的时间复杂度。本文依据加权分治技术设计出一个分支降阶递归算法来求解最小顶点覆盖问题,并通过加权分治技术分析得出该算法的时间复杂度为O(1.255ⁿ),优于常规分析下的时间复杂度O(1.325ⁿ) 。本文中的结果表明运用上述方法降低算法的时间复杂度是非常有效的。