Réunion d'hiver SMC 2020

Ottawa, 7 - 11 juin 2021

english
accueil réunion
accueil smc

Analyse variationnelle : applications et théorie
Org: Walaa Moursi et Henry Wolkowicz (Waterloo)
[PDF]

MINH BUI, University of Waterloo A Decomposition Method for Solving Multicommodity Network Equilibria [PDF]: We consider the numerical aspect of the multicommodity network equilibrium problem proposed by Rockafellar in 1995. Our method relies on the flexible monotone operator splitting framework recently proposed by Combettes and Eckstein.
ZHENAN FAN, University of British Columbia Polar deconvolution of mixed signals [PDF]: The signal demixing problem seeks to separate a superposition of multiple signals into its constituent components. We propose a two-stage approach that first decompresses and subsequently deconvolves the noisy and undersampled observations of the superposition. Probabilistic error bounds are given on the accuracy with which this process approximates the individual signals. The theory of polar convolution of convex sets and gauge functions plays a central role in the analysis and solution process. If the measurements are random and the noise is bounded, this approach stably recovers low-complexity and mutually incoherent signals, with high probability and with optimal sample complexity. We also develop an efficient algorithm, based on level-set and conditional-gradient methods, that solves the convex optimization problems with sublinear iteration complexity and linear space requirements. Numerical experiments on both real and synthetic data confirm the theory and the efficiency of the approach.
HAO HU, Clemson University The Linearization Problem Of A Binary Quadratic Problem And its Applications [PDF]: We provide several applications of the linearization problem of a binary quadratic problem. We propose a new lower bounding strategy, called the linearization-based scheme, that is based on a simple certificate for a quadratic function to be non-negative on the feasible set. This is a joint work with Prof. Renata Sotirov.
JIYOUNG IM, University of Waterloo Robust Interior Point Methods for Quantum Key Rate Computation for Quantum Key Distribution [PDF]: We derive a stable reformulation of the quantum key rate computation for finite dimensional quantum key distribution (QKD) problems. This avoids the difficulties from singularities that arise due to loss of positive definiteness. This allows for the derivation of an efficient Gauss-Newton Interior point approach. Empirical evidence illustrate the strength of this approach as we obtain high accuracy solutions and theoretically guaranteed upper and lower bounds for the quantum key rate.
XINXIN LI, Jilin University A Restricted Dual Peaceman-Rachford Splitting Method for a Strengthened DNN Relaxation for QAP [PDF]: Splitting methods in optimization arise when one can divide an optimization problem into two or more simpler subproblems. They have proven particularly successful for relaxations of problems involving discrete variables. We revisit and strengthen splitting methods for solving doubly nonnegative, DNN, relaxations of the particularly difficult, NP-hard quadratic assignment problem, QAP. We use a modified restricted contractive splitting method, rPRSM, approach. In particular, we show how to exploit redundant constraints in the subproblems. Our strengthened bounds exploit these new subproblems, as well as new dual multiplier estimates, to improve on the bounds and convergence results in the literature.
DOMINIQUE ORBAN, GERAD and Polytechnique Montréal A proximal quasi-Newton trust-region method for nonsmooth regularized optimization [PDF]: We develop a trust-region method for minimizing the sum of a smooth term $f$ and a nonsmooth term $h$, both of which can be nonconvex. Each iteration of our method minimizes a possibly nonconvex model of $f+h$ in a trust region. The model coincides with $f+h$ in value and subdifferential at the center. We establish global convergence to a first-order stationary point when $f$ satisfies a smoothness condition that holds, in particular, when it has Lipschitz-continuous gradient, and $h$ is proper and lower semi-continuous. The model of $h$ is required to be proper and lower-semi-continuous. Under these weak assumptions, we establish a worst-case $O(1/\epsilon^2)$ iteration complexity bound that matches the best known complexity bound of standard trust-region methods for smooth optimization. We detail a special instance in which we use a limited-memory quasi-Newton model of $f$ and compute a step with the proximal gradient method, resulting in a practical proximal quasi-Newton method. We describe our Julia implementations and report numerical results on inverse problems from sparse optimization and signal processing. Our trust-region algorithm exhibits promising performance and compares favorably with linesearch proximal quasi-Newton methods based on convex models.
MATTHIAS TAKOUDA, Laurentian University Rankings and Doubly Stochastic Matrices [PDF]: We present an approach to group decision-making where solutions to doubly stochastic matrix approximation problems are used to determine a ranking on a set of alternatives, only known a posteriori, that aggregate preferences or opinions of various experts. The proposed approach is applied in real life settings, where Alternating Projections and Douglas-Rachford feasibility methods are used.
HENRY WOLKOWICZ, University of Waterloo A Strengthened Barvinok-Pataki Bound on SDP Rank [PDF]: The Barvinok-Pataki bound provides an upper bound on the rank of extreme points of a spectrahedron. This bound depends solely on the number of affine constraints of the problem, i.e.,~on the algebra of the problem. Specifically, the triangular number of the rank $r$ is upper bounded by the number of affine constraints. We revisit this bound and provide a strengthened upper bound on the rank using the singularity degree of the spectrahedron. Thus we bring in the geometry and stability of the spectrahedron, i.e.,~increased instability as seen by higher singularity degree, yields a lower, strengthened rank bound.

haut de la page