Réunion d'hiver SMC 2010 Coast Plaza Hotel and Suites, Vancouver, 4 - 6 décembre 2010 www.smc.math.ca//Reunions/hiver10

Analyse convexe et non lisse
Org: Philip Loewen (UBC) et Yves Lucet (UBC-Okanagan)
[PDF]

HEINZ BAUSCHKE, UBC Okanagan
A Demiclosedness Principle and its Applications  [PDF]

Browder's Demiclosedness Principle is one of the building blocks of fixed point theory. In this talk, I will report on a new demiclosedness principle and its applications.

(Based on joint work with Patrick Combettes, Paris VI.)

JAMES V. BURKE, University of Washington
On the subdifferential regularity of max root functions for polynomials  [PDF]

In 2001, Burke and Overton showed that the abscissa mapping on polynomials is subdifferentially regular on the monic polynomials of degree $n$. In this talk I will discuss an extension of this result to the class of max polynomial root functions which includes both the polynomial abscissa and radius mappings. The approach to the computation of subgradient is somewhat simpler than that given by Burke and Overton and provides new insight into the variational properties of these functions.

This is joint work with Julia Eaton, University of Puget Sound.

MCLEAN EDWARDS, University of British Columbia
Relationships between classes of monotone operators  [PDF]

Among monotone operators, subdifferentials of convex functions are particularly well behaved. Generalizations are often defined by selecting a certain desirable property of subdifferentials. We consider the classes of monotone operators defined by five such properties: maximality, strict monotonicity, 3-cyclic monotonicity, 3*-monotonicity, and paramonotonicity. Surprisingly, only three general relationships (two of which are obvious) link these five classes. This talk is a report on a complete catalogue of theorems and examples addressing all possible combinations of these five properties. I will describe the relationships that hold in general, and illustrate some low dimensional and linear operators that explore the boundaries.

NASSIF GHOUSSOUB, University of British Columbia
Modern convexity methods in nonlinear PDEs  [PDF]

Convexity is making a comeback in PDE, Analysis, and geometry. I will try to show how.

YASIN GOCGUN, University of Washington
Approximate Dynamic Programming for Dynamic Stochastic Resource Allocation  [PDF]

Dynamic allocation of multiple renewable resources to different types of jobs arriving randomly over time is a class of scheduling problems that arise in many fields such as logistics, transportation, and healthcare. Due to stochasticity inherent in these problems, they are generally termed as Dynamic Stochastic Resource Allocation Problems (DSRAPs). In DSRAPs, the challenge faced by the decision-maker in each time-period is how to schedule jobs waiting in queue or which jobs to service for the current period so as to optimize a certain performance metric over a finite/infinite horizon, given resource constraints. These problems are naturally modeled as a Markov Decision Process (MDP), a mathematical framework used to model systems that evolve stochastically over time.

While different classes of DSRAPs have been studied over decades, there is no mathematical technique to solve realistic instances of these problems mainly due to their combinatorial nature. As such, researchers resort to approximation techniques such as Approximate Dynamic Programming (ADP) to tackle these problems, yet they typically ignore certain aspects of dynamic resource allocation because of imposing assumptions such as single resource and identical resource consumption values per job.

In this research, we employ a mathematical-programming-based ADP technique called Lagrangian-relaxation for dealing with a large class of the DSRAPs. Specifically, we develop abstract problem description, MDP models of these problems, and approximately solve them using the Lagrangian approach. The results of our extensive computational experiments reveal that the Lagrangian approach significantly outperforms easy-to-use heuristic decision rules.

RAFAL GOEBEL, Loyola University Chicago
Set-valued Lyapunov functions for pointwise asymptotic stability  [PDF]

Pointwise asymptotic stability of a set, for a difference inclusion, requires that each point of the set be Lyapunov stable and that every solution to the inclusion, from a neighborhood of the set, be convergent and have the limit in the set. It is equivalent to the usual asymptotic stability for a single equilibrium, but is different in general, especially for noncompact sets of equilibria. Set-valued Lyapunov functions are set-valued mappings which characterize pointwise asymptotic stability in a way similar to how Lyapunov functions characterize the usual asymptotic stability. The talk will present necessary and sufficient conditions for pointwise asymptotic stability in terms of weak and strict set-valued Lyapunov functions.

ZHAOSONG LU, Simon Fraser University
First-order Methods for Constrained Nonsmooth Optimization  [PDF]

We propose a novel augmented Lagrangian (AL) method for a class of constrained nonsmooth optimization problems. Also, we propose two nonmonotone gradient methods for solving the AL subproblems. Global and local convergence of the methods are established. Finally, we discuss the application of this method to a new formulation of sparse principal component analysis and present some computational results which substantially outperform the other existing approaches.

