Network flow-control using asynchronous stochastic approximation

We propose several stochastic approximation implementations for related algorithms in flow-control of communication networks. First, a discrete-time implementation of Kelly's primal flow-control algorithm is proposed. Convergence with probability 1 is shown, even in the presence of communication delays and stochastic effects seen in link congestion indications. This ensues from an analysis of the flow-control algorithm using the asynchronous stochastic approximation (ASA) framework. Two relevant enhancements are then pursued: a) an implementation of the primal algorithm using second-order information, and b) an implementation where edge-routers rectify misbehaving flows. Next, discretetime implementations of Kelly's dual algorithm and primaldual algorithm are proposed. Simulation results a) verifying the proposed algorithms and, b) comparing the stability properties are presented.

On duality in linear fractional programming

In this paper, a dual of a given linear fractional program is defined and the weak, direct and converse duality theorems are proved. Both the primal and the dual are linear fractional programs. This duality theory leads to necessary and sufficient conditions for the optimality of a given feasible solution. A unmerical example is presented to illustrate the theory in this connection. The equivalence of Charnes and Cooper dual and Dinkelbach’s parametric dual of a linear fractional program is also established.

Partial instantiation methods for inference in first-order logic

Satisfiability algorithms for propositional logic have improved enormously in recently years. This improvement increases the attractiveness of satisfiability methods for first-order logic that reduce the problem to a series of ground-level satisfiability problems. R. Jeroslow introduced a partial instantiation method of this kind that differs radically from the standard resolution-based methods. This paper lays the theoretical groundwork for an extension of his method that is general enough and efficient enough for general logic programming with indefinite clauses. In particular we improve Jeroslow's approach by (1) extending it to logic with functions, (2) accelerating it through the use of satisfiers, as introduced by Gallo and Rago, and (3) simplifying it to obtain further speedup. We provide a similar development for a "dual" partial instantiation approach defined by Hooker and suggest a primal-dual strategy. We prove correctness of the primal and dual algorithms for full first-order logic with functions, as well as termination on unsatisfiable formulas. We also report some preliminary computational results.

Efficient Algorithms for Linear Summed Error Structural SVMs

Structural Support Vector Machines (SSVMs) have become a popular tool in machine learning for predicting structured objects like parse trees, Part-of-Speech (POS) label sequences and image segments. Various efficient algorithmic techniques have been proposed for training SSVMs for large datasets. The typical SSVM formulation contains a regularizer term and a composite loss term. The loss term is usually composed of the Linear Maximum Error (LME) associated with the training examples. Other alternatives for the loss term are yet to be explored for SSVMs. We formulate a new SSVM with Linear Summed Error (LSE) loss term and propose efficient algorithms to train the new SSVM formulation using primal cutting-plane method and sequential dual coordinate descent method. Numerical experiments on benchmark datasets demonstrate that the sequential dual coordinate descent method is faster than the cutting-plane method and reaches the steady-state generalization performance faster. It is thus a useful alternative for training SSVMs when linear summed error is used.

Stochastic optimization for adaptive labor staffing in service systems

Service systems are labor intensive. Further, the workload tends to vary greatly with time. Adapting the staffing levels to the workloads in such systems is nontrivial due to a large number of parameters and operational variations, but crucial for business objectives such as minimal labor inventory. One of the central challenges is to optimize the staffing while maintaining system steady-state and compliance to aggregate SLA constraints. We formulate this problem as a parametrized constrained Markov process and propose a novel stochastic optimization algorithm for solving it. Our algorithm is a multi-timescale stochastic approximation scheme that incorporates a SPSA based algorithm for ‘primal descent' and couples it with a ‘dual ascent' scheme for the Lagrange multipliers. We validate this optimization scheme on five real-life service systems and compare it with a state-of-the-art optimization tool-kit OptQuest. Being two orders of magnitude faster than OptQuest, our scheme is particularly suitable for adaptive labor staffing. Also, we observe that it guarantees convergence and finds better solutions than OptQuest in many cases.

Bounds on the sum-rate capacity of the Gaussian MIMO X channel

We consider the MIMO X channel (XC), a system consisting of two transmit-receive pairs, where each transmitter communicates with both the receivers. Both the transmitters and receivers are equipped with multiple antennas. First, we derive an upper bound on the sum-rate capacity of the MIMO XC under individual power constraint at each transmitter. The sum-rate capacity of the two-user multiple access channel (MAC) that results when receiver cooperation is assumed forms an upper bound on the sum-rate capacity of the MIMO XC. We tighten this bound by considering noise correlation between the receivers and deriving the worst noise covariance matrix. It is shown that the worst noise covariance matrix is a saddle-point of a zero-sum, two-player convex-concave game, which is solved through a primal-dual interior point method that solves the maximization and the minimization parts of the problem simultaneously. Next, we propose an achievable scheme which employs dirty paper coding at the transmitters and successive decoding at the receivers. We show that the derived upper bound is close to the achievable region of the proposed scheme at low to medium SNRs.

