Fall 2015 Calendar

Octo­ber 13 [CORE]
Michael Over­ton, Courant Insti­tute of Math­e­mat­i­cal Sci­ences, New York Uni­ver­sity
Non­smooth, Non­con­vex Opti­miza­tion: Algo­rithms and Examples

Octo­ber 20
Sasha Aravkin, Depart­ment of Applied Math­e­mat­ics, Uni­ver­sity of Wash­ing­ton
An Inte­rior Point Approach for Data Science

Octo­ber 27
Damek Davis, Depart­ment of Math­e­mat­ics, Uni­ver­sity of Cal­i­for­nia, Los Angeles

Novem­ber 10
James Saun­der­son, Depart­ment of Elec­tri­cal Engi­neer­ing, Uni­ver­sity of Washington

Decem­ber 8
Vic­tor Falgas-Ravry, Depart­ment of Math­e­mat­ics, Van­der­bilt University

An Interior Point Approach for Data Science, Sasha Aravkin

Tues­day, Octo­ber 20, 2015, 4:00 pm

Sasha Aravkin, Uni­ver­sity of Wash­ing­ton .
An Inte­rior Point Approach for Data Science

Abstract: Many impor­tant appli­ca­tions can be for­mu­lated as large-scale opti­miza­tion prob­lems, includ­ing clas­si­fi­ca­tion in machine learn­ing, data assim­i­la­tion in weather pre­dic­tion, inverse prob­lems, and med­ical and seis­mic imag­ing. While first-order meth­ods have proven widely suc­cess­ful in recent years, recent devel­op­ments sug­gest that matrix-free second-order meth­ods, such as interior-point meth­ods, can be competitive.

We first develop a mod­el­ing frame­work for a wide range of prob­lems, and show how con­ju­gate rep­re­sen­ta­tions can be exploited to design an inte­rior point approach for this class. We then show sev­eral appli­ca­tions, with empha­sis on mod­el­ing and prob­lem struc­ture, and end by dis­cussing exten­sions to large-scale problems.

Michael Overton; Nonsmooth, Nonconvex Optimization: Algorithms and Examples

CORE Series
Tues­day, Octo­ber 13, 2015, 4:00 pm
Raitt Hall (RAI), Room 121
Michael Over­ton, New York Uni­ver­sity .
Non­smooth, Non­con­vex Opti­miza­tion: Algo­rithms and Examples

Abstract: In many appli­ca­tions one wishes to min­i­mize an objec­tive func­tion that is not con­vex and is not dif­fer­en­tiable at its min­i­miz­ers.
We dis­cuss two algo­rithms for min­i­miza­tion of non­smooth, non­con­vex func­tions. Gra­di­ent Sam­pling is a sim­ple method that, although com­pu­ta­tion­ally inten­sive, has a nice con­ver­gence theory.The method is robust and the con­ver­gence the­ory has recently been extended to con­strained prob­lems. BFGS is a well known method, devel­oped for smooth prob­lems, but which is remark­ably effec­tive for non­smooth prob­lems too. Although our the­o­ret­i­cal results in the non­smooth case are quite lim­ited, we have made some remark­able empir­i­cal obser­va­tions and have had broad suc­cess in appli­ca­tions. Lim­ited Mem­ory BFGS is a pop­u­lar exten­sion for large prob­lems, and it is also applic­a­ble to the non­smooth case, although our expe­ri­ence with it is more mixed.
Through­out the talk we illus­trate the ideas through exam­ples,
some very easy and some very chal­leng­ing. Our work is
with Jim Burke (U. Wash­ing­ton) and Adrian Lewis (Cornell).

Bio: Michael L. Over­ton is Pro­fes­sor of Com­puter Sci­ence and Math­e­mat­ics at the Courant Insti­tute of Math­e­mat­i­cal Sci­ences, New York Uni­ver­sity. He received his Ph.D. in Com­puter Sci­ence from Stan­ford Uni­ver­sity in 1979.
He is a fel­low of SIAM (Soci­ety for Indus­trial and Applied Math­e­mat­ics) and of the IMA (Insti­tute of Math­e­mat­ics and its Appli­ca­tions, UK). He served on the Coun­cil and Board of Trustees of SIAM from 1991 to 2005, includ­ing a term as Chair of the Board from 2004 to 2005. He served as Editor-in-Chief of SIAM Jour­nal on Opti­miza­tion from 1995 to 1999 and of the IMA Jour­nal of Numer­i­cal Analy­sis from 2007 to 2008, and was the Editor-in-Chief of the MPS(Mathematical Pro­gram­ming Society)-SIAM joint book series from 2003 to 2007. He is cur­rently an edi­tor of SIAM Jour­nal on Matrix Analy­sis and Appli­ca­tions, IMA Jour­nal of Numer­i­cal Analy­sis, Foun­da­tions of Com­pu­ta­tional Math­e­mat­ics, and Numerische Math­e­matik. His research inter­ests are at the inter­face of opti­miza­tion and
lin­ear alge­bra, espe­cially non­smooth opti­miza­tion prob­lems involv­ing eigen­val­ues, pseu­dospec­tra, sta­bil­ity and robust con­trol. He is the author of “Numer­i­cal Com­put­ing with IEEE Float­ing Point Arith­metic” (SIAM, 2001).

