12Global optimization
8Canonical duality theory
5Canonical duality theories
40102 Applied Mathematics
4Duality theory
4Integer programming
30103 Numerical and Computational Mathematics
3Combinatorial optimization
3Maximization problem
2Canonical dual transformation
2Canonical duality
2Convex set
2Dual problem
2Integer optimization
2Mathematical programming
2Maximal directed spanning tree
2NP-hard problems
2Nonconvex programming
2Optimization techniques
2Problem solving

Show More

Show Less

Format Type

3-HOP: a high-compression indexing scheme for reachability query

- Jin, Ruoming, Yang, Xiang, Ruan, Ning, Fuhry, David

**Authors:**Jin, Ruoming , Yang, Xiang , Ruan, Ning , Fuhry, David**Date:**2009**Type:**Text , Conference paper**Relation:**SIGMOD '09 Proceedings of the 2009 ACM SIGMOD International Conference on Management of data p. 813-826**Full Text:**false**Reviewed:****Description:**Reachability queries on large directed graphs have attracted much attention recently. The existing work either uses spanning structures, such as chains or trees, to compress the complete transitive closure, or utilizes the 2-hop strategy to describe the reachability. Almost all of these approaches work well for very sparse graphs. However, the challenging problem is that as the ratio of the number of edges to the number of vertices increases, the size of the compressed transitive closure grows very large. In this paper, we propose a new 3-hop indexing scheme for directed graphs with higher density. The basic idea of 3-hop indexing is to use chain structures in combination with hops to minimize the number of structures that must be indexed. Technically, our goal is to find a 3-hop scheme over dense DAGs (directed acyclic graphs) with minimum index size. We develop an efficient algorithm to discover a transitive closure contour, which yields near optimal index size. Empirical studies show that our 3-hop scheme has much smaller index size than state-of-the-art reachability query schemes such as 2-hop and path-tree when DAGs are not very sparse, while our query time is close to path-tree, which is considered to be one of the best reachability query schemes.

A highway-centric labeling approach for answering distance queries on large sparse graphs

- Jin, Ruoming, Ruan, Ning, Xiang, Yang, Lee, Victor

**Authors:**Jin, Ruoming , Ruan, Ning , Xiang, Yang , Lee, Victor**Date:**2012**Type:**Text , Conference paper**Relation:**ACM SIGMOD International Conference on Management of Data, 2012 p. 445-456**Full Text:**false**Reviewed:****Description:**The distance query, which asks the length of the shortest path from a vertex u to another vertex v, has applications ranging from link analysis, semantic web and other ontology processing, to social network operations. Here, we propose a novel labeling scheme, referred to as Highway-Centric Labeling, for answering distance queries in a large sparse graph. It empowers the distance labeling with a highway structure and leverages a novel bipartite set cover framework/algorithm. Highway-centric labeling provides better labeling size than the state-of-the-art 2-hop labeling, theoretically and empirically. It also offers both exact distance and approximate distance with bounded accuracy. A detailed experimental evaluation on both synthetic and real datasets demonstrates that highway-centric labeling can outperform the state-of-the-art distance computation approaches in terms of both index size and query time. © 2012 ACM.**Description:**Proceedings of the ACM SIGMOD International Conference on Management of Data

A sparsification approach for temporal graphical model decomposition

- Ruan, Ning, Jin, Ruoming, Lee, Victor, Huang, K

**Authors:**Ruan, Ning , Jin, Ruoming , Lee, Victor , Huang, K**Date:**2009**Type:**Text , Conference paper**Full Text:**false**Reviewed:**

Advances in Global Optimization

- Gao, David, Ruan, Ning, Xing, Wenxun

**Authors:**Gao, David , Ruan, Ning , Xing, Wenxun**Date:**2015**Type:**Text , Conference paper**Relation:**3rd World Congress on Global Optimization in Engineering and Science, WCGO 2013; Anhui, China; 8th-12th July 2013 Vol. 95**Full Text:**false**Reviewed:****Description:**This proceedings volume addresses advances in global optimization - a multidisciplinary research field that deals with the analysis, characterization, and computation of global minima and/or maxima of nonlinear, non-convex, and nonsmooth functions in continuous or discrete forms. The volume contains selected papers from the third biannual World Congress on Global Optimization in Engineering & Science (WCGO), held in the Yellow Mountains, Anhui, China on July 8-12, 2013. The papers fall into eight topical sections: mathematical programming; combinatorial optimization; duality theory; topology optimization; variational inequalities and complementarity problems; numerical optimization; stochastic models and simulation; and complex simulation and supply chain analysis.