Scalable sequential alternating proximal methods for sparse structural SVMs and CRFs

Structural Support Vector Machines (SSVMs) and Conditional Random Fields (CRFs) are popular discriminative methods used for classifying structured and complex objects like parse trees, image segments and part-of-speech tags. The datasets involved are very large dimensional, and the models designed using typical training algorithms for SSVMs and CRFs are non-sparse. This non-sparse nature of models results in slow inference. Thus, there is a need to devise new algorithms for sparse SSVM and CRF classifier design. Use of elastic net and L1-regularizer has already been explored for solving primal CRF and SSVM problems, respectively, to design sparse classifiers. In this work, we focus on dual elastic net regularized SSVM and CRF. By exploiting the weakly coupled structure of these convex programming problems, we propose a new sequential alternating proximal (SAP) algorithm to solve these dual problems. This algorithm works by sequentially visiting each training set example and solving a simple subproblem restricted to a small subset of variables associated with that example. Numerical experiments on various benchmark sequence labeling datasets demonstrate that the proposed algorithm scales well. Further, the classifiers designed are sparser than those designed by solving the respective primal problems and demonstrate comparable generalization performance. Thus, the proposed SAP algorithm is a useful alternative for sparse SSVM and CRF classifier design.

Social insect colony as a biological regulatory system: modelling information flow in dominance networks

