Réunion d'hiver SMC 2022
Toronto, 2 - 5 décembre 2022
Org: Walaa Moursi et Henry Wolkowicz (Waterloo)
[PDF]
- ANDERSEN ANG, University of Waterloo
Multigrid proximal gradient method for convex optimization [PDF]
-
We present a recent result on accelerating a 1st-order method for solving convex (possibly non-smooth) composite optimization problem of the form f(x) + g(x), where f is convex and differentiable and g is convex and possibly non-differentiable. We propose a multigrid (MG) based convergence acceleration method for the proximal gradient method. Coming from the domain of PDEs and scientific computing, the idea of multigrid assumes that the optimization problem has a hierarchical structure that can be exploited. By utilizing such hierarchy, acceleration can be achieved by a multi-level process.
We provide several theoretical results for the proposed method. We show a fixed-point property of the sequence generated by the method, and we provide a simple convergence analysis, based on a recent result on the Polyak-Lojasiewicz inequality, to show that the proposed method achieves a linear convergence rate on strongly convex problems.
Finally, we illustrate that the proposed MG-accelerated proximal gradient outperforms the proximal gradient method with Nesterov's acceleration, especially for large-sized problems in certain problem classes, such as a class of PDEs with a free boundary condition known as the elastic obstacle problem. If time permits, we will discuss briefly on the grid-independence convergence rate and also the on using MGProx for imaging application such as deblurrring.
- PHILLIP BRAUN, University of Western Ontario
On the Hadamard-Fischer's Inequality, the Inclusion-Exclusion Formula, and Bipartite Graphs [PDF]
-
The classical Hadamard-Fischer-Koteljanskii inequality is an inequality between principal minors of positive definite matrices. In this work, we present an extension of the Hadamard-Fischer-Koteljanskii inequality, that is inspired by the inclusion-exclusion formula for sets. We formulate necessary and sufficient conditions for the inequality to hold. We describe general structures of the collection of index sets involved. In analyzing these
structures, a graph-theoretical property that applies to bipartite graphs is found. We establish that
if the vertices of a bipartite graph satisfy simple conditions, then the bipartite graph contains a vertex subgraph
which is a cycle or a complete subgraph missing a matching. This is joint work with Hristo Sendov.
- KENNEDY IDU, University of Toronto
On Approximating Zeros of Monotone Operators in Banach Spaces [PDF]
-
The problem of finding and approximating zeros of monotone operators is well studied in Hilbert spaces motivated by its root in nonlinear problems of mathematical analysis and applications. Progress has been due to the nice geometry and identities of the space and its isomorphism to the dual. These readily lend problem to the powerful machinery of fixed point theory via transformation to the problem of finding fixed points of pseudocontractions. In general Banach spaces, where the notion of fixed points does not make sense for such operators, it is not immediately clear how to tow this path.
In this talk, we introduce a recent fixed point notion which presents a framework for the zero-problem in the sense of fixed point theory. Using this, we construct an approximation scheme which converges strongly to a solution of the zero-problem in Banach spaces. This is a joint work with Charles Chidume.
- HAESOL IM, University of Waterloo
Revisiting Degeneracy, Strict Feasibility, Stability in Linear Programming [PDF]
-
Currently, the simplex method and the interior point method are indisputably the most popular algorithms for solving linear programs. Unlike general conic programs, linear programs, LPs, with a finite optimal value do not require strict feasibility in order to establish strong duality. Hence strict feasibility is seldom a concern, even though strict feasibility is equivalent to stability and a compact dual optimal set. This lack of concern is also true for other types of degeneracy of basic feasible solutions in LP. In this note we discuss that the specific degeneracy that arises from lack of strict feasibility necessarily causes difficulties in both simplex and interior point methods. In particular, we show that the lack of strict feasibility implies that every basic feasible solution, BFS, is degenerate; thus conversely, the existence of a nondegenerate BFS implies that strict feasibility (regularity) holds. We prove the results using facial reduction and simple linear algebra. In particular, the facially reduced system reveals the implicit non-surjectivity of the linear map of the equality constraint system. As a consequence, we emphasize that facial reduction involves two steps where, the first guarantees strict feasibility, and the second recovers full row rank of the constraint matrix. This illustrates the implicit singularity of problems where strict feasibility fails, and also helps in obtaining new efficient techniques for preproccessing. We include an efficient preprocessing method that can be performed as an extension of phase-I of the two-phase simplex method.
- WALAA MOUSI, University of Waterloo
How to project onto the intersection of a closed affine subspace and a hyperplane [PDF]
-
Let A be a closed affine subspace and let B be a hyperplane in a Hilbert space. Suppose we
are given their associated nearest point mappings. We present a formula
for the projection onto their intersection. As a special case, we derive a formula for the
projection onto the intersection of two hyperplanes. These formulas provide useful information
even if the intersection is empty. Examples and numerical experiments are also provided.
- HRISTO SENDOV, The University of Western Ontario
Polar convexity and a refinement of the Gauss-Lucas theorem [PDF]
-
We will introduce the notion of polar convexity, which extends the usual notion of convexity.
We will give examples, explain its basic properties, and show how it arises in various situations. Then, we will use it to give a new refinement of the classical Gauss-Lucas theorem for complex polynomials. The Gauss-Lucas theorem states that the critical points of a polynomial are in the convex hull of its zeros.
- FEI WANG, Fields Institute and University of Waterloo
Singularity degree for non-facially exposed faces [PDF]
-
We define the singularity degree of a face which is not necessarily facially exposed. We show that the singularity degree of
a linear conic optimization problem is equal to the singularity degree of the minimal face on the linear image of the convex cone.
As an application, we give a bound of the singularity degree for generic frameworks and tensegrities underlying a Laman plus d graph ( Laman graph plus d edges). This is joint work with Henry Wolkowicz.
- HENRY WOLKOWICZ, University of Waterloo
Regularized Nonsmooth Newton Algorithms for Best Approximation, with Applications [PDF]
-
We consider nonsmooth algorithms for the best
approximation problem from polyhedral sets.
This classical problem has many varied approaches
and many applications. In particular, we study a regularized
semismooth method where the Jacobian is singular, and compare the computational
performance to that of classical projection methods,
e.g.,~the recently studied HLWB projection method.
We observe empirically that the regularized semismooth method significantly outperforms the HLWB approach. However, the HLWB has a convergence guarantee while the semismooth method does not due to singularity of the generalized Jacobian.
We provide several applications including solving large scale linear programs, triangles from branch and bound methods, and generalized constrained linear least squares. We include scaling methods that improve the efficiency and robustness.
work with Yair Censor, Walaa Moursi, Tyler Weames