An efficient classification using support vector machines

- Ruan, Ning, Chen, Yi, Gao, David

**Authors:**Ruan, Ning , Chen, Yi , Gao, David**Date:**2013**Type:**Text , Conference paper**Relation:**Proceedings of 2013 Science and Information Conference, SAI 2013 p. 585-589**Full Text:**false**Reviewed:****Description:**Support vector machine (SVM) is a popular method for classification in data mining. The canonical duality theory provides a unified analytic solution to a wide range of discrete and continuous problems in global optimization. This paper presents a canonical duality approach for solving support vector machine problem. It is shown that by the canonical duality, these nonconvex and integer optimization problems are equivalent to a unified concave maximization problem over a convex set and hence can be solved efficiently by existing optimization techniques. © 2013 The Science and Information Organization.

An interesting cryptography study based on knapsack problem

**Authors:**Ruan, Ning**Date:**2013**Type:**Text , Conference paper**Relation:**Proceedings - UKSim 15th International Conference on Computer Modelling and Simulation, UKSim 2013 p. 330-334**Full Text:****Reviewed:****Description:**Cryptography is an art that has been practised through the centuries. Interest in the applications of the knapsack problem to cryptography has arisen with the advent of public key cryptography. The knapsack problem is well documented problem and all research into its properties have lead to the conjecture that it is difficult to solve. In this paper the canonical duality theory is presented for solving general knapsack problem. By using the canonical dual transformation, the integer programming problem can be converted into a continuous canonical dual problem with zero duality gap. The optimality criterion are also discussed. Numerical examples show the efficiency of the method. Â© 2013 IEEE.

**Authors:**Ruan, Ning**Date:**2013**Type:**Text , Conference paper**Relation:**Proceedings - UKSim 15th International Conference on Computer Modelling and Simulation, UKSim 2013 p. 330-334**Full Text:****Reviewed:****Description:**Cryptography is an art that has been practised through the centuries. Interest in the applications of the knapsack problem to cryptography has arisen with the advent of public key cryptography. The knapsack problem is well documented problem and all research into its properties have lead to the conjecture that it is difficult to solve. In this paper the canonical duality theory is presented for solving general knapsack problem. By using the canonical dual transformation, the integer programming problem can be converted into a continuous canonical dual problem with zero duality gap. The optimality criterion are also discussed. Numerical examples show the efficiency of the method. Â© 2013 IEEE.

Application of canonical duality theory to fixed point problem

**Authors:**Ruan, Ning , Gao, David**Date:**2015**Type:**Text , Conference paper**Relation:**3rd World Congress on Global Optimization in Engineering and Science, WCGO 2013; Anhui, China; 8th-12th July 2013 Vol. 95, p. 157-163**Full Text:**false**Reviewed:****Description:**In this paper, we study general fixed point problem. We first rewrite the original problem in the canonical framework. Then, we proposed a canonical transformation of this problem, which leads to a convex differentiable dual problem and new iteration method. An illustrative example is presented. © Springer International Publishing Switzerland 2015.

Canonical dual least square method for solving general nonlinear systems of quadratic equations

**Authors:**Ruan, Ning , Gao, David**Date:**2010**Type:**Text , Journal article**Relation:**Computational Optimization and Applications Vol. 47, no. (2010), p. 335-347**Full Text:**false**Reviewed:****Description:**This paper presents a canonical dual approach for solving general non- linear algebraic systems. By using least square method, the nonlinear system of m -quadratic equations in n -dimensional space is first formulated as a nonconvex opti- mization problem. We then proved that, by the canonical duality theory developed by the second author, this nonconvex problem is equivalent to a concave maximization problem in R, which can be solved easily by well-developed convex optimization techniques. Both existence and uniqueness of global optimal solutions are discussed, and several illustrative examples are presented.**Description:**C1

