Variational Analysis: Theory and Applications
Org: Heinz Bauschke
and Xianfu Wang
- MANISH KRISHAN LAL, UBC Okanagan
Set-valued analysis of generalized bilinear sets [PDF]
We establish the dual relationships of sets of bilinear forms with the low-degree polynomials. As a result, we provide some results on formulas for projection onto these sets, which are then utilized into new algorithmic frameworks- such as feasibility-based algorithms, nonlinear linkage algorithms applied to a neural network training example.
- SHAMBHAVI SINGH, University of British Columbia Okanagan
Strong convergence of splitting algorithms by Ryu, by Malitsky-Tam, and by Campoy applied to normal cones of linear subspaces [PDF]
Finding a zero of a sum of maximally monotone operators is a fundamental problem in modern optimization and nonsmooth analysis. Assuming that the resolvents of the operators are available, this problem can be tackled with the Douglas-Rachford algorithm. However, when dealing with three or more operators, one must work in a product space with as many factors as there are operators. In ground-breaking recent work by Ryu and by Malitsky and Tam, it was shown that the number of factors can be reduced by one. A similar reduction was achieved recently by Campoy through a clever reformulation originally proposed by Kruger. All three splitting methods guarantee weak convergence to some solution of the underlying sum problem; strong convergence holds in the presence of uniform monotonicity.
In this paper, we provide a case study when the operators involved are normal cone operators of subspaces and the solution set is thus the intersection of the subspaces. Even though these operators lack strict convexity, we show that striking conclusions are available in this case: strong (instead of weak) convergence and the solution obtained is (not arbitrary but) the projection onto the intersection. Numerical experiments to illustrate our results are also provided.
- SHAWN WANG, Department of Mathematics, University of British Columbia Okanagan
Bregman circumcenters: basic theory [PDF]
Circumcenters play an important role in the design and analysis of accelerating
various iterative methods in optimization.
In this work,
we propose Bregman (pseudo-)circumcenters associated with finite sets. We show the existence
of and give explicit formulae for the unique backward and forward Bregman pseudo-circumcenters of finite sets. Moreover, we use duality to establish
connections between backward and forward Bregman (pseudo-)circumcenters. Joint work with Hui Ouyang.
- ZIYUAN WANG, UBCO
A non-Euclidean forward-reflected-backward method with inertial effects for nonconvex minimization [PDF]
We propose a non-Euclidean version of the Malitsky-Tam forward-reflected-backward method with inertial effects for monotone inclusion problems to solve nonconvex minimization problems. The convergence is guaranteed by the generalized concave Kurdyka-Łojasiewicz (KL) property of a quadratic regularization of the objective, under which the method has finite length property and converges to a stationary point globally.
- HENRY WOLKOWICZ, University of Waterloo
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,
PRSM, 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.
- JANE YE, University of Victoria
On relaxed constant positive linear dependence constraint qualification [PDF]
The classical relaxed constant positive linear dependence constraint qualification (RCPLD) is defined for a system of smooth equalities and inequalities. It is weaker than the usual constraint qualification such as Mangasarian Fromovitz constraint qualification. Moreover RCPLD is known to be a sufficient condition for the error bound property. In this work we extend RCPLD to a very general feasibility system which may include Lipschitz continuous inequality constraints, and closed sets. We show that RCPLD we introduced for the general system is still a constraint qualification and it is a sufficient condition for the error bound property under Clarke regularity conditions for the inequality constraints and the abstract constraint set. Moreover when the sets involved are the union of finitely many convex polyhedral sets, we propose a weaker form of RCPLD and its piecewise variant. We show that the weaker form of RCPLD is still a constraint qualification and its piecewise variant is a sufficient condition for the error bound property. This is a joint work with Mengwei Xu.