An additive utility mixed integer programming model for nonlinear discriminant analysis

Mathematical programming (MP) discriminant analysis models can be used to develop classification models for assigning observations of unknown class membership to one of a number of specified classes using values of a set of features associated with each observation. Since most MP discriminant analysis models generate linear discriminant functions, these MP models are generally used to develop linear classification models. Nonlinear classifiers may, however, have better classification performance than linear classifiers. In this paper, a mixed integer programming model is developed to generate nonlinear discriminant functions composed of monotone piecewise-linear marginal utility functions for each feature and the cut-off value for class membership. It is also shown that this model can be extended for feature selection. The performance of this new MP model for two-group discriminant analysis is compared with statistical discriminant analysis and other MP discriminant analysis models using a real problem and a number of simulated problem sets.     

Regularized fuzzy clusterwise ridge regression

Fuzzy clusterwise regression has been a useful method for investigating cluster-level heterogeneity of observations based on linear regression. This method integrates fuzzy clustering and ordinary least-squares regression, thereby enabling to estimate regression coefficients for each cluster and fuzzy cluster memberships of observations simultaneously. In practice, however, fuzzy clusterwise regression may suffer from multicollinearity as it builds on ordinary least-squares regression. To deal with this problem in fuzzy clusterwise regression, a new method, called regularized fuzzy clusterwise ridge regression, is proposed that combines ridge regression with regularized fuzzy clustering in a unified framework. In the proposed method, ridge regression is adopted to estimate clusterwise regression coefficients while handling potential multicollinearity among predictor variables. In addition, regularized fuzzy clustering based on maximizing entropy is utilized to systematically determine an optimal degree of fuzziness in memberships. A simulation study is conducted to evaluate parameter recovery of the proposed method as compared to the extant non-regularized counterpart. The usefulness of the proposed method is illustrated by an application concerning the relationship among the characteristics of used cars.     

Globally optimal clusterwise regression by mixed logical-quadratic programming

Exact global optimization of the clusterwise regression problem is challenging and there are currently no published feasible methods for performing this clustering optimally, even though it has been over thirty years since its original proposal. This work explores global optimization of the clusterwise regression problem using mathematical programming and related issues. A mixed logical-quadratic programming formulation with implication of constraints is presented and contrasted against a quadratic formulation based on the traditional big-M, which cannot guarantee optimality because the regression line coefficients, and thus errors, may be arbitrarily large. Clusterwise regression optimization times and solution optimality for two clusters are empirically tested on twenty real datasets and three series of synthetic datasets ranging from twenty to one hundred observations and from two to ten independent variables. Additionally, a few small real datasets are clustered into three lines.     

Extended DEA-Discriminant Analysis

A new non-parametric method is recently proposed for discriminant analysis (Sueyoshi, T., 1999. DEA-discriminant analysis in the view of goal programming. European Journal of Operational Research 115, 564–582). The new approach is referred to as “DEA-Discriminant Analysis (DEA-DA)” that is designed to identify the existence of an overlap between two groups, then determining the group membership of a newly sampled observation. A unique feature of the new technique is that it does not assume any discriminant function for group classification. As an extension of his study, this research proposes a new type of DEA-DA, or “Extended DEA-DA”, that can overcome some methodological drawbacks of its original formulation, but simultaneously maintaining its discriminant capabilities. Using a real data set regarding Japanese banks and a large simulation study, this research confirms that the Extended DEA-DA outperforms conventional linear and nonlinear discriminant analysis techniques.     

Functional fuzzy clusterwise regression analysis

We propose a functional extension of fuzzy clusterwise regression, which estimates fuzzy memberships of clusters and regression coefficient functions for each cluster simultaneously. The proposed method permits dependent and/or predictor variables to be functional, varying over time, space, and other continua. The fuzzy memberships and clusterwise regression coefficient functions are estimated by minimizing an objective function that adopts a basis function expansion approach to approximating functional data. An alternating least squares algorithm is developed to minimize the objective function. We conduct simulation studies to demonstrate the superior performance of the proposed method compared to its non-functional counterpart and to examine the performance of various cluster validity measures for selecting the optimal number of clusters. We apply the proposed method to real datasets to illustrate the empirical usefulness of the proposed method.     