Canonical dual solutions for fixed cost quadratic programs

- Gao, David, Ruan, Ning, Sherali, Hanif

**Authors:**Gao, David , Ruan, Ning , Sherali, Hanif**Date:**2010**Type:**Text , Book chapter**Relation:**Optimization and Optimal Control p. 139-156**Full Text:**false**Reviewed:****Description:**This chapter presents a canonical dual approach for solving a mixed-integer quadratic minimization problem with fixed cost terms. We show that this well-known NP-hard problem in R2n can be transformed into a continuous concave maximization dual problem over a convex feasible subset of R2n with zero duality gap. The resulting canonical dual problem can be solved easily, under certain conditions, by traditional convex programming methods. Both existence and uniqueness of global optimal solutions are discussed. Application to a decoupled mixed-integer problem is illustrated and analytic solutions for both a global minimizer and a global maximizer are obtained. Examples for both decoupled and general nonconvex problems are presented. Furthermore, we discuss connections between the proposed canonical duality theory approach and the classical Lagrangian duality approach. An open problem is proposed for future study.

- Gao, David, Ruan, Ning, Pardalos, Panos

**Authors:**Gao, David , Ruan, Ning , Pardalos, Panos**Date:**2012**Type:**Text , Book chapter**Relation:**Sensors: Theory, Algorithms, and applications optimization and its applications p. 37-56**Full Text:**false**Reviewed:****Description:**This chapter presents a canonical dual approach for solving a general sum of fourth-order polynomial minimization problem. This problem arises extensively in engineering and science, including database analysis, computational biology, sensor network communications, nonconvex mechanics, and ecology. We first show that this global optimization problem is actually equivalent to a discretized minimal potential variational problem in large deformation mechanics. Therefore, a general analytical solution is proposed by using the canonical duality theory developed by the first author. Both global and local extremality properties of this analytical solution are identified by a triality theory. Application to sensor network localization problem is illustrated. Our results show when the problem is not uniquely localizable, the “optimal solution” obtained by the SDP method is actually a local maximizer of the total potential energy. However, by using a perturbed canonical dual approach, a class of Euclidean distance problems can be converted to a unified concave maximization dual problem with zero duality gap, which can be solved by well-developed convex minimization methods. This chapter should bridge an existing gap between nonconvex mechanics and global optimization.

Canonical duality approach for non-linear dynamical systems

**Authors:**Ruan, Ning , Gao, David**Date:**2014**Type:**Text , Journal article**Relation:**IMA Journal of Applied Mathematics (Institute of Mathematics and Its Applications) Vol. 79, no. 2 (2014), p. 313-325**Full Text:**false**Reviewed:****Description:**This paper presents a canonical dual approach for solving a non-linear population growth problem governed by the well-known logistic equation. Using the finite difference and least squares methods, the non-linear differential equation is first formulated as a non-convex optimization problem with unknown parameters. We then prove that by the canonical duality theory, this non-convex problem is equivalent to a concave maximization problem over a convex feasible space, which can be solved easily to obtain a global optimal solution to this challenging problem. Several illustrative examples are presented.

Canonical duality theory and algorithm for solving challenging problems in network optimisation

**Authors:**Ruan, Ning , Gao, David**Date:**2012**Type:**Text , Conference paper**Relation:**19th International Conference on Neural Information Processing, ICONIP 2012 Vol. 7665 LNCS, p. 702-709**Full Text:****Reviewed:****Description:**This paper presents a canonical dual approach for solving a general nonconvex problem in network optimization. Three challenging problems, sensor network location, traveling salesman problem, and scheduling problem are listed to illustrate the applications of the proposed method. It is shown that by the canonical duality, these nonconvex and integer optimization problems are equivalent to unified concave maximization problem over a convex set and hence can be solved efficiently by existing optimization techniques. © 2012 Springer-Verlag.**Description:**2003010653

