In this paper we consider the problem of clustering m objects into c clusters. The objects are represented by points in an n-dimensional Euclidean space, and the objective is to classify these m points into c clusters...
详细信息
In this paper we consider the problem of clustering m objects into c clusters. The objects are represented by points in an n-dimensional Euclidean space, and the objective is to classify these m points into c clusters such that the distance between points within a cluster and its center (which is to be found) is minimized. The problem is a nonconvex program that has many local minima. It has been studied by many researchers and the most well-known algorithm for solving it is the k-means algorithm. In this paper, we develop a new algorithm for solving this problem based on a tabu search technique. Preliminary computational experience on the developed algorithm are encouraging and compare favorably with both the k-means and the simulated annealing algorithms.
This paper studies a bilevel programming problem with linear constraints, and in which the objective functions at both levels are concave bottleneck functions which are to be minimized. The problem is a non-convex pro...
详细信息
This paper studies a bilevel programming problem with linear constraints, and in which the objective functions at both levels are concave bottleneck functions which are to be minimized. The problem is a non-convex programming problem. It is shown that an optimal solution to the problem is attainable at an extreme point of the underlying region. The outer level objective function values are ranked in increasing order until a value is reached, one of the solutions corresponding to which is feasible for the problem. This solution is then the required global optimal solution.
The main purpose of this paper is the study of connections between combinatorial and continuous optimization. After reviewing some known results, new ways of establishing connections between the two fields are discuss...
详细信息
The main purpose of this paper is the study of connections between combinatorial and continuous optimization. After reviewing some known results, new ways of establishing connections between the two fields are discussed. Particularly, the importance of connecting combinatorial optimization with the field of variational inequalities is stressed. Related to this, the so-called gap function approach to solve a variational inequality is generalized, showing that methods for nonconvex and combinatorial programming may be useful in the variational field. Duality and further investigations are discussed.
A method of constructing test problems with known global solution for a class of reverse convex programs or linear programs with an additional reverse convex constraint is presented. The initial polyhedron is assumed ...
详细信息
A method of constructing test problems with known global solution for a class of reverse convex programs or linear programs with an additional reverse convex constraint is presented. The initial polyhedron is assumed to be a hypercube. The method then systematically generates cuts that slice the cube in such a way that a prespecified global solution on its edge remains intact. The proposed method does not require the solution of linear programs or systems of linear equations as is often required by existing techniques.
We derive a general principle demonstrating that by partitioning the feasible set, the duality gap, existing between a nonconvex program and its lagrangian dual, can be reduced, and in important special cases, even el...
详细信息
We derive a general principle demonstrating that by partitioning the feasible set, the duality gap, existing between a nonconvex program and its lagrangian dual, can be reduced, and in important special cases, even eliminated. The principle can be implemented in a Branch and Bound algorithm which computes an approximate global solution and a corresponding lower bound on the global optimal value. The algorithm involves decomposition and a nonsmooth local search. Numerical results for applying the algorithm to the pooling problem in oil refineries are given.
The optimization problem of a nonlinear real function over the weakly-efficient set associated to a nonlinear multi-objective program is examined. Necessary first-order conditions for a suboptimal solution are propose...
详细信息
The optimization problem of a nonlinear real function over the weakly-efficient set associated to a nonlinear multi-objective program is examined. Necessary first-order conditions for a suboptimal solution are proposed, assuming the convexity of the multi-objective program. Estimations of the optimal value are established and an algorithm for finding suboptimal solutions is proposed. The optimal value is approximated to any prescribed degree of accuracy using a weakly-efficient suboptimal solution.
The nonconvex programming problem of minimizing a quasi-concave function over an efficient (or weakly efficient) set of a multiobjective linear program is studied. A cutting plane algorithm which finds an approximate ...
详细信息
The nonconvex programming problem of minimizing a quasi-concave function over an efficient (or weakly efficient) set of a multiobjective linear program is studied. A cutting plane algorithm which finds an approximate optimal solution in a finite number of steps is developed. For the particular ''all linear'' case the algorithm performs better, finding an optimal solution in a finite time, and being more easily implemented.
The Fuzzy clustering (FC) problem is a non-convex mathematical program which usually possesses several local minima. The global minimum solution of the problem is found using a simulated annealing-based algorithm. Som...
详细信息
The Fuzzy clustering (FC) problem is a non-convex mathematical program which usually possesses several local minima. The global minimum solution of the problem is found using a simulated annealing-based algorithm. Some preliminary computational experiments are reported and the solution is compared with that generated by the Fuzzy C-means algorithm.
The problem (P) of optimizing a linear function over the efficient set of a multiple-objective linear program serves many useful purposes in multiple-criteria decision making. Mathematically, problem (P) can be classi...
详细信息
The problem (P) of optimizing a linear function over the efficient set of a multiple-objective linear program serves many useful purposes in multiple-criteria decision making. Mathematically, problem (P) can be classified as a global optimization problem. Such problems are much more difficult to solve than convex programming problems. In this paper, a nonadjacent extreme-point search algorithm is presented for finding a globally optimal solution for problem (P). The algorithm finds an exact extreme-point optimal solution for the problem after a finite number of iterations. It can be implemented using only linear programming methods. Convergence of the algorithm is proven, and a discussion is included of its main advantages and disadvantages.
The evolution of the bilinear programming problem is reviewed and a new, more general model is discussed. The model involves two decision vectors and reduces to a linear program when one of the decision vectors is fix...
详细信息
The evolution of the bilinear programming problem is reviewed and a new, more general model is discussed. The model involves two decision vectors and reduces to a linear program when one of the decision vectors is fixed. The class of problems under consideration contains traditional bilinear programs, general quadratic programs, and bilinearly constrained and quadratically constrained extensions of these problems. We describe how several important applications from the literature, including the multiple modular design problem, can be modeled as generalized bilinear programs. Finally, we derive a linear programming relaxation that can be used as a subproblem in algorithmic solution schemes based on outer approximation and branch and bound.
暂无评论