Seminars for Spring 2013
5/2/13 RUTCOR BrownBag - 12:00 Noon
Speaker: Mike Tortorella
Affiliation: Rutgers University
Title: Flows in Networks with Unreliable Elements
Abstract: In a flow network, when one or more network elements (switching nodes, transport systems) fails, congestion in the network can increase because some resources that were intended to be available to serve traffic have been removed from service. This talk describes a framework for solving problems related to this phenomenon and presents some preliminary results.
4/25/13 RUTCOR Colloquium - 1:30 PM
Speaker: Aida Khajavirad
Affiliation: IBM TJ Watson Research Center
Title: Covexification techniques for global optimization of nonconvex nonlinear optimization problems
Abstract:Several general-purpose deterministic global optimization algorithms have been developed for nonconvex nonlinear optimization problems over the past two decades. Central to the efficiency of such methods is their ability to construct sharp convex relaxations. Current global solvers rely on factorable programming techniques to iteratively decompose nonconvex factorable functions, until each intermediate expression can be outer-approximated by a convex feasible set. While it is easy to automate, this factorable programming technique often leads to weak relaxations.
In this talk, I present a number of new techniques for convexification of nonconvex NLPs. Namely, I (i) discuss the theory of convex envelopes and present closed-form expressions for the envelopes of various types of functions that are the building blocks of nonconvex problems and, (ii) introduce a new method to outer-approximate convex-transformable functions, an important class of generalized convex functions that subsumes many functional forms that frequently appear in nonconvex problems. In the second part of the talk, I will focus on computational implications of the proposed cutting planes. I will start by giving a brief overview of the global solver BARON and, subsequently present several new developments along with extensive numerical results on a number of standard test libraries.
4/04/13 RUTCOR Colloquium - 1:30 PM
Speaker: Amir Ali Ahmadi
Affiliation: Goldstine Fellow at IBM Watson Research Center, NY
Title: The Interplay of Convexity and Algorithmic Algebra
in Optimization and Systems Analysis
Abstract: Exciting recent developments at the interface of computational algebra and convex optimization have led to major algorithmic advances in a broad range of problems in optimization and systems theory. I will start this talk by giving an overview of these techniques and presenting applications in continuous and combinatorial optimization, statistics, and control theory. I will then focus on two recent results on computational and algebraic aspects of convexity in optimization: (i) I will show that deciding convexity of polynomials of degree as low as four is strongly NP-hard. This solves a problem that appeared as one of seven open problems in complexity theory for numerical optimization in 1992. (ii) I will introduce an algebraic, semidefinite programming (SDP) based sufficient condition for convexity known as sum-of-squares-convexity and present a complete characterization of the cases where it is equivalent to convexity. This characterization draws an interesting parallel to a seminal 1888 result of Hilbert in real algebraic geometry.
In the final part of the talk, I will move on to a problem with numerous applications in engineering and sciences: understanding the asymptotic behavior of linear dynamical systems under uncertainty. I will tackle this problem with a novel class of SDP-based algorithms (with provable guarantees) that are based on new connections between ideas from control theory and the theory of finite automata.
2/21/13 RUTCOR Colloquium - 1:30 PM
Speaker: Sergei Schreider
Affiliation: Royal Melbourne Institute of Technology, Australia
Title: Optimal allocations of resources for network systems: water and gas supply case studies
Abstract: Two optimization formulations were considered: one related to the water allocation another one to the gas supply systems. Their common feature is that the major constraints were related to the resource delivery capacities of the system carriers: channels and pipelines, respectively. Both formulations were considered as a single LP and multiple objective problems solved using compromised programming. The results were used for practical managerial decision making associated with infrastructural development of watersheds and further upgrading of gas supply systems anticipating the demand growth.
2/19/13 RUTCOR Colloquium - 2:00 PM (Please note time)
Speaker: Alexander Kelmans
Affiliation: University of Puerto Rico
Title: MORE ON GRAPH PLANARITY AND RELATED TOPICS
Abstract: We will discuss different possibilities to strengthen various classical results on graph planarity. In particular, we will present some strengthenings of the classical Kuratowski planarity criterion and Whitney planarity criterion, as well as the Kelmans planarity criterion. We will also describe some extensions of the Whitney circuit-isomorphism theorem on graphs for circuits of different type.
1/31/13 RUTCOR Colloquium - 1:30 PM
Speaker: Martin Milanic
Affiliation: University of Primorska, Koper, Slovenia
Title: On the identifiable subgraph problem
Abstract: A bipartite graph G=(L,R;E) with at least one edge is said to be identifiable if for every vertex v in L, the subgraph of G induced by its non-neighbors has a matching of cardinality |L|-1. This definition arises in the context of low-rank matrix factorization and is motivated by signal processing applications. The IDENTIFIABLE SUBGRAPH PROBLEM is the problem of determining whether a given bipartite graph G contains an identifiable L-subgraph, that is, an identifiable induced subgraph of G obtained by deleting from it some vertices in L together with all their neighbors. While the problem of finding a smallest subset J of L that induces an identifiable L-subgraph of G is APX-hard, the complexity of the identifiable subgraph problem is still open.
In this talk, we will focus on the problem from the point of view of parameterizing it according to the maximum degree of the vertices in R. It turns out that the case in which the maximum degree of vertices in R is at most 3 is as hard as the problem in general. On the other hand, we show that the problem becomes solvable in linear time if the maximum degree of vertices in R is at most 2. Our proof is based on the notion of a strongly cyclic graph, that is, a multigraph with at least one edge such that for every vertex v, no connected component of the graph obtained by deleting v is a tree. We show that a given bipartite graph is a no instance to the problem if and only if a multigraph naturally associated to it does not contain any strongly cyclic subgraph, and characterize such multigraphs in terms of finitely many minimal forbidden topological minors.
1/10/13 RUTCOR Colloquium - 1:30 PM
Speaker: Kei Kimura
Affiliation: University of Tokyo
Title: A Complexity Index of Integer Linear Systems Based on Their Sign Patterns
Abstract: In this paper, we consider solving the integer linear systems, i.e., given an m by n real matrix A, an m-dimensional real vector b, and a positive integer d, to compute an integer vector x in {0,1, ...,d-1}^n such that Ax \geq b, where m and n denote positive integers. The problem is one of the most fundamental NP-hard problems in computer science.
Based on the sign pattern of A, we propose a complexity index h
of the problem, which is a generalization of the one of satisfiability
problem proposed by Boros et al. (1994).
For a real r, let ILS(r) denote the family of the problem instances P
with h(P)=r.
We then show the following trichotomy:
. ILS(r) is linearly solvable, if r < 1,
. ILS(r) is weakly NP-hard and pseudo-polynomially solvable,
if r = 1,
. ILS(r) is strongly NP-hard, if r > 1.
This, for example, includes the existing results that quadratic systems and Horn systems can be solved in pseudo-polynomial time.
This is a joint work with Kaz Makino from Univ. Tokyo.