Jonathan Kelner; Bridging the Numerical and the Combinatorial: Emerging Tools, Techniques, and Design Principles for Graph Algorithms

CORE Series
May 19, 2015, 4:00pm
EEB 125
Jonathan Kel­ner, Depart­ment of Math­e­mat­ics, MIT.
Bridg­ing the Numer­i­cal and the Com­bi­na­to­r­ial: Emerg­ing Tools, Tech­niques, and Design Prin­ci­ples for Graph Algorithms

Abstract: Flow and cut prob­lems on graphs are among the most fun­da­men­tal and exten­sively stud­ied prob­lems in Oper­a­tions Research and Opti­miza­tion, play­ing a foun­da­tional role in both the the­ory and prac­tice of algo­rithm design. While the clas­si­cal algo­rithms for these prob­lems were largely based on com­bi­na­to­r­ial approaches, the past sev­eral years have wit­nessed the emer­gence of a pow­er­ful col­lec­tion of new tech­niques based on geom­e­try, spec­tral graph the­ory, com­pu­ta­tional lin­ear alge­bra, ran­dom­iza­tion, and iter­a­tive meth­ods from con­tin­u­ous opti­miza­tion. These numer­i­cal tech­niques have allowed researchers to pro­vide bet­ter prov­able algo­rithms for a wide range of graph prob­lems, in some cases break­ing algo­rith­mic bar­ri­ers that had stood for sev­eral decades.

The rela­tion­ship between graph the­ory and numer­i­cal analy­sis has proven fruit­ful in the other direc­tion as well. In addi­tion to pro­vid­ing numer­i­cal tech­niques for graph algo­rithms, it has given rise to new com­bi­na­to­r­ial tech­niques for com­pu­ta­tional lin­ear alge­bra. In par­tic­u­lar, it has led to fast algo­rithms for Lapla­cian lin­ear sys­tems, which have broad appli­ca­tions in numer­i­cal sci­en­tific com­put­ing, machine learn­ing, oper­a­tions research, com­puter vision, and net­work analy­sis, among others.

In this talk, I dis­cuss some of the recur­ring themes that arise in this con­flu­ence of fields. I will apply these to sketch algo­rithms that run in close to lin­ear time for two basic algo­rith­mic prob­lems: solv­ing Lapla­cian lin­ear sys­tems and find­ing approx­i­mately max­i­mum flows on undi­rected graphs.

The talk will be based on joint work with Yin Tat Lee, Aaron Sid­ford, Lorenzo Orec­chia, and Zeyuan Zhu.

Bio: Jonathan Kel­ner is an Asso­ciate Pro­fes­sor of Applied Math­e­mat­ics in the MIT Depart­ment of Math­e­mat­ics and a mem­ber of the MIT Com­puter Sci­ence and Arti­fi­cial Intel­li­gence Lab­o­ra­tory (CSAIL). His research focuses on the appli­ca­tion of tech­niques from pure math­e­mat­ics to the solu­tion of fun­da­men­tal prob­lems in algo­rithms and com­plex­ity the­ory. He was an under­grad­u­ate at Har­vard Uni­ver­sity, and he received his Ph.D. in Com­puter Sci­ence from MIT in 2006. Before join­ing the MIT fac­ulty, he spent a year as a mem­ber of the Insti­tute for Advanced Study. He has received a vari­ety of awards for his work, includ­ing an NSF CAREER Award, an Alfred P. Sloan Research Fel­low­ship, the Best Paper Awards at STOC 2011, SIGMETRICS 2011, and SODA 2014, the Harold E. Edger­ton Fac­ulty Achieve­ment Award, and the MIT School of Sci­ence Teach­ing Prize.

Frank Permenter; Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone

May 5, 2015, 2:00pm
THO 119
Frank Per­me­nter, EECS Depart­ment, MIT.
Par­tial facial reduc­tion: sim­pli­fied, equiv­a­lent SDPs via approx­i­ma­tions of the PSD cone

