Contributed Session Tue.1.MA 042

Tuesday, 10:30 - 12:00 h, Room: MA 042

Cluster 11: Integer & mixed-integer programming [...]

Non-standard optimization methods


Chair: Dennis Egbers



Tuesday, 10:30 - 10:55 h, Room: MA 042, Talk 1

Roman A. Polyak
Nonlinear equilibrium for optimal resource allocation


When linear programming (LP) is used for optimal allocation limited resources the prices for goods and the resources availability are given priory and independent on the production output and prices for the resources. Nonlinear equilibrium (NE) eliminates this basic drawback of LP allowing finding prices for goods and resources availability consistent with the production output and prices for the resources. Finding NE is equivalent to solving a variation inequality (VI) on the Cartesian product of the primal and dual non negative octants, projection on which is a very simple operation. We consider two methods: projected pseudo-gradient (PPG) and extra pseudo-gradient (EPG), for which the projection on the feasible set is the main operation. Both PPG and EPG can be viewed as pricing mechanisms for establishing economic equilibrium. We established convergence, proved global Q-linear rate and estimated complexity of both methods under various assumptions on the input data.



Tuesday, 11:00 - 11:25 h, Room: MA 042, Talk 2

Dennis Egbers
Some remarks on the LP-Newton method

Coauthors: Satoru Fujishige, Uwe Zimmermann


Nowadays it is well known that linear programming problems can be solved in weakly polynomial time. Still unresolved is the question whether there exists a strongly polynomial algorithm for linear programming or not. In 2009 Fujishige discussed some alternative approach inspired by successful application in submodular optimization in order to achieve some advancement in this direction which stimulated our research.
As shown by, i.e., Papadimitreou and Stieglitz, linear programming problems may w.l.o.g. be considered to be bounded. It is possible to reduce bounded LP to a sequence of LPs on zonotopes which can easily be solved by a greedy algorithm. The approach presented is based on the zonotope formulation and can be described as a Newton-type algorithm using a sequence of minimum norm point calculations iterating to the optimum. Based on previous work by Fujishige et al. we will present theoretical as well as practical results on the performance of the algorithm. In particular, different approaches for calculating the minimum norm point will be compared with respect to certain drawbacks in a previously applied algorithm of Wolfe.


  There are three major facts that should be watched out for in all payday loans in the United States. But at the same time, it acts only with sexual arousal. Cheap Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.