Some theoretical challenges in digital geometry: A perspective

In recent years image analysis has become a research field of exceptional significance, due to its relevance to real life problems in important societal and governmental sectors, such as medicine, defense, and security. The explicit purpose of the present Perspective is to suggest a number of strategic objectives for theoretical research, with an emphasis on the combinatorial approach in image analysis. Most of the proposed objectives relate to the need to make the theoretical foundations of combinatorial image analysis better integrated within a number of well-established subjects of theoretical computer science and discrete applied mathematics, such as the theory of algorithms and problem complexity, combinatorial optimization and polyhedral combinatorics, integer and linear programming, and computational geometry.     

Determination of the threshold value β of variable precision rough set by fuzzy algorithms

In the past, the choices of β values to be applied to find the β-reducts in VPRS for an information system are somewhat arbitrary. In this study, a systematic method which bridges the fuzzy set methodology and probabilistic approach of RS to solve the threshold value β determination problem in variable precision rough sets (VPRS) is proposed. Different from the existing probabilistic methods, the proposed method relies on the fuzzy membership degrees of each attribute of the objects to calculate β. The proposed method gives the membership degrees and fuzzy aggregation operators the probabilistic interpretations. Based on the probabilistic interpretations, the threshold value β of VPRS is directly derived from fuzzy membership degree by Implication Relations and Fuzzy Algorithms, in which the membership degrees are obtained by the standard Fuzzy C-means method. The argument is that errors of system classification would occur in the fuzzy-clustering phase prior to information classification, therefore the threshold value β should be constrained by the probability of belongingness of an object to the fuzzy clusters, i.e., through the values of membership functions. A few examples are given in the paper to demonstrate the differences with other β-determining methods.     

A new method of solving nonlinear mathematical programming problems involving r-invex functions

A new approach to a solution of a nonlinear constrained mathematical programming problem involving r-invex functions with respect to the same function η is introduced. An η-approximated problem associated with an original nonlinear mathematical programming problem is presented that involves η-approximated functions constituting the original problem. The equivalence between optima points for the original mathematical programming problem and its η-approximated optimization problem is established under r-invexity assumption.     

Simultaneous Model Selection via Rate-Distortion Theory,With Applications to Cluster and Significance Analysis of Gene Expression Data

High-dimensional data are prevalent across many application areas, and generate an ever-increasing demand for statistical methods of dimension reduction, such as cluster and significance analysis. One application area that has recently received much interest is the analysis of microarray gene expression data.

The results of cluster analysis are open to subjective interpretation. To facilitate the objective inference of such analyses, we use flexible parameterizations of the cluster means, paired with model selection, to generate sparse and easy-to-interpret representations of each cluster. Model selection in cluster analysis is combinatorial in the numbers of clusters and data dimensions, and thus presents a computationally challenging task.

In this article we introduce a model selection method based on rate-distortion theory, which allows us to turn the combinatorial model selection problem into a fast and simultaneous selection across clusters. The method is also applicable to model selection in significance analysis

We show that simultaneous model selection for cluster analysis generates objectively interpretable cluster models, and that the selection performance is competitive with a combinatorial search, at a fraction of the computational cost. Moreover, we show that the rate-distortion based significance analysis substantially increases the power compared with standard methods.

This article has supplementary material online.     

Pattern definition of the p-efficiency concept

This study revisits the celebrated p-efficiency concept introduced by Prékopa (Z.?Oper. Res. 34:441?C461, 1990) and defines a p-efficient point (pLEP) as a combinatorial pattern. The new definition uses elements from the combinatorial pattern recognition field and is based on the combinatorial pattern framework for stochastic programming problems proposed in Lejeune (Stochastic programming e-print series (SPEPS) 2010-5, 2010). The approach is based on the binarization of the probability distribution, and the generation of a consistent partially defined Boolean function representing the combination (F,p) of the binarized probability distribution F and the enforced probability level p. A combinatorial pattern provides a compact representation of the defining characteristics of a pLEP and opens the door to new methods for the generation of pLEPs. We show that a combinatorial pattern representing a pLEP constitutes a strong and prime pattern and we derive it through the solution of an integer programming problem. Next, we demonstrate that the (finite) collection of pLEPs can be represented as a disjunctive normal form (DNF). We propose a mixed-integer programming formulation allowing for the construction of the DNF that is shown to be prime and irreducible. We illustrate the proposed method on a problem studied by Prékopa (Stochastic programming: handbook in operations research and management science, vol.?10, Elsevier, Amsterdam, 2003).     

