Quasiconvex optimization

[Costas Skarakis]

Joachim, Lieven,

I am trying to solve a quasiconvex problem (generalized linear-
fractional to be precise) through convex feasibility problems and
bisection, as described in the book "Convex Optimization" by Boyd and
Vandenberghe.
Since my feasibility problem constraints are not all linear, I am
using the general solver cvxopt.solvers.cp. But as you say in the
documentation, the solver requires that the problem is solvable. As a
result, when the x I am checking is not feasible, instead of returning
status 'primal infeasible', the solver just goes through all maximum
allowed number of iterations and returns 'unknown'. I know that this
might return the correct result but it is slowing the computation
down.
I could change the 'maxiter' option, either statically, or somehow
dynamically to speed things up. But I was wondering if there was a
better way to go.

Costas

[Lieven Vandenberghe]

Costas,

To determine feasibility or infeasibility you can set up a "phase-1"
problem that is guaranteed to be feasible (see section 11.4 of the
Convex Optimization book). For example, to solve the feasibility
problem fi(x) <= 0, i=1,...,m, you can solve

minimize s
subject to fi(x) <= s, i=1,...,m
s >= -1

with variables x, s. This problem is always feasible (choose any x,
and s sufficiently large) and bounded below. Then you can determine
feasibility of the original problem from the sign of the optimal value
of s.

Lieven

[Costas Skarakis]

Lieven,

Thank you for your advice. It was indeed very helpful. However, I
still seem to be having problems with the general solver. Do all fi(x)
have to be smooth for the solver to work correctly? I understand it's
using gradient optimization methods and maybe if the gradient of some
fi is not continuous that might cause some problems. To be more
precise I am trying to do a generalised linear fractional problem, and
in particular, exercise 4.20 page 196 of the book. Is it the case that
cvxopt cannot handle this type of problems?

Thank you,
Costas

On Aug 7, 12:42 am, Lieven Vandenberghe

[Lieven Vandenberghe]

Costas,

The nonlinear solver requires that the functions are smooth (and
convex). The problem must also be primal and dual feasible.

Generalized linear-fractional problems can be solved using bisection
(ie, by implementing the algorithm on page 146). For the problem in
the exercise, the feasibility problem in step 2 of Algorithm 4.1 would
be:

Sk(p) >= t * ( Ik(p) + sigma_k ), k=1,...,n
plus the other linear inequalities in p.

This is a set of linear inequalities, so the feasibility problem can
be solved using the LP solver.

You may find the cvxmod package (cvxmod.net) very helpful. It
automates part of the problem specification for cvxopt.

Lieven