skip to main content


Title: A rearrangement minimization problem corresponding to p -Laplacian equation
In this paper a rearrangement minimization problem corresponding to solutions of the p -Laplacian equation is considered. The solution of the minimization problem determines the optimal way of exerting external forces on a membrane in order to have a minimum displacement. Geometrical and topological properties of the optimizer is derived and the analytical solution of the problem is obtained for circular and annular membranes. Then, we find nearly optimal solutions which are shown to be good approximations to the minimizer for specific ranges of the parameter values in the optimization problem. A robust and efficient numerical algorithm is developed based upon rearrangement techniques to derive the solution of the minimization problem for domains with different geometries in ℝ 2 and ℝ 3 .  more » « less
Award ID(s):
1818948
NSF-PAR ID:
10322737
Author(s) / Creator(s):
;
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
  1. 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
  2. Abstract

    This paper studies several solution paths of sparse quadratic minimization problems as a function of the weighing parameter of the bi-objective of estimation loss versus solution sparsity. Three such paths are considered: the “$$\ell _0$$0-path” where the discontinuous$$\ell _0$$0-function provides the exact sparsity count; the “$$\ell _1$$1-path” where the$$\ell _1$$1-function provides a convex surrogate of sparsity count; and the “capped$$\ell _1$$1-path” where the nonconvex nondifferentiable capped$$\ell _1$$1-function aims to enhance the$$\ell _1$$1-approximation. Serving different purposes, each of these three formulations is different from each other, both analytically and computationally. Our results deepen the understanding of (old and new) properties of the associated paths, highlight the pros, cons, and tradeoffs of these sparse optimization models, and provide numerical evidence to support the practical superiority of the capped$$\ell _1$$1-path. Our study of the capped$$\ell _1$$1-path is interesting in its own right as the path pertains to computable directionally stationary (= strongly locally minimizing in this context, as opposed to globally optimal) solutions of a parametric nonconvex nondifferentiable optimization problem. Motivated by classical parametric quadratic programming theory and reinforced by modern statistical learning studies, both casting an exponential perspective in fully describing such solution paths, we also aim to address the question of whether some of them can be fully traced in strongly polynomial time in the problem dimensions. A major conclusion of this paper is that a path of directional stationary solutions of the capped$$\ell _1$$1-regularized problem offers interesting theoretical properties and practical compromise between the$$\ell _0$$0-path and the$$\ell _1$$1-path. Indeed, while the$$\ell _0$$0-path is computationally prohibitive and greatly handicapped by the repeated solution of mixed-integer nonlinear programs, the quality of$$\ell _1$$1-path, in terms of the two criteria—loss and sparsity—in the estimation objective, is inferior to the capped$$\ell _1$$1-path; the latter can be obtained efficiently by a combination of a parametric pivoting-like scheme supplemented by an algorithm that takes advantage of the Z-matrix structure of the loss function.

     
    more » « less
  3. Abstract

    In materials that undergo martensitic phase transformation, macroscopic loading often leads to the creation and/or rearrangement of elastic domains. This paper considers an example involving a single-crystal slab made from two martensite variants. When the slab is made to bend, the two variants form a characteristic microstructure that we like to call “twinning with variable volume fraction.” Two 1996 papers by Chopra et al. explored this example using bars made from InTl, providing considerable detail about the microstructures they observed. Here we offer an energy-minimization-based model that is motivated by their account. It uses geometrically linear elasticity, and treats the phase boundaries as sharp interfaces. For simplicity, rather than model the experimental forces and boundary conditions exactly, we consider certain Dirichlet or Neumann boundary conditions whose effect is to require bending. This leads to certain nonlinear (and nonconvex) variational problems that represent the minimization of elastic plus surface energy (and the work done by the load, in the case of a Neumann boundary condition). Our results identify how the minimum value of each variational problem scales with respect to the surface energy density. The results are established by proving upper and lower bounds that scale the same way. The upper bounds are ansatz-based, providing full details about some (nearly) optimal microstructures. The lower bounds are ansatz-free, so they explain why no other arrangement of the two phases could be significantly better.

     
    more » « less
  4. We consider the problem of political redistricting: given the locations of people in a geographical area (e.g. a US state), the goal is to decompose the area into subareas, called districts, so that the populations of the districts are as close as possible and the districts are ``compact'' and ``contiguous,'' to use the terms referred to in most US state constitutions and/or US Supreme Court rulings. We study a method that outputs a solution in which each district is the intersection of a convex polygon with the geographical area. The average number of sides per polygon is less than six. The polygons tend to be quite compact. Every two districts differ in population by at most one (so we call the solution balanced). In fact, the solution is a centroidal power diagram: each polygon has an associated center in ℝ³ such that * the projection of the center onto the plane z = 0 is the centroid of the locations of people assigned to the polygon, and * for each person assigned to that polygon, the polygon's center is closest among all centers. The polygons are convex because they are the intersections of 3D Voronoi cells with the plane. The solution is, in a well-defined sense, a locally optimal solution to the problem of choosing centers in the plane and choosing an assignment of people to those 2-d centers so as to minimize the sum of squared distances subject to the assignment being balanced. * A practical problem with this approach is that, in real-world redistricting, exact locations of people are unknown. Instead, the input consists of polygons (census blocks) and associated populations. A real redistricting must not split census blocks. We therefore propose a second phase that perturbs the solution slightly so it does not split census blocks. In our experiments, the second phase achieves this while preserving perfect population balance. The district polygons are no longer convex at the fine scale because their boundaries must follow the boundaries of census blocks, but at a coarse scale they preserve the shape of the original polygons. 
    more » « less
  5. Thep‐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.

     
    more » « less