Your selections:

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

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:**

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

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.

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.

Solutions to quadratic minimization problems with box and integer constraints

**Authors:**Gao, David , Ruan, Ning**Date:**2010**Type:**Text , Journal article**Relation:**Journal of Global Optimization Vol. 47, no. 3 (2010), p. 463-484**Full Text:**false**Reviewed:**

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.

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.

SCARAB: scaling reachability computation on large graphs

- Jin, Ruoming, Ruan, Ning, Dey, Saikat, Xu, Jeffrey Yu

**Authors:**Jin, Ruoming , Ruan, Ning , Dey, Saikat , Xu, Jeffrey Yu**Date:**2012**Type:**Text , Conference paper**Relation:**ACM SIGMOD International Conference on Management of Data, 2012 p. 169-180**Full Text:**false**Reviewed:****Description:**Most of the existing reachability indices perform well on small- to medium- size graphs, but reach a scalability bottleneck around one million vertices/edges. As graphs become increasingly large, scalability is quickly becoming the major research challenge for the reachability computation today. Can we construct indices which scale to graphs with tens of millions of vertices and edges? Can the existing reachability indices which perform well on moderate-size graphs be scaled to very large graphs? In this paper, we propose SCARAB (standing for SCAlable ReachABility), a unified reachability computation framework: it not only can scale the existing state-of-the-art reachability indices, which otherwise could only be constructed and work on moderate size graphs, but also can help speed up the online query answering approaches. Our experimental results demonstrate that SCARAB can perform on graphs with millions of vertices/edges and is also much faster then GRAIL, the state-of-the-art scalability index approach.

**Authors:**Ruan, Ning , Gao, David**Date:**2014**Type:**Text , Conference paper**Relation:**Proceedings of the 11th World Congress on Computational Mechanics (WCCM XI) p. 1-2**Full Text:**false**Reviewed:**

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.

Path-tree: An efficient reachability indexing scheme for large directed graphs

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

**Authors:**Jin, Ruoming , Ruan, Ning , Xiang, Yang , Wang, Haixun**Date:**2011**Type:**Text , Journal article**Relation:**ACM Transactions on Database Systems Vol. 36, no. 1 (2011), p.**Full Text:**false**Reviewed:**

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.

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.

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.

On modeling and complete solutions to general fixpoint problems in multi-scale systems with applications

**Authors:**Ruan, Ning , Gao, David**Date:**2018**Type:**Text , Journal article**Relation:**Fixed Point Theory and Applications Vol. 2018, no. 1 (2018), p. 1-19**Full Text:****Reviewed:****Description:**This paper revisits the well-studied fixed point problem from a unified viewpoint of mathematical modeling and canonical duality theory, i.e., the general fixed point problem is first reformulated as a nonconvex optimization problem, its well-posedness is discussed based on the objectivity principle in continuum physics; then the canonical duality theory is applied for solving this challenging problem to obtain not only all fixed points, but also their stability properties. Applications are illustrated by problems governed by nonconvex polynomial, exponential, and logarithmic operators. This paper shows that within the framework of the canonical duality theory, there is no difference between the fixed point problems and nonconvex analysis/optimization in multidisciplinary studies.

**Authors:**Ruan, Ning , Gao, David**Date:**2018**Type:**Text , Journal article**Relation:**Fixed Point Theory and Applications Vol. 2018, no. 1 (2018), p. 1-19**Full Text:****Reviewed:****Description:**This paper revisits the well-studied fixed point problem from a unified viewpoint of mathematical modeling and canonical duality theory, i.e., the general fixed point problem is first reformulated as a nonconvex optimization problem, its well-posedness is discussed based on the objectivity principle in continuum physics; then the canonical duality theory is applied for solving this challenging problem to obtain not only all fixed points, but also their stability properties. Applications are illustrated by problems governed by nonconvex polynomial, exponential, and logarithmic operators. This paper shows that within the framework of the canonical duality theory, there is no difference between the fixed point problems and nonconvex analysis/optimization in multidisciplinary studies.

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.

- 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 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

Solving facility location problem based on duality approach

**Authors:**Ruan, Ning**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. 165-172**Full Text:**false**Reviewed:****Description:**The facility location problem is one of the most widely studied discrete location problems, whose applications arise in a variety of settings, such as routers or servers in a communication network, warehouses or distribution centres in a supply chain, hospitals or airports in a public service system. The problem involves locating a number of facilities to minimize the sum of the fixed setup costs and the variable costs of serving the market demand from these facilities. First a dual problem is developed for the facility location problem. Then general optimality conditions are also obtained, which generate sequences globally converging to a primal and dual solutions, respectively. © Springer International Publishing Switzerland 2015.

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.

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