**Authors:**Ruan, Ning , Gao, David**Date:**2012**Type:**Text , Conference paper**Relation:**19th International Conference on Neural Information Processing, ICONIP 2012 Vol. 7665 LNCS, p. 702-709**Full Text:****Reviewed:****Description:**This paper presents a canonical dual approach for solving a general nonconvex problem in network optimization. Three challenging problems, sensor network location, traveling salesman problem, and scheduling problem are listed to illustrate the applications of the proposed method. It is shown that by the canonical duality, these nonconvex and integer optimization problems are equivalent to unified concave maximization problem over a convex set and hence can be solved efficiently by existing optimization techniques. © 2012 Springer-Verlag.**Description:**2003010653

Complete solutions to mixed integer programming

**Authors:**Ruan, Ning**Date:**2013**Type:**Text , Journal article**Relation:**American Journal of Computational Mathematics Vol. 3, no. 3B (2013), p. 27-30**Full Text:**false**Reviewed:****Description:**This paper considers a new canonical duality theory for solving mixed integer quadratic programming problem. It shows that this well-known NP -hard problem can be converted into concave maximization dual problems without duality gap. And the dual problems can be solved, under certain conditions, by polynomial algorithms.

Computing label-constraint reachability in graph databases

- Jin, Ruoming, Hong, Hui, Wang, Haixun, Ruan, Ning, Yang, Xiang

**Authors:**Jin, Ruoming , Hong, Hui , Wang, Haixun , Ruan, Ning , Yang, Xiang**Date:**2010**Type:**Text , Conference paper**Relation:**SIGMOD '10: Proceedings of the 2010 ACM SIGMOD International Conference on Management of data,**Full Text:**false**Reviewed:****Description:**Our world today is generating huge amounts of graph data such as social networks, biological networks, and the semantic web. Many of these real-world graphs are edge-labeled graphs, i.e., each edge has a label that denotes the relationship between the two vertices connected by the edge. A fundamental research problem on these labeled graphs is how to handle the label-constraint reachability query: Can vertex u reach vertex v through a path whose edge labels are constrained by a set of labels? In this work, we introduce a novel tree-based index framework which utilizes the directed maximal weighted spanning tree algorithm and sampling techniques to maximally compress the generalized transitive closure for the labeled graphs. An extensive experimental evaluation on both real and synthetic datasets demonstrates the efficiency of our approach in answering label-constraint reachability queries.

Distance preserving graph simplification

- Ruan, Ning, Jin, Ruoming, Yan, Huang

**Authors:**Ruan, Ning , Jin, Ruoming , Yan, Huang**Date:**2011**Type:**Text , Conference paper**Relation:**ICDM '11 Proceedings of the 2011 IEEE 11th International Conference on Data Mining p. 1200-1205**Full Text:**false**Reviewed:**

Effective and efficient itemset pattern summarization: regression-based approaches

- Jin, Ruoming, Abu-ata, Muad, Xiang, Yang, Ruan, Ning

**Authors:**Jin, Ruoming , Abu-ata, Muad , Xiang, Yang , Ruan, Ning**Date:**2008**Type:**Text , Conference paper**Relation:**KDD '08 Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining**Full Text:**false**Reviewed:****Description:**In this paper, we propose a set of novel regression-based approaches to effectively and efficiently summarize frequent itemset patterns. Specifically, we show that the problem of minimizing the restoration error for a set of itemsets based on a probabilistic model corresponds to a non-linear regression problem. We show that under certain conditions, we can transform the non-linear regression problem to a linear regression problem. We propose two new methods, k-regression and tree-regression, to partition the entire collection of frequent itemsets in order to minimize the restoration error. The K-regression approach, employing a K-means type clustering method, guarantees that the total restoration error achieves a local minimum. The treeregression approach employs a decision-tree type of top-down partition process. In addition, we discuss alternatives to estimate the frequency for the collection of itemsets being covered by the k representative itemsets. The experimental evaluation on both real and synthetic datasets demonstrates that our approaches significantly improve the summarization performance in terms of both accuracy (restoration error), and computational cost.

Efficiently answering reachability queries on very large directed graphs

- Jin, Ruoming, Xiang, Yang, Ruan, Ning, Wang, Haixun

