University of British Columbia, Vancouver, August 13-15, 2009

Optimization and Approximation
Org: Michael Friedlander (UBC), Pedro González-Casanova (DGSCA: UNAM) and Luis Verde-Star (UAM-Iztapalapa)

HEINZ BAUSCHKE, University of British Columbia Okanagan
Chebyshev and Klee sets with respect to Bregman distances

A set is called Chebyshev if every point has a unique nearest point in it. It is well known that-in Euclidean space-a set is Chebyshev if and only if it is closed, convex and nonempty. The corresponding Hilbert space question remains a famous open problem. Most studies have focused on obtaining results in general Banach space, under additional assumptions on the Chebyshev set.

A related question-again open in Hilbert space-concerns Klee sets and farthest points, which turn out to be singletons in Euclidean space.

In this talk, I will survey recent results on Chebyshev and Klee sets that revisit these questions from a new perspective: rather than working with a distance induced by a Banach space norm, we consider the Bregman distance induced by a well-behaved convex function.

Based on joint works with Mason Mackelm (UBCO), Jason Sewell (UBCO), Shawn Wang (UBCO), Jane Ye (UVic), Xiaoming Yuan (Hong Kong Baptist University).

MICHAEL FRIEDLANDER, University of British Columbia, Vancouver, BC
Spot: A linear-operator toolbox for Matlab

Linear operators are at the core of many of the most basic algorithms for signal and image processing. Matlab's high-level, matrix-based language allows us to express naturally many of the underlying matrix operations-e.g., computation of matrix-vector products and manipulation of matrices-and is thus a powerful platform on which to develop concrete implementations of these algorithms. Many of the most useful operators, however, do not lend themselves to the explicit matrix representations that Matlab provides. This talk describes the new Spot Toolbox, which aims to bring the expressiveness of Matlab's built-in matrix notation to problems for which explicit matrices are not practical. I will demonstrate features of the toolbox with examples from compressed sensing and image reconstruction.

This is joint work with Ewout van den Berg.

PEDRO GONZÁLEZ-CASANOVA, Universidad Nacional Autonoma de Mexico
Vector field approximation using radial basis functions

Approximation of vector fields from a set of scattered vector data by radial basis functions interpolation methods, have a wide applicability to different fields, like meteorology, fluid mechanics and elasticity. Within the last years, several authors have formulated and analyzed different RBFs interpolation techniques to solve this kind of problems. A major limitation, from the applied point of view, is that these meshfree interpolants have been built by minimizing some particular energy functional defined Rn. Thus in general, no boundary conditions can be incorporated into these numerical approximations. In this talk by using a rather different approach, based on a Lagrange multipliers technique, we present a solution to this problem within the context of RBFs methods. Numerical examples, based on multiquadric kernels, applied to atmospheric reconstruction fields will be presented.

Joint work with D. Cervantes and C. Gout.

SUSANA GÓMEZ, National University of Mexico, Mexico City
Modeling the Optimal Cleaning of Polluting Oil in the Open Sea

In this ongoing work, a model of the movement of oil spots in the open sea and the numerical methods to solve the resulting partial differential equations, implemented on a distributed parallel machine, are presented. The model includes the effect of a Pumping Ship, that aspires the polluting oil.

The ship will follow a global optimal trajectory, that maximizes the amount of pollutant pumped. The global optimization will be carried out using a fast evolutionary algorithm. Numerical results will be presented.

JOSÉ LUIS MARTÍNEZ-MORALES, Universidad Nacional Autonoma de Mexico, A.P. 273, Admon. de correos #3 C.P. 62251 Cuernavaca, Mor., Mexico
Approximation by Penalized Least Squares

Consider a compact Riemannian manifold and a set of scattered points lying on it. In this talk we are interested in the following problem.

Problem: Given vectors x1, ..., xp, find a vector-valued function defined on the manifold which approximates the data

f(xi) » xi.

JAN MODERSITZKI, McMaster University
Numerical Methods for Total Variation in Image Processing

Starting with the outstanding paper of Rudin, Osher, and Fatemi from 1992, total variation has become a versatile and powerful tool in modern image processing. Despite its popularity, a numerical treatment of total variation is not straightforward and many publications address this problem from various perspectives.

This presentation aims to introduce to numerical schemes for total variation and ways to bypass difficulties arising from the none differentiability of total variation. To keep the focus clear and concrete, image denoising serves as a template problem. The starting point is the minimization of joined energy functional, composed from a simple L2-norm based data fitting term and a total variation based regularizer.

Moreover, the presentation summarizes, discusses, and relates popular approaches such as the naive primal, a dual approach of Vogel, the split Bregman method of Goldstein and Osher, and the augmented Lagrangian approach of Tai and Wu. As the starting point is a variational framework, emphasis is also given to alternative perspectives for a numerical treatment such as the optimize then discretize and discretize then optimize approaches.

