2014 CMS Winter Meeting

McMaster University, December 5 - 8, 2014

Plenary, Prize and Public Lectures By session By speaker Posters

Recent Advances in Variational Analysis and Linear Optimization
Org: Antoine Deza (McMaster) and Henry Wolkowicz (Waterloo)
[PDF]

ABDO ALFAKIH, University of Windsor A New Semidefinite Farkas lemma and the dimensional rigidity of bar frameworks [PDF]: We present a new semidefinite Farkas lemma involving the rank. This lemma is then used to present a new proof of a characterization by Connelly and Gortler of dimensional rigidity of bar frameworks. The proof of this lemma is based on the Borwein-Wolkowicz facial reduction algorithm.
HEINZ BAUSCHKE, The University of British Columbia The Douglas-Rachford Algorithm: Recent Progress [PDF]: The Douglas-Rachford algorithm is one of the most successful methods for feasibility and optimization. A notable feature is its ability to accommodate nonsmooth objective function and it also has been applied as a heuristic method on nonconvex problems with great success.
In this talk, I will report on recent progress on the understanding of this algorithm. I will focus on the range of the operator and new qualitative and quantitative convergence results.
YUEN-LAM (VRIS) CHEUNG, University of Colorado Boulder Efficient and Accurate Solutions for Linear Programs with Bound Constraints [PDF]: We consider linear programs with lower and upper bound constraints on the variables. We use a nullspace representation for the primal linear constraints, which allows for a system that is well-conditioned as the barrier parameter goes to zero. We also use a single dual variable for each upper and lower bound pair, rather than one variable for each bound. This reduces the size of the linear system to solve at each iteration.
This is joint work with Michael Saunders and Henry Wolkowicz.
AHAD DEHGHANI, GERAD A Primal-Dual Regularized Interior-Point Method for Semidefinite Programming [PDF]: Interior-point methods in semidefinite programming (SDP) require the solution of a sequence of linear systems which are used to derive the search directions. Safeguards are typically required in order to handle rank-deficient Jacobians and free variables. We generalize the primal-dual regularization of Friedlander and Orban to SDP and show that it is possible to recover an optimal solution of the original primal-dual pair by taking one step of Newton method to a sequence of regularized SDPs at each iteration for both the NT and dual HKM directions. Computationally, a sparse $LDL^T$ factorization may be used on a sparse augmented system instead of the more costly symmetric indefinite factorization. Benefits of our approach include increased robustness and a simpler implementation. Our method does not require the constraints to be linearly independent and does not assume that Slater's condition holds. We report numerical experience on standard problems that illustrate our findings.
ANTOINE DEZA, McMaster University On the polynomial Hirsch conjecture and its continuous analogue [PDF]: The simplex and primal-dual interior point methods are the most computationally successful algorithms for linear optimization. While simplex methods follow an edge path, interior point methods follow the central path. Within this framework, the curvature of a polytope, defined as the largest possible total curvature of the associated central path, can be regarded as the continuous analogue of its diameter. In this talk, we highlight links between the edge and central paths, and between the diameter and the curvature of a polytope. We recall continuous results of Dedieu, Malajovich, and Shub, and discrete results of Holt and Klee and of Klee and Walkup, as well as related conjectures such as the Hirsch conjecture that was disproved by Santos. We also present analogous results dealing with average and worst-case behaviour of the curvature and diameter of polytopes, including a result of Allamigeon, Benchimol, Gaubert, and Joswig who constructed a counterexample to the continuous analogue of the polynomial Hirsch conjecture. Based on joint work with Tamás Terlaky (Lehigh), Feng Xie (Microsoft), and Yuriy Zinchenko (Calgary).
YICHUAN (DANIEL) DING, Sauder School of Business, University of British Columbia An Overloaded Bipartite Queueing System with Scoring-Based Priority Rules [PDF]: We consider an overloaded bipartite queueing system (OBQS) with multitype customers and service providers. In such a system, a service provider assigns each customer a score based on customer type, duration of waiting time, and server type. Service is then provided first to the customer with the highest score. We approximate the behavior of such a system using a fluid limit process, which has two important features: (1) the routing flow rates at a transient state coincide with the maximal flow in a parameterized network and can be efficiently computed based on a nested-cut structure using a so-called GGT algorithm; (2) the routing flow rates at the steady state coincide with the minimal-cost maximal-flow in a capacitated network. Given these properties, we can efficiently characterize the unique fluid limit process. This result has three immediate applications: (1) it predicts the outcome of an OBQS equipped with a scoring-based routing policy; (2) it sheds insight into designing a score formula with a given set of objectives; and (3) by applying the result to the special case when the OBQS is FCFS, we make new progress in addressing the open question raised by Talreja and Whitt (2008).
WARREN HARE, UBC Numerical Variational Analysis [PDF]: Numerical Analysis, the study of approximating analytic properties of a function, has established a collection of formulas for approximating derivatives, gradients, and Hessians. Naturally, these formulas are designed under restrictive smoothness assumptions on the function. Variational Analysis includes a great deal of research on understanding analytic properties of nonsmooth functions, for example the classic subdifferential of a convex function. In this talk we advance the idea of Numerical Variational Analysis, the study of approximating analytic properties of a nonsmooth function. We discuss some recent results and note that open research directions abound.
MICHAEL METEL, McMaster University Chance Constrained Optimization for Parimutuel Horse Race Betting [PDF]: The merit of chance constrained optimization in the context of horse racing will be explored. An overview of the parimutuel betting market will be presented, with the methods of forecasting race outcomes and payouts. New chance constrained models for expected profit maximization will be introduced with a focus on risk management. Initial results will be presented with testing performed on historical race data.
WALAA MOURSI, University of British Columbia Generalized solutions for the sum of two maximally monotone operators. [PDF]: A common theme in mathematics is to define generalized solutions to deal with problems that potentially do not have solutions. A classical example is the introduction of least squares solutions via the normal equations associated with a possibly infeasible system of linear equations. In this talk, we introduce a ``normal problem" associated with finding a zero of the sum of two maximally monotone operators. If the original problem admits solutions, then the normal problem returns this same set of solutions. The normal problem may yield solutions when the original problem does not admit any; furthermore, it has attractive variational and duality properties. Several examples illustrate our theory.
BARTOSZ PROTAS, McMaster University Probing Fundamental Bounds in Hydrodynamics Using Variational Optimization Methods [PDF]: In the presentation we will review recent results and discuss some emerging research directions concerning application of the modern methods of PDE-constrained optimization to study a class of fundamental problems in mathematical fluid mechanics. These problems concern the sharpness of certain estimates, such as the bounds on the maximum enstrophy growth in 3D flows governed by the Navier-Stokes system, which are intimately related to the question of spontaneous singularity formation, known as the ``blow-up'' problem. We demonstrate how new insights concerning such problems can be obtained by formulating them as variational PDE optimization problems which can be solved computationally using discretized gradient flows. Vortex states determined in this way represent the most extreme flow behavior allowed for by the Navier-Stokes dynamics and are therefore natural candidates for blow-up. In offering a systematic approach to finding such flow solutions which saturate known estimates, the proposed paradigm provides a bridge between theory and computation. In the presentation we will show a number of new results concerning extreme vortex states in 2D and 3D Navier-Stokes flows, and will discuss their relation to the available theoretical bounds obtained with methods of mathematical analysis. [Joint work with Dr. Diego Ayala]
HRISTO SENDOV, The University of Western Ontario Loci of complex polynomials [PDF]: For every complex polynomial $p(z)$, closed point sets are defined, called loci of $p(z)$. A closed set in the extended complex plane is a locus of $p(z)$ if it contains a zero of any of its apolar polynomials and is the smallest such set with respect to inclusion. Using the notion locus, several classical theorems in the geometry of polynomials can be refined (such as Grace's theorem, Grace-Walsh-Szego coincidence theorem, complex Rolle's theorem, and Laguerre's Theorem). We establish several fundamental properties of the loci and investigate their intriguing connections with the higher-order polar derivatives of $p(z)$. This is a joint work with Blagovest Sendov.
SHAWN XIANFU WANG, University of British Columbia Kelowna Weak subdifferentials, rl-density and maximal monotonicity [PDF]: We show that weak subdifferentials of a proper lower semicontinuous function are rl-dense if the function has its prox-bound being one. As a special case, we can prove Rockafellar's result that the subdifferential of a proper convex lower semicontinuous function is maximally monotone.
HENRY WOLKOWICZ, University of Waterloo Coordinate Shadows of Semi-definite and Euclidean Distance Matrix Completions [PDF]: We consider the sets of input data defining feasible semi-definite and Euclidean distance matrix completion problems. We characterize when these sets are closed based on the structure of the underlying graphs, and show that in the presence of boundary data, an intuitive facial reduction technique may drastically reduce the size of the positive semi-definite formulations of these completion problems. We exploit facial reduction based on the cliques of the graph. Chordality of the graph plays an essential role.
YURIY ZINCHENKO, University of Calgary On a shortest 2-path problem [PDF]: An electric power supplier needs to build a transmission line between 2 jurisdictions. Ideally, the design of the new electric power line would be such that it maximizes some user-defined utility function, for example, minimizes the construction cost or the environmental impact. Due to reliability considerations, the power line developer has to install not just one, but two transmission lines, separated by a certain distance from one-another, so that even if one of the lines fails, the end user will still receive electricity along the second line. We discuss how such a problem can be modelled, and in particular, demonstrate a setting that allows to solve this problem in polynomial time.

Sponsors