AMS Spring 2018 Western Sectional Meeting
Special Session on Nonsmooth Optimization and Applications
(Dedicated to Prof. B. S. Mordukhovich on the occasion of his 70th birthday)
Portland State University, Portland, OR
April 14-15, 2018 (Saturday - Sunday)
AMS Official Program Webpage
Organizers:
Mau Nam Nguyen, Portland State University
Hung M. Phan, University of Massachusetts Lowell
Shawn Xianfu Wang, University of British Columbia
(Supported by the Pacific Institute for the Mathematical Sciences (PIMS) and Portland State University)
Schedule and Abstracts
Saturday April 14, 2018, 8:00 a.m.-10:50 a.m.
Room 53, Cramer Hall
| 8:00 a.m. | Discrete approximations and optimal control of prox-regular sweeping processes. Boris Mordukhovich*, Wayne State University |
| This talk concerns optimal control problems for several versions of the controlled sweeping process governed by dissipative differential inclusions while the main attention is paid to brand new results concerning a nonconvex prox-regular version of the sweeping process and its applications. Such dynamic optimization problems constitute a new and challenging class in optimal control of discontinuous systems with intrinsic state constraints of inequality and equality types. We develop the method of discrete approximations for this class of optimal control problems and establish its strong convergence properties. Using advanced tools of variational analysis and generalized differentiation allows us to derive necessary optimality conditions for discrete-time problems and then pass to the limit with respect to the vanishing discretization step. In this way we derive nondegenerate necessary optimality conditions for the original sweeping control problems expressed in terms of given local minimizers and problem data. Some efficient applications of the obtained results to the planar crowd motion model are also discussed in the talk. (Received February 03, 2018) | |
| 8:30 a.m. | Variational analysis perspective on linear convergence of some first order methods for nonsmooth optimization problems. Jane J. Ye*, University of Victoria |
| In this work we try to understand linear convergence of some first-order methods such as the proximal gradient method and its variants for minimizing the sum of a smooth function and a nonsmooth function from a variational analysis perspective. We introduce a new analytic framework based on some theories on variational analysis such as the error bound/calmness/metric subregularity. This variational analysis perspective enables us to provide some concrete sufficient conditions for checking linear convergence. By using the new framework we are able to improve some existing results and obtain novel results unknown in the literature. (Received January 24, 2018) | |
| 9:00 a.m. |
Subgradient methods without convexity: error bounds, linear convergence, and statistical guarantees. Damek Davis, Cornell University Dmitriy Drusvyatskiy*, University of Washington Kellie J MacPhee, University of Washington Courtney Paquette, Lehigh University |
| Subgradient methods converge linearly on a convex function that grows sharply away from its solution set. In this talk, I will explain that the same is true for sharp functions that are only weakly convex, provided that the subgradient methods are initialized within a fixed tube around the solution set. A variety of statistical and signal processing tasks come equipped with good initialization, and provably lead to formulations that are both weakly convex and sharp. Therefore, in such settings, subgradient methods can serve as cheap local search procedures. I will illustrate the techniques on phase retrieval and covariance estimation problems. (Received February 05, 2018) | |
| 9:30 a.m. |
Applications of the generalized matrix-fractional function. Tim Hoheisel*, McGill University James V. Burke, University of Washington |
| The generalized matrix-fractional function (GMF) is (shown to be) a support function of the graph of the function mapping a matrix to the product with its transpose intersected with an affine manifold. It establishes connections between optimal value functions for quadratic optimization problems, covariance estimation, and the nuclear norm. We present a detailed study of the convex-analytical properties of the GMF, in particular, we give a full description of its subdifferential and characterize the points of differentiability. We will show that many powerful results on Ky-Fan norms and variational Gram functions arise from infimal projections of the sum of the GMF and a closed, proper, convex function. (Received October 17, 2017) | |
| 10:00 a.m. |
Calculus of the Simplex Gradient. Warren L Hare*, University of British Columbia Gabriel Jarry-Bolduc, University of British Columbia |
| Derivative-free optimization (DFO) is the mathematical study of the optimization algorithms that do not use derivatives. The Simplex Gradient, essentially the gradient of a linear interpolation approximation, is a common tool in DFO. Recent work by Regis extended the definition of the Simplex gradient to include a unified framework for under-determined and over-determined interpolation sets. Regis also introduced a sum-rule and product-rule for the simplex gradient of two functions. Unfortunately, the product-rule only works under a restrictive set of assumptions. In this talk, we review Regis’ framework, and product rule. We then provide an alternate product rule, which requires no unreasonable assumptions for application. We introduce a chain rule, and include several corollaries (such as a quotient rule). (Received January 31, 2018) | |
| 10:30 a.m. |
Variational analysis on the signed distance functions. Xianfu Wang*, University of British Columbia Okanagan Honglin Luo, Chongqing Normal University, PRC Lukens Brett, University of British Columbia Okanagan |
| The signed distance function (or oriented distance function) of a set in a metric space determines the distance of a given point from the boundary of the set, with the sign determined by whether the point is in the set or in its complement. The knowledge of signed distance functions is a very valuable information in various fields of applied mathematics such as collision detection, binary classification, shape analysis, fuzzy numbers ranking and level set methods. One distinguished feature of the signed distance function is that it reflects the geometric structure of the set much better than the distance function does. We explore many interesting analytical properties of signed distance functions, and use the signed distance function to construct convex functions with nonconvex subdifferential domains. (Received January 28, 2018) |
Saturday April 14, 2018, 3:00 p.m.-5:50 p.m.
Room 53, Cramer Hall
| 3:00 p.m. |
Analyticity, Spectral Analysis, and Uniform Stability of a Heat-viscoelastic Plate Interaction Models. Roberto Triggiani*, University of Memphis |
| Analyticity, Spectral Analysis, and Uniform Stability of a Heat-viscoelastic Plate Interaction Model We consider a heat equation defined on an interior bounded domain coupled with a visco-elastic plate defined on a surrounding external domain. Coupling occurs at the interface between the two domains, through high order coupling conditions between the two dynamics. The complicated boundary conditions of the plate are physical. We establish that the coupled system generates a strongly continuous contraction semi-group on the natural space of finite energy, which moreover is analytic and uniformly stable. A sharp spectral analysis is also provided. In particular, the the resolvent operator of generator fails to be compact. (Received January 21, 2018) | |
| 3:30 p.m. |
Second-Order Optimality Conditions for Singular Extremals in Optimal Control Problems with Equality Endpoint Constraints. Ilya Shvartsman*, Penn State Harrisburg |
| We use the method of finite-dimensional approximations to derive second-order necessary optimality conditions for singular Pontryagin local minimizers in optimal control problems with equality endpoint constraints. The talk is based on the joint work with A. Arutyunov and Z. Zhukovskaya. (Received January 16, 2018) | |
| 4:00 p.m. |
Boundary Feedback Control with Applications to High Intensity Focused Ultrasound (HIFU). Irena Lasiecka*, University of Memphis, |
| This talk will discuss boundary feedback control associated with PDE models arising in HIFU modles -which are PDE’s of third order i time. This leads to a notion of a non-standard Riccati equations which provide suitable gain operators for the feedback control. Singularity of the control action compromises the usual regularity of the associated Riccati operators-making the analysis challenging particularly in the case of boundary controls. In this latter case, the loss of regularity is “double” - due to singularity caused by the appearance if time derivatives in control function and also due to the intrinsic loss associated with unbounded and un-closeable trace operators. In order to construct viable theory one needs to develop suitable regularity theory within teh framework of non-smooth optimization. It will be shown how the propagation of hidden trace regularity in hyperbolic dynamics allows to build suitable concepts. (Received January 28, 2018) | |
| 4:30 p.m. |
Optimal control of a perturbed sweeping process. Giovanni Colombo, Universita di Padova Boris S. Mordukhovich, Wayne State University Dao Nguyen*, Wayne State University |
| This talk deals with an optimal control problem for a perturbed sweeping (Moreau) process, where control function is in additive perturbations on the right-hand side of the dissipative differential inclusion without changing the moving set and merely measurable without any Lipschitzian. It should be emphasized that the velocity mapping in the differential inclusions under consideration is highly non-Lipschitz, unbounded and the control is just measurable, which cannot be treated by means of known results in optimal control for differential inclusions. To overcome such principal issues, we develop the method of discrete approximations married with catching-up algorithm and combine it with appropriate generalized differential tools of modern variational analysis, which allows us to adequately replace the original optimal control problem by a sequence of well-posed finite-dimensional optimization problems whose optimal solutions strongly converge to that of the original controlled perturbed sweeping process. Then we use this direct method to obtain nondegenerate necessary optimality conditions for the so-called intermediate relaxed local minimum of the controlled sweeping process. Furthermore, the established necessary optimality conditions are illustrated by several examples. (Received February 06, 2018) | |
| 5:00 p.m. |
Optimizing the polynomial radius and abscissa subject to affine constraints. Julia Eaton*, University of Washington Tacoma Mert Gurbuzbalaban, Rutgers University Sara Grundel, Max Planck Institute for Dynamics of Complex Systems Michael Overton, Courant Institute of Mathematical Sciences |
| Polynomial root optimization problems arise in the control of continuous and discrete time dynamical systems. The polynomial abscissa (the largest real part of an root of a polynomial) and the polynomial radius (the largest root in modulus) are examples of functions of polynomial root functions connected to such problems. A polynomial is Schur stable if its roots lie in the unit disk and it is Hurwitz stable if its roots lie in the left-half plane. We consider optimizing the polynomial radius and abscissa subject to affine constraints on the coefficients. For the radius, we recover a 2012 result of root activity when there is only one constraint, and extend this result when there are multiple constraints. For the polynomial abscissa, we derive similar results when the optimal solution is attained. We derive information about the variational structure of set of Hurwitz stable polynomials in order to understand the case where the optimal value is not attained. (Received February 04, 2018) | |
| 5:30 p.m. |
Proximal Averages for Minimization of Entropy Functionals. Scott Boivin Lindstrom*, CARMA Priority Research Centre, University of Newcastle |
| We provide a basic overview of the convex analysis of the Lambert W function and go on to explore its role in duality theory where it appears quite naturally in the closed forms of the convex conjugates for important functions. We exploit these forms to solve minimization problems for entropy functionals. We then explore the analogous relevance of the Lambert W function for computing proximal averages, solving another set of entropy functionals and revealing several advantages of the homotopy afforded therein. This presentation includes work from collaborations with Jonathan M. Borwein and Heinz H. Bauschke. (Received December 04, 2017) |
Sunday April 15, 2018, 8:00 a.m.-10:50 a.m.
Room 53, Cramer Hall
| 8:00 a.m. |
Foundations of gauge and perspective duality. James V Burke*, Seattle, Washington Aleksandr Aravkin, University of Washington Dmitriy Drusvyatskiy, University of Washington Michael P Friedlender, University of British Columbia Kellie MacPhee, University of Washington |
| Common numerical methods for constrained convex optimization are predicated on efficiently computing nearest points to the feasible region. The presence of a design matrix in the constraints yields feasible regions with more complex geometries. When the functional components are gauges, there is an equivalent optimization problem-the gauge dual- where the matrix appears only in the objective function and the corresponding feasible region is easy to project onto. We discuss the foundations of gauge duality and show that the paradigm arises from an elementary perturbation perspective. This puts gauge and Fenchel-Rockafellar duality on an equal footing, explain gauge dual variables as sensitivity measures, and show how to recover primal solutions from those of the gauge dual. (Received February 04, 2018) | |
| 8:30 a.m. |
A linear-time algorithm to check the convexity of piecewise linear-quadratic functions. Yves Lucet*, University of British Columbia Heinz H Bauschke, University of British Columbia Hung M Phan, University of Massachusetts Lowell |
| Functions that are piecewise defined are a common sight in mathematics while convexity is a property especially desired in optimization. Suppose now a piecewise-defined function is convex on each of its defining components - when can we conclude that the entire function is convex? Our main result provides sufficient conditions for a piecewise-defined function f to be convex. We also provide a sufficient condition for checking the convexity of a piecewise linear-quadratic function, which play an important role in computer-aided convex analysis. Finally, we propose a finite algorithm running in linear worst-case time complexity to determine whether a bivariate piecewise linear-quadratic function is convex. (Received February 06, 2018) | |
| 9:00 a.m. |
Spectral Subgradient Method for Unconstrained Optimization. Milagros Loreto*, University of Washington Bothell Yiting Xu, University of Washington Bothell David Kotval, Middle Tennessee State University |
| The spectral subgradient method combines the classical subgradient approach with the spectral step length, which does not require any previous knowledge of the optimal value, to solve nonsmooth unconstrained minimization problems. We focus on the interesting case where the objective function is convex and continuously differentiable almost everywhere, but often non-differentiable at minimizers. We present numerical results on different sets of nonsmooth functions to compare our proposed method with other traditional subgradient methods, showing that using the spectral step length can improve the quality of the solution found (Received February 04, 2018) | |
| 9:30 a.m. |
On the sum of projectors onto convex sets. Heinz H. Bauschke, Mathematics, University of British Columbia, Kelowna, B.C. V1V 1V7, Canada Minh N. Bui*, Mathematics, University of British Columbia, Kelowna, B.C. V1V 1V7, Canada Xianfu Wang, Mathematics, University of British Columbia, Kelowna, B.C. V1V 1V7, Canada |
| The projectors onto the Minkowski sum of closed convex sets is generally not equal to the sum of individual projectors. In this talk, we provide a complete answer to the question of characterizing the instances where such an equality holds. Our results unify and extend the case of linear subspaces and Zarantonello’s results for projectors onto cones. We establish the partial sum property for projectors onto convex cones, and we also present various examples as well as a detailed analysis in the univariate case. This talk is based on a joint work with Heinz Bauschke and Xianfu Wang. (Received February 06, 2018) | |
| 10:00 a.m. |
On the generic nature of various classes of convex functions. Jon D Vanderwerff*, La Sierra University |
| This talk will examine whether certain classes of convex functions such as uniformly convex, or those attaining certain types of strong minimums are residual in the space of proper lower semicontinuous functions on a Banach space. The results are motivated by a recent paper of C. Planiden and X. Wang. (Received February 06, 2018) | |
| 10:30 a.m. |
Constrained clustering and multifacility location via distance function penalty methods and DC programming. Mau Nam Nguyen, Portland State University Sam Reynolds, Portland State University Tuyen Tran*, Portland State University |
| Cluster analysis tackles an emerging class of optimization problems that have numerous applications in data science, machine learning, and multifacility location problems, to name a few. In this talk we introduce a constrained model of multifacility location and use the distance function penalty method, Nesterov’s smoothing techniques and the DCA to provide an effective optimization scheme for solving the problem. In our problem, the centers to be found must lie in the intersection of some given set constraints. Different numerical examples with artificial and real data sets are provided to test our method. This talk is based on the joint work with Mau Nam Nguyen and Sam Reynolds. (Received February 03, 2018) |
Sunday April 15, 2018, 2:00 p.m.-4:50 p.m.
Room 53, Cramer Hall
| 2:00 p.m. |
A Semismooth Inverse Mapping Theorem for C1+ Functions under Tilt Stability. Ebrahim Sarabi*, Miami University |
| Taking into account an unconstrained optimization problem with a C1+ objective function, we present a semismooth inverse mapping theorem for its tilt-stable local minimizers. Then we introduce a Newton method via the notion of the graphical derivative and will discuss its superlinear convergence for tilt-stable local minimizers of this problem. The talk is based on a joint work with Boris Mordukhovich. (Received February 06, 2018) | |
| 2:30 p.m. |
Linear convergence of iterative soft thresholding and solution uniqueness to general Lasso in Hilbert spaces. Nghia T. A. Tran, Oakland University, Rochester, MI Ming Yan, Michigan State University Trinh Tran*, Oakland University, Rochester, MI |
| Iterative soft thresholding is a popular and effective method for solving Lasso problem. Local linear convergence of this method was obtained in many works with nontrivial assumptions on initial data. In this talk, we attempt to improve the result. Indeed, we prove the global linear convergence of this method without supposing any expensive condition on the problem. This is a good result since it helps undermine the conditions in the previous works. The approach also allows us to obtain new characterizations to the uniqueness of optimal solution to Lasso. (Received February 02, 2018) | |
| 3:00 p.m. |
On directional pseudo/quasi-normality and directional enhanced KKT conditions. Kuang Bai*, University of Victoria |
| In this paper we mainly study the metric subregularity of a set-valued map which is the sum of a single-valued Lipschitz continuous mapping and a closed subset. First we derive a sufficient condition for metric subregularity called quasi-first order sufficient condition for metric subregularity (FOSCMS) that is weaker than the FOSCMS recently introduced by Gfrerer. Then we introduce a directional version of the pseudo-normality and quasi-normality which is weaker than the classical pseudo-normality and quasi-normality respectively. The directional quasi-normality are stronger than the quasi-FOSCMS but easier to verify. An example is used to illustrate that the directional pseduo-normality can be weaker than both the FOSCMS and the quasi-normality. For the class of set-valued maps where the Lipschitz mapping is linear and the closed set is the union of finitely many convex polyhedral sets, we show that the directional pseudo-normality holds automatically at each point of the graph. Finally we apply our results to non-smooth optimization problems. Under directional pseudo/quasi-normality, we show that any local minimizer must satisfy the directional enhanced KKT condition which is a stronger optimality condition than the classical enhanced KKT condition. (Received February 05, 2018) | |
| 3:30 p.m. |
A nonsmooth program for jamming hard spheres. Peter Hinow*, University of Wisconsin - Milwaukee |
| We study packings of n hard spheres of equal radius in the d-dimensional unit cube. We present a nonsmooth function whose local extrema are the radii of jammed packings (where no subset of spheres can be moved keeping all others fixed) and show that for a fixed number of spheres there are only finitely many radii of such jammed configurations. We propose an algorithm for the maximization of this maximal radius function and present examples for 5 - 8 disks in the unit square and 4 - 6 spheres in the unit cube. The method allows straightforward generalization to packings of spheres in other compact containers. The origin of this research is a problem in pharmaceutical science on predicting the release kinetics of matrix tablets. This work has been partially supported by the US National Science Foundation through grant DMS 1016214. (Received December 29, 2017) | |
| 4:00 p.m. |
An Efficient Algorithm for Finding a 3-Dim Maximum Independent Set. Michael A Laidacker*, Lamar University, Beaumont, TX |
| The algorithm is of interest since it answers the associated NP-complete problem for any given Instance. The talk will describe the algorithm and some of its consequences. (It should be noted that the preliminary report has been read by several other faculty members with no report of errors.) (Received November 21, 2017) | |
| 4:30 p.m. |
On Mordukhovich's Criteria for Lipschitz Properties of Nonsmooth Functions and Set-Valued Mappings. Mau Nam Nguyen*, Portland State University |
| In this talk we revisit Mordukhovich’s subdifferential criterion for Lipschitz continuity of nonsmooth functions and coderivative criterion for the Aubin/Lipschitz-like property of set-valued mappings. The criteria are useful and beautiful results in modern variational analysis showing the state of the art of the field. We also present some applications of the criteria to obtain necessary and sufficient conditions for Lipschitz properties of a number of important class of nonsmooth functions and set-valued mappings. (Received February 05, 2018) |