Social insects provide an excellent platform to investigate flow of information in regulatory systems since their successful social organization is essentially achieved by effective information transfer through complex connectivity patterns among the colony members. Network representation of such behavioural interactions offers a powerful tool for structural as well as dynamical analysis of the underlying regulatory systems. In this paper, we focus on the dominance interaction networks in the tropical social wasp Ropalidia marginata-a species where behavioural observations indicate that such interactions are principally responsible for the transfer of information between individuals about their colony needs, resulting in a regulation of their own activities. Our research reveals that the dominance networks of R. marginata are structurally similar to a class of naturally evolved information processing networks, a fact confirmed also by the predominance of a specific substructure-the `feed-forward loop'-a key functional component in many other information transfer networks. The dynamical analysis through Boolean modelling confirms that the networks are sufficiently stable under small fluctuations and yet capable of more efficient information transfer compared to their randomized counterparts. Our results suggest the involvement of a common structural design principle in different biological regulatory systems and a possible similarity with respect to the effect of selection on the organization levels of such systems. The findings are also consistent with the hypothesis that dominance behaviour has been shaped by natural selection to co-opt the information transfer process in such social insect species, in addition to its primal function of mediation of reproductive competition in the colony.

Simultaneous perturbation methods for adaptive labor staffing in service systems

We consider the problem of optimizing the workforce of a service system. Adapting the staffing levels in such systems is non-trivial due to large variations in workload and the large number of system parameters do not allow for a brute force search. Further, because these parameters change on a weekly basis, the optimization should not take longer than a few hours. Our aim is to find the optimum staffing levels from a discrete high-dimensional parameter set, that minimizes the long run average of the single-stage cost function, while adhering to the constraints relating to queue stability and service-level agreement (SLA) compliance. The single-stage cost function balances the conflicting objectives of utilizing workers better and attaining the target SLAs. We formulate this problem as a constrained parameterized Markov cost process parameterized by the (discrete) staffing levels. We propose novel simultaneous perturbation stochastic approximation (SPSA)-based algorithms for solving the above problem. The algorithms include both first-order as well as second-order methods and incorporate SPSA-based gradient/Hessian estimates for primal descent, while performing dual ascent for the Lagrange multipliers. Both algorithms are online and update the staffing levels in an incremental fashion. Further, they involve a certain generalized smooth projection operator, which is essential to project the continuous-valued worker parameter tuned by our algorithms onto the discrete set. The smoothness is necessary to ensure that the underlying transition dynamics of the constrained Markov cost process is itself smooth (as a function of the continuous-valued parameter): a critical requirement to prove the convergence of both algorithms. We validate our algorithms via performance simulations based on data from five real-life service systems. For the sake of comparison, we also implement a scatter search based algorithm using state-of-the-art optimization tool-kit OptQuest. From the experiments, we observe that both our algorithms converge empirically and consistently outperform OptQuest in most of the settings considered. This finding coupled with the computational advantage of our algorithms make them amenable for adaptive labor staffing in real-life service systems.

Evaluation of wheat or corn dried distillers' grains with solubles on performance and carcass characteristics of feedlot steers

[EN]A study was conducted on crossbred steers (n=275; 376±924 kg) to evaluate performance and carcass quality of cattle fed wheat or corn dried distillers’ grains with solubles (DDGS). The control ration contained 86.6% rolled barley grain, 5.7% supplement and 7.7% barley silage (DM basis). The four treatments included replacement of barley grain at 20 or 40% of the diet (DM basis) with wheat or corn DDGS. Steers were slaughtered at a common end weight of 645 kg with 100 steers randomly (n=20 per treatment) selected for determination of the retail yield of sub-primal boneless boxed beef (SPBBB). Data were analyzed as a completely randomized design using pen as the experimental unit. Feeding increasing levels of wheat DDGS led to a quadratic increase in dry matter intake (DMI) (P<0.01), whereas increasing levels of corn DDGS led to a quadratic decrease in DMI (P=0.01). Average daily gain was not influenced (P=0.13) by feeding wheat or corn DDGS, but cattle fed corn DDGS exhibited a quadratic increase (P=0.01) in gain:feed. As a result, a quadratic increase (P<0.01) in calculated NEg of the diet was observed as corn DDGS levels increased. A linear decrease (P=0.04) in days on feed (169, 166 and 154 d) was noted when increasing levels of wheat DDGS (0, 20 and 40%) were fed. Dressing percentage increased in a linear fashion with wheat DDGS (P<0.01) inclusion level and in a quadratic fashion (P=0.01) as corn DDGS inclusion level increased although other carcass traits were not affected (P=0.10) by treatment. The results indicate that replacement of barley grain with corn or wheat DDGS up to 40% of the diet (DM) can lead to superior performance (improved gain:feed or reduced days on feed, respectively) with no detrimental effect on quality grade or carcass SPBBB yield.

Fishing effort validation and substitution possibilities among components: the case study of the VIII division European anchovy fishery

Command and control regulation programs, particularly input constraints, typically fail to achieve stated objectives, because fishermen may substitute unregulated for regulated inputs. It is, thus, essential to have an understanding of the internal structure of production technology. A primal formulation is used to estimate a translog production function at the vessels level that includes fishing effort and fisherman’s skill. The flexibility of the selected functional permits the analysis of the substitution possibilities among inputs by estimating the elasticity of substitution with no prior constraints. Particular attention is paid to the empirical validation of fishing effort as an aggregate input, which implies either, the acceptation of the joint hypothesis that inputs making up effort are weakly separable from the inputs out of the subgroup or considering that effort is an intermediate input produced by a non-separable two stage technology. Cross sectional data from the Spanish purse seine fleet operating in the VIII Division European anchovy fishery provide evidence of limited input substitution possibilities among the inputs making up the empirically validated fishing effort translog micro-production function.

Optimizar una producción II. Estudio y Comparación de un Problema de Programación lineal y su Dual. Resolución y Valoración de un caso práctico y su programación usando Excel y Win QSB.

En este trabajo se va a explicar la relación que existe entre la optimización de un problema lineal y el problema dual correspondiente. Se usara la herramienta Solver del Microsoft Excel para resolver los el problema de programación lineal planteado. Se analizaran los resultados obtenidos tanto del problema primal como del problema dual y se explicara el significado de los resultados obtenidos. Se finalizara con unas conclusiones donde se expondría lo aprendido durante este trabajo y el significado económico de este tipo de problemas.

A Direct Approach to Robustness Optimization

This dissertation reformulates and streamlines the core tools of robustness analysis for linear time invariant systems using now-standard methods in convex optimization. In particular, robust performance analysis can be formulated as a primal convex optimization in the form of a semidefinite program using a semidefinite representation of a set of Gramians. The same approach with semidefinite programming duality is applied to develop a linear matrix inequality test for well-connectedness analysis, and many existing results such as the Kalman-Yakubovich--Popov lemma and various scaled small gain tests are derived in an elegant fashion. More importantly, unlike the classical approach, a decision variable in this novel optimization framework contains all inner products of signals in a system, and an algorithm for constructing an input and state pair of a system corresponding to the optimal solution of robustness optimization is presented based on this information. This insight may open up new research directions, and as one such example, this dissertation proposes a semidefinite programming relaxation of a cardinality constrained variant of the H ∞ norm, which we term sparse H ∞ analysis, where an adversarial disturbance can use only a limited number of channels. Finally, sparse H ∞ analysis is applied to the linearized swing dynamics in order to detect potential vulnerable spots in power networks.

Distribution of Healthcare resources II.Study and Comparison of a Linear Programming Problem and its Dual. Resolution and Evaluation of a Practical Case and its Programming using Excel and Win QSB.

[EN]This research had as primary objective to model different types of problems using linear programming and apply different methods so as to find an adequate solution to them. To achieve this objective, a linear programming problem and its dual were studied and compared. For that, linear programming techniques were provided and an introduction of the duality theory was given, analyzing the dual problem and the duality theorems. Then, a general economic interpretation was given and different optimal dual variables like shadow prices were studied through the next practical case: An aesthetic surgery hospital wanted to organize its monthly waiting list of four types of surgeries to maximize its daily income. To solve this practical case, we modelled the linear programming problem following the relationships between the primal problem and its dual. Additionally, we solved the dual problem graphically, and then we found the optimal solution of the practical case posed through its dual, following the different theorems of the duality theory. Moreover, how Complementary Slackness can help to solve linear programming problems was studied. To facilitate the solution Solver application of Excel and Win QSB programme were used.

Os sistemas de recompensa nas interfaces contemporâneas de comunicação

Na atualidade observa-se vastos estudos sobre os processos na área do Design acerca de como projetar experiências e prototipar interações entre pessoas e sistemas, e mesmo entre pessoas por intermédio de sistemas. Enquanto todo tipo de produto produz uma experiência de uso, com a evolução da interatividade as relações estabelecidas entre os usuários e os produtos tornaram-se mais complexas e modificaram-se ao longo dos anos. A abordagem teórica destinada a tratar essas questões também expandiu e diversificou-se simultaneamente. A partir de um estudo sobre os processos interativos e o campo teórico relacionado, foi possível identificar um fenômeno relativamente recente em interfaces nas quais pode ser verificado um alto nível de interação, a saber: os sistemas de recompensa. Cabe salientar que este termo foi emprestado da Neurociência, aonde é utilizado para descrever o circuito responsável pelo gerenciamento do comportamento através da indução de prazer e dor. Portanto, o autor desta dissertação propõe uma acepção do termo no âmbito do design de componentes interativos para designar o artifício, que muitas interfaces atuais incorporaram, de conceder aos usuários a possibilidade de apreciarem, ou não, determinado conteúdo em rede. Assim, pode-se compreender que o emprego do termo aqui é metafórico. Neste processo os usuários podem fornecer outros tipos de feedback ao sistema, como por exemplo um comentário, ou compartilhamento, estimulando assim uma série de desdobramentos interativos e repercussões para a experiência de uso do produto. Este trabalho propõe uma investigação qualitativa sobre as interações concernentes aos sistemas de recompensa, abordando tanto questões objetivas funcionais dos sistemas, quanto questões referentes ao feedback dos usuários. O Facebook será amplamente analisado, por ter sido uma interface pioneira na manipulação dos sistemas de recompensa, na qual estes componentes alcançaram um alto nível de desenvolvimento até este momento. A justificativa para esta pesquisa se deve a dois fatores particularmente relevantes: primeiro, a ausência de conteúdo significativo na literatura relacionada atual. Em segundo lugar, a notável expansão dos sistemas criados com esta finalidade, conforme será demonstrado no estudo. O objetivo deste projeto é compreender de que forma o design dos sistemas de recompensa influenciam o fluxo de interações e o comportamento dos usuários atualmente. Para tanto, esta pesquisa procura verificar como determinados aspectos teóricos do design - dedicados à compreensão da dinâmica de processos interativos - se aplicam a experiências reais de interação no mundo contemporâneo. Por exemplo, diversos modelos e frameworks nas áreas de HCI (Interação Humano-Computador), UX (experiência do usuário), e design de experiências destacam conceitos condizentes com aspectos identificados nos sistemas de recompensa que por sua vez encontram-se em processo de desenvolvimento, guiados por tendências comerciais de uma forma quase que intuitiva, no sentido de que pouca atenção tem sido dada na literatura sobre as bases neuronais que fazem este processo funcionar. Desta forma, pretende-se fornecer subsídios para uma melhor compreensão do impacto que os sistemas de recompensa analisados nesta dissertação desempenham sobre a experiência de uso entre consumidores e produtos delineados dentro deste paradigma