Abstract: Semi­def­i­nite pro­grams (SDPs) aris­ing in prac­tice fre­quently have no inte­rior and hence can be refor­mu­lated as smaller prob­lems more eas­ily solved. Unfor­tu­nately, find­ing these refor­mu­la­tions requires exe­cut­ing a facial reduc­tion pro­ce­dure, which is typ­i­cally com­pu­ta­tion­ally expen­sive. In this talk, we develop a prac­ti­cal facial reduc­tion pro­ce­dure based on com­pu­ta­tion­ally effi­cient approx­i­ma­tions of the pos­i­tive semi­def­i­nite cone. The pro­posed method sim­pli­fies SDPs with no inte­rior by solv­ing a sequence of eas­ier opti­miza­tion prob­lems (e.g. lin­ear pro­grams) and could be a use­ful pre-processing step for SDP solvers. We demon­strate effec­tive­ness of the method on SDPs aris­ing in prac­tice, and describe our publicly-available soft­ware imple­men­ta­tion. We also give a post-processing pro­ce­dure for dual solu­tion recov­ery that gen­er­ally applies to facial-reduction-based pre-processing tech­niques. Joint work with Pablo Parrilo.

Joel Tropp; Applied Random Matrix Theory

CORE Series
Tues­day, April 28, 2015, 4pm
EEB 125
Joel Tropp, Cal­tech.
Applied Ran­dom Matrix Theory

Abstract: Ran­dom matri­ces now play a role in many areas of the­o­ret­i­cal, applied, and com­pu­ta­tional math­e­mat­ics. There­fore, it is desir­able to have tools for study­ing ran­dom matri­ces that are flex­i­ble, easy to use, and pow­er­ful. Over the last fif­teen years, researchers have devel­oped a remark­able fam­ily of results, called matrix con­cen­tra­tion inequal­i­ties, that bal­ance these criteria.

This talk offers an invi­ta­tion to the field of matrix con­cen­tra­tion inequal­i­ties. The pre­sen­ta­tion begins with some his­tory of ran­dom matrix the­ory, and it intro­duces an impor­tant prob­a­bil­ity inequal­ity for scalar ran­dom vari­ables. It describes a flex­i­ble model for ran­dom matri­ces that is suit­able for many prob­lems, and it dis­cusses one of the most impor­tant matrix con­cen­tra­tion results, the matrix Bern­stein inequal­ity. The talk con­cludes with some appli­ca­tions drawn from algo­rithms, com­bi­na­torics, sta­tis­tics, sig­nal pro­cess­ing, sci­en­tific com­put­ing, and beyond.

Bio: Joel A. Tropp is Pro­fes­sor of Applied & Com­pu­ta­tional Math­e­mat­ics at the Cal­i­for­nia Insti­tute of Tech­nol­ogy. He earned his PhD degree in Com­pu­ta­tional Applied Math­e­mat­ics from the Uni­ver­sity of Texas at Austin in 2004. Dr. Tropp’s work lies at the inter­face of applied math­e­mat­ics, elec­tri­cal engi­neer­ing, com­puter sci­ence, and sta­tis­tics. This research con­cerns the the­o­ret­i­cal and com­pu­ta­tional aspects of data analy­sis, sparse mod­el­ing, ran­dom­ized lin­ear alge­bra, and ran­dom matrix the­ory. Dr. Tropp has received sev­eral major awards for young researchers, includ­ing the 2007 ONR Young Inves­ti­ga­tor Award and the 2008 Pres­i­den­tial Early Career Award for Sci­en­tists and Engi­neers. He is also the win­ner of the 6th Vasil A. Popov prize and the 2011 Mon­roe H. Mar­tin prize.

Andreas Griewank; Lipschitzian Piecewise Smooth Optimization

April 14, 2015, 4:00pm
GUG 220
Andreas Griewank, Insti­tut für Math­e­matik, Hum­boldt Uni­ver­sity of Berlin.
Lip­schitz­ian Piece­wise Smooth Optimization

Abstract: We address the prob­lem of min­i­miz­ing objec­tives from the class of piece­wise dif­fer­en­tiable func­tions whose non­smooth­ness can be encap­su­lated in the absolute value func­tion. They pos­sess local piece­wise lin­ear approx­i­ma­tions with a dis­crep­ancy that can be bounded by a qua­dratic prox­i­mal term. This over­es­ti­mat­ing local model is con­tin­u­ous but gen­er­ally non­con­vex. It can be gen­er­ated in its {\em abs-normal-form} by a minor exten­sion of stan­dard algo­rith­mic dif­fer­en­ti­a­tion tools. Here we demon­strate how the local model can be min­i­mized by a bun­dle type method, which ben­e­fits from the avail­abil­ity of addi­tional {\em gray-box-information} via the abs-normal form. In the con­vex case our algo­rithms real­izes the con­sis­tent steep­est descent tra­jec­tory for which finite con­ver­gence was estab­lished by Hirri­art Urruty and Claude Lemarechal, specif­i­cally cov­er­ing counter exam­ples where steep­est descent with exact line-search famously fails.