Abstract : Continuous optimization is a branch of optimization with applications in many fields. In view of their usefulness, in this minisymposium we will focus on: (i) nonlinear programming, where an objective function is minimized or maximized while satisfying some constraints; (ii) multiobjective optimization, where multiple objective functions are considered; and (iii) conic optimization, which deals with more general conic constraints. The goal of this minisymposium is to present some recent developments on those topics. In particular, proposals of efficient algorithms, advanced theoretical results and applications in machine learning will be discussed.
Organizer(s) : Yasushi Narushima, Ellen H. Fukuda, Bruno F. Lourenço
00815 (1/4) : 1C @A502 [Chair: Ellen Hidemi Fukuda]
[03738] Recent developments in multiobjective fast iterative shrinkage-thresholding algorithms
Format : Talk at Waseda University
Author(s) :
Ellen Hidemi Fukuda (Kyoto University)
Abstract : In this talk, we will present an overview of multiobjective proximal gradient methods, that solve problems of the type $\textrm{min} \, f(x)+g(x)$, where $f \colon \Re^n \to \Re^m$ is continuously differentiable and $g \colon \Re^n \to (\Re\cup\{+\infty\})^m$ is closed, proper and convex. We will also discuss their accelerated versions, including the multiobjective fast iterative shrinkage-thresholding algorithm (FISTA), monotone FISTA, and restarting FISTA. We will show the associated convergence results and some numerical experiments.
[04395] Adaptive Gradient-Based Method for Convex Optimization Problems Under Error Bounds
Format : Talk at Waseda University
Author(s) :
Masaru Ito (Nihon University)
Abstract : First-order methods for smooth convex optimization problems is a fundamental methodology for large-scale optimization arising in machine learning. We present an adaptive first-order method to find an approximate solution in terms of small gradient norm that does not require the problem dependent parameters and automatically accelerates under error bound condition like strong convexity. The iteration complexity to find an approximate solution is shown to be optimal.
Abstract : We introduce two new classes of accelerated distributed proximal conjugate gradient algorithms for multi-agent constrained optimization problems; given as minimization of a function decomposed as a sum of M number of smooth and M number of non-smooth functions over the common fixed points of M number of nonlinear mappings. Exploiting the special properties of the cost component function of the objective function and the nonlinear mapping of the constraint problem of each agent, a new inertial accelerated incremental and parallel computing distributed algorithms will be presented based on the combinations of computations of proximal, conjugate gradient and Halpern methods. Some numerical experiments and comparisons are given to illustrate our results.
[03850] Extensions of Constant Rank Qualification Constrains condition to Nonlinear Conic Programming
Format : Talk at Waseda University
Author(s) :
Hector Ramirez (Universidad de Chile)
Abstract : We present new constraint qualification conditions for nonlinear conic programming that extend some of the constant rank-type conditions from nonlinear programming. Specifically, we propose a general and geometric approach, based on the study of the faces of the cone, for defining a new extension of this condition to the conic context. We then compare these new conditions with some of the existing ones, including the nondegeneracy condition, Robinson’s constraint qualification, and the metric subregularity constraint qualification. The main advantage of the latter is that we are able to recast the strong second-order properties of the constant rank condition in a conic context. In particular, we obtain a second-order necessary optimality condition that is stronger than the classical one obtained under Robinson’s constraint qualification, in the sense that it holds for every Lagrange multiplier, even though our condition is independent of Robinson’s condition.
Anderson Ervino Schwertner (State University of Maringá)
Francisco Nogueira Calmon Sobral (State University of Maringá)
Abstract : The Low Order-Value Optimization (LOVO) problem seeks to minimize the minimum among a finite number of function values within a feasible set and has several applications, such as protein alignment and portfolio optimization, among others. In this work, we are interested in the constrained black-box LOVO problem, whose feasible set is convex, closed, and nonempty. We developed and implemented a derivative-free trust-region algorithm, and established global convergence and worst-case complexity results.
[04101] A Stochastic Variance Reduced Gradient using Second Order Information
Format : Talk at Waseda University
Author(s) :
Hardik Tankaria (Kyoto University)
Nobuo Yamashita (Kyoto University)
Abstract : In this talk, we consider to improve the stochastic variance reduced gradient (SVRG) method via incorporating the curvature information of the objective function. We propose to reduce the variance of stochastic gradients using the computationally efficient method of second order approximation by incorporating it into the SVRG. We also incorporate a (Barzilai-Borwein) BB-step size as its variant. We show linear convergence for not only the proposed method but also for the other existing SVRG variants that use second-order information as a variance reduction. We show the numerical experiments on the benchmark datasets and demonstrate the comparison of proposed methods with existing variance reduced methods.
[03875] Post-Processing with Projection and Rescaling Algorithm for Symmetric Cone Programs
Format : Talk at Waseda University
Author(s) :
Shinichi Kanoh (University of Tsukuba)
Akiko Yoshise (University of Tsukuba)
Abstract : We propose a post-processing algorithm for symmetric cone programs based on the Projection and Rescaling Algorithm (PRA). Our algorithm is devised to return a more accurate solution using the output solution from MOSEK solver and the PRA proposed by Kanoh & Yoshise (2021). Numerical experiments with SDPLIB instances show that our algorithm outputs a solution with a very small value of DIMACS error compared to the solution that MOSEK solver returned.
[04338] Random Subsapce Newton method for unconstrained non-convex optimization
Format : Talk at Waseda University
Author(s) :
Pierre-Louis Poirion (RIKEN -AIP)
Abstract : In this talk, we present a randomized subspace regularized Newton method for a non-convex function. We will be interested in particular to the local convergence rate of the method.
[01619] Generalized Levenberg-Marquardt method with oracle complexity bound and local convergence
Format : Talk at Waseda University
Author(s) :
Naoki Marumo (University of Tokyo)
Akiko Takeda (University of Tokyo)
Takayuki Okuno (Seikei University)
Abstract : The generalized Levenberg–Marquardt, abbreviated as LM, method has been developed for minimizing the sum of a possibly nonsmooth convex function and a smooth composite function. In this talk, we propose a new generalized LM method with three theoretical guarantees: iteration complexity bound, oracle complexity bound, and local convergence under a Holderian growth condition. These theoretical guarantees are achieved by use of an accelerated gradient method for solving convex subproblems.
[04603] Line search methods for nonconvex optimization in deep learning
Format : Online Talk on Zoom
Author(s) :
Yuki Tsukada (Meiji University)
Hideaki Iiduka (Meiji University)
Abstract : Stochastic gradient descent (SGD) using line search methods achieves high accuracies for several classification tasks in deep learning. Moreover, it can find optimal parameters for deep neural network models by using nonconvex optimization. This talk experimentally investigates the convergence speed of SGD using line search methods with several batch sizes. Our results indicate that the smaller the batch size is, the smaller the stochastic first-order oracle complexity becomes.
[01615] Proximal structured quasi-Newton method for nonlinear least squares with nonsmooth regularizer
Format : Talk at Waseda University
Author(s) :
Shummin Nakayama (The University of Electro-Communications)
Yasushi Narushima (Keio University)
Hiroshi Yabe (Tokyo University of Science)
Abstract : We consider composite minimization problems whose objective function is the sum of a nonlinear least squares formed smooth function and a nonsmooth regularizer. Structured quasi-Newton methods are efficient for solving nonlinear least squares problems and proximal Newton-type methods are efficient for composite minimization problems. In this talk, combining the above two methods, we propose a proximal structured quasi-Newton-type method. Finally, we present some numerical experiments to investigate the efficiency of the proposed method.
[03538] Newton-type proximal gradient method for multi-objective optimization with composite D.C. functions
Format : Talk at Waseda University
Author(s) :
Yasushi Narushima (Keio University)
Antoine J.V. Vadès (Keio University)
Hiroshi Ben (Keio University)
Abstract : In this talk, we propose a Newton-type proximal gradient method for multi-objective optimization whose objective functions are the sum of a continuously differentiable function and a Difference of Convex (D.C.) function. The proposed method is an extension of Newton-type proximal gradient methods for single-objective optimization. We give an algorithm of the proposed method with the Armijo-type line search and show its global convergence. Finally, we present some numerical results for comparison with the existing methods.
[04582] Sharp convex exact penalty formulations in statistical signal recovery
Format : Talk at Waseda University
Author(s) :
Alex Liheng Wang (Purdue University)
Lijun Ding (University of Wisconsin Madison)
Abstract : This talk presents a sample complexity vs. conditioning tradeoff in signal recovery problems including sparse recovery, low-rank matrix sensing, and phase retrieval. We introduce condition numbers related to the "sharpness" of these problems and show that they can be used to control the accuracy of the recovery procedure in the presence of noise and the convergence rates of a new first-order method. These condition numbers approach constants a small factor above the statistical thresholds.
[02314] Accelerating nuclear-norm regularized low-rank matrix optimization through Burer-Monteiro decomposition
Format : Talk at Waseda University
Author(s) :
Ching-pei Lee (Institute of Statistical Mathematics)
Ling Liang (National University of Singapore)
Tianyun Tang (National University of Singapore)
Kim-Chuan Toh (National University of Singapore)
Abstract : This work proposes a rapid algorithm, BM-Global, for nuclear-norm-regularized convex and low-rank matrix optimization problems. BM-Global efficiently decreases the objective value via low-cost steps leveraging the nonconvex but smooth Burer-Monteiro (BM) decomposition, while effectively escapes saddle points and spurious local minima ubiquitous in the BM form to obtain guarantees of fast convergence rates to the global optima of the original nuclear-norm-regularized problem through aperiodic inexact proximal gradient steps on it. The proposed approach adaptively adjusts the rank for the BM decomposition and can provably identify an optimal rank for the BM decomposition problem automatically in the course of optimization through tools of manifold identification. BM-Global hence also spends significantly less time on parameter tuning than existing matrix-factorization methods, which require an exhaustive search for finding this optimal rank. Extensive experiments on real-world large-scale problems of recommendation systems, regularized kernel estimation, and molecular conformation confirm that BM-Global can indeed effectively escapes spurious local minima at which existing BM approaches are stuck, and is a magnitude faster than state-of-the-art algorithms for low-rank matrix optimization problems involving a nuclear-norm regularizer.
[05168] The Goemans and Williamson Algorithm Extended to Fractional Cut Covering
Format : Talk at Waseda University
Author(s) :
Nathan Benedetto Proença (University of Waterloo)
Marcel K. de Carli Silva (University of São Paulo)
Cristiane Sato (Federal University of ABC Region)
Levent Tunçel (University of Waterloo)
Abstract : The fractional cut-covering number is the optimal value of a linear
programming relaxation for the problem of covering each edge by a set
of cuts.
By exploiting the relationship of this problem with the maximum cut
problem, we obtain a primal-dual extension to the celebrated work of
Goemans and Williamson, including an approximation algorithm and new
optimality certificates.
[01270] Solving graph equipartition SDPs on an algebraic variety
Format : Talk at Waseda University
Author(s) :
Tianyun Tang (National University of Singapore)
Kim-Chuan Toh (National University of Singapore)
Abstract : In this talk, we focus on using the Burer-Monteiro method to solve the graph equipartition SDP. The constraints of the low rank SDP problem is an algebraic variety with conducive geometric properties which we analyse. This allows us to develop an algorithm based on Riemannian optimization that can escape from a non-optimal singular point. Numerical experiments are conducted to verify the efficiency of our algorithm.
