An exact algorithm to compute an optimal 3D oriented bounding box was published in 1985 by Joseph O'Rourke, but it is slow and extremely hard to implement. In this article we propose a new approach, where the computation of the minimal-volume OBB is formulated as an unconstrained optimization problem on the rotation group SO (3,ℝ). It is solved using a hybrid method combining the genetic and Nelder-Mead algorithms. This method is analyzed and then compared to the current state-of-the-art techniques. It is shown to be either faster or more reliable for any accuracy.
Optimization is a major field in applied mathematics. Many applications involve the search of the best solution to a problem according to some criterion. Depending on the considered optimization problem, finding the best solution is not always possible in a reasonable amount of time. Heuristic algorithms are often used when the problem is too difficult to solve exactly. These methods are used to speed up the search for a good solution but they do not guarantee that an optimal solution will be found. In this thesis, we explore such heuristic approaches for three different matrix problems. First, we study the minimum-volume bounding box problem, which consists in finding the smallest rectangular parallelepiped enclosing a given set of points in the three-dimensional space. This problem appears for example in collision detection, which is a very important issue in computational geometry and computer graphics. In these applications, a solution has to be determined in a very short amount of time. We propose a new hybrid algorithm able to approximate optimal bounding boxes at a low computational cost. In particular, it is several orders of magnitude faster than the only currently known exact algorithm. Second, we investigate the subset selection problem. Given a large set of features, we want to choose a small subset containing the most relevant features while removing the redundant ones. This problem has applications in data mining since this can be seen as a dimensionality reduction problem. We develop several windowed algorithms that tackle the subset selection problem for the maximum-volume criterion, which is NP-hard. Finally, we address the topic of the approximation of the joint spectral radius. This quantity characterizes the growth rate of product of matrices and is NP-hard to approximate. The joint spectral radius appears in many fields, including system theory, graph theory, combinatorics, language theory... We present an experimental study of existing approaches and propose a new genetic-based algorithm that is able to find bounds on the joint spectral radius in a short amount of time.
Let Σ be a set of n× n matrices and let us consider the following linear iteration: x(t +1) = Atx(t), At ∈ Σ for all t. These kinds of switched linear systems arise in many applications such as asynchronous systems, hybrid systems, switching control, ... The stability under arbitrary switchings of this system depends on a quantity called the joint spectral radius (JSR), which represents the maximal growth rate of such a discrete linear system. More precisely, the JSR of a set Σ of matrices is defined by the following expression: ρ(Σ) = lim k→∞ max{‖Ai1 . . .Aik‖ 1/k | Ai ∈ Σ}, independently of the matrix norm used. For bounded sets Σ, the JSR is also equal to the so-called generalized spectral radius ρ , defined by the following equation: ρ(Σ) = limsup k→∞ max{ρ(Ai1 . . .Aik) 1/k | Ai ∈ Σ}. For the linear iterations we consider, all trajectories converge thus to the origin if and only if the JSR of the corresponding set of matrices is strictly less than 1. Another quantity of interest is the joint spectral subradius (JSS), also called lower spectral radius, which represents the minimal achievable growth rate: ρ(Σ) = lim k→∞ min{‖Ai1 . . .Aik‖ 1/k | Ai ∈ Σ}. The JSS is related to the mortality problem, where we ask if the zero matrix can be expressed as a finite product of matrices in Σ. The joint spectral quantities are notoriously difficult to compute. Indeed, it is NP-Hard to approximate the JSR ; moreover, the problem of checking whether ρ ≤ 1 is undecidable, and the decidability of the question ρ < 1 is currently unknown. Furthermore, the problem of approximating the JSS is undecidable in the general case (see [1] for a survey on the joint spectral quantities). Despite these negative theoretical results, several algorithms have been designed in order to approximate the JSR. Indeed, in the case of the JSR, the following easy property holds: ρ(Σ) = inf ‖·‖ max{‖A‖ | A ∈ Σ}. Thus, one way to compute the JSR is to try to find a norm such that ρ(Σ) = max{‖A‖ | A ∈ Σ}, i.e., an extremal norm. Several methods have been designed using this fact (see for example [2], [3], [4]). In this paper, we will study and compare several techniques for the computation of the joint spectral quantities, such as semidefinite programming that computes the infimum on a class of norms, or geometric algorithms that tries to approximate the unit ball of an extremal norm using polytopes.
Let A and B be two n×n matrices with rows denoted by ai and bi. We consider the discrete linear system characterized by the equation : x(t +1) = Mtx(t), Mt ∈ Σ(A,B), where the set Σ(A,B) consists of all 2n matrices such that the ith row is either ai or bi. Here, we are interested in the growth rate and the boundedness of such systems, i.e. the question whether the matrix products MtMt−1 . . .M0 remain bounded for all products. In particular, we are interested in the case where B is the identity matrix. Indeed, this particular case can be interpreted as an asynchronous linear iteration with zero-delay, where only a subset σ ⊂ {1, . . . ,n} of the variables are updated with the matrix A at each time step: xk(t +1) = ∑ j ak jx j(t) if k ∈ σ , = xk(t) if k / ∈ σ . Such iterations arise in several contexts, for example in parallel and distributed computation [1], where a processor i needs the value x j(t) to be transferred from processor j in order to compute xi(t + 1). Update is thus impossible if the value is not yet available. Another example is consensus problems where groups of agents update their opinions asynchronously. The maximal growth rate of such a discrete linear system can be measured by a quantity called joint spectral radius (JSR). The JSR of a set Σ of matrices is defined by the following expression: ρ(Σ) = lim k→∞ max{‖Ai1 . . .Aik‖ 1/k | Ai ∈ Σ}, independently of the matrix norm used. For bounded sets Σ, the JSR is also equal to the so-called generalized spectral radius ρ , defined by the following equation: ρ(Σ) = limsup k→∞ max{ρ(Ai1 . . .Aik) 1/k | Ai ∈ Σ}. For the linear iterations we consider, all trajectories converge thus to the origin if and only if the JSR of the corresponding set of matrices is strictly less than 1. The computation of the JSR is notoriously difficult in the general case: the problem of checking whether ρ ≤ 1 has been proved undecidable [2] and the decidability of the question ρ < 1 is currently unknown (see [3] for a survey). However, in our case, i.e. matrices with row uncertainties, if A is nonnegative, then the JSR ρ(Σ(A, I)) is easy to compute [4] and is in fact even equal to max{ρ(A),1}. If we allow negative entries in the matrix A, it can be seen that this does not hold anymore, and we show with a simple example that the JSR can be strictly greater than the spectral radii of all matrices in Σ(A, I). A related open question is thus whether it is possible to compute the joint spectral radius and to decide boundedness of Σ(A, I) in polynomial time. In this talk, we discuss properties and complexity issues involving such sets of matrices.
A new method for trouble call analysis in low voltage distribution systems based on set covering theory and the tabu search (TS) technique is proposed. First, a new mathematical model for the trouble call analysis is developed based upon customer trouble calls, taking into account the protective device location, selectivity and operation possibility in the distribution network protection schema. Secondly, a new method is presented to solve this problem using a TS-based method to efficiently search for the protective device(s) that was the most likely to have operated. Finally, a sample distribution system is used to demonstrate the feasibility and efficiency of the developed method. Test results suggest that the developed TS-based method is efficient.
A first class of methods considers the definition of the jsr and uses the relation ρk(Σ) ≤ ρ(Σ) ≤ ρ(Σ) ≤ ρk(Σ), which holds for all k. The idea is thus to generate sets of products in order to compute ρk(Σ) and ρk(Σ) while discarding as many products as possible, using a branch-and-bound technique. Unfortunately, this sequence of bounds is generally slow to converge, in particular the upper bound.
'%3e%3cpath fill='%23012169' d='M0 0v30h60V0z'/%3e%3cpath stroke='%23fff' stroke-width='6' d='m0 0 60 30m0-30L0 30'/%3e%3cpath stroke='%23C8102E' stroke-width='4' d='m0 0 60 30m0-30L0 30' clip-path='url(%23b)'/%3e%3cpath stroke='%23fff' stroke-width='10' d='M30 0v30M0 15h60'/%3e%3cpath stroke='%23C8102E' stroke-width='6' d='M30 0v30M0 15h60'/%3e%3c/g%3e%3c/svg%3e)
'/%3e%3cuse xlink:href='%23a' transform='rotate(23.036 .093 25.536)'/%3e%3cuse xlink:href='%23a' transform='rotate(45.87 1.273 16.18)'/%3e%3cuse xlink:href='%23a' transform='rotate(69.945 .996 12.078)'/%3e%3cuse xlink:href='%23a' transform='rotate(20.66 -19.689 31.932)'/%3e%3c/svg%3e)
'/%3e%3c/defs%3e%3cpath fill='%23012169' d='M0 0h10080v5040H0z'/%3e%3cpath stroke='%23fff' stroke-width='.6' d='m0 0 6 3m0-3L0 3' clip-path='url(%23b)' transform='scale(840)'/%3e%3cpath stroke='%23e4002b' stroke-width='.4' d='m0 0 6 3m0-3L0 3' clip-path='url(%23c)' transform='scale(840)'/%3e%3cpath stroke='%23fff' stroke-width='840' d='M2520 0v2520M0 1260h5040'/%3e%3cpath stroke='%23e4002b' stroke-width='504' d='M2520 0v2520M0 1260h5040'/%3e%3cg fill='%23fff'%3e%3cuse xlink:href='%23d' x='2520' y='3780'/%3e%3cuse xlink:href='%23a' x='7560' y='4200'/%3e%3cuse xlink:href='%23a' x='6300' y='2205'/%3e%3cuse xlink:href='%23a' x='7560' y='840'/%3e%3cuse xlink:href='%23a' x='8680' y='1869'/%3e%3cuse xlink:href='%23e' x='8064' y='2730'/%3e%3c/g%3e%3c/svg%3e)