## 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

**Abstract:**

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**

**Abstract:**

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.