Search results for: 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 347

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 185

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 152

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 228

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 278

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 116

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 293

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 445

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 475