-
Tighter yet more tractable relaxations and nontrivial instance generation for sparse standard quadratic optimization
Authors:
Immanuel Bomze,
Bo Peng,
Yuzhou Qiu,
E. Alper Yildirim
Abstract:
The Standard Quadratic optimization Problem (StQP), arguably the simplest among all classes of NP-hard optimization problems, consists of extremizing a quadratic form (the simplest nonlinear polynomial) over the standard simplex (the simplest polytope/compact feasible set). As a problem class, StQPs may be nonconvex with an exponential number of inefficient local solutions. StQPs arise in a multit…
▽ More
The Standard Quadratic optimization Problem (StQP), arguably the simplest among all classes of NP-hard optimization problems, consists of extremizing a quadratic form (the simplest nonlinear polynomial) over the standard simplex (the simplest polytope/compact feasible set). As a problem class, StQPs may be nonconvex with an exponential number of inefficient local solutions. StQPs arise in a multitude of applications, among them mathematical finance, machine learning (clustering), and modeling in biosciences (e.g., selection and ecology). This paper deals with such StQPs under an additional sparsity or cardinality constraint, which, even for convex objectives, renders NP-hard problems. One motivation to study StQPs under such sparsity restrictions is the high-dimensional portfolio selection problem with too many assets to handle, in particular, in the presence of transaction costs. Here, relying on modern conic optimization techniques, we present tractable convex relaxations for this relevant but difficult problem. We propose novel equivalent reformulations of these relaxations with significant dimensional reduction, which is essential for the tractability of these relaxations when the problem size grows. Moreover, we propose an instance generation procedure which systematically avoids too easy instances. Our extensive computational results illustrate the high quality of the relaxation bounds in a significant number of instances. Furthermore, in contrast with exact mixed-integer quadratic programming models, the solution time of the relaxations is very robust to the choices of the problem parameters. In particular, the reduced formulations achieve significant improvements in terms of the solution time over their counterparts.
△ Less
Submitted 3 June, 2024;
originally announced June 2024.
-
Feature selection in linear SVMs via hard cardinality constraint: a scalable SDP decomposition approach
Authors:
Immanuel Bomze,
Federico D'Onofrio,
Laura Palagi,
Bo Peng
Abstract:
In this paper, we study the embedded feature selection problem in linear Support Vector Machines (SVMs), in which a cardinality constraint is employed, leading to a fully explainable selection model. The problem is NP-hard due to the presence of the cardinality constraint, even though the original linear SVM amounts to a problem solvable in polynomial time. To handle the hard problem, we first int…
▽ More
In this paper, we study the embedded feature selection problem in linear Support Vector Machines (SVMs), in which a cardinality constraint is employed, leading to a fully explainable selection model. The problem is NP-hard due to the presence of the cardinality constraint, even though the original linear SVM amounts to a problem solvable in polynomial time. To handle the hard problem, we first introduce two mixed-integer formulations for which novel SDP relaxations are proposed. Exploiting the sparsity pattern of the relaxations, we decompose the problems and obtain equivalent relaxations in a much smaller cone, making the conic approaches scalable. To make the best usage of the decomposed relaxations, we propose heuristics using the information of its optimal solution. Moreover, an exact procedure is proposed by solving a sequence of mixed-integer decomposed SDPs. Numerical results on classical benchmarking datasets are reported, showing the efficiency and effectiveness of our approach.
△ Less
Submitted 15 April, 2024;
originally announced April 2024.
-
On Tractable Convex Relaxations of Standard Quadratic Optimization Problems under Sparsity Constraints
Authors:
Immanuel Bomze,
Bo Peng,
Yuzhou Qiu,
E. Alper Yıldırım
Abstract:
Standard quadratic optimization problems (StQPs) provide a versatile modelling tool in various applications. In this paper, we consider StQPs with a hard sparsity constraint, referred to as sparse StQPs. We focus on various tractable convex relaxations of sparse StQPs arising from a mixed-binary quadratic formulation, namely, the linear optimization relaxation given by the reformulation-linearizat…
▽ More
Standard quadratic optimization problems (StQPs) provide a versatile modelling tool in various applications. In this paper, we consider StQPs with a hard sparsity constraint, referred to as sparse StQPs. We focus on various tractable convex relaxations of sparse StQPs arising from a mixed-binary quadratic formulation, namely, the linear optimization relaxation given by the reformulation-linearization technique, the Shor relaxation, and the relaxation resulting from their combination. We establish several structural properties of these relaxations in relation to the corresponding relaxations of StQPs without any sparsity constraints, and pay particular attention to the rank-one feasible solutions retained by these relaxations. We then utilize these relations to establish several results about the quality of the lower bounds arising from different relaxations. We also present several conditions that ensure the exactness of each relaxation.
△ Less
Submitted 6 October, 2023;
originally announced October 2023.
-
The star formation history of the Sco-Cen association. Coherent star formation patterns in space and time
Authors:
Sebastian Ratzenböck,
Josefa E. Großschedl,
João Alves,
Núria Miret-Roig,
Immanuel Bomze,
John Forbes,
Alyssa Goodman,
Alvaro Hacar,
Doug Lin,
Stefan Meingast,
Torsten Möller,
Martin Piecka,
Laura Posch,
Alena Rottensteiner,
Cameren Swiggum,
Catherine Zucker
Abstract:
We reconstruct the star formation history of the Sco-Cen OB association using a novel high-resolution age map of the region. We develop an approach to produce robust ages for Sco-Cen's recently identified 37 stellar clusters using the SigMA algorithm. The Sco-Cen star formation timeline reveals four periods of enhanced star formation activity, or bursts, remarkably separated by about 5 Myr. Of the…
▽ More
We reconstruct the star formation history of the Sco-Cen OB association using a novel high-resolution age map of the region. We develop an approach to produce robust ages for Sco-Cen's recently identified 37 stellar clusters using the SigMA algorithm. The Sco-Cen star formation timeline reveals four periods of enhanced star formation activity, or bursts, remarkably separated by about 5 Myr. Of these, the second burst, which occurred about 15 million years ago, is by far the dominant, and most of Sco-Cen's stars and clusters were in place by the end of this burst. The formation of stars and clusters in Sco-Cen is correlated but not linearly, implying that more stars were formed per cluster during the peak of the star formation rate. Most of the clusters that are large enough to have supernova precursors were formed during the 15 Myr period. Star and cluster formation activity has been continuously declining since then. We have clear evidence that Sco-Cen formed from the inside out and contains 100-pc long chains of contiguous clusters exhibiting well-defined age gradients, from massive older clusters to smaller young clusters. These observables suggest an important role for feedback in forming about half of Sco-Cen stars, although follow-up work is needed to quantify this statement. Finally, we confirm that the Upper-Sco age controversy discussed in the literature during the last decades is solved: the nine clusters previously lumped together as Upper-Sco, a benchmark region for planet formation studies, exhibit a wide range of ages from 3 to 19 Myr.
△ Less
Submitted 14 May, 2023; v1 submitted 15 February, 2023;
originally announced February 2023.
-
Projection free methods on product domains
Authors:
Immanuel Bomze,
Francesco Rinaldi,
Damiano Zeffiro
Abstract:
Projection-free block-coordinate methods avoid high computational cost per iteration and at the same time exploit the particular problem structure of product domains. Frank-Wolfe-like approaches rank among the most popular ones of this type. However, as observed in the literature, there was a gap between the classical Frank-Wolfe theory and the block-coordinate case. Moreover, most of previous res…
▽ More
Projection-free block-coordinate methods avoid high computational cost per iteration and at the same time exploit the particular problem structure of product domains. Frank-Wolfe-like approaches rank among the most popular ones of this type. However, as observed in the literature, there was a gap between the classical Frank-Wolfe theory and the block-coordinate case. Moreover, most of previous research concentrated on convex objectives. This study now deals also with the non-convex case and reduces above-mentioned theory gap, in combining a new, fully developed convergence theory with novel active set identification results which ensure that inherent sparsity of solutions can be exploited in an efficient way. Preliminary numerical experiments seem to justify our approach and also show promising results for obtaining global solutions in the non-convex case.
△ Less
Submitted 6 December, 2023; v1 submitted 9 February, 2023;
originally announced February 2023.
-
Significance Mode Analysis (SigMA) for hierarchical structures. An application to the Sco-Cen OB association
Authors:
Sebastian Ratzenböck,
Josefa E. Großschedl,
Torsten Möller,
João Alves,
Immanuel Bomze,
Stefan Meingast
Abstract:
We present a new clustering method, Significance Mode Analysis (SigMA), to extract co-spatial and co-moving stellar populations from large-scale surveys such as ESA Gaia. The method studies the topological properties of the density field in the multidimensional phase space. We validate SigMA on simulated clusters and find that it outperforms competing methods, especially in cases where many cluste…
▽ More
We present a new clustering method, Significance Mode Analysis (SigMA), to extract co-spatial and co-moving stellar populations from large-scale surveys such as ESA Gaia. The method studies the topological properties of the density field in the multidimensional phase space. We validate SigMA on simulated clusters and find that it outperforms competing methods, especially in cases where many clusters are closely spaced. We apply the new method to Gaia DR3 data of the closest OB association to Earth, Scorpio-Centaurus (Sco-Cen), and find more than 13,000 co-moving young objects, with about 19% of these having a sub-stellar mass. SigMA finds 37 co-moving clusters in Sco-Cen. These clusters are independently validated by their narrow HRD sequences and, to a certain extent, by their association with massive stars too bright for Gaia, hence unknown to SigMA. We compare our results with similar recent work and find that the SigMA algorithm recovers richer populations, is able to distinguish clusters with velocity differences down to about 0.5 km s$^{-1}$, and reaches cluster volume densities as low as 0.01 sources/pc$^3$. The 3D distribution of these 37 coeval clusters implies a larger extent and volume for the Sco-Cen OB association than typically assumed in the literature. Additionally, we find the association to be more actively star-forming and dynamically more complex than previously thought. We confirm that the star-forming molecular clouds in the Sco-Cen region, namely, Ophiuchus, L134/L183, Pipe Nebula, Corona Australis, Lupus, and Chamaeleon, are part of the Sco-Cen The application of SigMA to Sco-Cen demonstrates that advanced machine learning tools applied to the superb Gaia data allows to construct an accurate census of the young populations, to quantify their dynamics, and to reconstruct the recent star formation history of the local Milky Way.
△ Less
Submitted 25 November, 2022;
originally announced November 2022.
-
Frank-Wolfe and friends: a journey into projection-free first-order optimization methods
Authors:
Immanuel. M. Bomze,
Francesco Rinaldi,
Damiano Zeffiro
Abstract:
Invented some 65 years ago in a seminal paper by Marguerite Straus-Frank and Philip Wolfe, the Frank-Wolfe method recently enjoys a remarkable revival, fuelled by the need of fast and reliable first-order optimization methods in Data Science and other relevant application areas. This review tries to explain the success of this approach by illustrating versatility and applicability in a wide range…
▽ More
Invented some 65 years ago in a seminal paper by Marguerite Straus-Frank and Philip Wolfe, the Frank-Wolfe method recently enjoys a remarkable revival, fuelled by the need of fast and reliable first-order optimization methods in Data Science and other relevant application areas. This review tries to explain the success of this approach by illustrating versatility and applicability in a wide range of contexts, combined with an account on recent progress in variants, both improving on the speed and efficiency of this surprisingly simple principle of first-order optimization.
△ Less
Submitted 18 June, 2021;
originally announced June 2021.
-
Fast cluster detection in networks by first-order optimization
Authors:
Immanuel M. Bomze,
Francesco Rinaldi,
Damiano Zeffiro
Abstract:
Cluster detection plays a fundamental role in the analysis of data. In this paper, we focus on the use of s-defective clique models for network-based cluster detection and propose a nonlinear optimization approach that efficiently handles those models in practice. In particular, we introduce an equivalent continuous formulation for the problem under analysis, and we analyze some tailored variants…
▽ More
Cluster detection plays a fundamental role in the analysis of data. In this paper, we focus on the use of s-defective clique models for network-based cluster detection and propose a nonlinear optimization approach that efficiently handles those models in practice. In particular, we introduce an equivalent continuous formulation for the problem under analysis, and we analyze some tailored variants of the Frank-Wolfe algorithm that enable us to quickly find maximal s-defective cliques. The good practical behavior of those algorithmic tools, which is closely connected to their support identification properties, makes them very appealing in practical applications. The reported numerical results clearly show the effectiveness of the proposed approach.
△ Less
Submitted 29 March, 2021;
originally announced March 2021.
-
The $ρ$ Oph region revisited with Gaia EDR3
Authors:
Natalie Grasser,
Sebastian Ratzenböck,
João Alves,
Josefa Großschedl,
Stefan Meingast,
Catherine Zucker,
Alvaro Hacar,
Charles Lada,
Alyssa Goodman,
Marco Lombardi,
John C. Forbes,
Immanuel M. Bomze,
Torsten Möller
Abstract:
Context. Young and embedded stellar populations are important probes of the star formation process. Paradoxically, we have a better census of nearby embedded young populations than the slightly more evolved optically visible young populations. The high accuracy measurements and all-sky coverage of Gaia data are about to change this situation. Aims. This work aims to construct the most complete sam…
▽ More
Context. Young and embedded stellar populations are important probes of the star formation process. Paradoxically, we have a better census of nearby embedded young populations than the slightly more evolved optically visible young populations. The high accuracy measurements and all-sky coverage of Gaia data are about to change this situation. Aims. This work aims to construct the most complete sample to date of YSOs in the $ρ$ Oph region. Methods. We compile a catalog of 1114 Ophiuchus YSOs from the literature and crossmatch it with the Gaia EDR3, Gaia-ESO and APOGEE-2 surveys. We apply a multivariate classification algorithm to this catalog to identify new, co-moving population candidates. Results. We find 191 new high-fidelity YSO candidates in the Gaia EDR3 catalog belonging to the $ρ$ Oph region. The new sources appear to be mainly Class III M-stars and substellar objects and are less extincted than the known members. We find 28 previously unknown sources with disks. The analysis of the proper motion distribution of the entire sample reveals a well-defined bimodality, implying two distinct populations sharing a similar 3D volume. The first population comprises young stars' clusters around the $ρ$ Ophiuchi star and the main Ophiuchus clouds (L1688, L1689, L1709). In contrast, the second population is older ($\sim$ 10 Myr), dispersed, has a distinct proper motion, and is possibly from the Upper Sco group. The two populations are moving away from each other at about 4.1 km/s, and will no longer overlap in about 4 Myr. Finally, we flag 17 sources in the literature as impostors, which are sources that exhibit large deviations from the average distance and proper motion properties of the $ρ$ Oph population. Our results show the importance of accurate 3D space and motion information for improved stellar population analysis. (Abridged)
△ Less
Submitted 8 June, 2021; v1 submitted 28 January, 2021;
originally announced January 2021.
-
Uncertainty Preferences in Robust Mixed-Integer Linear Optimization with Endogenous Uncertainty
Authors:
Immanuel Bomze,
Markus Gabl
Abstract:
In robust optimization one seeks to make a decision under uncertainty, where the goal is to find the solution with the best worst-case performance. The set of possible realizations of the uncertain data is described by a so-called uncertainty set. In many scenarios, a decision maker may influence the uncertainty regime she is facing, for example, by investing in market research, or in machines whi…
▽ More
In robust optimization one seeks to make a decision under uncertainty, where the goal is to find the solution with the best worst-case performance. The set of possible realizations of the uncertain data is described by a so-called uncertainty set. In many scenarios, a decision maker may influence the uncertainty regime she is facing, for example, by investing in market research, or in machines which work with higher precision. Recently, this situation was addressed in the literature by introducing decision dependent uncertainty sets (endogenous uncertainty), i.e., uncertainty sets whose structure depends on (typically discrete) decision variables. In this way, one can model the trade-off between reducing the cost of robustness versus the cost of the investment necessary for influencing the uncertainty. However, there is another trade-off to be made here. With different uncertainty regimes, not only do the worst-case optimal solutions vary, but also other aspects of that solutions such as max-regret, best-case performance or predictability of the performance. A decision maker may still be interested in having a performance guarantee, but at the same time be willing to forgo superior worst-case performance if those other aspects can be enhanced by switching to a suitable uncertainty regime. We introduce the notion of uncertainty preference in order to capture such stances. We present three ways to formalize uncertainty preferences and study the resulting mathematical models. The goal is to have reformulations/approximations of these models which can be solved with standard methods. The workhorse is mixed-integer linear and conic optimization. We apply our framework to the uncertain shortest path problem and conduct numerical experiments for the resulting models. We can demonstrate that our models can be handled very well by standard mixed-integer linear solvers.
△ Less
Submitted 24 January, 2022; v1 submitted 30 November, 2020;
originally announced November 2020.
-
Extended stellar systems in the solar neighborhood. IV. Meingast 1: the most massive stellar stream in the solar neighborhood
Authors:
S. Ratzenböck,
S. Meingast,
J. Alves,
T. Möller,
I. Bomze
Abstract:
Nearby stellar streams carry unique information on the dynamical evolution and disruption of stellar systems in the Galaxy, the mass distribution in the disk, and provide unique targets for planet formation and evolution studies. We revisit the stream discovered in Meingast et al (2019) to search for new members, using Gaia DR2 data and a machine learning approach. We use a bagging classifier of o…
▽ More
Nearby stellar streams carry unique information on the dynamical evolution and disruption of stellar systems in the Galaxy, the mass distribution in the disk, and provide unique targets for planet formation and evolution studies. We revisit the stream discovered in Meingast et al (2019) to search for new members, using Gaia DR2 data and a machine learning approach. We use a bagging classifier of one-class Support Vector Machines to perform a search in positions and proper motions for new stream members. We use the variable prediction frequency resulting from the multitude of classifiers to estimate a stream membership criterion which we use to select high fidelity sources. We use the HR diagram and the Cartesian velocity distribution as test and validation tools. We find about 2000 stream members with high-fidelity, or about an order of magnitude more than previously known, unveiling the stream's population across the entire stellar mass spectrum, from B-stars to M-stars, including white dwarfs. We find that, apart from being slightly more metal-poor, the HRD of the stream is indistinguishable from that of the Pleiades cluster. For the mass range at which we are mostly complete, $\sim$0.2 M$_\odot$ $ < $ M $ < $ $\sim$4 M$_\odot$, we find a normal IMF, allowing us to estimate the total mass of stream to be about 2000 M$_\odot$, making this relatively young stream by far the most massive known. In addition, we identify several white dwarfs as potential stream members. The nearby Meingast 1 stream, due to its richness, age, and distance, is a new fundamental laboratory for star and planet formation and evolution studies for the poorly studied gravitationally unbound star-formation mode. We also demonstrate that One-Class Support Vector Machines can be effectively used to unveil the full stellar populations of nearby stellar systems with Gaia data.
△ Less
Submitted 13 February, 2020;
originally announced February 2020.
-
Active set complexity of the Away-step Frank-Wolfe Algorithm
Authors:
Immanuel M. Bomze,
Francesco Rinaldi,
Damiano Zeffiro
Abstract:
In this paper, we study active set identification results for the away-step Frank-Wolfe algorithm in different settings. We first prove a local identification property that we apply, in combination with a convergence hypothesis, to get an active set identification result. We then prove, in the nonconvex case, a novel $O(1/\sqrt{k})$ convergence rate result and active set identification for differe…
▽ More
In this paper, we study active set identification results for the away-step Frank-Wolfe algorithm in different settings. We first prove a local identification property that we apply, in combination with a convergence hypothesis, to get an active set identification result. We then prove, in the nonconvex case, a novel $O(1/\sqrt{k})$ convergence rate result and active set identification for different stepsizes (under suitable assumptions on the set of stationary points). By exploiting those results, we also give explicit active set complexity bounds for both strongly convex and nonconvex objectives. While we initially consider the probability simplex as feasible set, in the appendix we show how to adapt some of our results to generic polytopes.
△ Less
Submitted 24 December, 2019;
originally announced December 2019.
-
Hessian barrier algorithms for linearly constrained optimization problems
Authors:
Immanuel M. Bomze,
Panayotis Mertikopoulos,
Werner Schachinger,
Mathias Staudigl
Abstract:
In this paper, we propose an interior-point method for linearly constrained optimization problems (possibly nonconvex). The method - which we call the Hessian barrier algorithm (HBA) - combines a forward Euler discretization of Hessian Riemannian gradient flows with an Armijo backtracking step-size policy. In this way, HBA can be seen as an alternative to mirror descent (MD), and contains as speci…
▽ More
In this paper, we propose an interior-point method for linearly constrained optimization problems (possibly nonconvex). The method - which we call the Hessian barrier algorithm (HBA) - combines a forward Euler discretization of Hessian Riemannian gradient flows with an Armijo backtracking step-size policy. In this way, HBA can be seen as an alternative to mirror descent (MD), and contains as special cases the affine scaling algorithm, regularized Newton processes, and several other iterative solution methods. Our main result is that, modulo a non-degeneracy condition, the algorithm converges to the problem's set of critical points; hence, in the convex case, the algorithm converges globally to the problem's minimum set. In the case of linearly constrained quadratic programs (not necessarily convex), we also show that the method's convergence rate is $\mathcal{O}(1/k^ρ)$ for some $ρ\in(0,1]$ that depends only on the choice of kernel function (i.e., not on the problem's primitives). These theoretical results are validated by numerical experiments in standard non-convex test functions and large-scale traffic assignment problems.
△ Less
Submitted 8 May, 2019; v1 submitted 25 September, 2018;
originally announced September 2018.
-
Extended Trust-Region Problems with One or Two Balls: Exact Copositive and Lagrangian Relaxations
Authors:
I. M. Bomze,
V. Jeyakumar,
G. Li
Abstract:
We establish a geometric condition guaranteeing exact copositive relaxation for the nonconvex quadratic optimization problem under two quadratic and several linear constraints, and present sufficient conditions for global optimality in terms of generalized Karush-Kuhn-Tucker multipliers. The copositive relaxation is tighter than the usual Lagrangian relaxation. We illustrate this by providing a wh…
▽ More
We establish a geometric condition guaranteeing exact copositive relaxation for the nonconvex quadratic optimization problem under two quadratic and several linear constraints, and present sufficient conditions for global optimality in terms of generalized Karush-Kuhn-Tucker multipliers. The copositive relaxation is tighter than the usual Lagrangian relaxation. We illustrate this by providing a whole class of quadratic optimization problems that enjoys exactness of copositive relaxation while the usual Lagrangian duality gap is infinite. Finally, we also provide verifiable conditions under which both the usual Lagrangian relaxation and the copositive relaxation are exact for an extended CDT (two-ball trust-region) problem. Importantly, the sufficient conditions can be verified by solving linear optimization problems.
△ Less
Submitted 2 October, 2017; v1 submitted 26 February, 2017;
originally announced February 2017.
-
New results on the cp rank and related properties of co(mpletely)positive matrices
Authors:
Naomi Shaked-Monderer,
Abraham Berman,
Immanuel M. Bomze,
Florian Jarre,
Werner Schachinger
Abstract:
Copositive and completely positive matrices play an increasingly important role in Applied Mathematics, namely as a key concept for approximating NP-hard optimization problems. The cone of copositive matrices of a given order and the cone of completely positive matrices of the same order are dual to each other with respect to the standard scalar product on the space of symmetric matrices. This pap…
▽ More
Copositive and completely positive matrices play an increasingly important role in Applied Mathematics, namely as a key concept for approximating NP-hard optimization problems. The cone of copositive matrices of a given order and the cone of completely positive matrices of the same order are dual to each other with respect to the standard scalar product on the space of symmetric matrices. This paper establishes some new relations between orthogonal pairs of such matrices lying on the boundary of either cone. As a consequence, we can establish an improvement on the upper bound of the cp-rank of completely positive matrices of general order, and a further improvement for such matrices of order six.
△ Less
Submitted 23 November, 2013; v1 submitted 27 April, 2013;
originally announced May 2013.
-
Improving SDP bounds for minimizing quadratic functions over the l1-ball
Authors:
Immanuel M. Bomze,
Florian Frommlet,
Martin Rubey
Abstract:
In this note, we establish superiority of the so-called copositive bound over a bound suggested by Nesterov for the quadratic problem to minimize a quadratic form over the l1-ball. We illustrate the improvement by simulation results. The copositive bound has the additional advantage that it can be easily extended to the inhomogeneous case of quadratic objectives including a linear term. We also…
▽ More
In this note, we establish superiority of the so-called copositive bound over a bound suggested by Nesterov for the quadratic problem to minimize a quadratic form over the l1-ball. We illustrate the improvement by simulation results. The copositive bound has the additional advantage that it can be easily extended to the inhomogeneous case of quadratic objectives including a linear term. We also indicate some improvements of the eigenvalue bound for the quadratic optimization over the lp-ball with 1<p<2, at least for p close to one.
△ Less
Submitted 22 March, 2005; v1 submitted 9 March, 2005;
originally announced March 2005.
