Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 12

Search results for: compactly semidefinite representable set

12 Approximation of Convex Set by Compactly Semidefinite Representable Set

Authors: Anusuya Ghosh, Vishnu Narayanan

Abstract:

The approximation of convex set by semidefinite representable set plays an important role in semidefinite programming, especially in modern convex optimization. To optimize a linear function over a convex set is a hard problem. But optimizing the linear function over the semidefinite representable set which approximates the convex set is easy to solve as there exists numerous efficient algorithms to solve semidefinite programming problems. So, our approximation technique is significant in optimization. We develop a technique to approximate any closed convex set, say K by compactly semidefinite representable set. Further we prove that there exists a sequence of compactly semidefinite representable sets which give tighter approximation of the closed convex set, K gradually. We discuss about the convergence of the sequence of compactly semidefinite representable sets to closed convex set K. The recession cone of K and the recession cone of the compactly semidefinite representable set are equal. So, we say that the sequence of compactly semidefinite representable sets converge strongly to the closed convex set. Thus, this approximation technique is very useful development in semidefinite programming.

Keywords: semidefinite programming, semidefinite representable set, compactly semidefinite representable set, approximation

Procedia PDF Downloads 286
11 An Optimization Model for Maximum Clique Problem Based on Semidefinite Programming

Authors: Derkaoui Orkia, Lehireche Ahmed

Abstract:

The topic of this article is to exploring the potentialities of a powerful optimization technique, namely Semidefinite Programming, for solving NP-hard problems. This approach provides tight relaxations of combinatorial and quadratic problems. In this work, we solve the maximum clique problem using this relaxation. The clique problem is the computational problem of finding cliques in a graph. It is widely acknowledged for its many applications in real-world problems. The numerical results show that it is possible to find a maximum clique in polynomial time, using an algorithm based on semidefinite programming. We implement a primal-dual interior points algorithm to solve this problem based on semidefinite programming. The semidefinite relaxation of this problem can be solved in polynomial time.

Keywords: semidefinite programming, maximum clique problem, primal-dual interior point method, relaxation

Procedia PDF Downloads 142
10 Second Representation of Modules over Commutative Rings

Authors: Jawad Abuhlail, Hamza Hroub

Abstract:

Let R be a commutative ring. Representation theory studies the representation of R-modules as (possibly finite) sums of special types of R-submodules. Here we are interested in a class of R-modules between the class of semisimple R-modules and the class of R-modules that can be written as (possibly finite) sums of secondary R-submodules (we know that every simple R-submodule is secondary). We investigate R-modules which can be written as (possibly finite) sums of second R-submodules (we call those modules second representable). Moreover, we investigate the class of (main) second attached prime ideals related to a module with such representation. We provide sufficient conditions for an R-module M to get a (minimal) second representation. We also found the collection of second attached prime ideals for some types of second representable R-modules, in particular within the class of injective R-modules. As we know that every simple R-submodule is second and every second R-submodule is secondary, we can see the importance of the second representable R-module.

Keywords: lifting modules, second attached prime ideals, second representations, secondary representations, semisimple modules, second submodules

Procedia PDF Downloads 92
9 Scalable Learning of Tree-Based Models on Sparsely Representable Data

Authors: Fares Hedayatit, Arnauld Joly, Panagiotis Papadimitriou

Abstract:

Many machine learning tasks such as text annotation usually require training over very big datasets, e.g., millions of web documents, that can be represented in a sparse input space. State-of the-art tree-based ensemble algorithms cannot scale to such datasets, since they include operations whose running time is a function of the input space size rather than a function of the non-zero input elements. In this paper, we propose an efficient splitting algorithm to leverage input sparsity within decision tree methods. Our algorithm improves training time over sparse datasets by more than two orders of magnitude and it has been incorporated in the current version of scikit-learn.org, the most popular open source Python machine learning library.

Keywords: big data, sparsely representable data, tree-based models, scalable learning

Procedia PDF Downloads 197
8 System Identification in Presence of Outliers

Authors: Chao Yu, Qing-Guo Wang, Dan Zhang

Abstract:

The outlier detection problem for dynamic systems is formulated as a matrix decomposition problem with low-rank, sparse matrices and further recast as a semidefinite programming (SDP) problem. A fast algorithm is presented to solve the resulting problem while keeping the solution matrix structure and it can greatly reduce the computational cost over the standard interior-point method. The computational burden is further reduced by proper construction of subsets of the raw data without violating low rank property of the involved matrix. The proposed method can make exact detection of outliers in case of no or little noise in output observations. In case of significant noise, a novel approach based on under-sampling with averaging is developed to denoise while retaining the saliency of outliers and so-filtered data enables successful outlier detection with the proposed method while the existing filtering methods fail. Use of recovered “clean” data from the proposed method can give much better parameter estimation compared with that based on the raw data.

Keywords: outlier detection, system identification, matrix decomposition, low-rank matrix, sparsity, semidefinite programming, interior-point methods, denoising

