solving convex almost bilevel linear programs using cvxopt

[Geoffrey Irving]

Hello,

I'm investigating Nash equilibria in simplified poker games, which
lead to convex programs of the form

min c^T x
s.t. x >= 0
Bx <= b
Gx in C

where C is a convex set of the form

z in C iff forall y>=0, D y = d => z^T y >= 1

C is actually polyhedral, but (at least naively) would require an
exponential number of linear constraints to describe explicitly. As
far as I know, C can't be expressed with standard convex sets (second
order cones, semidefinite cones, etc.). However, we can evaluate
properties such as the distance from a point to the boundary of C
efficiently using linear programming, so the whole program seems
amenable to interior point methods.

Incidentally, this kind of program is a special case of bilevel linear
programming, but is convex (unlike general bilevel linear programming)
and therefore not NP-hard.

Is it possible to express such a program in current cvxopt? The
nonlinear optimization routine doesn't seem to apply, since the C
constraint isn't twice continuously differentiable. Alternatively,
how difficult would it be to extend cvxopt to support this type of
constraint?

Thanks,
Geoffrey

[Geoffrey Irving]

I asked elsewhere about this, and learned that my program can be
converted into a single standard linear program by applying duality to
the inner problem. Thus, I'm all set.

Thanks,
Geoffrey