Solving multi-level multi-objective linear programming problems through fuzzy goal programming approach

In this paper, two new algorithms are presented to solve multi-level multi-objective linear programming (ML-MOLP) problems through the fuzzy goal programming (FGP) approach. The membership functions for the defined fuzzy goals of all objective functions at all levels are developed in the model formulation of the problem; so also are the membership functions for vectors of fuzzy goals of the decision variables, controlled by decision makers at the top levels. Then the fuzzy goal programming approach is used to achieve the highest degree of each of the membership goals by minimizing their deviational variables and thereby obtain the most satisfactory solution for all decision makers.     

A Global Optimization RLT-based Approach for Solving the Fuzzy Clustering Problem

The field of cluster analysis is primarily concerned with the partitioning of data points into different clusters so as to optimize a certain criterion. Rapid advances in technology have made it possible to address clustering problems via optimization theory. In this paper, we present a global optimization algorithm to solve the fuzzy clustering problem, where each data point is to be assigned to (possibly) several clusters, with a membership grade assigned to each data point that reflects the likelihood of the data point belonging to that cluster. The fuzzy clustering problem is formulated as a nonlinear program, for which a tight linear programming relaxation is constructed via the Reformulation-Linearization Technique (RLT) in concert with additional valid inequalities. This construct is embedded within a specialized branch-and-bound (B&B) algorithm to solve the problem to global optimality. Computational experience is reported using several standard data sets from the literature as well as using synthetically generated larger problem instances. The results validate the robustness of the proposed algorithmic procedure and exhibit its dominance over the popular fuzzy c-means algorithmic technique and the commercial global optimizer BARON.     

H∞ estimation for fuzzy membership function optimization

Given a fuzzy logic system, how can we determine the membership functions that will result in the best performance? If we constrain the membership functions to a specific shape (e.g., triangles or trapezoids) then each membership function can be parameterized by a few variables and the membership optimization problem can be reduced to a parameter optimization problem. The parameter optimization problem can then be formulated as a nonlinear filtering problem. In this paper we solve the nonlinear filtering problem using H_∞ state estimation theory. However, the membership functions that result from this approach are not (in general) sum normal. That is, the membership function values do not add up to one at each point in the domain. We therefore modify the H_∞ filter with the addition of state constraints so that the resulting membership functions are sum normal. Sum normality may be desirable not only for its intuitive appeal but also for computational reasons in the real time implementation of fuzzy logic systems. The methods proposed in this paper are illustrated on a fuzzy automotive cruise controller and compared to Kalman filtering based optimization.     

An interactive dynamic approach based on hybrid swarm optimization for solving multiobjective programming problem with fuzzy parameters

Real engineering design problems are generally characterized by the presence of many often conflicting and incommensurable objectives. Naturally, these objectives involve many parameters whose possible values may be assigned by the experts. The aim of this paper is to introduce a hybrid approach combining three optimization techniques, dynamic programming (DP), genetic algorithms and particle swarm optimization (PSO). Our approach integrates the merits of both DP and artificial optimization techniques and it has two characteristic features. Firstly, the proposed algorithm converts fuzzy multiobjective optimization problem to a sequence of a crisp nonlinear programming problems. Secondly, the proposed algorithm uses H-SOA for solving nonlinear programming problem. In which, any complex problem under certain structure can be solved and there is no need for the existence of some properties rather than traditional methods that need some features of the problem such as differentiability and continuity. Finally, with different degree of α we get different α-Pareto optimal solution of the problem. A numerical example is given to illustrate the results developed in this paper.     

Helly-type theorems and Generalized Linear Programming

