François Glineur

UCL / CORE
Voie du Roman Pays 34 bte L1.03.01
B-1348 Louvain-la-Neuve, Belgium

directory page

Curriculum vitae

Convex optimization

• algorithms (first-order methods and interior-point methods),
• modelling (approximations, extended formulations) and duality,
• applications of optimization in general.

Nonnegative matrix factorization

• algorithms and complexity,
• nonnegative rank and applications,
• numerical linear algebra in general.

Preprints

• Spectrum Optimization in Multi-User Multi-Carrier Systems with Iterative Convex and Nonconvex Approximation Methods, Paschalis Tsiaflakis, François Glineur, submitted to IEEE Transactions on Information Theory, 2012.
• A nuclear-norm based convex formulation for informed source separation, Augustin Lefèvre, François Glineur, P.-A. Absil, submitted to European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning (ESANN 2013), 2012. Link to arXiv.
• ONP-MF: An Orthogonal Nonnegative Matrix Factorization Algorithm with Application to Clustering, Filippo Pompili, Nicolas Gillis, P.-A. Absil, and François Glineur, submitted to European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning (ESANN 2013), 2012. Link to arXiv.
• A Global-Local Synthesis Approach for Large Non-regular Arrays, Thibault Clavier, Nima Razavi-Ghods, François Glineur, David González Ovejero, Eloy de Lera Acedo, Christophe Craeye, Paul Alexander, submitted to IEEE Transactions on Antennas and Propagation, 2012.
• Weighted Sum Rate Maximization for Downlink OFDMA with Subcarrier-pair based Opportunistic DF Relaying, Tao Wang, François Glineur, Jérome Louvaux, Luc Vandendorpe, submitted to IEEE Transactions on Signal Processing, 2012.
• First-Order Methods of Smooth Convex Optimization with Inexact Oracle, Olivier Devolder, François Glineur, Yurii Nesterov, submitted to Mathematical Programming, 2011. Link to Optimization Online. Link to CORE Discussion Paper.
• A Continuous Characterization of the Maximum-Edge Biclique Problem, , submitted to Journal of Global Optimization, 2011. Link to arXiv. Link to CORE Discussion Paper.

Journal articles

• An Efficient Sampling Method for Regression-Based Polynomial Chaos Expansion, Samih Zein, Benoît Colson, François Glineur, Communications in Computational Physics, Volume 13, Number 4 (2013), 1173–1188, Global Science Press. 10.4208/cicp.020911.200412a ; DIAL handle ; abstract.

  The polynomial chaos expansion (PCE) is an efficient numerical method for performing a reliability analysis. It relates the output of a nonlinear system with the uncertainty in its input parameters using a multidimensional polynomial approximation (the so-called PCE). Numerically, such an approximation can be obtained by using a regression method with a suitable design of experiments. The cost of this approximation depends on the size of the design of experiments. If the design of experiments is large and the system is modeled with a computationally expensive FEA (Finite Element Analysis) model, the PCE approximation becomes unfeasible. The aim of this work is to propose an algorithm that generates efficiently a design of experiments of a size defined by the user, in order to make the PCE approximation computationally feasible. It is an optimization algorithm that seeks to find the best design of experiments in the D-optimal sense for the PCE. This algorithm is a coupling between genetic algorithms and the Fedorov exchange algorithm. The efficiency of our approach in terms of accuracy and computational time reduction is compared with other existing methods in the case of analytical functions and finite element based functions.