YVES LUCET, UBC Okanagan
Recent Developments in Computational Convex Analysis: Convex Hulls and Graph-Matrix Calculus  [PDF]

We present a couple of algorithms to compute the convex envelope of piecewise linear-quadratic (PLQ) univariate functions. The first is simple to implement but has quadratic complexity while the second is more involved but has linear time complexity. In addition, we present a new family of algorithms for computing convex operators of PLQ functions by manipulating the graph of the subdifferential using Goebel's graph-matrix calculus rules.

TAMON STEPHEN, Simon Fraser University
Minimal Conflicting Sets in ancestral genome reconstruction  [PDF]

We consider problems of generating minimal obstacles (Conflicting Sets) to the consecutive-ones property for binary matrices used in ancestral genome reconstruction. We show that this problem can be reduced to a joint generation problem for boolean functions, and that this strategy can be helpful in discriminating between true and false positive ancestral syntenies in simulated and real data sets.

This is joint work with Cedric Chauve, Utz-Uwe Haus and Vivija You.

MOHAMED TAWHID, Thompson Rivers University
Solving Nonlinear Complementarity Problem by a Derivative-Free Descent Method  [PDF]

We consider smooth/nonsmooth nonlinear complementarity Problem (NCP). We show under certain assumptions, any stationary point of the unconstrained minimization problem is already a solution of smooth NCP. Also, we suggest a derivative-free descent algorithm and give conditions for its convergence. Furthermore, we present some preliminary numerical results.

SHAWN WANG, University of British Columbia Okanagan
Self-dual Regularization of Monotone Operators via the Resolvent Average  [PDF]

We give two self-dual regularization of maximal monotone operators on Hilbert spaces. These regularization and their set-valued inverse are strongly monotone, single-valued and Lipschitz with full domain. Moreover, these regularization graphically converges to the original monotone operator. If a maximal monotone operator has nonempty zeros, these self-dual regularization can be used to find its least norm solution. When the maximal monotone operator is the subdifferential of a proper lower semicontinuous convex function with nonempty minimizers, this translates to find the least norm minimizer.

LIN XIAO, Microsoft Research
Optimizing Orthogonality  [PDF]

We consider a new method for the problem of multi-class classification in machine learning. Our formulation involves minimizing the weighted sum of the absolute values of the inner products between a set of vectors, which promotes orthogonality between the vectors. We give a sufficient condition on the weights such that this objective is a convex function of all the vectors. We also propose an efficient dual-averaging method for solving such a nonsmooth convex optimization problem.

LIANGJIN YAO, UBC Okanagan
The sum of a maximal monotone operator of type (FPV) and a maximal monotone operator with full domain is maximal monotone  [PDF]

The most important open problem in Monotone Operator Theory concerns the maximal monotonicity of the sum of two maximal monotone operators provided that Rockafellar's constraint qualification holds.

In this paper, we prove the maximal monotonicity of the sum of $A + B$ provided that $A$ and $B$ are maximal monotone operators such that $\operatorname{dom} A\cap\operatorname{int}\operatorname{dom} B\neq\varnothing$, $A+N_{\overline{\operatorname{dom} B}}$ is of type (FPV), and $\operatorname{dom} A\cap\overline{\operatorname{dom} B}\subseteq\operatorname{dom} B$. The proof utilizes the Fitzpatrick function in an essential way.

JIM ZHU, Western Michigan University
Why bankers need to know convex analysis  [PDF]

Maximizing (expected) concave utility functions has been a traditional model in economic and financial decision making. In early 1970s the work by Black and Scholes on option pricing lead to a `revolution'. The paradigm shifted to price financial assets with replicating portfolio. Later Cox and Ross proposed simpler computation method using risk-neutral probability which became a default in the financial industry. However, the result is less than idea. In this talk we argue that the Black-Scholes method is a special case of concave utility maximization and the Cox-Ross formula is the natural result of its dual. Moreover, in the system of Black-Scholes and Cox-Ross, the analysis of sensitivity to model perturbation is dangerously inadequate. After many financial crises, it is perhaps time to return to the time tested method of utility maximization in which convex analysis plays an essential role.

YURIJ ZINCHENKO, University of Calgary
Numerical estimation of the relative entropy of entanglement in Quantum Information Theory  [PDF]

We propose a practical algorithm for the calculation of the relative entropy of entanglement (REE), defined as the minimum relative entropy between a state and the set of states with positive partial transpose. Our algorithm is based on a practical semi-definite cutting plane approach. In low dimensions the implementation of the algorithm in MATLAB provides an estimation for the REE with an absolute error smaller than 1e-3.