**Authors:**Jin, Ruoming , Xiang, Yang , Ruan, Ning , Wang, Haixun**Date:**2008**Type:**Text , Conference paper**Relation:**SIGMOD '08 Proceedings of the 2008 ACM SIGMOD international conference on Management of data, p. 595-608**Full Text:**false**Reviewed:****Description:**Efficiently processing queries against very large graphs is an important research topic largely driven by emerging real world applications, as diverse as XML databases, GIS, web mining, social network analysis, ontologies, and bioinformatics. In particular, graph reachability has attracted a lot of research attention as reachability queries are not only common on graph databases, but they also serve as fundamental operations for many other graph queries. The main idea behind answering reachability queries in graphs is to build indices based on reachability labels. Essentially, each vertex in the graph is assigned with certain labels such that the reachability between any two vertices can be determined by their labels. Several approaches have been proposed for building these reachability labels; among them are interval labeling (tree cover) and 2-hop labeling. However, due to the large number of vertices in many real world graphs (some graphs can easily contain millions of vertices), the computational cost and (index) size of the labels using existing methods would prove too expensive to be practical. In this paper, we introduce a novel graph structure, referred to as path-tree, to help labeling very large graphs. The path-tree cover is a spanning subgraph of G in a tree shape. We demonstrate both analytically and empirically the effectiveness of our new approaches.

Global optimal solutions to general sensor network localization problem

**Authors:**Ruan, Ning , Gao, David**Date:**2014**Type:**Text , Journal article**Relation:**Performance Evaluation Vol. 75-76, no. (2014), p. 1-16**Full Text:**false**Reviewed:****Description:**Sensor network localization problem is to determine the position of the sensor nodes in a network given pairwise distance measurements. Such problem can be formulated as a quartic polynomial minimization via the least squares method. This paper presents a canonical duality theory for solving this challenging problem. It is shown that the nonconvex minimization problem can be reformulated as a concave maximization dual problem over a convex set in a symmetrical matrix space, and hence can be solved efficiently by combining a general (linear or quadratic) perturbation technique with existing optimization techniques. Applications are illustrated by solving some relatively large-scale problems. Our results show that the general sensor network localization problem is not NP-hard unless its canonical dual problem has no solution in its positive definite domain. Fundamental ideas for solving general NP-hard problems are discussed. (C) 2014 Elsevier B.V. All rights reserved.

Global optimal solutions to nonconvex euclidean distance geometry problems

**Authors:**Ruan, Ning , Gao, David**Date:**2012**Type:**Text , Conference paper**Relation:**20th International Symposium on Mathematical Theory of Networks and Systems**Full Text:**false**Reviewed:****Description:**This paper presents a canonical dual approach for solving nonconvex minimization problems in Euclidean distance geometry. The variant of this problem arises extensively in engineering and science, including computational biology, sensor network communications, database analysis, information technology, and global optimization. Due to the nonconvexity, most of these problems are NP-hard and traditional convex optimization methods can not be used directly for finding global optimal solutions. We first show that this type of nonconvex problems can be transferred to a concave maximization problem over a convex set. Then a general analytical solution is proposed by using the canonical duality theory. Applications are illustrated by network localization and minimization of Rosenbrock function. Furthermore, by using a perturbed canonical dual approach, a class of Euclidean distance problems can be converted to a unified concave maximization dual problem with zero duality gap, which can be solved by well-developed convex minimization methods.

Global solutions to fractional programming problem with ratio of nonconvex functions

**Authors:**Ruan, Ning , Gao, David**Date:**2015**Type:**Text , Journal article**Relation:**Applied Mathematics and Computation Vol. 255, no. (2015), p. 66-72**Full Text:**false**Reviewed:****Description:**This paper presents a canonical dual approach for minimizing a sum of quadratic function and a ratio of nonconvex functions in Rn. By introducing a parameter, the problem is first equivalently reformed as a nonconvex polynomial minimization with elliptic constraint. It is proved that under certain conditions, the canonical dual is a concave maximization problem in R2 that exhibits no duality gap. Therefore, the global optimal solution of the primal problem can be obtained by solving the canonical dual problem. © 2014 Elsevier Inc. All rights reserved.

Are you sure you would like to clear your session, including search history and login status?