DOMINIQUE P. ORBAN, GERAD and École Polytechnique, Montréal
An Interior-Penalty Method for Mathematical Programs with Vanishing Constraints

MPVCs are degenerate nonlinear programs that model topology and structural optimization problems. They resemble problems with complementarity constraints yet different sets of qualification conditions are used to formulate necessary optimality conditions. We extend a mixed interior/exterior elastic penalty method to MPVCs. Global and fast local convergence are established. We illustrate our algorithm on instances of structural problems.

MICHAEL L. OVERTON, Courant Institute, New York University, New York, NY
Nonsmooth Optimization via BFGS

The BFGS algorithm has long been recognized as one of the most useful algorithms for minimization of a smooth function f, convex or not. We investigate the behavior of the BFGS algorithm, both theoretically and experimentally, when it is applied to a nonsmooth function f, not necessarily convex.

Joint work with Adrian Lewis.

MICHAEL SAUNDERS, Stanford University, California
QPBLUR: An active-set convex QP solver based on regularized KKT systems

SNOPT obtains search directions from semidefinite QP subproblems, which are currently solved by SQOPT. For large problems with many degrees of freedom, the nullspace active-set method of SQOPT becomes inefficient.

QPBLUR is an alternative convex QP solver intended for use within SNOPT. It uses primal and dual regularization to ensure that the KKT system for any active set is nonsingular. A single-phase active-set method becomes possible. Warm starts can proceed from any given active set, and block-LU updates of the KKT factors as in QPBLU (Hanh Huynh's PhD dissertation, 2008) allow use of sparse-matrix packages such as LUSOL, MA57, PARDISO, SuperLU, or UMFPACK.

Joint work with Chris Maes, iCME, Stanford University.

LUIS VERDE-STAR, Universidad Autonoma Metropolitana, Mexico City
Computation of Hermite-Pade interpolants by iterated polynomial interpolation

Let I be an open interval and f : I ® R a sufficiently differentiable function such that f(x) ¹ 0 for x Î I. Suppose that u0,u1,u2, ... is a sequence of monic polynomials such that for k ³ 0 we have that uk divides uk+1 and has all its roots in I.

If g is a sufficiently differentiable function defined on I, we denote by H(g,uk) the polynomial of smallest degree that interpolates g at the multiset of roots of uk in the sense of Hermite.

We construct a sequence of polynomials p0,p1,p2,... defined as follows:

p0 = H(f,u0),     p1 = H(p0/f,u1),
for k even     pk = H(f pk-1,uk), and
for k odd     pk = H(pk-1/f, uk).
We show that for each even integer k the rational function pk/pk+1 is a Hermite-Padé interpolant for f at the multiset of roots of uk. We present some examples and numerical results. We also consider some particular choices for the sequence uk and indicate some possible modifications of our construction.

SHAWN WANG, University of British Columbia Okanagan, Kelowna, BC Canada
Resolvent Averages of Monotone Operators

Monotone operators play important roles in optimization and convex analysis. We define a new average of monotone operators by using resolvents. The new average enjoys self-duality. When the monotone operators are positive definite matrices, the new average lies between harmonic average and arithmetic average. Proximal average will also be discussed.

This is a joint work with Heinz Bauschke and Sarah Moffit.

JANE YE, Department of Mathematics and Statistics, University of Victoria
Optimizing condition numbers

In this talk we consider the problem of minimizing condition numbers over a compact convex subset of the cone of symmetric positive semi-definite n×n matrices. We show that the condition number is a Clarke regular strongly pseudoconvex function. We prove that a global solution of the problem can be approximated by an exact or an inexact solution of a nonsmooth convex program. This asymptotic analysis provides a valuable tool for designing an implementable algorithm for solving the problem of minimizing condition numbers.

YURIY ZINCHENKO, University of Calgary, MS446, 2500 University Drive NW, Calgary, Alberta, Canada, T2N 1N4
Shrink-wrapping trajectories for linear programming

Hyperbolic Programming (HP)-minimizing a linear functional over an affine subspace of a real vector space intersected with hyperbolicity cone-is a class of convex optimization problems that contains Linear Programming (LP). For any LP one can readily provide a sequence of HP relaxations. Based on the hyperbolic relaxations, a new Shrink-Wrapping approach to solve LP has been proposed by Renegar. We study the geometry of Shrink-Wrapping trajectories for LP, which generalize the notion of central path in IPM. In particular, we analyze the geometry of these trajectories in the proximity of the so-called central line, and contrast the behavior of these trajectories with that of the central path for some pathological LP instances.

Event Sponsors

Canadian Mathematical Society      Sociedad Matemática Mexicana      Pacific Institute for the Mathematical Sciences      Centre de recherches mathématiques Fields Institute MITACS

© Canadian Mathematical Society :