Description
Workshop of the Corvinus Center for Operation Research (CCOR)
Keynote speaker: Yurii Nesterov (CORE/INMA, UCLouvain, Belgium)
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
Az előadásokat hibrid formában szervezzük, online Zoomon lehet majd csatlakozni.
For Zoom access please contact E.-Nagy Marianna (marianna.eisenberg-nagy[at]uni-corvinus.hu).
Abstracts:
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.
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.