Procedia PDF Downloads 239
7 A Semidefinite Model to Quantify Dynamic Forces in the Powertrain of Torque Regulated Bascule Bridge Machineries

Authors: Kodo Sektani, Apostolos Tsouvalas, Andrei Metrikine

Abstract:

The reassessment of existing movable bridges in The Netherlands has created the need for acceptance/rejection criteria to assess whether the machineries are meet certain design demands. However, the existing design code defines a different limit state design, meant for new machineries which is based on a simple linear spring-mass model. Observations show that existing bridges do not confirm the model predictions. In fact, movable bridges are nonlinear systems consisting of mechanical components, such as, gears, electric motors and brakes. Next to that, each movable bridge is characterized by a unique set of parameters. However, in the existing code various variables that describe the physical characteristics of the bridge are neglected or replaced by partial factors. For instance, the damping ratio ζ, which is different for drawbridges compared to bascule bridges, is taken as a constant for all bridge types. In this paper, a model is developed that overcomes some of the limitations of existing modelling approaches to capture the dynamics of the powertrain of a class of bridge machineries First, a semidefinite dynamic model is proposed, which accounts for stiffness, damping, and some additional variables of the physical system, which are neglected by the code, such as nonlinear braking torques. The model gives an upper bound of the peak forces/torques occurring in the powertrain during emergency braking. Second, a discrete nonlinear dynamic model is discussed, with realistic motor torque characteristics during normal operation. This model succeeds to accurately predict the full time history of the occurred stress state of the opening and closing cycle for fatigue purposes.

Keywords: Dynamics of movable bridges, Bridge machinery, Powertrains, Torque measurements

Procedia PDF Downloads 58
6 On the Topological Entropy of Nonlinear Dynamical Systems

Authors: Graziano Chesi

Abstract:

The topological entropy plays a key role in linear dynamical systems, allowing one to establish the existence of stabilizing feedback controllers for linear systems in the presence of communications constraints. This paper addresses the determination of a robust value of the topological entropy in nonlinear dynamical systems, specifically the largest value of the topological entropy over all linearized models in a region of interest of the state space. It is shown that a sufficient condition for establishing upper bounds of the sought robust value of the topological entropy can be given in terms of a semidefinite program (SDP), which belongs to the class of convex optimization problems.

Keywords: non-linear system, communication constraint, topological entropy

Procedia PDF Downloads 255
5 Analytical Design of IMC-PID Controller for Ideal Decoupling Embedded in Multivariable Smith Predictor Control System

Authors: Le Hieu Giang, Truong Nguyen Luan Vu, Le Linh

Abstract:

In this paper, the analytical tuning rules of IMC-PID controller are presented for the multivariable Smith predictor that involved the ideal decoupling. Accordingly, the decoupler is first introduced into the multivariable Smith predictor control system by a well-known approach of ideal decoupling, which is compactly extended for general nxn multivariable processes and the multivariable Smith predictor controller is then obtained in terms of the multiple single-loop Smith predictor controllers. The tuning rules of PID controller in series with filter are found by using Maclaurin approximation. Many multivariable industrial processes are employed to demonstrate the simplicity and effectiveness of the presented method. The simulation results show the superior performances of presented method in compared with the other methods.

Keywords: ideal decoupler, IMC-PID controller, multivariable smith predictor, Padé approximation

Procedia PDF Downloads 345
4 The Second Smallest Eigenvalue of Complete Tripartite Hypergraph

Authors: Alfi Y. Zakiyyah, Hanni Garminia, M. Salman, A. N. Irawati

Abstract:

In the terminology of the hypergraph, there is a relation with the terminology graph. In the theory of graph, the edges connected two vertices. In otherwise, in hypergraph, the edges can connect more than two vertices. There is representation matrix of a graph such as adjacency matrix, Laplacian matrix, and incidence matrix. The adjacency matrix is symmetry matrix so that all eigenvalues is real. This matrix is a nonnegative matrix. The all diagonal entry from adjacency matrix is zero so that the trace is zero. Another representation matrix of the graph is the Laplacian matrix. Laplacian matrix is symmetry matrix and semidefinite positive so that all eigenvalues are real and non-negative. According to the spectral study in the graph, some that result is generalized to hypergraph. A hypergraph can be represented by a matrix such as adjacency, incidence, and Laplacian matrix. Throughout for this term, we use Laplacian matrix to represent a complete tripartite hypergraph. The aim from this research is to determine second smallest eigenvalues from this matrix and find a relation this eigenvalue with the connectivity of that hypergraph.

Keywords: connectivity, graph, hypergraph, Laplacian matrix

Procedia PDF Downloads 386
3 Design of Transmit Beamspace and DOA Estimation in MIMO Radar

Authors: S. Ilakkiya, A. Merline

Abstract:

