Academic literature on the topic 'Active Set Newton Algorithm'

In this paper, a stochastic quasi-Newton algorithm for nonconvex stochastic optimization is presented. It is derived from a classical modified BFGS formula. The update formula can be extended to the framework of limited memory scheme. Numerical experiments on some problems in machine learning are given. The results show that the proposed algorithm has great prospects.

Solving systems of nonlinear equations and inequalities is of critical importance in many engineering problems. In general, the existence of inequalities in the problem adds to its difficulty. We propose a new projected Hessian Gauss-Newton algorithm for solving general nonlinear systems of equalities and inequalities. The algorithm uses the projected Gauss-Newton Hessian in conjunction with an active set strategy that identifies active inequalities and a trust-region globalization strategy that ensures convergence from any starting point. We also present a global convergence theory for the proposed algorithm.

Phase-field fracture models lead to variational problems that can be written as a coupled variational equality and inequality system. Numerically, such problems can be treated with Galerkin finite elements and primal-dual active set methods. Specifically, low-order and high-order finite elements may be employed, where, for the latter, only few studies exist to date. The most time-consuming part in the discrete version of the primal-dual active set (semi-smooth Newton) algorithm consists in the solutions of changing linear systems arising at each semi-smooth Newton step. We propose a new parallel matrix-free monolithic multigrid preconditioner for these systems. We provide two numerical tests, and discuss the performance of the parallel solver proposed in the paper. Furthermore, we compare our new preconditioner with a block-AMG preconditioner available in the literature.

As is well known, the nonnegative matrix factorization (NMF) is a dimension reduction method that has been widely used in image processing, text compressing, signal processing, and so forth. In this paper, an algorithm on nonnegative matrix approximation is proposed. This method is mainly based on a relaxed active set and the quasi-Newton type algorithm, by using the symmetric rank-one and negative curvature direction technologies to approximate the Hessian matrix. The method improves some recent results. In addition, some numerical experiments are presented in the synthetic data, imaging processing, and text clustering. By comparing with the other six nonnegative matrix approximation methods, this method is more robust in almost all cases.

ABSTRACT We present a machine learning model to classify active galactic nuclei (AGNs) and galaxies (AGN-galaxy classifier) and a model to identify type 1 (optically unabsorbed) and type 2 (optically absorbed) AGN (type 1/2 classifier). We test tree-based algorithms, using training samples built from the X-ray Multi-Mirror Mission–Newton (XMM–Newton) catalogue and the Sloan Digital Sky Survey (SDSS), with labels derived from the SDSS survey. The performance was tested making use of simulations and of cross-validation techniques. With a set of features including spectroscopic redshifts and X-ray parameters connected to source properties (e.g. fluxes and extension), as well as features related to X-ray instrumental conditions, the precision and recall for AGN identification are 94 and 93 per cent, while the type 1/2 classifier has a precision of 74 per cent and a recall of 80 per cent for type 2 AGNs. The performance obtained with photometric redshifts is very similar to that achieved with spectroscopic redshifts in both test cases, while there is a decrease in performance when excluding redshifts. Our machine learning model trained on X-ray features can accurately identify AGN in extragalactic surveys. The type 1/2 classifier has a valuable performance for type 2 AGNs, but its ability to generalize without redshifts is hampered by the limited census of absorbed AGN at high redshift.

