


Analyse variationnelle et optimisation
Org: Jiming Peng (MacMaster) et Jane Ye (Victoria) [PDF]
 DIDIER AUSSEL, University of Perpignan, 52 av. P. Alduy, 66860 Perpignan
Cedex, France
On quasiconvex mathematical programming problems with
equilibrium constraints
[PDF] 
A mathematical programming problem with equilibrium constraints (MPEC)
is a constrained optimization problem with equality and inequality
constraints and, additionally, some equilibrium constraints:
In general the constraint region associated to this problem is neither
compact nor convex, even if the constraint functions are supposed to
be linear. Nevertheless under the weak assumption that g is
quasiconvex and h, H and G are quasiaffine, the constraint set
appears to be locally starshaped.
The locally starshapedness is a rich structure and we will first
present some existence results, necessary and sufficient optimality
conditions for the problem of minimizing a quasiconvex function over a
locally starshaped set.
Corresponding results for quasiconvex MPECs will be obtained as
particular cases.
References
 [1]

D. Aussel and J. Ye,
Quasiconvex programming with locally starshaped constraint
region and applications to quasiconvex MPEC.
Optimization, to appear.
 [2]

D. Aussel and N. Hadjisavvas,
Adjusted sublevel sets, normal operator and quasiconvex
programming.
SIAM J. Optim., to appear.
 HEINZ BAUSCHKE, UBC Okanagan
Fitzpatrick functions and (cyclically) monotone operators
[PDF] 
In 1988, Simon Fitzpatrick defined a new convex function
F_{A}nowadays called the Fitzpatrick functionassociated with a
monotone operator A, and similarly a monotone operator G_{f}
associated with a convex function f.
This talk surveys recent joint works with Alex McLaren (Guelph) and
Hristo Sendov (Guelph), and with Jon Borwein (Dalhousie) and Shawn
Wang (UBC Okanagan).
We consider the Fitzpatrick function of the subdifferential operator
of a proper, lower semicontinuous, and convex function. This operator
is cyclically monotone. A refinement of the classical FenchelYoung
inequality is derived and conditions for equality are investigated.
The results are illustrated by several examples.
We also study the problem, originally posed by Fitzpatrick, of
determining when A=G_{FA}. Fitzpatrick proved that this identity
is satisfied whenever A is a maximal monotone; however, he also
observed that it can hold even in the absence of maximal
monotonicity. We propose a new condition sufficient for this
identity, formulated in terms of the polarity notions introduced
recently by MartinezLegaz and Svaiter.
 JIM BURKE, University of Washington
Variational Analysis and the Roots of Polynomials
[PDF] 
In a number of applications to stability and control one is interested
in the behavior of certain functions of the roots of a polynomial as
the polynomial varies. For example, how does the maximum modulus of
the roots of a polynomial change as the coefficients of the polynomial
varies?
In this talk we show how convex the geometry of the sets of roots of a
polynomial and its derivative can be used to give insight into the
variational behavior of such functions.
 RICK CARON, University of Windsor, Windsor, ON
Random methods for the analysis of quadratic constraint sets
[PDF] 
We review a framework for the analysis of sets of constraints, with no
explicit assumptions, and we show the connection between minimal
representations, irreducible infeasible systems, minimal infeasibility
sets, as well as other attributes of the preprocessing of mathematical
programs.
We show how the framework facilitates the development of a
probabilistic preprocessing algorithm for a variety of mathematical
programs, and we apply it specifically to convex quadratic constraint
sets. We show, by example, that the method is surprisingly effective
in finding feasible solutions.
Coauthor: Dr. Tim Traynor, University of Windsor.
 JOHN DENNIS, Rice University and University of Washington
