Variational Analysis: Applications and Theory
Org:
Walaa Moursi and
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 twostage 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 lowcomplexity and mutually incoherent signals, with high probability and with optimal sample complexity. We also develop an efficient algorithm, based on levelset and conditionalgradient 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 linearizationbased scheme, that is based on a simple certificate for a quadratic function to be
nonnegative 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 GaussNewton 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 PeacemanRachford 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, NPhard 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 quasiNewton trustregion method for nonsmooth regularized optimization [PDF]

We develop a trustregion 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 firstorder stationary point when $f$ satisfies a smoothness condition that holds, in particular, when it has Lipschitzcontinuous gradient, and $h$ is proper and lower semicontinuous. The model of $h$ is required to be proper and lowersemicontinuous. Under these weak assumptions, we establish a worstcase $O(1/\epsilon^2)$ iteration complexity bound that matches the best known complexity bound of standard trustregion methods for smooth optimization. We detail a special instance in which we use a limitedmemory quasiNewton model of $f$ and compute a step with the proximal gradient method, resulting in a practical proximal quasiNewton method. We describe our Julia implementations and report numerical results on inverse problems from sparse optimization and signal processing. Our trustregion algorithm exhibits promising performance and compares favorably with linesearch proximal quasiNewton methods based on convex models.
 MATTHIAS TAKOUDA, Laurentian University
Rankings and Doubly Stochastic Matrices [PDF]

We present an approach to group decisionmaking 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 DouglasRachford feasibility methods are used.
 HENRY WOLKOWICZ, University of Waterloo
A Strengthened BarvinokPataki Bound on SDP Rank [PDF]

The BarvinokPataki 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.
© Canadian Mathematical Society