The Corvinus Center for Operations Research (CCOR) invites you to CCOR Workshop on Interior Point Methods with three speakers, Yurii Nesterov, Tibor Illés and Anita Varga. The event will be organized in a hybrid way.
Venue: Corvinus University, Building E, Room: E.338
(You can ask Zoom link via email marianna dot eisenberg-nagy at uni-corvinus dot hu)
Date: February 16, 10.30-13.30
Keynote speaker: Yurii Nesterov (CORE/INMA, UCLouvain, Belgium)
Speakers: Tibor Illés (CCOR/ODI, Corvinus University) and
Anita Varga (Budapest University of Technology and Economics)
Program:
10.30-11.00: Tibor Illés: Simple approach for the interior point theory of Linear Complementarity Problems with P* matrices
11.00-11.30: Anita Varga: Interior point heuristics for a class of market exchange models
11.30-12.30: Lunch
12.30-13.30: Yurii Nesterov: Set-Limited Functions and Polynomial-Time Interior-Point Methods
Abstracts
Yurii Nesterov: Set-Limited Functions and Polynomial-Time Interior-Point Methods
In this talk, we revisit some elements of the theory of self-concordant functions. We replace the notion of self-concordant barrier by a new notion of set-limited function, which forms a wider class. We show that the proper set-limited functions ensure polynomial time complexity of the corresponding path-following method (PFM). Our new PFM follows a deviated path, which connects an arbitrary feasible point with the solution of the problem. We present some applications of our approach to the problems of unconstrained optimization, for which it ensures a global linear rate of convergence even for nonsmooth objective function.
Slides, video
Tibor Illés: Simple approach for the interior point theory of Linear Complementarity Problems with P* matrices
We consider Linear Complementarity Problems (LCPs) with P* matrices. The aim of this talk is to build up the interior point theory of LCPs, using only Newton-steps, without using the notation of logarithmic barrier function or heavy mathematics like the implicit function theorem. Based on the interior point assumption we prove the compactness and non-emptiness of the solution set of LCP, the existence and uniqueness of the central path. Furthermore, we show that the central path converges to a maximally complementary solution.
Anita Varga: Interior point heuristics for a class of market exchange models
Co-authors: Marianna E.-Nagy, Tibor Illés (Corvinus Centre for Operations Research, CIAS/ODI, Corvinus University of Budapest)
The Fisher type market exchange model (MEM) is a special case of the Arrow-Debreu type MEM. In this case, the players are divided into two groups, consumers and producers. Producers sell their products for money, and the consumers have an initial amount of money that they can use to buy a bundle of goods which maximizes their utility functions. In the talk we present different interior point heuristics for the skew-symmetric weighted linear complementarity problem (WLCP) introduced by Potra in 2012. The Fisher type market exchange model can be considered as a special WLCP, and this way the new algorithms can also be applied to the Fisher type MEM. We also present our numerical results and compare them with the interior point algorithms introduced by Ye and Potra.