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

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.

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.

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.

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.

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.

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

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