- Award ID(s):
- 1818948
- PAR ID:
- 10322737
- Date Published:
- Journal Name:
- ESAIM: Control, Optimisation and Calculus of Variations
- Volume:
- 28
- ISSN:
- 1292-8119
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
The problem of minimizing the rank of a symmetric positive semidefinite matrix subject to constraints can be cast equivalently as a semidefinite program with complementarity constraints (SDCMPCC). The formulation requires two positive semidefinite matrices to be complementary. This is a continuous and nonconvex reformulation of the rank minimization problem. We investigate calmness of locally optimal solutions to the SDCMPCC formulation and hence show that any locally optimal solution is a KKT point. We develop a penalty formulation of the problem. We present calmness results for locally optimal solutions to the penalty formulation. We also develop a proximal alternating linearized minimization (PALM) scheme for the penalty formulation, and investigate the incorporation of a momentum term into the algorithm. Computational results are presented.more » « less
-
null (Ed.)The connectivity of networks has been widely studied in many high-impact applications, ranging from immunization, critical infrastructure analysis, social network mining, to bioinformatic system studies. Regardless of the end application domains, connectivity minimization has always been a fundamental task to effectively control the functioning of the underlying system. The combinatorial nature of the connectivity minimization problem imposes an exponential computational complexity to find the optimal solution, which is intractable in large systems. To tackle the computational barrier, greedy algorithm is extensively used to ensure a near-optimal solution by exploiting the diminishing returns property of the problem. Despite the empirical success, the theoretical and algorithmic challenges of the problems still remain wide open. On the theoretical side, the intrinsic hardness and the approximability of the general connectivity minimization problem are still unknown except for a few special cases. On the algorithmic side, existing algorithms are hard to balance between the optimization quality and computational efficiency. In this article, we address the two challenges by (1) proving that the general connectivity minimization problem is NP-hard and is the best approximation ratio for any polynomial algorithms, and (2) proposing the algorithm CONTAIN and its variant CONTAIN + that can well balance optimization effectiveness and computational efficiency for eigen-function based connectivity minimization problems in large networks.more » « less
-
The
p ‐dispersion problem is a spatial optimization problem that aims to maximize the minimum separation distance among all assigned nodes. This problem is characterized by an innate spatial structure based on distance attributes. This research proposes a novel approach, named thedistance‐based spatially informed property (D‐SIP) method to reduce the problem size of thep ‐dispersion instances, facilitating a more efficient solution while maintaining optimality in nearly all cases. The D‐SIP is derived from investigating the underlying spatial characteristics from the behaviors of thep ‐dispersion problem in determining the optimal location of nodes. To define the D‐SIP, this research applies Ripley'sK ‐function to the different types of point patterns, given that the optimal solutions of thep ‐dispersion problem are strongly associated with the spatial proximity among points discovered by Ripley'sK ‐function. The results demonstrate that the D‐SIP identifies collective dominances of optimal solutions, leading to buildingthe spatially informed p‐dispersion model . The simulation‐based experiments show that the proposed method significantly diminishes the size of problems, improves computational performance, and secures optimal solutions for 99.9% of instances (999 out of 1,000 instances) under diverse conditions. -
Abstract The classic double bubble theorem says that the least-perimeter way to enclose and separate two prescribed volumes in ℝ N is the standard double bubble. We seek the optimal double bubble in ℝ N with density, which we assume to be strictly log-convex. For N = 1 we show that the solution is sometimes two contiguous intervals and sometimes three contiguous intervals. In higher dimensions we think that the solution is sometimes a standard double bubble and sometimes concentric spheres (e.g. for one volume small and the other large).more » « less
-
Abstract We establish an equivalence between a family of adversarial training problems for non-parametric binary classification and a family of regularized risk minimization problems where the regularizer is a nonlocal perimeter functional. The resulting regularized risk minimization problems admit exact convex relaxations of the type $L^1+\text{(nonlocal)}\operatorname{TV}$, a form frequently studied in image analysis and graph-based learning. A rich geometric structure is revealed by this reformulation which in turn allows us to establish a series of properties of optimal solutions of the original problem, including the existence of minimal and maximal solutions (interpreted in a suitable sense) and the existence of regular solutions (also interpreted in a suitable sense). In addition, we highlight how the connection between adversarial training and perimeter minimization problems provides a novel, directly interpretable, statistical motivation for a family of regularized risk minimization problems involving perimeter/total variation. The majority of our theoretical results are independent of the distance used to define adversarial attacks.