The Proximal Average: Basic Theory
The recently introduced proximal average of
two convex functions is a convex function with many useful properties.
In this talk, we present the basic properties of the
proximal average with respect to the standard convex-analytical notions
(domain, Fenchel conjugate, subdifferential, proximal
mapping, and others).
Based on joint work with Rafal Goebel (U Washington),
Yves Lucet (UBC Okanagan) and Xianfu Wang (UBC Okanagan).
A Progressive Barrier Approach to Derivative-Free Nonlinear Programming
This is ongoing work towards our goal of providing effective algorithms for derivative-free blackbox nonlinear programming. The class of problems we target are evaluated by calling
"blackbox" computer codes. Often, some constraints are much cheaper to evaluate than others.
And evaluating the objective function generally requires evaluating all the constraints. Indeed,
some of the constraints only return "yes" if they are satisfied and "no" if they are not., and some
constraints must be satisfied or the objective function and other constraints cannot be evaluated.
There are even so-called "hidden constraints", which show up unexpectedly as the solution process proceeds by failing to return a value for the objective function or constraints.
Our mesh adaptive direct search (MADS) algorithm has a satisfying convergence analysis for
locally Lipschitz functions, and it is effective for these problems when an initial feasible point is
known, but for many problems, finding a feasible point is difficult.
In this talk, I will introduce our "progressive barrier" modification of MADS. The progressive barrier idea is related to the Flethcher/Leyffler filter approach. I will give some preliminary theoretical and
numerical results that show promise for this MADS-PB algorithm, but we have results so far for
only one real engineering problem, so it is too soon to tell.
Joint work with Charles Audet (Ecole Polytechnique de Montreal).
Six Degrees of Separation - from Paul Erdos and Kevin Bacon to Navigable Networks and Decentralized Search: A Markov Chain Approach
Many of us who have never met or seen Paul Erdos have a very small Erdos number, typically 2 or 3. Several actors who have never appeared in a Hollywood movie with Kevin Bacon have a small Bacon number, again, 2 or 3. Indeed, even though the world's population is about 6 billion, we are often connected to apparent strangers by a short chain of intermediate acquaintances, often 6. What is it about social networks that they have Six Degrees of Separation? Stanley Milgram's social experiments suggest that people are able to find these short chains by using only local information. What kind of networks are navigable by decentralized search? Mathematicians, computer scientists, and physicists have energetically studied such questions in the last decade and proposed navigable probabilistic network models. Along these lines, we develop a new family of Small World network models using a well-known Markov chain technique called Hit-and-Run. We show that there is a unique model within this family that admits efficient decentralized search.
Local strong convexity and local Lipschitz continuity of the gradient of a convex function
It is known that a convex function is (essentially) differentiable if
and only if its conjugate function is (essentially) strictly convex.
Similarly, a convex function has a globally Lipschitz continuous
gradient if and only if the conjugate function is strongly convex. The talk will present a
property of the conjugate function that
is dual to local Lipschitz continuity of the gradient of a convex
function.
Based on joint work with Terry Rockafellar.
Bundle Methods for Nonconvex Optimization
The Classical Bundle Methods (such as cutting planes methods and proximal bundle methods) have
shown success in dealing with black-box optimization problems in the convex setting. This has prompted
researched into how to extend the convex variants into methods which can deal with at least some nonconvex
problems. In this talk we review some old approaches and suggest one new approach which has shown some
promise in numerical testing.
(based on joint work with C. Sagastizabal)
Cross-Directional Response Modelling in Paper Machines
Industrial paper-making machines can produce a sheet of paper 10 metres wide at a speed comparable to highway driving. The control systems that monitor and adjust such paper characteristics as thickness and moisture content are essential to the machine's operation, and even small improvements have big payoffs. I will sketch the industrial context and outline some recent work with Bhushan Gopaluni (UBC Chemical and Biological Engineering) on one of the many parameter estimation problems arising in this area.
Primal-dual first-order methods for cone programming
In this talk, we consider the general linear cone programming problem, and propose primal-dual convex (smooth and/or nonsmooth) minimization reformulations for it. We then discuss a class of first-order methods suitable for solving these reformulations including Nesterov's optimal method, Nesterov's smooth approximation scheme and Nemirovski's prox-method, and propose a variant of Nesterov's optimal method which has outperformed the latter one in our computational experiments. We also derive iteration-complexity bounds for these first-order methods applied to the proposed primal-dual reformulations of the general linear cone programming problem. We also propose another class of first-order methods, namely, limit-memory quasi-Newton line search methods for solving the general linear cone programming problem. Computational performance of all of these methods on a set of randomly generated linear programming and/or semidefinite programming (SDP) instances are presented.
Primal-dual symmetric anti-derivatives
The finite convex integration problem consists of building a convex function from a finite sample of subgradients. After recalling previous work on finite convex integration, we will present new results from monotone operator theory that unify the Fitzpatrick and Rockafellar functions, and allow us to define primal-dual symmetric antiderivatives using the proximal average. Several examples will illustrate the numerical aspects, and recent computer-aided convex analysis advances that greatly helped in conjecturing the results will be mentioned.
Differential Variational Inequalities: An elementary introduction
This talk is an elementary introduction to the subject of
differential variational inequalities (DVIs), which is a new paradigm at
the interface of mathematical programming and dynamical systems that
combines three important characteristics: dynamics, inequalities, and
disjunctions. Thus a DVI can be used to model a wide variety of
evolutionary systems (dynamics) subject to unilateral constraints
(inequalities) and undergoing mode switches (disjunctions).
Mathematically, a DVI is defined by an ordinary differential equation
(ODE) parameterized by an algebraic variable that is required to be a
solution to an optimization problem, a complementarity problem, or a
variational inequality that in turn depends on the state of the ODE.
Properly specialized, a DVI includes as special cases a differential
algebraic equation (DAE), a switched (multi-modal) system, and certain
kinds of ODEs with discontinuous right-hand sides. Most importantly,
DVIs arise from many applied contexts, such as contact problems in
mechanical engineering, genetic regulatory networks in biological
systems, dynamic traffic equilibrium problems, and differential Nash
games. In the talk, we will begin with a very simple bimodal system,
highlight some of the
challenges of such a system, extend the system to a DVI, discuss some
selected issues, and conclude with a highly complex frictional contact
problem formulated as an ODE with a semismooth right-hand side. The
latter formulation requires advanced sensitivity analysis of variational
inequalities and a semismooth implicit function theorem. Much
is known about a DVI and yet even more open issues remain to be explored.
This talk reports joint work with Kanat Camlibel (Eindhoven), Lanshan Han
(RPI), Jinglai Shen (UMBC), and David Stewart (Iowa).
Generalized Linear Regression and its Motivations
A framework will be described in which linear regression, as a way of approximating a random variable by other random variables, can be carried out in a variety of ways, which moreover can be tuned to the needs of a particular model in finance or operations research. Axiomatic concepts of error measure, deviation measure and risk measure are coordinated with certain ``statistics'' that likewise say something about a random variable. Problems of regression utilizing these concepts can be explored in a range of examples. These examples indicate how recent progress in the treatment of risk preferences can now be incorporated in the statistical methodology which underlies mathematical modeling in a stochastic environment.
Basis Pursuit Denoising and the Dantzig Selector
Many imaging and compressed sensing applications seek sparse
solutions to under-determined least-squares problems.
The Lasso and BPDN approaches of bounding the 1-norm of the
solution have led to several computational algorithms.
PDCO uses an interior method to handle general linear
constraints and bounds. Homotopy, LARS, and STOMP are
specialized active-set methods for handling the implicit
bounds. l1ls and GPSR are further recent entries in the
l1-regularized least-squares competition, both based on
bound-constrained optimization.
The Dantzig Selector of Candes and Tao is promising in its
production of sparse solutions using only linear programming
technology. Again, interior or active-set (simplex) methods
may be used. We compare the BPDN and DS approaches via
their dual problems and some numerical examples.
Joint work with Michael Friedlander (UBC).
The Hahn--Banach--Lagrange theorem
We discuss the Hahn--Banach--Lagrange theorem, a generalized form of the Hahn--Banach theorem. As applications, we derive various results on the existence of linear functionals in functional analysis, on the existence of Lagrange multipliers for convex optimization problems, with an explicit sharp lower bound on the norm of the solutions (multipliers), on finite families of convex functions (leading rapidly to a minimax theorem), on the existence of subgradients of convex functions, and on the Fenchel conjugate of a convex function. We give a complete proof of Rockafellar's version of the Fenchel duality theorem, and an explicit sharp lower bound for the norm of the solutions of the Fenchel duality theorem in terms of elementary geometric concepts.
A general primal-dual symmetric average
We provide a general primal-dual symmetric average for two convex functions. It covers many known averages like: arithmetic average, epi-graphical average, and infimal convolution. When applied to the Fitzpatrick function and the conjugate of Fitzpatrick function associated to a monotone operator, our average produces an auto-conjugate which can be used for explicitly finding the maximal monotone extension of the given monotone operator, which completely solves one of the open questions posed by Fitzpatrick. This is joint work with H. H. Bauschke.
Exploiting Symmetry in Graph Eigenvalue Optimization
Given a graph, we consider the problem of optimally assigning weights on the edges to minimize a function of the eigenvalues of the weighted Laplacian matrix. If the graph has a large symmetry group, we show how Exploiting symmetry can reduce both the number of variables and the size of matrices in the optimization problem. We describe two general approaches for symmetry exploitation based on orbit theory and block-diagonalization, respectively. These approaches enable numerical solution of large-scale instances, otherwise computationally infeasible to solve.