MINOS Superbasic Variables - Primer

[Rick]

Hello:

Would someone like offer a brief conceptual primer on superbasic variables and how they relate to MINOS, poorly scaled NLPs, and termination criteria? There doesn't appear to be much available information online, or in the AMPL book, that is conceptual and concise. Some particular questions are listed below.

What are superbasic variables?

How are they used in MINOS?

What does the ampl output - "cannot find superbasic to replace basic variable" indicate?

What are the common causes of this termination message?

what is the impact of poorly scaled problems on the set of superbasic variables?

Any helpful thoughts or comments about how to interpret or troubleshoot a model that yields the output message listed above.

Regards,
Rick

[Robert Fourer]

The concept of superbasic variables as used by MINOS is described briefly in the AMPL/MINOS documentation (www.ampl.com/BOOKLETS/ampl-minos.pdf):

 

"For mathematical programs that are nonlinear in the objective but linear in the constraints, MINOS employs a reduced gradient approach, which can be viewed as a generalization of the simplex algorithm. In addition to the basic variables, the algorithm maintains a subset of superbasic variables that also may vary between their bounds. An iteration attempts to reduce the objective within the subspace of basic and superbasic variables, employing a quasi-Newton algorithm — adapted from unconstrained nonlinear optimization — to select a search direction and step length. When no further progress can be made with the current collection of basic and superbasic variables, a new superbasic variable is chosen from among the nonbasic ones; when a basic or superbasic variables encounters a bound as a result of a step, it is made nonbasic."

 

In the case of a basic variable encountering a bound as a result of a step, and being made nonbasic, an appropriate superbasic variable must be chosen to replace it.  If no appropriate superbasic variable can be found, then you would get the error message that you are seeing.

 

There's more detailed information in this User's Guide to MINOS and in several papers, for which you will find links at www.stanford.edu/group/SOL/minos.htm.  Also you may want to directly contact MINOS developer Michael Saunders <saun...@stanford.edu> to discuss MINOS performance issues in more depth.

 

Bob Fourer

am...@googlegroups.com

 

 

From: am...@googlegroups.com [mailto:am...@googlegroups.com]

On Behalf Of Rick
Sent: Wednesday, July 17, 2013 2:47 PM
To: am...@googlegroups.com
Subject: [AMPL 7254] MINOS Superbasic Variables - Primer

[Michael Saunders]

Thanks for helping with this answer Bob.

I meant to reply to Rick, but I'm traveling in France.

The main concept about superbasic variables is that

NLP solutions may not be at a vertex of the feasible region.

For LPs, simplex has n-m nonbasic variables "frozen" at their

current value (typically an upper or lower bound), and the m

basic variables have values that make Ax = b.

When simplex improves the objective by moving a nonbasic

variable away from its current value, that variable wants to

move as far as possible (because the objective is linear).

Normally some basic variable reaches a bound and becomes

nonbasic, and gets replaced in the basis by the nonbasic that

moved.

For nonlinear problems, the nonbasic variable being moved

might want to stop in midair (with improved objective).  If it

went further, the objective would no longer improve.  Superbasic

variables are the ones that stop in midair.  Every iteration moves

them as well as the basic variables.  If a basic variable reaches

a bound, it becomes nonbasic as in simplex, but it has to be

replaced by a superbasic variable.

It's *extremely rare* for minos to say it can't find a suitable

superbasic to replace a basic variable.  It means all of the

columns associated with superbasics would give you an

essentially singular basis if any of them replaced the basic that

just reached a bound.

The most likely reason is poorly scaled variables and constraints.

If your NLP has linear constraints, you should turn on Scale option 2

(scale all variables).

If you have nonlinear constraints, automatic scaling is much more

problematical.  If you have a *good starting point*, you could try

Scale option 2 again.  It will compute scales from the Jacobian

(derivatives of the constraints) at the *first point that satisfies the

linear constraints*.  The Jacobian at that point may or may not be

similar to the Jacobian at an optimal solution.

We need to know more about your model to give any further advice.

Good luck,

Michael

--
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ampl+uns...@googlegroups.com.
To post to this group, send email to am...@googlegroups.com.
Visit this group at http://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/groups/opt_out.