Search

The problem of community detection with two equal-sized communities is closely related to the minimum graph bisection problem over certain random graph models. In the stochastic block model distribution over networks with community structure, a well-known semidefinite programming (SDP) relaxation of the minimum bisection problem recovers the underlying communities whenever possible. Motivated by their superior scalability, we study the theoretical performance of linear programming (LP) relaxations of the minimum bisection problem for the same random models. We show that, unlike the SDP relaxation that undergoes a phase transition in the logarithmic average degree regime, the LP relaxation fails in recovering the planted bisection with high probability in this regime. We show that the LP relaxation instead exhibits a transition from recovery to nonrecovery in the linear average degree regime. Finally, we present nonrecovery conditions for graphs with average degree strictly between linear and logarithmic. Funding: A. Del Pia is partially funded by Office of Naval Research (ONR) [Grant N00014-19-1-2322]. D. Kunisky is supported by the ONR [Grant N00014-20-1-2335], a Simons Investigator Award to Daniel Spielman, and the National Science Foundation [Grants DMS-1712730 and DMS-1719545]. [ABSTRACT FROM AUTHOR]

We propose a deterministic approach for global optimization of nonconvex quasiseparable problems encountered frequently in engineering systems design. Our branch and bound-based optimization algorithm applies Lagrangian decomposition to (1) generate tight lower bounds by exploiting the structure of the problem and (2) enable parallel computing of subsystems and use of efficient dual methods. We apply the approach to two important product design applications: (1) product family optimization with a fixed-platform configuration and (2) single product design using an integrated marketing-engineering framework. Results show that Lagrangian bounds are much tighter than the factorable programming bounds implemented by the commercial global solver BARON, and the proposed lower bounding scheme shows encouraging robustness and scalability, enabling solution of some highly nonlinear problems that cause difficulty for existing solvers. The deterministic approach also provides lower bounds on the global optimum, eliminating uncertainty of solution quality inherent to popular applications of stochastic and local solvers. [DOI: 10.1115/1.3087559] Keywords: global optimization, decomposition, quasiseparable, nonconvex, MINLP, branch and bound, product family

A core challenge in product family optimization is to jointly determine (1) the optimal selection of components to be shared across product variants and (2) the optimal values for design variables that define those components. Each of these subtasks depends on the other; however; due to the combinatorial nature and high computational cost of the joint problem, prior methods have forgone optimality of the full problem by fixing the platform a priori, restricting the platform configuration to all-or-none component sharing, or optimizing the joint problem in multiple stages. In this paper, we address these restrictions by (1) introducing an extended metric to account for generalized commonality, (2) relaxing the metric' to the continuous space to enable gradient-based optimization, and (3) proposing a decomposed single-stage method for optimizing the joint problem. The approach is demonstrated on a family of ten bathroom scales. Results indicate that generalized commonality dramatically improves the quality of optimal solutions, and the decomposed single-stage approach offers substantial improvement in scalability and tractability of the joint problem, providing a practical tool for optimizing families consisting of many variants. [DOI: 10.1115/1.2918906]

We introduce the ratio-cut polytope defined as the convex hull of ratio-cut vectors corresponding to all partitions of n points in ℝm into at most K clusters. This polytope is closely related to the convex hull of the feasible region of a number of clustering problems such as K-means clustering and spectral clustering. We study the facial structure of the ratio-cut polytope and derive several types of facet-defining inequalities. We then consider the problem of K-means clustering and introduce a novel linear programming (LP) relaxation for it. Subsequently, we focus on the case of two clusters and derive sufficient condition under which the proposed LP relaxation recovers the underlying clusters exactly. Namely, we consider the stochastic ball model, a popular generative model for K-means clustering, and we show that if the separation distance between cluster centers satisfies Δ > 1 + √3, then the LP relaxation recovers the planted clusters with high probability. This is a major improvement over the only existing recovery guarantee for an LP relaxation of K-means clustering stating that recovery is possible with high probability if and only if Δ > 4. Our numerical experiments indicate that the proposed LP relaxation significantly outperforms a popular semidefinite programming relaxation in recovering the planted clusters. [ABSTRACT FROM AUTHOR]

We consider the multilinear polytope defined as the convex hull of the set of binary points z satisfying a collection of equations of the form ze =*** E, where E denotes a family of subsets of {1; : : :; n} of cardinality at least two. Such sets are of fundamental importance in many types of mixed-integer nonlinear optimization problems, such as 0 - 1 polynomial optimization. Utilizing an equivalent hypergraph representation, we study the facial structure of the multilinear polytope in conjunction with the acyclicity degree of the underlying hypergraph. We provide explicit characterizations of the multilinear polytopes corresponding to Berge-acylic and γ-acyclic hypergraphs. As the multilinear polytope for γ-acyclic hypergraphs may contain exponentially many facets in general, we present a strongly polynomial-time algorithm to solve the separation problem, implying polynomial solvability of the corresponding class of 0-1 polynomial optimization problems. As an important byproduct, we present a new class of cutting planes for constructing tighter polyhedral relaxations of mixed-integer nonlinear optimization problems with multilinear subexpressions. [ABSTRACT FROM AUTHOR]