Timezone: »
We consider solving nonlinear optimization problems with equality constraints. We propose a randomized algorithm based on sequential quadratic programming (SQP) with a differentiable exact augmented Lagrangian as the merit function. In each SQP iteration, we solve the Newton system inexactly via iterative randomized sketching. The accuracy of the inexact solution and the penalty parameter of the augmented Lagrangian are adaptively controlled in the algorithm to ensure that the inexact random search direction is a descent direction of the augmented Lagrangian. This allows us to establish global convergence almost surely. Moreover, we show that a unit stepsize is admissible for the inexact search direction provided the iterate lies in a neighborhood of the solution. Based on this result, we show that the proposed algorithm exploits local linear convergence. We apply the algorithm on benchmark nonlinear problems in CUTEst test set and on constrained logistic regression with datasets from LIBSVM to demonstrate its superior performance.
Author Information
Ilgee Hong (University of Chicago)
Sen Na (ICSI and University of California, Berkeley)
Mladen Kolar (U Chicago)
More from the Same Authors
-
2022 : Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems »
Yuchen Fang · Sen Na · Mladen Kolar -
2022 : Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models: First-Order Stationarity »
Yuchen Fang · Sen Na · Mladen Kolar -
2022 : Poster Session 2 »
Jinwuk Seok · Bo Liu · Ryotaro Mitsuboshi · David Martinez-Rubio · Weiqiang Zheng · Ilgee Hong · Chen Fan · Kazusato Oko · Bo Tang · Miao Cheng · Aaron Defazio · Tim G. J. Rudner · Gabriele Farina · Vishwak Srinivasan · Ruichen Jiang · Peng Wang · Jane Lee · Nathan Wycoff · Nikhil Ghosh · Yinbin Han · David Mueller · Liu Yang · Amrutha Varshini Ramesh · Siqi Zhang · Kaifeng Lyu · David Yunis · Kumar Kshitij Patel · Fangshuo Liao · Dmitrii Avdiukhin · Xiang Li · Sattar Vakili · Jiaxin Shi -
2022 Poster: A Nonconvex Framework for Structured Dynamic Covariance Recovery »
Katherine Tsai · Mladen Kolar · Sanmi Koyejo -
2021 Poster: Global Convergence of Online Optimization for Nonlinear Model Predictive Control »
Sen Na -
2017 Workshop: Advances in Modeling and Learning Interactions from Complex Data »
Gautam Dasarathy · Mladen Kolar · Richard Baraniuk -
2017 Poster: The Expxorcist: Nonparametric Graphical Models Via Conditional Exponential Densities »
Arun Suggala · Mladen Kolar · Pradeep Ravikumar -
2016 : Mladen Kolar. Post-Regularization Inference for Dynamic Nonparanormal Graphical Models. »
Mladen Kolar -
2016 Poster: Statistical Inference for Pairwise Graphical Models Using Score Matching »
Ming Yu · Mladen Kolar · Varun Gupta -
2014 Workshop: Modern Nonparametrics 3: Automating the Learning Pipeline »
Eric Xing · Mladen Kolar · Arthur Gretton · Samory Kpotufe · Han Liu · Zoltán Szabó · Alan Yuille · Andrew G Wilson · Ryan Tibshirani · Sasha Rakhlin · Damian Kozbur · Bharath Sriperumbudur · David Lopez-Paz · Kirthevasan Kandasamy · Francesco Orabona · Andreas Damianou · Wacha Bounliphone · Yanshuai Cao · Arijit Das · Yingzhen Yang · Giulia DeSalvo · Dmitry Storcheus · Roberto Valerio -
2013 Workshop: Modern Nonparametric Methods in Machine Learning »
Arthur Gretton · Mladen Kolar · Samory Kpotufe · John Lafferty · Han Liu · Bernhard Schölkopf · Alexander Smola · Rob Nowak · Mikhail Belkin · Lorenzo Rosasco · peter bickel · Yue Zhao -
2012 Workshop: Modern Nonparametric Methods in Machine Learning »
Sivaraman Balakrishnan · Arthur Gretton · Mladen Kolar · John Lafferty · Han Liu · Tong Zhang -
2011 Poster: Minimax Localization of Structural Information in Large Noisy Matrices »
Mladen Kolar · Sivaraman Balakrishnan · Alessandro Rinaldo · Aarti Singh -
2011 Spotlight: Minimax Localization of Structural Information in Large Noisy Matrices »
Mladen Kolar · Sivaraman Balakrishnan · Alessandro Rinaldo · Aarti Singh -
2009 Poster: Time-Varying Dynamic Bayesian Networks »
Le Song · Mladen Kolar · Eric Xing -
2009 Spotlight: Time-Varying Dynamic Bayesian Networks »
Le Song · Mladen Kolar · Eric Xing -
2009 Poster: Sparsistent Learning of Varying-coefficient Models with Structural Changes »
Mladen Kolar · Le Song · Eric Xing -
2009 Spotlight: Sparsistent Learning of Varying-coefficient Models with Structural Changes »
Mladen Kolar · Le Song · Eric Xing