Mesh Adaptive Direct Search Algorithms
[PDF] 
The Mesh Adaptive Direct Search (MADS) class of derivativefree
algorithms is effective for industrial strength nonlinear inequality
constrained optimization. It has been incorporated into the MATLAB
GADS package.
MADS is the direct result of applying nonsmooth analysis to GPS, an
earlier class of similar algorithms. This powerful tools of nonsmooth
analysis made clear GPS deficiencies glossed over by assuming
smoothness. MADS has a satisfying convergence theory based on the
Clarke calculus and Rockafeller's notion of a hypertangent cone.
MADS replaced GPS in our NOMAD software presently in use by our
industrial collaborators. It is applicable to a wider class of
problems than GPS, including yes/no constraints, and in all trials to
date, MADS is more reliable and efficient.
This research was done in collaboration with Professor Charles Audet
of Ecole Polytechnique de Montréal.
 YUYING LI, University of Waterloo, 200 University Avenue West, Waterloo,
ON
A Graduated Nonconvexity Method for Applications in Finance
[PDF] 
Investment and risk management in finance often require determining a
small number of assets to minimize some measure of tracking error.
Determining such a solution requires solving a mixed nonlinear integer
programming problem. We propose a graduated nonconvexity method to
minimize portfolio tracking error with the total number of assets no
greater than a specified integer K. The solution of this tracking
error minimization problem is the global minimizer of the sum of the
tracking error function and the discontinuous counting function. We
attempt to track the globally minimal tracking error portfolio by
approximating the discontinuous counting function with a sequence of
continuously differentiable nonconvex functions, a graduated
nonconvexity process. We discuss the advantages of this approach and
present numerical results in index tracking and hedging under basis
risk applications in finance.
 YVES LUCET, University of British Columbia Okanagan, 3333 University Way,
Kelowna, BC V1V 1V7
Fast Moreau Envelope Algorithms and Applications
[PDF] 
We present a new algorithm (named NEP for NonExpansive Proximal
mapping) to compute the discrete Moreau envelope M_{l,X} (s) = min_{x Î X} [[( sx ^{2})/(2l)] + f(x)] of a
function f, where X is a discrete grid and l > 0. Numerical
comparisons between the NEP and two existing algorithms: The
Lineartime Legendre Transform (LLT) and the Parabolic Envelope (PE)
algorithms will be shown along with worstcase time complexity,
convergence results, numerical comparison, and examples.
The algorithms will be applied to compute numerical solutions to
HamiltonJacobi equations, and the distance transform of image
processing.
References
 [1]

Y. Lucet, Faster than the Fast Legendre Transform, the
Lineartime Legendre Transform. Numer. Algorithms
16(1997), 171185.
 [2]

, Fast Moreau Envelope computation I: Numerical
algorithms. Technical Report, University of British Columbia
Okanagan, 2005.
 [3]

,
A linear euclidean distance transform algorithm based on the
Lineartime Legendre Transform. In: Proceedings of the Second
Canadian Conference on Computer and Robot Vision (CRV 2005), Victoria,
BC, May 2005, IEEE Computer Society Press.
 JIMING PENG, McMaster University, Hamilton, Ontario
01 Semidefinite Programming for Clustering: Modeling and
Approximation
[PDF] 
In the past few years, spectral clustering has caught much attention
in the machine learning community and numerous algorithms have been
proposed and wellstudied. In this paper, we present a unified
framework for these methods based on a new optimization model: 01
semidefinite programming (01 SDP). We also show that various
constrained clustering problems can be embedded into the new 01 SDP
model. Secondly, we consider the issue of how to solve the underlying
01 SDP problem. We consider two approximation methods based on
principal component analysis (PCA) and projected PCA, respectively and
prove that both algorithms can provide a 2approximation to the
original clustering problem. The complexity of these approximation
algorithms are also discussed.
 MOHAMED TAWHID, Thompson Rivers University
On some applications of Hdifferentiability to optimization
and complementarity problems
[PDF] 
In this talk, we consider two applications of Hdifferentiability.
In the first application, we derive a necessary optimality condition
for a local minimum of an Hdifferentiable function. In the second
application, we consider a nonlinear complementarity problem
corresponding to an Hdifferentiable function f and show how,
under appropriate conditions on an Hdifferential of f, minimizing
a merit function corresponding to f leads to a solution of the
nonlinear complementarity problem. These two applications were
motivated by numerous studies carried out for C^{1}, convex, locally
Lipschitzian, and semismooth function by various researchers.
 PAUL TSENG, University of Washington
