An algorithm for minimizing clustering functions
- Authors: Bagirov, Adil , Ugon, Julien
- Date: 2005
- Type: Text , Journal article
- Relation: Optimization Vol. 54, no. 4-5 (Aug-Oct 2005), p. 351-368
- Full Text:
- Reviewed:
- Description: The problem of cluster analysis is formulated as a problem of nonsmooth, nonconvex optimization. An algorithm for solving the latter optimization problem is developed which allows one to significantly reduce the computational efforts. This algorithm is based on the so-called discrete gradient method. Results of numerical experiments are presented which demonstrate the effectiveness of the proposed algorithm.
- Description: C1
- Description: 2003001266
A feature selection approach for unsupervised classification based on clustering
- Authors: Rubinov, Alex , Soukhoroukova, Nadejda , Ugon, Julien
- Date: 2004
- Type: Text , Conference paper
- Relation: Paper presented at Sixth International Conference on Optimization: Techniques and Applications (ICOTA) , University of Ballarat, Ballarat, Victoria : 9th-11th December 2004
- Full Text: false
- Description: Data have been collected for many years in different scientific (industrial, medical) research groups. Very often these groups kept all the the they could collect. It is possible that the data contains a lot of noisy features which do not bring any information, but make the problem more complicated. The additional study of eliminating non-informative and selecting informative features is very important in the area of Data Mining. There are several feature selection methods which were developed for supervised classification. The area of feature selection for unsupervised classification is not so developed. In this paper we present a new feature selection approach for unsupervised classification, based on clustering and nonsmooth optimisation techniques.
- Description: 2003004085
Piecewise partially separable functions and a derivative-free algorithm for large scale nonsmooth optimization
- Authors: Bagirov, Adil , Ugon, Julien
- Date: 2006
- Type: Text , Journal article
- Relation: Journal of Global Optimization Vol. 35, no. 2 (Jun 2006), p. 163-195
- Full Text:
- Reviewed:
- Description: This paper introduces the notion of piecewise partially separable functions and studies their properties. We also consider some of many applications of these functions. Finally, we consider the problem of minimizing of piecewise partially separable functions and develop an algorithm for its solution. This algorithm exploits the structure of such functions. We present the results of preliminary numerical experiments.
- Description: 2003001532
Classification through incremental max-min separability
- Authors: Bagirov, Adil , Ugon, Julien , Webb, Dean , Karasozen, Bulent
- Date: 2011
- Type: Text , Journal article
- Relation: Pattern Analysis and Applications Vol. 14, no. 2 (2011), p. 165-174
- Relation: http://purl.org/au-research/grants/arc/DP0666061
- Full Text: false
- Reviewed:
- Description: Piecewise linear functions can be used to approximate non-linear decision boundaries between pattern classes. Piecewise linear boundaries are known to provide efficient real-time classifiers. However, they require a long training time. Finding piecewise linear boundaries between sets is a difficult optimization problem. Most approaches use heuristics to avoid solving this problem, which may lead to suboptimal piecewise linear boundaries. In this paper, we propose an algorithm for globally training hyperplanes using an incremental approach. Such an approach allows one to find a near global minimizer of the classification error function and to compute as few hyperplanes as needed for separating sets. We apply this algorithm for solving supervised data classification problems and report the results of numerical experiments on real-world data sets. These results demonstrate that the new algorithm requires a reasonable training time and its test set accuracy is consistently good on most data sets compared with mainstream classifiers. © 2010 Springer-Verlag London Limited.
The excess degree of a polytope
- Authors: Pineda-Villavicencio, Guillermo , Ugon, Julien , Yost, David
- Date: 2018
- Type: Text , Journal article
- Relation: SIAM Journal on Discrete Mathematics Vol. 32, no. 3 (2018), p. 2011-2046, http://purl.org/au-research/grants/arc/DP180100602
- Full Text:
- Reviewed:
- Description: We define the excess degree \xi (P) of a d-polytope P as 2f1 - df0, where f0 and f1 denote the number of vertices and edges, respectively. This parameter measures how much P deviates from being simple. It turns out that the excess degree of a d-polytope does not take every natural number: the smallest possible values are 0 and d - 2, and the value d - 1 only occurs when d = 3 or 5. On the other hand, for fixed d, the number of values not taken by the excess degree is finite if d is odd, and the number of even values not taken by the excess degree is finite if d is even. The excess degree is then applied in three different settings. First, it is used to show that polytopes with small excess (i.e., \xi (P) < d) have a very particular structure: provided d ot = 5, either there is a unique nonsimple vertex, or every nonsimple vertex has degree d + 1. This implies that such polytopes behave in a similar manner to simple polytopes in terms of Minkowski decomposability: they are either decomposable or pyramidal, and their duals are always indecomposable. Second, we characterize completely the decomposable d-polytopes with 2d + 1 vertices (up to combinatorial equivalence). Third, all pairs (f0, f1), for which there exists a 5-polytope with f0 vertices and f1 edges, are determined.
Global optimality conditions and optimization methods for polynomial programming problems
- Authors: Wu, Zhiyou , Tian, Jing , Ugon, Julien
- Date: 2015
- Type: Text , Journal article
- Relation: Journal of Global Optimization Vol. 62, no. 4 (2015), p. 617-641
- Full Text: false
- Reviewed:
- Description: This paper is concerned with the general polynomial programming problem with box constraints, including global optimality conditions and optimization methods. First, a necessary global optimality condition for a general polynomial programming problem with box constraints is given. Then we design a local optimization method by using the necessary global optimality condition to obtain some strongly or -strongly local minimizers which substantially improve some KKT points. Finally, a global optimization method, by combining the new local optimization method and an auxiliary function, is designed. Numerical examples show that our methods are efficient and stable.
On the reconstruction of polytopes
- Authors: Doolittle, Joseph , Nevo, Eran , Pineda-Villavicencio, Guillermo , Ugon, Julien , Yost, David
- Date: 2019
- Type: Text , Journal article
- Relation: Discrete and Computational Geometry Vol. 61, no. 2 (2019), p. 285-302. http://purl.org/au-research/grants/arc/DP180100602
- Full Text:
- Reviewed:
- Description: Blind and Mani, and later Kalai, showed that the face lattice of a simple polytope is determined by its graph, namely its 1-skeleton. Call a vertex of a d-polytope nonsimple if the number of edges incident to it is more than d. We show that (1) the face lattice of any d-polytope with at most two nonsimple vertices is determined by its 1-skeleton; (2) the face lattice of any d-polytope with at most d- 2 nonsimple vertices is determined by its 2-skeleton; and (3) for any d> 3 there are two d-polytopes with d- 1 nonsimple vertices, isomorphic (d- 3) -skeleta and nonisomorphic face lattices. In particular, the result (1) is best possible for 4-polytopes. © 2018, Springer Science+Business Media, LLC, part of Springer Nature.
Nonsmooth DC programming approach to clusterwise linear regression : Optimality conditions and algorithms
- Authors: Bagirov, Adil , Ugon, Julien
- Date: 2018
- Type: Text , Journal article
- Relation: Optimization Methods and Software Vol. 33, no. 1 (2018), p. 194-219
- Relation: http://purl.org/au-research/grants/arc/DP140103213
- Full Text: false
- Reviewed:
- Description: The clusterwise linear regression problem is formulated as a nonsmooth nonconvex optimization problem using the squared regression error function. The objective function in this problem is represented as a difference of convex functions. Optimality conditions are derived, and an algorithm is designed based on such a representation. An incremental approach is proposed to generate starting solutions. The algorithm is tested on small to large data sets. © 2017 Informa UK Limited, trading as Taylor & Francis Group.
The linkedness of cubical polytopes: the cube
- Authors: Bui, Hoa , Pineda-Villavicencio, Guillermo , Ugon, Julien
- Date: 2021
- Type: Text , Journal article
- Relation: Electronic Journal of Combinatorics Vol. 28, no. 3 (2021), p.
- Relation: http://purl.org/au-research/grants/arc/DP180100602
- Full Text:
- Reviewed:
- Description: The paper is concerned with the linkedness of the graphs of cubical polytopes. A graph with at least 2k vertices is k-linked if, for every set of k disjoint pairs of vertices, there are k vertex-disjoint paths joining the vertices in the pairs. We say that a polytope is k-linked if its graph is k-linked. We establish that the d-dimensional cube is [(d + 1)/2]-linked, for every d ≠ 3; this is the maximum possible linkedness of a d-polytope. This result implies that, for every d ≥ 1, a cubical d-polytope is [d/2]-linked, which answers a question of Wotzlaw (Incidence graphs and unneighborly polytopes, Ph.D. thesis, 2009). Finally, we introduce the notion of strong linkedness, which is slightly stronger than that of linkedness. A graph G is strongly k-linked if it has at least 2k + 1 vertices and, for every vertex v of G, the subgraph G − v is k-linked. We show that cubical 4-polytopes are strongly 2-linked and that, for each d ≥ 1, d-dimensional cubes are strongly
Polytopes close to being simple
- Authors: Pineda-Villavicencio, Guillermo , Ugon, Julien , Yost, David
- Date: 2020
- Type: Text , Journal article
- Relation: Discrete and Computational Geometry Vol. 64, no. 1 (2020), p. 200-215
- Relation: http://purl.org/au-research/grants/arc/DP180100602
- Full Text:
- Reviewed:
- Description: It is known that polytopes with at most two nonsimple vertices are reconstructible from their graphs, and that d-polytopes with at most d- 2 nonsimple vertices are reconstructible from their 2-skeletons. Here we close the gap between 2 and d- 2 , showing that certain polytopes with more than two nonsimple vertices are reconstructible from their graphs. In particular, we prove that reconstructibility from graphs also holds for d-polytopes with d+ k vertices and at most d- k+ 3 nonsimple vertices, provided k
Generalised rational approximation and its application to improve deep learning classifiers
- Authors: Peiris, V , Sharon, Nir , Sukhorukova, Nadezda , Ugon, Julien
- Date: 2021
- Type: Text , Journal article
- Relation: Applied Mathematics and Computation Vol. 389, no. (2021), p.
- Relation: https://purl.org/au-research/grants/arc/DP180100602
- Full Text: false
- Reviewed:
- Description: A rational approximation (that is, approximation by a ratio of two polynomials) is a flexible alternative to polynomial approximation. In particular, rational functions exhibit accurate estimations to nonsmooth and non-Lipschitz functions, where polynomial approximations are not efficient. We prove that the optimisation problems appearing in the best uniform rational approximation and its generalisation to a ratio of linear combinations of basis functions are quasiconvex even when the basis functions are not restricted to monomials. Then we show how this fact can be used in the development of computational methods. This paper presents a theoretical study of the arising optimisation problems and provides results of several numerical experiments. We apply our approximation as a preprocessing step to deep learning classifiers and demonstrate that the classification accuracy is significantly improved compared to the classification of the raw signals. © 2020
- Description: This research was supported by the Australian Research Council (ARC), Solving hard Chebyshev approximation problems through nonsmooth analysis (Discovery Project DP180100602 ). This research was partially sponsored by Tel Aviv-Swinburne Research Collaboration Grant (2019).