Recent combinatorial algorithms for linear programming can also be applied to certain nonlinear problems. We call these Generalized Linear-Programming, or GLP, problems. We connect this class to a collection of results from combinatorial geometry called Helly-type theorems. We show that there is a Helly-type theorem about the constraint set of every GLP problem. Given a familyH of sets with a Helly-type theorem, we give a paradigm for finding whether the intersection ofH is empty, by formulating the question as a GLP problem. This leads to many applications, including linear expected time algorithms for finding line transversals and mini-max hyperplane fitting. Our applications include GLP problems with the surprising property that the constraints are nonconvex or even disconnected.     

Integer programming formulation of combinatorial optimization problems

This paper considers in a somewhat general setting when a combinatorial optimization problem can be formulated as an (all-integer) integer programming (IP) problem. The main result is that any combinatorial optimization problem can be formulated as an IP problem if its feasible region S is finite but there are many rather sample problems that have no IP formulation if their S is infinite. The approach used for finite S usually gives a formulation with a relatively small number of additional variables for example, an integer polynomial of n 0?1 variables requires at most n + 1 additional variables by our approach, whereas 2ⁿ - (n + 1) additional variables at maximum are required by other existing methods. Finally, the decision problem of deciding whether an arbitrarily given combinatorial optimization problem has an IP formulation is considered and it is shown by an argument closely related to Hilbert's tenth problem (drophantine equations) that no such algorithm exists.     

A bulk arrival queueing model with fuzzy parameters and varying batch sizes

This paper develops a nonlinear programming approach to derive the membership functions of the steady-state performance measures in bulk arrival queueing systems with varying batch sizes, in that the arrival rate and service rate are fuzzy numbers. The basic idea is based on Zadeh’s extension principle. Two pairs of mixed integer nonlinear programs (MINLP) with binary variables are formulated to calculate the upper and lower bounds of the system performance measure at possibility level α. From different values of α, the membership function of the system performance measure is constructed. For practice use, the defuzzification of performance measures is also provided via Yager ranking index. To demonstrate the validity of the proposed method, a numerical example is solved successfully.     

Obviating some of the theoretical barriers of data envelopment analysis-discriminant analysis: an application in predicting cluster membership of customers

Data envelopment analysis-discriminant analysis (DEA-DA) has been used for predicting cluster membership of decision-making units (DMUs). One of the possible applications of DEA-DA is in the marketing research area. This paper uses cluster analysis to cluster customers into two clusters: Gold and Lead. Then, to predict cluster membership of new customers, DEA-DA is applied. In DEA-DA, an arbitrary parameter imposing a small gap between two clusters (η) is incorporated. It is shown that different η leads to different prediction accuracy levels since an unsuitable value for η leads to an incorrect classification of DMUs. We show that even the data set with no overlap between two clusters can be misclassified. This paper proposes a new DEA-DA model to tackle this issue. The aim of this paper is to illustrate some computational difficulties in previous DEA-DA approaches and then to propose a new DEA-DA model to overcome the difficulties. A case study demonstrates the efficacy of the proposed model.     

动态投入产出灰色最优控制模型

根据灰色系统理论,建立了动态投入产出问题的灰色最优控制模型.利用灰集合理论,把灰色最优控制问题转化为以隶属度为目标函数的(非灰色的)非线性规划问题,从而可利用非线性规划的方法求解这个灰色最优控制问题.     

Solving fuzzy queueing decision problems via a parametric mixed integer nonlinear programming method

This paper proposes a mathematical programming method to construct the membership functions of the fuzzy objective value of the cost-based queueing decision problem with the cost coefficients and the arrival rate being fuzzy numbers. On the basis of Zadeh’s extension principle, three pairs of mixed integer nonlinear programs (MINLP) parameterized by the possibility level α are formulated to calculate the lower and upper bounds of the minimal expected total cost per unit time at α, through which the membership function of the minimal expected total cost per unit time of the fuzzy objective value is constructed. To provide a suitable optimal service rate for designing queueing systems, the Yager’s ranking index method is adopted. Two numerical examples are solved successfully to demonstrate the validity of the proposed method. Since the objective value is completely expressed by a membership function rather than by a crisp value, it conserves the fuzziness of the input information, thus more information is provided for designing queueing systems. The successful extension of queueing decision models to fuzzy environments permits queueing decision models to have wider applications in practice.