In this paper we give a general framework for isotone optimization. First we discuss a generalized version of the pool-adjacent-violators algorithm (PAVA) to minimize a separable convex function with simple chain constraints. Besides of general convex functions we extend existing PAVA implementations in terms of observation weights, approaches for tie handling, and responses from repeated measurement designs. Since isotone optimization problems can be formulated as convex programming problems with linear constraints we then develop a primal active set method to solve such problem. This methodology is applied on specific loss functions relevant in statistics. Both approaches are implemented in the R package isotone. (authors' abstract)

This thesis presents a study of impedance optimisation of active microstrip patch antennas to multiple frequency points. A single layered aperture coupled microstrip patch antenna has been optimised to match the source reflection coefficient of a transistor in designing an active antenna. The active aperture coupled microstrip patch antenna was optimised to satisfy Global Positioning System (GPS) frequency specifications. A rudimentary aperture coupled microstrip patch antenna consists of a rectangular antenna element etched on the top surface of two dielectric substrates. The substrates are separated by a ground plane and a microstrip feed is etched on the bottom surface. A rectangular aperture in the ground plane provides coupling between the feed and the antenna element. This type of antenna, which conveniently isolates any circuit at the feed from the antenna element, is suitable for integrated circuit design and is simple to fabricate. An active antenna design directly couples an antenna to an active device, therefore saving real estate and power. This thesis focuses on designing an aperture coupled patch antenna directly coupled to a low noise amplifier as part of the front end of a GPS receiver. In this work an in-house software package, dubbed ACP by its creator Dr Rod Waterhouse, for calculating aperture coupled microstrip patch antenna performance parameters was linked to HP-EEsof, a microwave computer aided design and simulation package by Hewlett-Packard. An ANSI C module in HP-EEsof was written to bind the two packages. This process affords the client the benefit of powerful analysis tools offered in HP-EEsof and the fast analysis of ACP for seamless system design. Moreover, the optimisation algorithms in HP-EEsof were employed to investigate which algorithms are best suited for optimising patch antennas. The active antenna design presented in this study evades an input matching network, which is accomplished by designing the antenna to represent the desired source termination of a transistor. It has been demonstrated that a dual-band microstrip patch antenna can be successfully designed to match the source reflection coefficient, avoiding the need to insert a matching network. Maximum power transfer in electrical circuits is accomplished by matching the impedance between entities, which is generally acheived with the use of a matching network. Passive matching networks employed in amplifier design generally consist of discrete components up to the low GHz frequency range or distributed elements at greater frequencies. The source termination for a low noise amplifier will greatly influence its noise, gain and linearity which is controlled by designing a suitable input matching network. Ten diverse search methods offered in HP-EEsof were used to optimise an active aperture coupled microstrip patch antenna. This study has shown that the algorithms based on the randomised search techniques and the Genetic algorithm provide the most robust performance. The optimisation results were used to design an active dual-band antenna.

In the last decade acoustic noise has become more and more regarded as a problem. In cars, boats, trains and aircraft, low-frequency noise reduces comfort. Lightweight materials and more powerful engines are used in high-speed vehicles, resulting in a general increase in interior noise levels. Low-frequency noise is annoying and during periods of long exposure it causes fatigue and discomfort. The masking effect which low-frequency noise has on speech reduces speech intelligibility. Low-frequency noise is sought to be attenuated in a wide range of applications in order to improve comfort and speech intelligibility. The use of conventional passive methods to attenuate low-frequency noise is often impractical since considerable bulk and weight are required; in transportation large weight is associated with high fuel consumption. In order to overcome the problems of ineffective passive suppression of low-frequency noise, the technique of active noise control has become of considerable interest. The fundamental principle of active noise control is based on secondary sources producing ``anti-noise.'' Destructive interference between the generated and the primary sound fields results in noise attenuation. Active noise control systems significantly increase the capacity for attenuating low-frequency noise without major increase in volume and weight. This doctoral dissertation deals with the topic of active noise control within the passenger cabin in aircraft, and within headsets. The work focuses on methods, controller structures and adaptive algorithms for attenuating tonal low-frequency noise produced by synchronized or moderately synchronized propellers generating beating sound fields. The control algorithm is a central part of an active noise control system. A multiple-reference feedforward controller based on the novel actuator-individual normalized Filtered-X Least-Mean-Squares algorithm is introduced, yielding significant attenuation of such period noise. This algorithm is of the LMS-type, and owing to the novel normalization it can also be regarded as a Newton-type algorithm. The new algorithm combines low computational complexity with high performance. For that reason the algorithm is suitable for use in systems with a large number of control sources and control sensors in order to reduce the computional power required by the control system. The computational power of the DSP hardware is limited, and therefore algorithms with high computational complexity allow fewer control sources and sensors to be used, often with reduced noise attenuation as a result. In applications, such as controlling aircraft cabin noise, where a large multiple-channel system is needed to control the relative complex interior sound field, it is of great importance to keep down the computational complexity of the algorithm so that a large number of loudspeakers and microphones can be used. The dissertation presents theoretical work, off-line computer experiments and practical real-time experiments using the actuator-individual normalized algorithm. The computer experiments are principally based on real-life cabin noise data recorded during flight in a twin-engine propeller aircraft and in a helicopter. The practical experiments were carried out in a full-scale fuselage section from a propeller aircraft.
Buller i vår dagliga miljö kan ha en negativ inverkan på vår hälsa. I många sammanhang, i tex bilar, båtar och flygplan, förekommer lågfrekvent buller. Lågfrekvent buller är oftast inte skadligt för hörseln, men kan vara tröttande och försvåra konversationen mellan personer som vistas i en utsatt miljö. En dämpning av bullernivån medför en förbättrad taluppfattbarhet samt en komfortökning. Att dämpa lågfrekvent buller med traditionella passiva metoder, tex absorbenter och reflektorer, är oftast ineffektivt. Det krävs stora, skrymmande absorbenter för att dämpa denna typ av buller samt tunga skiljeväggar för att förhindra att bullret transmitteras vidare från ett utrymme till ett annat. Metoder som är mera lämpade vid dämpning av lågfrekvent buller är de aktiva. De aktiva metoderna baseras på att en vågrörelse som ligger i motfas med en annan överlagras och de släcker ut varandra. Bullerdämpningen erhålls genom att ett ljudfält genereras som är lika starkt som bullret men i motfas med detta. De aktiva bullerdämpningsmetoderna medför en effektiv dämpning av lågfrekvent buller samtidigt som volymen, tex hos bilkupen eller båt/flygplanskabinen ej påverkas nämnvärt. Dessutom kan fordonets/farkostens vikt reduceras vilket är tacksamt för bränsleförbrukningen. I de flesta tillämpningar varierar bullrets karaktär, dvs styrka och frekvensinnehåll. För att följa dessa variationer krävs ett adaptivt (självinställande) reglersystem som styr genereringen av motljudet. I propellerflygplan är de dominerande frekvenserna i kabinbullret relaterat till propellrarnas varvtal, man känner alltså till frekvenserna som skall dämpas. Man utnyttjar en varvtalssignal för att generera signaler, så kallade referenssignaler, med de frekvenser som skall dämpas. Dessa bearbetas av ett reglersystem som generar signaler till högtalarna som i sin tur generar motljudet. För att ställa in högtalarsignalerna så att en effektiv dämpning erhålls, används mikrofoner utplacerade i kabinen som mäter bullret. För att åstadkomma en effektiv bullerdämpning i ett rum, tex i en flygplanskabin, behövs flera högtalare och mikrofoner, vilket kräver ett avancerat reglersystem. I doktorsavhandlingen ''Active Control of Propeller-Induced Noise in Aircraft'' behandlas olika metoder för att reducera kabinbuller härrörande från propellrarna. Här presenteras olika strukturer på reglersystem samt beräkningsalgoritmer för att ställa in systemet. För stora system där många högtalare och mikrofoner används, samt flera frekvenser skall dämpas, är det viktigt att systemet inte behöver för stor beräkningskapacitet för att generera motljudet. Metoderna som behandlas ger en effektiv dämpning till låg beräkningskostnad. Delar av materialet som presenteras i avhandlingen har ingått i ett EU-projekt med inriktning mot bullerundertryckning i propellerflygplan. I projektet har flera europeiska flygplanstillverkare deltagit. Avhandlingen behandlar även aktiv bullerdämpning i headset, som används av helikopterpiloter. I denna tillämpning har aktiv bullerdämpning används för att öka taluppfattbarheten.

Le but de cette thèse est de définir une méthode d'optimisation de formes qui conjugue l'utilisation de la dérivée seconde de forme et la méthode des lignes de niveaux pour la représentation d'une forme.On considèrera d'abord deux cas plus simples : un cas d'optimisation paramétrique et un cas d'optimisation discrète.Ce travail est divisé en quatre parties.La première contient le matériel nécessaire à la compréhension de l'ensemble de la thèse.Le premier chapitre rappelle des résultats généraux d'optimisation, et notamment le fait que les méthodes d'ordre deux ont une convergence quadratique sous certaines hypothèses.Le deuxième chapitre répertorie différentes modélisations pour l'optimisation de formes, et le troisième se concentre sur l'optimisation paramétrique puis l'optimisation géométrique.Les quatrième et cinquième chapitres introduisent respectivement la méthode des lignes de niveaux (level-set) et la méthode des éléments-finis.La deuxième partie commence par les chapitres 6 et 7 qui détaillent des calculs de dérivée seconde dans le cas de l'optimisation paramétrique puis géométrique.Ces chapitres précisent aussi la structure et certaines propriétés de la dérivée seconde de forme.Le huitième chapitre traite du cas de l'optimisation discrète.Dans le neuvième chapitre on introduit différentes méthodes pour un calcul approché de la dérivée seconde, puis on définit un algorithme de second ordre dans un cadre général.Cela donne la possibilité de faire quelques premières simulations numériques dans le cas de l'optimisation paramétrique (Chapitre 6) et dans le cas de l'optimisation discrète (Chapitre 7).La troisième partie est consacrée à l'optimisation géométrique.Le dixième chapitre définit une nouvelle notion de dérivée de forme qui prend en compte le fait que l'évolution des formes par la méthode des lignes de niveaux, grâce à la résolution d'une équation eikonale, se fait toujours selon la normale.Cela permet de définir aussi une méthode d'ordre deux pour l'optimisation.Le onzième chapitre détaille l'approximation d'intégrales de surface et le douzième chapitre est consacré à des exemples numériques.La dernière partie concerne l'analyse numérique d'algorithmes d'optimisation de formes par la méthode des lignes de niveaux.Le Chapitre 13 détaille la version discrète d'un algorithme d'optimisation de formes.Le Chapitre 14 analyse les schémas numériques relatifs à la méthodes des lignes de niveaux.Enfin le dernier chapitre fait l'analyse numérique complète d'un exemple d'optimisation de formes en dimension un, avec une étude des vitesses de convergence
The main purpose of this thesis is the definition of a shape optimization method which combines second-order differentiationwith the representation of a shape by a level-set function. A second-order method is first designed for simple shape optimization problems : a thickness parametrization and a discrete optimization problem. This work is divided in four parts.The first one is bibliographical and contains different necessary backgrounds for the rest of the work. Chapter 1 presents the classical results for general optimization and notably the quadratic rate of convergence of second-order methods in well-suited cases. Chapter 2 is a review of the different modelings for shape optimization while Chapter 3 details two particular modelings : the thickness parametrization and the geometric modeling. The level-set method is presented in Chapter 4 and Chapter 5 recalls the basics of the finite element method.The second part opens with Chapter 6 and Chapter 7 which detail the calculation of second-order derivatives for the thickness parametrization and the geometric shape modeling. These chapters also focus on the particular structures of the second-order derivative. Then Chapter 8 is concerned with the computation of discrete derivatives for shape optimization. Finally Chapter 9 deals with different methods for approximating a second-order derivative and the definition of a second-order algorithm in a general modeling. It is also the occasion to make a few numerical experiments for the thickness (defined in Chapter 6) and the discrete (defined in Chapter 8) modelings.Then, the third part is devoted to the geometric modeling for shape optimization. It starts with the definition of a new framework for shape differentiation in Chapter 10 and a resulting second-order method. This new framework for shape derivatives deals with normal evolutions of a shape given by an eikonal equation like in the level-set method. Chapter 11 is dedicated to the numerical computation of shape derivatives and Chapter 12 contains different numerical experiments.Finally the last part of this work is about the numerical analysis of shape optimization algorithms based on the level-set method. Chapter 13 is concerned with a complete discretization of a shape optimization algorithm. Chapter 14 then analyses the numerical schemes for the level-set method, and the numerical error they may introduce. Finally Chapter 15 details completely a one-dimensional shape optimization example, with an error analysis on the rates of convergence

Neste trabalho é apresentada uma abordagem do Método de Newton associado à função penalidade quadrática e ao método dos conjuntos ativos na solução do problema de Fluxo de Potência Ótimo (FPO). A formulação geral do problema de FPO é apresentada, assim como a técnica utilizada na resolução do sistema de equações. A fatoração da matriz Lagrangeana é feita por elementos ao invés das estruturas em blocos. A característica de esparsidade da matriz Lagrangeana é levada em consideração. Resultados dos testes realizados em 4 sistemas (3, 14, 30 e 118 barras) são apresentados.
This work presents an approach on Newton\'s Method associated with the quadratic penalty function and the active set methods in the solution of Optimal Power Flow Problem (OPF). The general formulation of the OPF problem is presented, as will as the technique used in the equation systems resolution. The Lagrangean matrix factorization is carried out by elements instead of structures in blocks. The characteristic of sparsity of the Lagrangean matrix is taken in to account. Numerical results of tests realized in systems of 3, 14, 30 and 118 buses are presented to show the efficiency of the method.

In computational science and engineering there are growing numbers of increasingly sophisticated, rigorous and realistic numerical simulations of physical systems. Detailed knowledge of a particular area of enquiry is expressed in mathematical terms, realised in computer programs and run on increasingly powerful computer systems. The use of such simulations is now commonplace in a growing collection of industrial design areas. Often, users of these models want to understand their behaviour in response to a variety of input stimuli, bounded by various operational parameters. Commonplace in the engineering design process is the need to find the combination of design parameters that minimise (or maximise) some design objective. Optimisation programs seek to apply mathematical techniques and heuristics to guide a computer in choosing trial parameter sets itself in an attempt to satisfy the expressed design objective. The more realistic the numerical simulations become, the more demanding of computational resources they become. Many of them consume hours, or days, of computing time on supercomputers to deliver a single trial solution. Optimisation algorithms invariably require the model be run more than once, often many times. In the absence of any means to reduce the computational cost of a single run any further, there can be two responses to this dilemma: 1. reduce the number of model evaluations required by the optimisation algorithm, or 2. reduce the time the whole collection of model evaluations takes by running as many as possible at the same time. The research in this thesis is directed toward developing methods that use the approach of parallel computing to reduce total optimisation time by exploiting concurrency within the optimisation algorithms developed. For generality it assumes the numerical simulations to which it may be applied will have real-valued parameters, i.e. they are continuous, and that they may be non-linear in nature. The following contributions are described: 1. The idea of developing a set of 'sandbox' case studies for effective testing of optimisation algorithms is presented and established as a feasible alternative to the use of artificial test functions. An initial set of problems with varying characteristics is also presented. 2. A parallel implementation of the quasi-Newton gradient method with BFGS update and its efficacy in comparison to a corresponding sequential algorithm and widely-used method of simulated annealing is demonstrated. 3. The use of a method of parallel line search with the Nelder-Mead simplex algorithm and its advantages compared to the original algorithm, in speed and reliability, are clearly shown. 4. New direct search methods, the Reducing Set Concurrent Simplex (RSCS) algorithm with line searching variants, are presented, and their superior performance compared to a variety of direct search methods demonstrated. 5. A novel Evolutionary Programming algorithm using concepts of self-organised criticality, EPSOC, is presented, and demonstrated to be superior in performance to a wide variety of gradient, direct search and stochastic methods on a set of test cases drawn from real-world problems. Evidence is presented of its potential for multi-objective optimisation using a novel implementation with multiple, 'virtual' archives. 6. Methods of preconditioning optimisation problems to reduce the total time taken to achieve an optimal result are presented. Temporal preconditioning, based on the time behaviour of the numerical simulations, is demonstrated to yield substantial speedup. 7. Some conclusions have been drawn on the applicability of specific optimisation methods to different classes of real-world problems. All of the methods described are implemented in the framework of a general-purpose optimisation toolset, Nimrod/O, to provide a sound basis for future work, easy adoption across a wide range of engineering design problems and potential commercial application.
Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
School of Computing and Information Technology
Full Text

Dans cette thèse, nous étudions trois types de problèmes stochastiques : les problèmes avec contraintes probabilistes, les problèmes distributionnellement robustes et les problèmes avec recours. Les difficultés des problèmes stochastiques sont essentiellement liées aux problèmes de convexité du domaine des solutions, et du calcul de l’espérance mathématique ou des probabilités qui nécessitent le calcul complexe d’intégrales multiples. A cause de ces difficultés majeures, nous avons résolu les problèmes étudiées à l’aide d’approximations efficaces.Nous avons étudié deux types de problèmes stochastiques avec des contraintes en probabilités, i.e., les problèmes linéaires avec contraintes en probabilité jointes (LLPC) et les problèmes de maximisation de probabilités (MPP). Dans les deux cas, nous avons supposé que les variables aléatoires sont normalement distribués et les vecteurs lignes des matrices aléatoires sont indépendants. Nous avons résolu LLPC, qui est un problème généralement non convexe, à l’aide de deux approximations basée sur les problèmes coniques de second ordre (SOCP). Sous certaines hypothèses faibles, les solutions optimales des deux SOCP sont respectivement les bornes inférieures et supérieures du problème du départ. En ce qui concerne MPP, nous avons étudié une variante du problème du plus court chemin stochastique contraint (SRCSP) qui consiste à maximiser la probabilité de la contrainte de ressources. Pour résoudre ce problème, nous avons proposé un algorithme de Branch and Bound pour calculer la solution optimale. Comme la relaxation linéaire n’est pas convexe, nous avons proposé une approximation convexe efficace. Nous avons par la suite testé nos algorithmes pour tous les problèmes étudiés sur des instances aléatoires. Pour LLPC, notre approche est plus performante que celles de Bonferroni et de Jaganathan. Pour MPP, nos résultats numériques montrent que notre approche est là encore plus performante que l’approximation des contraintes probabilistes individuellement.La deuxième famille de problèmes étudiés est celle relative aux problèmes distributionnellement robustes où une partie seulement de l’information sur les variables aléatoires est connue à savoir les deux premiers moments. Nous avons montré que le problème de sac à dos stochastique (SKP) est un problème semi-défini positif (SDP) après relaxation SDP des contraintes binaires. Bien que ce résultat ne puisse être étendu au cas du problème multi-sac-à-dos (MKP), nous avons proposé deux approximations qui permettent d’obtenir des bornes de bonne qualité pour la plupart des instances testées. Nos résultats numériques montrent que nos approximations sont là encore plus performantes que celles basées sur les inégalités de Bonferroni et celles plus récentes de Zymler. Ces résultats ont aussi montré la robustesse des solutions obtenues face aux fluctuations des distributions de probabilités. Nous avons aussi étudié une variante du problème du plus court chemin stochastique. Nous avons prouvé que ce problème peut se ramener au problème de plus court chemin déterministe sous certaine hypothèses. Pour résoudre ce problème, nous avons proposé une méthode de B&B où les bornes inférieures sont calculées à l’aide de la méthode du gradient projeté stochastique. Des résultats numériques ont montré l’efficacité de notre approche. Enfin, l’ensemble des méthodes que nous avons proposées dans cette thèse peuvent s’appliquer à une large famille de problèmes d’optimisation stochastique avec variables entières
In this thesis, we studied three types of stochastic problems: chance constrained problems, distributionally robust problems as well as the simple recourse problems. For the stochastic programming problems, there are two main difficulties. One is that feasible sets of stochastic problems is not convex in general. The other main challenge arises from the need to calculate conditional expectation or probability both of which are involving multi-dimensional integrations. Due to the two major difficulties, for all three studied problems, we solved them with approximation approaches.We first study two types of chance constrained problems: linear program with joint chance constraints problem (LPPC) as well as maximum probability problem (MPP). For both problems, we assume that the random matrix is normally distributed and its vector rows are independent. We first dealt with LPPC which is generally not convex. We approximate it with two second-order cone programming (SOCP) problems. Furthermore under mild conditions, the optimal values of the two SOCP problems are a lower and upper bounds of the original problem respectively. For the second problem, we studied a variant of stochastic resource constrained shortest path problem (called SRCSP for short), which is to maximize probability of resource constraints. To solve the problem, we proposed to use a branch-and-bound framework to come up with the optimal solution. As its corresponding linear relaxation is generally not convex, we give a convex approximation. Finally, numerical tests on the random instances were conducted for both problems. With respect to LPPC, the numerical results showed that the approach we proposed outperforms Bonferroni and Jagannathan approximations. While for the MPP, the numerical results on generated instances substantiated that the convex approximation outperforms the individual approximation method.Then we study a distributionally robust stochastic quadratic knapsack problems, where we only know part of information about the random variables, such as its first and second moments. We proved that the single knapsack problem (SKP) is a semedefinite problem (SDP) after applying the SDP relaxation scheme to the binary constraints. Despite the fact that it is not the case for the multidimensional knapsack problem (MKP), two good approximations of the relaxed version of the problem are provided which obtain upper and lower bounds that appear numerically close to each other for a range of problem instances. Our numerical experiments also indicated that our proposed lower bounding approximation outperforms the approximations that are based on Bonferroni's inequality and the work by Zymler et al.. Besides, an extensive set of experiments were conducted to illustrate how the conservativeness of the robust solutions does pay off in terms of ensuring the chance constraint is satisfied (or nearly satisfied) under a wide range of distribution fluctuations. Moreover, our approach can be applied to a large number of stochastic optimization problems with binary variables.Finally, a stochastic version of the shortest path problem is studied. We proved that in some cases the stochastic shortest path problem can be greatly simplified by reformulating it as the classic shortest path problem, which can be solved in polynomial time. To solve the general problem, we proposed to use a branch-and-bound framework to search the set of feasible paths. Lower bounds are obtained by solving the corresponding linear relaxation which in turn is done using a Stochastic Projected Gradient algorithm involving an active set method. Meanwhile, numerical examples were conducted to illustrate the effectiveness of the obtained algorithm. Concerning the resolution of the continuous relaxation, our Stochastic Projected Gradient algorithm clearly outperforms Matlab optimization toolbox on large graphs

This thesis addresses different aspects of machine listening using two different approaches, namely (1) A supervised and adaptive sparse representation based approach for identifying the type of background noise and the speaker and separating the speech and background noise, and (2) An unsupervised acoustic-phonetics knowledge based approach for detecting transitions between broad phonetic classes in a speech signal and significant excitation instants called as glottal closure instants (GCIs) in voiced speech, for applications like speech segmentation, recognition and modification. Real life speech signals generally contain a foreground speech by a particular speaker in the presence of a background environment like factory or traffic noise. These audio signals termed as noisy speech signals are available in the form of recordings say, audio intercepts or real time signals which can be single channel or multi channel. Real time signals are available during mobile communication and in hearing aids. Processing of these signals has been approached by the research community for various independent applications like classification of components of the noisy speech signal, source separation, enhancement, speech recognition, audio coding, duration modification and speaker normalization. Machine listening encapsulates solutions to these applications in a single system. It extracts useful information from noisy speech signals, and attempts to understand the content as much as humans do. In the case of speech enhancement, especially for the hearing impaired, the suppression of background noise for improving the intelligibility of speech would be more effective, if the type of background noise can be classified first. Other interesting applications of noise identification are forensics, machinery noise diagnostics, robotic navigation systems and acoustic signature classification of aircrafts or vehicles. Another motivation to identify the nature of background noise is to narrow down to the possible geographical location of a speaker. Speaker classification helps us to identify the speaker in an audio intercept. In the supervised sparse representation based approach, a dictionary learning based noise and speaker classification algorithm is proposed using a cosine similarity measure for learning atoms of the dictionary and is compared with other non-negative dictionary learning methods. For training, we learn dictionaries for speaker and noise sources separately using the various dictionary learning methods. We have used the Active Set Newton Algorithm (ASNA) and supervised non-negative matrix factorization for source recovery in the testing phase. Based on the objective measure of signal to distortion ratio (SDR), we get the frame-wise noise classification accuracy of 97.8% for fifteen different noises taken from the NOISEX database. The proposed evaluation metric of sum of weights (SW) applied on concatenated dictionaries gives a good accuracy, for speaker classification on clean speech, using high energy subsets of test frames and dictionary atoms. We get the best utterance level speaker classification accuracy of 100% for 30 speakers taken from TIMIT database on clean speech. We have then dealt with noisy speech signals assuming a single speaker speaking in a noisy environment. The noisy speech signals have been simulated at different SNRs using different noise and speaker sources. We have classified the speaker and background noise class of the noisy speech signal and subsequently separated the speech and noise components. Given a test noisy speech signal, a noise label is assigned to a subset of frames selected using the SDR measure, and an accumulated measure is used to classify the noise in the whole test signal. The speaker is classified using the proposed metric of accumulated sum of weights on high energy features, estimated using ASNA with L1 regularization from the concatenation of speaker dictionaries and the identified noise source dictionary. Using the dictionaries of the identified speaker and noise source, we obtain the estimate of the separated speech and noise signal using ASNA with L1 regularization and supervised non-negative matrix factorization (NMF). We obtain around 98% accuracy for noise classification and 89% for speaker classification at an SNR of 10 dB for a combination of 30 speakers and 15 noise sources. In the case of an unknown noise, the noise source is estimated as the nearest known noise label. The distribution of an unknown noise source amongst the known noise classes gives an indication of the possible noise source. The dictionary corresponding to the estimated noise label is updated adaptively using the features from the noise-only frames of the test signal. The updated dictionary is then used for speaker classification, and subsequently separation is carried out. In the case of an unknown speaker, the nearest speaker is estimated and the corresponding dictionary is updated using a clean speech segment from the test signal. We assume that a clean speech segment is available for adapting the speech dictionary. We have observed an improvement in signal to distortion ratio (SDR) after separation of speech and noise components using an adaptive dictionary. Adaptive noise dictionary gives an improvement of about 18% in speaker classification accuracy and 4 dB in SDR over an out-of-set dictionary, after enhancement of noisy speech at an SNR of 0 dB. In the case of a conversation, a divide and conquer algorithm is proposed to recursively estimate the noise sources, and estimate the approximate instant of noise transition and the number of noise types. We have then experimented on a conversation simulated by concatenating two different noise signals, each containing speech segments of distinct speakers and obtained a mean absolute error in the detection of noise transition instant of 10 ms at -10 dB SNR. Each of the segments obtained based on the transition instant can be treated as a single noise mixed with speech from a single speaker and subsequent speaker classification and source separation can be done as in the previous case. We have also addressed the classification of speakers and subsequent separation of speakers in overlapped speech, obtaining a mean speaker classification accuracy of 84% for the speaker 1 to speaker 2 ratio (S1S2R) of 0 dB. The advantage of the proposed dictionary learning and sparse representation based approach is that the training and classification model is independent of the selected classes of speakers and noises. Dictionaries for new classes can be easily added or the old classes can be removed or replaced instead of retraining. Also, the same model can be used for identifying other types of classes like language and gender. We have achieved speaker and noise classification and subsequent separation using only spectral features for dictionary learning. This is in contrast to the stochastic model based approaches where the model needs to be retrained whenever a new class is added. In the unsupervised acoustic-phonetics knowledge based approach, we detect transitions between broad phonetic classes in a speech signal which has applications such as landmark detection and segmentation. The proposed rule based hierarchical method detects transitions from silence to non-silence, sonorant to non-sonorant and vice-versa. We exploit the relative abrupt changes in the characteristics of the speech signal to detect the transitions. Relative thresholds learnt from a small development set are used to determine the parameter values. We propose different measures for detecting transitions between broad phonetic classes in a speech signal based on abrupt amplitude changes. A measure is defined on the quantized speech signal to detect transitions between very low amplitude or silence (S) and non-silence (N) segments. The S-segments could be stop closures, pauses or silence regions at the beginning and/or ending of an utterance. We propose two other measures to detect the transitions between sonorant and non-sonorant segments and vice-versa. We make use of the fact that most sonorants have higher energy in the low frequencies, than other phone classes such as unvoiced fricatives, affricates and unvoiced stops. For this reason, we use a bandpass speech signal (60-340 Hz) for extracting temporal features. A subset of the extrema (minimum or maximum amplitude samples) between every pair of successive zero-crossings and above a threshold is selected from each frame of the bandpass filtered speech signal. Occurrences of the first and the last extrema lie far before and after the mid-point (reference) of a frame, if the speech signal belongs to a non-transition segment; else, one of these locations lie within a few samples from the reference, indicating a transition frame. The advantage of this approach is that it does not require significant training data for determining the parameters of the proposed approach. When tested on the entire TIMIT database for clean speech, of the transitions detected, 93.6% are within a tolerance of 20 ms from the hand labeled boundaries. Sonorant, unvoiced non-sonorant and silence classes and their respective onsets are detected with an accuracy of about 83.5% for the same tolerance using the labelled TIMIT database as reference. The results are as good as, and in some respects better than the state-of-the-art methods for similar tasks. The proposed method is also tested on the test set of the TIMIT database for robustness with respect to white, babble and Schroeder noise, and about 90% of the transitions are detected within the tolerance of 20 ms at the signal to noise ratio of 5 dB. We have also estimated glottal closure instants (GCIs) useful for a variety of applications such as pitch and duration modification, speaking rate modification, pitch normalization, speech coding/ compression, and speaker normalization. The instant at which the vocal tract is significantly excited within each glottal cycle in a speech signal is referred to as the epoch or the GCI. Subband analysis of linear prediction residual (LPR) is proposed to estimate the GCIs from voiced speech segments. A composite signal is derived as the sum of the envelopes of the subband components of the LPR signal. Appropriately chosen peaks of the composite signal are the GCI candidates. The temporal locations of the candidates are refined using the LPR to obtain the GCIs, which are validated against the GCIs obtained from the electroglottograph signal, recorded simultaneously. The robustness is studied using additive white, pink, blue, babble, vehicle, HF channel noises for different signal to noise ratios and reverberation. The proposed method is evaluated using six different databases and compared with three state-of-the-art LPR based methods. The GCI detection performance of the proposed algorithm is quantified using the following measures: identification rate (IDR), miss rate (MR), false alarm rate (FAR), standard deviation of error (SDE) and accuracy to 0.25 ms. We have shown that significant GCI information exists in each subband of speech up to 2000 Hz, and a minimum of 89% identification rate (for subbands other than lowpass) can be obtained for clean speech using the proposed method. The results show that the performance of the proposed method is comparable to the best of the LPR based techniques for clean, and noisy speech.

The tutorial contains practical examples of organization and conducting accounting and tax accounting of foreign economic activity and the examples that reveal the specifics of foreign exchange operations. Given a multivariate system of control of knowledge of students with answers and solution algorithm is a full set of the Fund of assessment tools for current and intermediate control. Used active learning methods in the form of colloquiums, business games, discussions and other interactive forms. Meets the requirements of Federal state educational standards of higher education of the last generation. Designed for students enrolled in our undergraduate and graduate students of economic universities. It can be useful to executives and managers of organizations, chief accountants and economists, auditors in their practical work, as presented in the textbook material allows to solve a dispute.

The theory of phonological structure (called ‘Radical CV Phonology’) is first outlined in Chapter 2. This theory is a development of Dependency Phonology. The chapter introduces a theory of elements and minimal vowel representations based on the Successive Division Algorithm. Other topics of relevance are underspecification, markednes, and enhancement. The model of Radical CV Phonology functions as the theoretical background of the set of elements that are active in the harmony systems that will be analyzed in Chapters 4–10 and is, as such, of interest to readers who want to know why we have these particular elements.

Abstract In this paper we discuss applications of the numerical optimization methods for nonsmooth optimization, developed in [IK1] for the variational formulation of image restoration problems involving bounded variation type energy criterion. The Uzawa’s algorithm, first order augmented Lagrangian methods and Newton-like update using the active set strategy are described.

Abstract Solution of nonlinear design optimization problems via a sequence of linear programs is regaining attention for solving certain model classes, such as in structural design and chemical process design. An active set strategy modification of an algorithm by Palacios-Gomez is presented. A special interior linear programming algorithm with active set strategy is used also for solving the subproblem and generating the working set of the outer iterations. Examples are included.