2019/04/03 – Mini-workshop

On the 3rd of April of 2019, we will hold a mini-workshop from 14:00 to 17:40 at room 534, Engineering building 14th.
The schedule will be as follows:

14:00-14:40 Ting Kei Pong (The Hong Kong Polytechnic University):
Gauge optimization: Duality and polar envelope
14:40-15:20 Bruno F. Lourenço (University of Tokyo):
Generalized subdifferentials of spectral functions
15:20-16:00 Michael Metel (RIKEN-AIP):
Stochastic gradient methods for non-smooth non-convex optimization
16:00-16:20 (break)
16:20-17:00 Masaru Ito (Nihon University):
Adaptive and nearly optimal first-order method under Hölderian error bound condition
17:00-17:40 Takashi Tsuchiya (National Graduate School for Policy Studies):
Duality theory of SDP revisited: Another Analysis on Why Positive Duality Gaps Arise in SDP

Abstracts of the talks:
——————————————-
Title: Gauge optimization: Duality and polar envelope
Speaker: Ting Kei Pong
Abstract:
Gauge optimization seeks the element of a convex set that is minimal with respect to a gauge function, and arises naturally in various contemporary applications such as machine learning and signal processing. In this talk, we
explore the gauge duality framework proposed by Freud. We then define the polar envelope and discuss some of its important properties. The polar envelope is a convolution operation specialized to gauges, and is analogous to Moreau envelope. We will highlight the important roles the polar envelope plays in gauge duality and in the construction of algorithms for gauge optimization. This is joint work with Michael Friedlander and Ives Macêdo.

——————————————-
Title: Generalized subdifferentials of spectral functions
Speaker: Bruno F. Lourenço
Abstract:
In this talk, we explain how to compute the regular, approximate and horizon subdifferentials of spectral functions over Jordan algebras.We will also show how the obtained formulae can be used to
compute the exponent of the Kurdyka–Łojasiewicz inequality for spectral functions, which is useful for the analysis of gradient methods in nonsmooth optimization. As an application, we compute the generalized subdifferentials of the k-th largest eigenvalue function. This is a joint work with Akiko Takeda.

——————————————-
Title: Stochastic gradient methods for non-smooth non-convex optimization
Speaker: Michael Metel

——————————————-
Title: Adaptive and nearly optimal first-order method under Hölderian error bound condition
Speaker:
Masaru Ito
Abstract:
Knowledge of strong convexity or its relaxed error bound conditions of the objective function is important to accelerate the convergence of first-order methods. In this work, we focus on the Hölderian Error Bound (HEB) condition, which is a generalization of the strong convexity relative to the solution set, parameterizing the exponent. An adaptive and nearly optimal first-order method is presented, which reduces the requirement of prior knowledge of the HEB exponent.

——————————————-
Title: Duality theory of SDP revisited: Another Analysis on Why Positive Duality Gaps Arise in SDP
Speaker: Takashi Tsuchiya
Abstract:
In this talk, we study the duality structure of semidefinite programs to understand positive duality gap in SDP. It is shown that there exists a relaxation of the dual problem whose optimal value coincides with the primal optimal value, whenever the primal is weakly feasible. The relaxed dual SDP is constructed by removing several linear constraints from the dual, and therefore is likely to have larger optimal value generically, leading to a positive duality gap. It can also happen that the relaxed dual problem coincides the dual itself, i.e., no linear constraint is removed in the construction process of relaxation, in which case strong duality holds. Strong duality under the Slater condition or strong duality in LP can be understood in this context. The analysis suggests that the existence of positive duality gap is a rather generic phenomenon when both the primal and dual problems are weakly feasible.
This is a joint work with Bruno F. Lourenco and Masakazu Muramatsu.

 

2019/04/02 and 2019/04/03 – Talks by Ting Kei Pong (Hong Kong Polytechnic University)

Date:  2nd April (Tue) 10:30-11:30
Place: #235,  Engineering Bldg.6
Speaker: Ting Kei Pong  (the Hong Kong Polytechnic University)
http://www.mypolyuweb.hk/~tkpong/

Title: Deducing Kurdyka-Łojasiewicz exponent of optimization
models

Abstract: Kurdyka-Łojasiewicz (KL) exponent is an important
quantity for determining the qualitative convergence
behavior of many first-order methods. In this talk, we
review some known connections between the KL exponent and
other important error bound concepts, and discuss some
calculus rules that allow us to determine the KL exponent of
new functions from functions with known KL exponent.
Specifically, we will show that KL exponents are preserved
under Lagrange relaxation and inf-projection, under mild
assumptions. This allows us to deduce, under suitable
assumptions, the KL exponent of many important convex or
nonconvex optimization models, such as group fused LASSO,
least squares with MCP or SCAD regularization, least squares
with rank constraint, and envelope functions such as the
Moreau envelope or the forward-backward envelope.
This is a joint work with Guoyin Li and Peiran Yu.
————–
Date:  3rd April (Wed) 14:00-14:40
Place: #534,  Engineering Bldg.14
Speaker: Ting Kei Pong    (the Hong Kong Polytechnic University)
http://www.mypolyuweb.hk/~tkpong/
Title: Gauge optimization: Duality and polar envelope

Abstract: Gauge optimization seeks the element of a convex
set that is minimal with respect to a gauge function, and
arises naturally in various contemporary applications such
as machine learning and signal processing. In this talk, we
explore the gauge duality framework proposed by Freud. We
then define the polar envelope and discuss some of its
important properties. The polar envelope is a convolution
operation specialized to gauges, and is analogous to Moreau
envelope. We will highlight the important roles the polar
envelope plays in gauge duality and in the construction of
algorithms for gauge optimization.
This is joint work with Michael Friedlander and Ives Macêdo.

2019/06/18 – Talk by Reiichiro Kawai (The University of Sydney)

Date:  18th June (Tue) 16:00-17:00
Place: #235,  Engineering Bldg.6
Speaker:  Reiichiro Kawai (The University of Sydney)
https://sydney.edu.au/science/people/reiichiro.kawai.php

Title: Computable primal and dual bounds for stochastic control
Abstract:
We discuss the linear programming framework for stochastic
optimal control problems collectively via its duality
principle. The primal minimization corresponds to the
well-studied moment problem based upon a set of necessary
equality constraints on the occupation and boundary
measures, whereas the dual maximization is built on a set of
sufficient inequality constraints on the test polynomial
function with a flexible choice of optimality criteria. The
dual maximization is particularly effective in two senses:
Its single implementation yields a remarkably tight global
bound at once in the form of polynomial functions over the
whole problem domain; an optimal solution to a dual problem
can be reused directly as a feasible solution to different
dual problems, such as with different initial conditions,
objective functions and terminal times. The proposed
approach is capable of tackling extremely complex problems,
such as a combined optimal stopping and stochastic control
problem under a multivariate degenerate dynamics with jumps.
This talk is based on joint work with Chunxi Jiao.