SOCP Relaxation of Sensor Network Localization
[PDF] 
We study a secondorder cone programming (SOCP) relaxation of the
NPhard sensor network localization problem. We show that SOCP
relaxation, though weaker than SDP relaxation, has nice properties
that make it useful as a problem preprocessor. In particular, an
error bound result shows that sensors that are uniquely positioned
among interior solutions of the SOCP relaxation are accurate up to the
square root of the distance error. Thus, these sensors, which can be
easily identified, are accurately positioned. In our numerical
simulation, the interior solution found can accurately position up to
8090% of the sensors. We also propose a smoothing coordinate
gradient descent method for finding an interior solution faster than
using SeDuMi.
 XIANFU WANG, University of British Columbia: Okanagan
The extremal characterization of reflexive spaces
[PDF] 
Assume that a Banach space has a Fréchet differentiable and locally
uniformly convex norm. We show that the reflexive property of the
Banach space is not only sufficient but also a necessary condition for
the fulfillment of the proximal extremal principle in nonsmooth
analysis.
 HERRE WIERSMA, Dalhousie University
Asplund Decomposition of Monotone Operators
[PDF] 
A somewhat overlooked 1970 paper by Edgar Asplund establishes a
decomposition for a maximal monotone operator T : X®X^{*} on a general Banach space X. The operator T is decomposed as
the pointwise sum of the (wellbehaved) subdifferential mapping
¶f of a convex function f, and an `acyclic' component A.
I will reproduce a modern version of this result, and summarize
current knowledge of the properties of this acyclic part.
 HENRY WOLKOWICZ, Faculty of Mathematics, University of Waterloo, Waterloo,
Ontario
Approximate and Exact Completion Problems for Euclidean
Distance Matrices using Semidefinite Programming
[PDF] 
A partial predistance matrix A is a matrix with zero diagonal and
with certain elements fixed to given nonnegative values; the
other elements are considered free. The EDM completion
problem chooses nonnegative values for the free elements in order to
obtain a Euclidean distance matrix, EDM. The nearest (or approximate)
EDM problem is to find a Euclidean distance matrix that is nearest in
the Frobenius norm to the matrix A, when the free variables are
discounted.
Applications for EDM include: molecular conformation problems in
chemistry; multidimensional scaling and multivariate analysis problems
in statistics; sensor localization; genetics, geography,
etc.
We present two algorithms: one for the exact completion problem and
one for the approximate completion problem. Both use a reformulation
of EDM into a semidefinite programming problem, SDP. The first
algorithm is based on an implicit equation for the completion that for
many instances provides an explicit solution. The other algorithm is
based on primaldual interiorpoint methods that exploit the structure
and sparsity. Included are results on maps that arise that keep the
EDM and SDP cones invariant.
We conclude with numerical tests.
 JANE YE, University of Victoria
Optimality conditions for generalized semiinfinite
programming problems
[PDF] 
In this talk we consider the first order optimality conditions for the
class of generalized semiinfinite programming problems (GSIPs). We
extend the wellknown constraint qualifications for finite programming
problems such as the calmness condition, the Abadie constraint
qualification, the KuhnTucker constraint qualification, the Zangwill
constraint qualification, the Slater condition, the linear
independence constraint qualification and the weak reverse convex
constraint qualification to GSIPs and analyze the extent to which a
corresponding KarushKuhnTucker condition depends on these
extensions. Relationships among various constraint qualifications are
also given.
 XIAOMING YUAN, University of Victoria, Victoria, BC V8W 3P4
Some hybrid methods for structured monotone variational
inequalities
[PDF] 
This talk presents some hybrid methods for solving monotone
variational inequalities with separate structures. In particular,
some descent directions are derived from the wellknown alternating
directions method and its variants and thus some hybrid methods are
presented. The optimal step sizes along the descent directions also
improve the efficiency of the new methods. Some numerical results
demonstrate that the new methods are effective in practice.

