Contributed Session Fri.3.H 0107

Friday, 15:15 - 16:45 h, Room: H 0107

Cluster 16: Nonlinear programming [...]

Decomposition and relaxation methods


Chair: Oleg Burdakov



Friday, 15:15 - 15:40 h, Room: H 0107, Talk 1

Quentin Louveaux
Relaxation schemes for the evaluation of a policy in batch mode reinforcement learning

Coauthors: Bernard Boigelot, Damien Ernst, Raphaƫl Fonteneau


We study the min max optimization problem introduced for computing policies for batch mode reinforcement learning in a deterministic setting. First, we show that this problem is NP-hard. In the two-stage case, we provide two relaxation schemes. The first relaxation scheme works by dropping some constraints in order to obtain a problem that is solvable in polynomial time. The second relaxation scheme, based on a Lagrangian relaxation where all constraints are dualized, leads to a conic quadratic programming problem. We also theoretically prove and empirically illustrate that both relaxation schemes provide better results than those given previously for the same problem.



Friday, 15:45 - 16:10 h, Room: H 0107, Talk 2

Oleg Burdakov
An approach to solving decomposable optimization problems with coupling constraints

Coauthors: John C. Dunn, Mike Kalish


We consider a problem of minimizing f1(x)+f2(y) over
x ∈ X ⊆ Rn and y ∈ Y ⊆ Rm subject to
a number of extra coupling constraints of the form g1(x)g2(y) ≥ 0.
Due to these constraints, the problem may have a large number
of local minima.
For any feasible combination of signs of g1(x) and g2(y),
the coupled problem is decomposable, and the resulting two problems
are assumed to be easily solved.
An approach to solving the coupled problem is presented. We apply
it to solving coupled monotonic regression problems arising in
experimental psychology.


  There are three major facts that should be watched out for in all payday loans in the United States. What can cause long-term use of Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.