• Double Smoothing Technique for Large-Scale Linearly Constrained Convex Optimization , Olivier Devolder, François Glineur, Yurii Nesterov, SIAM Journal on Optimization, Volume 22, Issue 2 (2012), 702–727, SIAM. 10.1137/110826102 ; DIAL handle ; abstract, published PDF.

  In this paper, we propose an efficient approach for solving a class of large-scale convex optimization problems. The problem we consider is the minimization of a convex function over a simple (possibly infinite-dimensional) convex set, under the additional constraint Au in T, where A is a linear operator and T is a convex set whose dimension is small compared to the dimension of the feasible region. In our approach, we dualize the linear constraints, solve the resulting dual problem with a purely dual gradient-type method and show how to reconstruct an approximate primal solution. Because the linear constraints have been dualized, the dual objective function typically becomes separable, and therefore easy to compute. In order to accelerate our scheme, we introduce a novel double smoothing technique that involves regularization of the dual problem to allow the use of a fast gradient method. As a result, we obtain a method with complexity O(1/epsilon log(1/epsilon) gradient iterations, where epsilon is the desired accuracy for the primal-dual solution. Our approach covers, in particular, optimal control problems with a trajectory governed by a system of linear differential equations, where the additional constraints can, for example, force the trajectory to visit some convex sets at certain moments in time.

• On the Geometric Interpretation of the Nonnegative Rank, Nicolas Gillis, François Glineur, Linear Algebra and its Applications, Volume 437, Issue 11 (1 December 2012), 2685–2712, Elsevier. 10.1016/j.laa.2012.06.038 ; DIAL handle ; abstract.

  The nonnegative rank of a nonnegative matrix is the minimum number of nonnegative rank-one factors needed to reconstruct it exactly. The problem of determining this rank and computing the corresponding nonnegative factors is difficult; however it has many potential applications, e.g., in data mining and graph theory. In particular, it can be used to characterize the minimal size of any extended reformulation of a given polytope. In this paper, we introduce and study a related quantity, called the restricted nonnegative rank. We show that computing this quantity is equivalent to a problem in computational geometry, and fully characterize its computational complexity. This in turn sheds new light on the nonnegative rank problem, and in particular allows us to provide new improved lower bounds based on its geometric interpretation. We apply these results to slack matrices and linear Euclidean distance matrices and obtain counter-examples to two conjectures of Beasley and Laffey, namely we show that the nonnegative rank of linear Euclidean distance matrices is not necessarily equal to their dimension, and that the rank of a matrix is not always greater than the nonnegative rank of its square.

• Accelerated Multiplicative Updates and Hierarchical ALS Algorithms for Nonnegative Matrix Factorization , Nicolas Gillis, François Glineur, Neural Computation, Volume 24, Number 4 (April 2012), 1085–1105, MIT Press Journals. 10.1162/NECO_a_00256 ; DIAL handle ; abstract, published PDF.

  Nonnegative matrix factorization (NMF) is a data analysis technique used in a great variety of applications such as text mining, image processing, hyperspectral data analysis, computational biology, and clustering. In this letter, we consider two well-known algorithms designed to solve NMF problems: the multiplicative updates of Lee and Seung and the hierarchical alternating least squares of Cichocki et al. We propose a simple way to significantly accelerate these schemes, based on a careful analysis of the computational cost needed at each iteration, while preserving their convergence properties. This acceleration technique can also be applied to other algorithms, which we illustrate on the projected gradient method of Lin. The efficiency of the accelerated algorithms is empirically demonstrated on image and text data sets and compares favorably with a state-of-the-art alternating nonnegative least squares algorithm.

• A multilevel approach for nonnegative matrix factorization, Nicolas Gillis, François Glineur, Journal of Computational and Applied Mathematics, Volume 236, Issue 7 (January 2012), 1708–1723, Elsevier. 10.1016/j.cam.2011.10.002 ; DIAL handle ; abstract.

  Nonnegative matrix factorization (NMF), the problem of approximating a nonnegative matrix with the product of two low-rank nonnegative matrices, has been shown to be useful in many applications, such as text mining, image processing, and computational biology. In this paper, we explain how algorithms for NMF can be embedded into the framework of multilevel methods in order to accelerate their initial convergence. This technique can be applied in situations where data admit a good approximate representation in a lower dimensional space through linear transformations preserving nonnegativity. Several simple multilevel strategies are described and are experimentally shown to speed up significantly three popular NMF algorithms (alternating nonnegative least squares, multiplicative updates and hierarchical alternating least squares) on several standard image datasets.

• Low-Rank Matrix Approximation with Weights or Missing Data Is NP-Hard , Nicolas Gillis, François Glineur, SIAM Journal on Matrix Analysis and Applications, Volume 32, Issue 4 (2011), 1149–1165, SIAM. 10.1137/110820361 ; DIAL handle ; abstract, published PDF.

  Weighted low-rank approximation (WLRA), a dimensionality reduction technique for data analysis, has been successfully used in several applications, such as in collaborative filtering to design recommender systems or in computer vision to recover structure from motion. In this paper, we prove that computing an optimal WLRA is NP-hard, already when a rank-one approximation is sought. In fact, we show that it is hard to compute approximate solutions to the WLRA problem with some prescribed accuracy. Our proofs are based on reductions from the maximum-edge biclique problem and apply to strictly positive weights as well as to binary weights (the latter corresponding to low-rank matrix approximation with missing data).

• ACUTA: A novel method for eliciting additive value functions on the basis of holistic preference statements, Géraldine Bous, Philippe Fortemps, François Glineur, Marc Pirlot, European Journal of Operational Research, Volume 206, Issue 2 (16 October 2010), 435–444, Elsevier. 10.1016/j.ejor.2010.03.009 ; DIAL handle ; abstract.

  In multiple criteria decision aiding, it is common to use methods that are capable of automatically extracting a decision or evaluation model from partial information provided by the decision maker about a preference structure. In general, there is more than one possible model, leading to an indetermination which is dealt with sometimes arbitrarily in existing methods. This paper aims at filling this theoretical gap: we present a novel method, based on the computation of the analytic center of a polyhedron, for the selection of additive value functions that are compatible with holistic assessments of preferences. We demonstrate the most important characteristics of this technique with an experimental and comparative study of several existing methods belonging to the UTA family.

• Using underapproximations for sparse nonnegative matrix factorization, Nicolas Gillis, François Glineur, Pattern Recognition, Volume 43, Issue 4 (April 2010), 1676–1687, Elsevier. 10.1016/j.patcog.2009.11.013 ; DIAL handle ; abstract.

  Nonnegative matrix factorization consists in (approximately) factorizing a nonnegative data matrix by the product of two low-rank nonnegative matrices. It has been successfully applied as a data analysis technique in numerous domains, e.g., text mining, image processing, microarray data analysis, collaborative filtering, etc. We introduce a novel approach to solve NMF problems, based on the use of an underapproximation technique, and show its effectiveness to obtain sparse solutions. This approach, based on Lagrangian relaxation, allows the resolution of NMF problems in a recursive fashion. We also prove that the underapproximation problem is NP-hard for any fixed factorization rank, using a reduction of the maximum edge biclique problem in bipartite graphs. We test two variants of our underapproximation approach on several standard image datasets and show that they provide sparse part-based representations with low reconstruction error. Our results are comparable and sometimes superior to those obtained by two standard sparse nonnegative matrix factorization techniques.

• An interior-point method for the single-facility location problem with mixed norms using a conic formulation, Robert Chares, François Glineur, Mathematical Methods of Operations Research, Volume 68, Number 3 (2008), 383–405, Springer. 10.1007/s00186-008-0225-x ; DIAL handle ; abstract.

  We consider the single-facility location problem with mixed norms, i.e. the problem of minimizing the sum of the distances from a point to a set of fixed points in Rn, where each distance can be measured according to a different p-norm. We show how this problem can be expressed into a structured conic format by decomposing the nonlinear components of the objective into a series of constraints involving three-dimensional cones. Using the availability of a self-concordant barrier for these cones, we present a polynomial-time algorithm (a long-step path-following interior-point scheme) to solve the problem up to any given accuracy. Finally, we report computational results for this algorithm and compare with standard nonlinear optimization solvers applied to this problem.

• de Finetti’s retention problem for proportional reinsurance revisited, François Glineur, Jean-François Walhin, Blätter der DGVFM, Volume 27, Number 3 (2006), 451–462, Springer. 10.1007/BF02809170 ; DIAL handle ; abstract.

  We use convex optimization to provide a rigorous proof of de Finetti’s retention result for proportional reinsurance. We then extend this result to variable quota share reinsurance and surplus reinsurance with table of lines. We demonstrate by a numerical example that in general neither variable quota share reinsurance nor surplus reinsurance with table of lines may be considered as optimal reinsurance structures.

• Conic Formulation for lp-Norm Optimization, François Glineur, Tamás Terlaky, Journal of Optimization Theory and Applications, Volume 122, Number 2 (August 2004), 285–307, Springer. 10.1023/B:JOTA.0000042522.65261.51 ; DIAL handle ; abstract.

  In this paper, we formulate the lp-norm optimization problem as a conic optimization problem, derive its duality properties (weak duality, zero duality gap, and primal attainment) using standard conic duality and show how it can be solved in polynomial time applying the framework of interior-point algorithms based on self-concordant barriers.

• Improving complexity of structured convex optimization problems using self-concordant barriers, François Glineur, European Journal of Operational Research, Volume 143, Issue 2 (1 December 2002), 291–310, Elsevier. 10.1016/S0377-2217(02)00297-7 ; DIAL handle ; abstract.

  The purpose of this paper is to provide improved complexity results for several classes of structured convex optimization problems using the theory of self-concordant functions developed by Nesterov and Nemirovski in SIAM Studies in Applied Mathematics, SIAM Publications, Philadelphia, 1994. We describe the classical short-step interior-point method and optimize its parameters in order to provide the best possible iteration bound. We also discuss the necessity of introducing two parameters in the definition of self-concordancy and which one is the best to fix. A lemma due to den Hertog et al. in Mathematical Programming Series B 69 (1) (1995) is improved, which allows us to review several classes of structured convex optimization problems and improve the corresponding complexity results.

• Proving Strong Duality for Geometric Optimization Using a Conic Formulation, François Glineur, Annals of Operations Research, Volume 105, Numbers 1-4 (2001), 155–184, Springer. 10.1023/A:1013357600036 ; DIAL handle ; abstract.

  Geometric optimization is an important class of problems that has many applications, especially in engineering design. In this article, we provide new simplified proofs for the well-known associated duality theory, using conic optimization. After introducing suitable convex cones and studying their properties, we model geometric optimization problems with a conic formulation, which allows us to apply the powerful duality theory of conic optimization and derive the duality results valid for geometric optimization.

• Conic optimization: an elegant framework for convex optimization, François Glineur, Belgian Journal of Operations Research, Statistics and Computer Science, Volume 41, Numbers 1-2 (2001), 5–28, Sogesci-B.V.W.B.. DIAL handle ; abstract.

  The purpose of this survey article is to introduce the reader to a very elegant formulation of convex optimization problems called conic optimization and outline its many advantages. After a brief introduction to convex optimization, the notion of convex cone is introduced, which leads to the conic formulation of convex optimization problems. This formulation features a very symmetric dual problem, and several useful duality theorems pertaining to this conic primal-dual pair are presented. The usefulness of this approach is then demonstrated with its application to a well-known class of convex problems called lp-norm optimization. A suitably defined convex cone leads to a conic formulation for this problem, which allows us to derive its dual and the associated weak and strong duality properties in a seamless manner.

• An extended conic formulation for geometric optimization, François Glineur, Foundations of Computing and Decision Sciences, Volume 25, Number 3 (2000), 161–174, Poznań University of Technology. DIAL handle ; abstract.

  The author has recently proposed a new way of formulating two classical classes of structured convex problems, geometric and lp-norm optimization, using dedicated convex cones. This approach has some advantages over the traditional formulation: it simplifies the proofs of the well-known associated duality properties (i.e. weak and strong duality) and the design of a polynomial algorithm becomes straightforward. In this article, we make a step towards the description of a common framework that includes these two classes of problems. Indeed, we present an extended variant of the cone for geometric optimization previously introduced by the author and show it is equally suitable to formulate this class of problems. This new cone has the additional advantage of being very similar to the cone used for lp-norm optimization, which opens the way to a common generalization.

• Interior-point methods for linear programming: a guided tour, François Glineur, Belgian Journal of Operations Research, Statistics and Computer Science, Volume 38, Number 1 (1998), 3–30, Sogesci-B.V.W.B.. DIAL handle ; abstract.

  The purpose of mathematical programming, a branch of optimization, is to minimize (or maximize) a function of several variables under a set of constraints. This is a very important problem arising in many real-world situations (e.g. cost or duration minimization). When the function to optimize and its associated set of constraints are linear, we talk about linear programming. The simplex algorithm, first developed by Dantzig in 1947, is a very efficient method to solve this class of problems. It has been thoroughly studied and improved since its first appearance, and is now widely used in commercial software to solve a great variety of problems (production planning, transportation, scheduling, etc.). However, an article by Karmarkar introduced in 1984 a new class of methods: the so-called interior-point methods. Most of the ideas underlying these new methods originate from the nonlinear optimization domain. These methods are both theoretically and practically efficient, can be used to solve large-scale problems and can be generalized to other types of convex optimization problems. The purpose of this article is to give an overview of this rather new domain, providing a clear and understandable description of these methods, both from a theoretical and a practical point of view.

Chapters in books

• Solving Infinite-dimensional Optimization Problems by Polynomial Approximation , Olivier Devolder, François Glineur, Yurii Nesterov, in Recent Advances in Optimization and its Applications in Engineering, edited by Moritz Diehl, François Glineur, Elias Jarlebring, Wim Michiels (2010), 31–40, Springer (ISBN 978-3-642-12597-3). 10.1007/978-3-642-12598-0_3 ; DIAL handle ; abstract, final PDF.

  We solve a class of convex infinite-dimensional optimization problems using a numerical approximation method that does not rely on discretization. Instead, we restrict the decision variable to a sequence of infinite-dimensional linear subspaces of the original infinite-dimensional space and solve the corresponding infinite-dimensional problems in a efficient way using structured convex optimization techniques. We prove that, under some reasonable assumptions, the sequence of these optimal values converges to the optimal value of the original infinite-dimensional problem and give an explicit description of the corresponding rate of convergence.

• Impact of the Material Distribution Formalism on the Efficiency of Evolutionary Methods for Topology Optimization , Jonathan Denies, Bruno Dehez, François Glineur, Hamid Ben Ahmed, in Recent Advances in Optimization and its Applications in Engineering, edited by Moritz Diehl, François Glineur, Elias Jarlebring, Wim Michiels (2010), 461–470, Springer (ISBN 978-3-642-12597-3). 10.1007/978-3-642-12598-0_40 ; DIAL handle ; abstract, final PDF.

  We consider an evolutionary method applied to a topology optimization problem. We compare two material distribution formalisms (static vs. Voronoi-based dynamic), and two sets of reproduction mechanisms (standard vs. topology-adapted). We test those four variants on both theoretical and practical test cases, to show that the Voronoi-based formalism combined with adapted reproduction mechanisms performs better and is less sensitive to its parameters.

• Les méthodes de point intérieur , François Glineur, in Programmation linéaire, Jacques Teghem (2003), 263–285, Editions Ellipses (ISBN 978-2-8004-1317-4). DIAL handle ; abstract, final PDF.

Refereed proceedings

• Genetic algorithm-based topology optimization: Performance improvement through dynamic evolution of the population size , Jonathan Denies, Bruno Dehez, François Glineur and Hamid Ben Ahmed, in Proceedings of the 2012 International Symposium on Power Electronics, Electrical Drives, Automation and Motion (SPEEDAM 2012), Sorrento, Italy (June 20-22 2012), 1033–1038 (ISBN 978-1-4673-1299-8). 10.1109/SPEEDAM.2012.6264469 ; DIAL handle ; abstract, final PDF.

  Topological optimization tool using genetic algorithm as optimization algorithm are known as very expensive in computation time. In this paper, we study an approach to improve performance of topological optimization tool by introducing a dynamic variation of the population size of children during the process of optimization. This method allows to improve performance of each generation by adapting the number of children created and by introducing a coefficient of reproduction for each individual inside the population of parents. Through this coefficient of reproduction, the number of children assigns to each parent is calculated. The number of evaluations at each generation changes and the tool can saves evaluations in order to increase the number of iterations.

• A novel class of iterative approximation methods for DSL spectrum optimization , Paschalis Tsiaflakis and François Glineur, in Proceedings of the IEEE International Conference on Communications (ICC 2012), Ottawa (June 10-15 2012), 3193-3198 (ISBN ). DIAL handle ; abstract, final PDF.

  Spectrum optimization is a promising means to tackle the crosstalk problem in DSL systems, and corresponds to a challenging nonconvex optimization problem. Iterative convex approximation (ICA) methods have been proposed in the literature to deal with this optimization problem. These methods consist in solving a series of improving convex approximations and are typically implemented in a per-user iterative approach. In this paper we develop a novel class of iterative methods that focus explicitly on per-user iterative implementations, and which consist of improved per-user approximations that are tighter and simpler to solve (in closed-form) than state-of-the-art ICA methods. As a result, the proposed methods improve the convergence speed as fewer approximations are required to converge, and display a significantly lower computational cost. Furthermore, three of the proposed methods can tackle the issue of getting stuck in bad locally optimal solutions, and hence improve solution quality with respect to existing ICA methods.

• Extended Lanczos Bidiagonalization for Dimension Reduction in Information Retrieval , François Glineur, Linzhang Lu, Paul Van Dooren and Xuansheng Wang, in Proceedings of the 8th International Conference on Natural Computation (ICNC'12), Chongqing, China (May 29-31 2012), 138–144 (ISBN 978-1-4577-2133-5). DIAL handle ; abstract, final PDF.

  We describe an extended bidiagonalization scheme designed to compute low-rank approximations of very large data matrices. Its goal is identical to that of the truncated singular value decomposition, but it is significantly cheaper. It consists in an extension of the standard Lanczos bidiagonalization that improves its approximation capabilities, while keeping the computational cost reasonable. This low-rank approximation yields much cheaper computations of the matrix-vector products that are central in many information retrieval tasks. We demonstrate effectiveness of this approach on applications in face recognition and latent semantic indexing.

• Study of a topology optimization tool associating a hybrid algorithm with a Voronoï-based formalism for the design of electromagnetic devices , Jonathan Denies, Hamid Ben Ahmed, François Glineur and Bruno Dehez, in Proceedings of the XIX International Conference on Electrical Machines (ICEM 2010), Rome (September 6-8 2010), 1–6 (ISBN 978-1-4244-4174-7). 10.1109/ICELMACH.2010.5607889 ; DIAL handle ; abstract, final PDF.

  This paper presents and compares three topology optimization tools differing from the optimization algorithms they implement. The first two are respectively based on a local optimization algorithm, i.e. a Nelder-Mead method, and a global one, i.e. a genetic algorithm. The third uses a hybrid algorithm associating the local and the global algorithms used in the first two. Each of them implements the same material distribution formalism, i.e. a dynamic formalism based on Voronoi cells. The results obtained on a practical study case, the design of an electromagnet, show the better performance of the hybrid algorithm as well in terms of speed of the convergence as in terms of quality of the final solution and therefore the interest of coupling the exploration abilty of the global search with the intensification abilty of the local search.

• Topology optimization method applied to the design of electromagnetic devices: focus on convexity issues , Thibaut Labbé, François Glineur and Bruno Dehez, in Proceedings of the 8th International Symposium on Advanced Electromechanical Motion Systems & Electric Drives Joint Symposium (ELECTROMOTION 2009), Lille (July 1-3 2009), 1–6 (ISBN 978-1-4244-5150-0). 10.1109/ELECTROMOTION.2009.5259087 ; DIAL handle ; abstract, final PDF.

  To perform parameter and shape optimization, an initial topology is required which affects the final solution. Topology optimization methods have the advantage to release this constraint. They are based on a splitting of the design space into cells, in which they attempt to distribute optimally some given materials. In this paper, the optimization is based on a discrete formulation of the Maxwell equations obtained thanks to a finite element model. The gradient of the objective function is computed immediately from this discrete form, which is more convenient than the adjoint variable method. A line-search method (steepest descent direction) is then applied. The step size is computed by a simple and quick algorithm, to achieve good and fast convergence. Several convexity issues were already highlighted in topology optimization. We explain how we can face some of them by performing the optimization on a variable linked to the permeability by a given mapping. This mapping actually affects the value of intermediate materials and must be selected carefully to avoid the algorithm to be trapped in some local minimizers. In order to illustrate the concepts presented along the paper, the method is applied for the topology optimization of a linear reluctant actuator.

• Document classification using nonnegative matrix factorization and underapproximation , Michael W. Berry, Nicolas Gillis and François Glineur, in Proceedings of the IEEE International Symposium on Circuits and Systems, 2009 (ISCAS 2009), Taipei (May 24-27 2009), 2782–2785 (ISBN 978-1-4244-3827-3). 10.1109/ISCAS.2009.5118379 ; DIAL handle ; abstract, final PDF.

  In this study, we use nonnegative matrix factorization (NMF) and nonnegative matrix underapproximation (NMU) approaches to generate feature vectors that can be used to cluster Aviation Safety Reporting System (ASRS) documents obtained from the Distributed National ASAP Archive (DNAA). By preserving nonnegativity, both the NMF and NMU facilitate a sum-of-parts representation of the underlying term usage patterns in the ASRS document collection. Both the training and test sets of ASRS documents are parsed and then factored by both algorithms to produce a reduced-rank representations of the entire document space. The resulting feature coefficient matrix factors are used to cluster ASRS documents so that the (known) associated anomalies of training documents are directly mapped to the feature vectors. Dominant features of test documents are then used to generate anomaly relevance scores for those documents. We demonstrate that the approximate solution obtained by NMU using Lagrangrian duality can lead to a better sum-of-parts representation and document classification accuracy.

Theses

• Topics in convex optimization: interior-point methods, conic duality and approximations , François Glineur, co-supervised by Jacques Teghem and Tamás Terlaky, PhD thesis, Faculté Polytechnique de Mons, Belgium (January 2001), 218 pages. abstract, PDF.

  Optimization is a scientific discipline that lies at the boundary between pure and applied mathematics. Indeed, while some of its developments involve rather theoretical concepts, its most successful algorithms are heavily used by numerous companies to solve scheduling and design problems on a daily basis.
  Our research started with the study of the conic formulation for convex optimization problems. This approach was already studied in the seventies but has recently gained a lot of interest due to development of a new class of algorithms called interior-point methods. This setting is able to exploit the two most important characteristics of convexity:
  - a very rich duality theory (existence of a dual problem that is strongly related to the primal problem, with a very symmetric formulation),
  - the ability to solve these problems efficiently, both from the theoretical (polynomial algorithmic complexity) and practical (implementations allowing the resolution of large-scale problems) points of view.
  Most of the research in this area involved so-called self-dual cones, where the dual problem has exactly the same structure as the primal: the most famous classes of convex optimization problems (linear optimization, convex quadratic optimization and semidefinite optimization) belong to this category. We brought some contributions in this field:
  - a survey of interior-point methods for linear optimization, with an emphasis on the fundamental principles that lie behind the design of these algorithms,
  - a computational study of a method of linear approximation of convex quadratic optimization (more precisely, the second-order cone that can be used in the formulation of quadratic problems is replaced by a polyhedral approximation whose accuracy can be guaranteed a priori) ; this technique was also successfully applied to the resolution of limit analysis problems in mechanical engineering,
  - an application of semidefinite optimization to classification, whose principle consists in separating different classes of patterns using ellipsoids defined in the feature space (this approach was successfully applied to the prediction of student grades).
  However, our research focussed on a much less studied category of convex problems which does not rely on self-dual cones, \IE structured problems whose dual is formulated very differently from the primal. We studied in particular
  - geometric optimization, developed in the late sixties, which possesses numerous application in the field of engineering (entropy optimization, used in information theory, also belongs to this class of problems)
  - lp-norm optimization, a generalization of linear and convex quadratic optimization, which allows the formulation of constraints built around expressions of the form abs(ax+b^p) (where p is a fixed exponent strictly greater than 1).
  For each of these classes of problems, we introduced a new type of convex cone that made their formulation as standard conic problems possible. This allowed us to derive very simplified proofs of the classical duality results pertaining to these problems, notably weak duality and the absence of a duality gap (strong duality property without any constraint qualification, which does not hold in the general convex case). We also uncovered a very surprising result that stipulates that geometric optimization can be viewed as a limit case of lp-norm optimization. Encouraged by the similarities we observed, we developed a general framework that encompasses these two classes of problems and unifies all the previously obtained conic formulations. This framework, called separable optimization, allows the modelling of many more classes of problems while keeping the zero duality gap property.
  We also brought our attention to the design of interior-point methods to solve these problems. The theory of polynomial algorithms for convex optimization developed by Nesterov and Nemirovsky asserts that the main ingredient for these methods is a computable self-concordant barrier function for the corresponding cones. We were able to define such a barrier function in the case of lp-norm optimization (whose parameter, which is the main determining factor in the algorithmic complexity of the method, is proportional to the number of variables in the formulation and independent from p) as well as in the case of the general framework mentioned above. Our objective is now to exploit the inherent symmetry of this formulation in order to solve these problems efficiently using primal-dual methods.
  Finally, we contributed a survey of the self-concordancy property, improving some useful results about the value of the complexity parameter for certain categories of barrier functions and providing some insight on the reason why the most commonly adopted definition for self-concordant functions is the best possible.

• Pattern separation via ellipsoids and conic programming , François Glineur, supervised by Jacques Teghem, Master thesis (D.E.A.), Faculté Polytechnique de Mons, Belgium (September 1998), 58 pages. abstract, PDF.

  The first chapter is about mathematical programming. We will start by describing how and why researchers were led to study special types of mathematical programs, namely convex programs and conic programs. We will also provide a detailed discussion about conic duality and give a classification of conic programs. We will then describe what are self-scaled cones and why they are so useful in conic programming. Finally, we will give an overview of what can be modelled using a SQL conic program, keeping in mind our pattern separation problem. Since most of the material in the chapter is standard, many of the proofs are omitted.
  The second chapter will concentrate on pattern separation. After a short description of the problem, we will successively describe four different separation methods using SQL conic programming. For each method, various properties are investigated. Each algorithm has in fact been successively designed with the objective of eliminating the drawbacks of the previous one, while keeping its good properties. We conclude this chapter with a small section describing the state of the art in pattern separation with ellipsoids.
  The third chapter reports some computational experiments with our four methods, and provides a comparison with other separation procedures. Finally, we conclude this work by providing a short summary, highlighting the author's personal contribution and giving some interesting perspectives for further research.