Is there a way to solve "nested" optimization problems in AMPL?

[at]

I have in mind the following type of problem:

(1)

min_{x,y} f(x,y)

subject to g(y) <= 0

where both x and y are variables of the problem.

In the applications I have in mind, optimizing f over both x and y subject to g(y) <= 0 is difficult because the problem is non-convex and y is a high-dimensional variable.

However, I also happen to know that for a fixed value of x, the problem is convex (in my case, linear) in the remaining variables y.

That is, for each fixed value of x^{*}, I know that it is very easy to solve:

(2)

min_{y} f(x^{*}, y)

subject to g(y) <= 0

I would like to exploit the knowledge that (2) is easy to solve when solving (1). If I let h(x) denote the optimal value in (2) as a function of the fixed point x, then the problem would be

(3)

min_{x} h(x)

This will still be a non-convex problem, but I expect that it should be easier to solve than trying to solve (1) directly, since it exploits the knowledge that the "nested" problem (2) is easy to solve. (Applications like this are fairly common in statistics, for example "profiled likelihood" types of problems.)

I can see how to solve (3) in a "standard" language like C++ or Python by writing a function for the inner optimization problem. However, I can't see how to do this in AMPL. Is there a way?

[Robert Fourer]

The only way that (3) could be described in the representation that AMPL sends to solvers would be to implement h(x) as a user-defined C function, which itself would invoke an AMPL process at each call to solve the linear program (2).  That would be quite a stretch of AMPL's user-defined function technology, however, and might be too inefficient.

As an alternative you could use an AMPL API to program the interaction between AMPL and a nonlinear solver.  Depending how the solver is set up, you might alternate between making calls through the AMPL API to solve the linear program, and making calls to a nonlinear solver's API to determine a new iterate; or your program might receive callbacks from a nonlinear solver and use the AMPL API to solve the LP the function values that are returned. Currently there are APIs for Java and MATLAB (http://ampl.com/products/api/) and one for C++ will be released very soon now.

Bob Fourer
am...@googlegroups.com

[at]

Thanks for the information Bob. I think I should be able to come up with a reasonable implementation by using the API.