A multiple-input multiple-output (MIMO) radar systems use modulated waveforms and directive antennas to transmit electromagnetic energy into a specific volume in space to search for targets. This paper deals with the design of transmit beamspace matrix and DOA estimation for multiple-input multiple-output (MIMO) radar with collocated antennas.The design of transmit beamspace matrix is based on minimizing the difference between a desired transmit beampattern and the actual one while enforcing the constraint of uniform power distribution across the transmit array elements. Rotational invariance property is established at the transmit array by imposing a specific structure on the beamspace matrix. Semidefinite programming and spatial-division based design (SDD) are also designed separately. In MIMO radar systems, DOA estimation is an essential process to determine the direction of incoming signals and thus to direct the beam of the antenna array towards the estimated direction. This estimation deals with non-adaptive spectral estimation and adaptive spectral estimation techniques. The design of the transmit beamspace matrix and spectral estimation techniques are studied through simulation.

Keywords: adaptive and non-adaptive spectral estimation, direction of arrival estimation, MIMO radar, rotational invariance property, transmit, receive beamforming

Procedia PDF Downloads 433
2 Quantum Information Scrambling and Quantum Chaos in Silicon-Based Fermi-Hubbard Quantum Dot Arrays

Authors: Nikolaos Petropoulos, Elena Blokhina, Andrii Sokolov, Andrii Semenov, Panagiotis Giounanlis, Xutong Wu, Dmytro Mishagli, Eugene Koskin, Robert Bogdan Staszewski, Dirk Leipold

Abstract:

We investigate entanglement and quantum information scrambling (QIS) by the example of a many-body Extended and spinless effective Fermi-Hubbard Model (EFHM and e-FHM, respectively) that describes a special type of quantum dot array provided by Equal1 labs silicon-based quantum computer. The concept of QIS is used in the framework of quantum information processing by quantum circuits and quantum channels. In general, QIS is manifest as the de-localization of quantum information over the entire quantum system; more compactly, information about the input cannot be obtained by local measurements of the output of the quantum system. In our work, we will first make an introduction to the concept of quantum information scrambling and its connection with the 4-point out-of-time-order (OTO) correlators. In order to have a quantitative measure of QIS we use the tripartite mutual information, in similar lines to previous works, that measures the mutual information between 4 different spacetime partitions of the system and study the Transverse Field Ising (TFI) model; this is used to quantify the dynamical spreading of quantum entanglement and information in the system. Then, we investigate scrambling in the quantum many-body Extended Hubbard Model with external magnetic field Bz and spin-spin coupling J for both uniform and thermal quantum channel inputs and show that it scrambles for specific external tuning parameters (e.g., tunneling amplitudes, on-site potentials, magnetic field). In addition, we compare different Hilbert space sizes (different number of qubits) and show the qualitative and quantitative differences in quantum scrambling as we increase the number of quantum degrees of freedom in the system. Moreover, we find a "scrambling phase transition" for a threshold temperature in the thermal case, that is, the temperature of the model that the channel starts to scramble quantum information. Finally, we make comparisons to the TFI model and highlight the key physical differences between the two systems and mention some future directions of research.

Keywords: condensed matter physics, quantum computing, quantum information theory, quantum physics

Procedia PDF Downloads 18
1 Maintenance Optimization for a Multi-Component System Using Factored Partially Observable Markov Decision Processes

Authors: Ipek Kivanc, Demet Ozgur-Unluakin

Abstract:

Over the past years, technological innovations and advancements have played an important role in the industrial world. Due to technological improvements, the degree of complexity of the systems has increased. Hence, all systems are getting more uncertain that emerges from increased complexity, resulting in more cost. It is challenging to cope with this situation. So, implementing efficient planning of maintenance activities in such systems are getting more essential. Partially Observable Markov Decision Processes (POMDPs) are powerful tools for stochastic sequential decision problems under uncertainty. Although maintenance optimization in a dynamic environment can be modeled as such a sequential decision problem, POMDPs are not widely used for tackling maintenance problems. However, they can be well-suited frameworks for obtaining optimal maintenance policies. In the classical representation of the POMDP framework, the system is denoted by a single node which has multiple states. The main drawback of this classical approach is that the state space grows exponentially with the number of state variables. On the other side, factored representation of POMDPs enables to simplify the complexity of the states by taking advantage of the factored structure already available in the nature of the problem. The main idea of factored POMDPs is that they can be compactly modeled through dynamic Bayesian networks (DBNs), which are graphical representations for stochastic processes, by exploiting the structure of this representation. This study aims to demonstrate how maintenance planning of dynamic systems can be modeled with factored POMDPs. An empirical maintenance planning problem of a dynamic system consisting of four partially observable components deteriorating in time is designed. To solve the empirical model, we resort to Symbolic Perseus solver which is one of the state-of-the-art factored POMDP solvers enabling approximate solutions. We generate some more predefined policies based on corrective or proactive maintenance strategies. We execute the policies on the empirical problem for many replications and compare their performances under various scenarios. The results show that the computed policies from the POMDP model are superior to the others. Acknowledgment: This work is supported by the Scientific and Technological Research Council of Turkey (TÜBİTAK) under grant no: 117M587.

Keywords: factored representation, maintenance, multi-component system, partially observable Markov decision processes

Procedia PDF Downloads 69