|
Below are a few examples illustrating typical Dr Ampl output.
The Wächter-Biegler example
^
The Wächter-Biegler example
See Failure of global convergence for a class
of interior-point methods for nonlinear programming,
Andreas Wächter and Larry Biegler, Mathematical Programming A,
number 88, pp. 565-574, 2000.
The following model represents the three variables problem
|
minimize
|
x1
|
|
subject to
|
x12 - x2 + a = 0,
|
|
|
x1 - x3 - b = 0,
|
|
|
x2 ≥ 0,
|
|
|
x3 ≥ 0,
|
where a and b ≥ 0 are real parameters.
model;
var x {1..3};
param a;
param b >= 0;
minimize objective:
x[1];
subject to equality1:
x[1]^2 - x[2] + a = 0;
subject to equality2:
x[1] - x[3] - b = 0;
subject to bound1:
x[2] >= 0;
subject to bound2:
x[3] >= 0;
The model is initialized with the following data
data;
let a:= 1;
let b:= 1;
# Choose starting point to satisfy the WB assumptions
let x[2] := 1; # Anything > 0
let x[3] := 1; # Anything > 0
if a <= 0 then {
let x[1] := -sqrt( x[2] - a ) - 1;
} else {
let x[1] := - 3*a/(4*b) - sqrt( 9*a^2/(16*b^2) + a/2 + x[2] + 3*a*x[3]/(2*b) ) - 1;
}
In this model, Choosing a = -b2 violates
second-order sufficiency and strict complementarity.
The model was decoded using the following AMPL commands
option presolve 10; # Perform presolve operations
option show_stats 1; # Display info while decoding
option var_bounds 2; # Transmit tightest bounds on variables
option nl_comments 2; # Display info in nl file
option auxfiles rc; # Generate variables and constraints names
model wb.mod;
data wb.dat;
write gwb; # Write nl file
We walk through the output of Dr Ampl step by step. The output
is organized in a sequence of stages.
In the first stage, statistics on the problem, its variables and its constraints
are gathered. A number indicated between square brackets is a total, e.g., the
total number of constraints, and the numbers below it should sum up exactly to
its value. From these results, we see how many variables appear nonlinearly in
the objectives and constraints, whether initial values are given, etc.
Finally, we obtain the number of nonzero elements in the constraints Jacobian
and the objective(s) gradient(s).
DrAmpl:: Problem wb
Stage 1: Problem Statistics
Problem statistics Variables statistics
------------------ --------------------
Objectives: [1 ] Variables: [3 ]
Nonlinear objectives: 0 Continuous: 3
Linear objectives: 1 Binary: 0
Constraints: [2 ] Other integer: 0
Range: 0 Variables
Equality: 2 bounded above only: 0
Inequality: 0 | below only: 3
Spurious: 0 |_ above and below: 0
------------------ fixed: 0
Nonlinear general: 0 free : 0
Quadratic: [1 ]
Range 0
Equality 1
Inequality 0
Spurious 0
Linear general: 1
Nonlinear network: 0 Nonlinearity statistics
Linear network: 0 -----------------------
Complementarity cond: [0 ] Variables appearing nonlinearly: [1 ]
Linear: 0 in objectives only: 0
Nonlinear: 0 in constraints only: 1
Provides initial point: Yes in both: 0
Provides initial dual point: Yes Integer vars appearing nonlinearly: [0 ]
in objectives only: 0
Sparsity statistics in constraints only: 0
-------------------
nnz in Jacobian: 4
nnz in obj. gradients: 1
In the second stage, Dr. Ampl matches the features of this problem with
the description of an optimization tree. Information is displayed at it is
gathered. The final verdict appears last. We stress that some names were made
up to save space. In the present case, the problem is a "quadratically-constrained
LP", i.e., a problem with a linear objective and quadratic constraints. Looking
at the model above, that is indeed the nature of the problem.
Stage 2: Problem Classification
Problem type
-------------
-Problem has bounded variables
-Problem has linear constraints
-Problem has quadratic constraints
Analyzing problem using objective #0
------------------------------------
-This objective is linear
-Problem is a constrained NLP
-Problem seems to be an LP
-Problem seems to be a quadratically-constrained LP
with equality constraints
with bounds
Problem class code : 42
In Stage 3, we attempt to find lower and upper bounds on
the objective function based on known bounds on the variables
(if any). This is what we refer to as forward mode.
In the present case, the objective is simply
x1 and the model does not define any
explicit bound on this variable. So how can Dr. Ampl
determine that 1 is a lower bound on the objective value? The answer
lies in the AMPL script above.
Since b=1, the second equality constraint becomes
x1 = 1 + x3 and since there is an
explicit nonnegativity bound on x3, we obtain
x1 ≥ 1. It is this type of tighter bound
on the variables that AMPL transmits to the solver by means of
the option var_bounds 2. In this case, AMPL's
presolve was sufficient to determine this bound. However it
only examines linear constraints. To some extent, Dr. Ampl
is capable of performing similar operations even if the
constraints involve nonlinear expressions. It is not useful in
this particular example since the first equality constraint
gives x12 ≥ -1.
Stage 3: Bounding Objective Functions
Objective objective
Lower bound on lin part of objective : 1
Upper bound on lin part of objective : Infinity
Constant term in objective: 0
Overall: 1 <= objective <= Infinity
Similarly, bounds can be obtained on the constraint functions
and this may be used to determine redundant constraints. A
simple example of a redundant constraint is
(x-1)2 ≥ -1. In our model, there are
no redundant constraints.
Stage 4: Constraint Redundancy
Found 0 redundant constraints.
Stage 5 uses the constraints of the model to obtain tighter
bounds on the variables. This is what we refer to as reverse
mode. In this case, since we have determined that
x1 ≥ 1, the first constraint implies
x2 = x12 + 1 ≥ 2.
Stage 5: Bounds tightening
Pass 0
equality1 implies 2 <= x[2] <= Infinity
Pass 1
Pass 2
Pass 3
Pass 4
Once bound propagation in reverse mode is finished and tighter bounds
were obtained, we can re-propagate them in forward mode into all
nonlinear expressions of the model and see if this results in better
bounds on the objective value. In this case, the tighter bound on
x2 has no influence on the objective.
Stage 6: Tightening nonlinear sub-expressions
Stage 7: Bounding objective again
Objective objective
Lower bound on lin part of objective : 1
Upper bound on lin part of objective : Infinity
Constant term in objective: 0
Overall: 1 <= objective <= Infinity
The next stage is concerned with the convexity properties of the problem.
Objectives and constraints are examined in turn. First, we attempt to
prove convexity or concavity using mathematical deduction on the
combination of expressions found in each DAG. In the present case, the
objective is linear, hence convex, and the only nonlinear constraint is
the first one. It is determined to be convex.
Stage 8: Symbolic Convexity Proving of Objectives and Constraints
No nonlinear objective
Detected 0/0 nonlinear convex inequality constraints,
1/1 nonlinear convex equality constraints,
0/0 nonlinear concave inequality constraints,
0/1 nonlinear concave equality constraints.
The flip side of the convexity coin is the numerical disproving phase
in which we attempt to catch expressions which could not be proved
convex or concave with symbolic arguments. The convexity of the
constraint which was deemed convex in the previous stage cannot be
disproved and hence, we have good reasons to believe it is indeed a
convex function. The problem is not convex however, since this
constraint in an equality constraint.
Stage 9: Numerical Convexity Disproving of Objectives and Constraints
No nonlinear objective
Attempting to disprove convexity of constraints
In hindsight,
Detected 0/0 nonlinear convex inequality constraints,
1/1 nonlinear convex equality constraints,
0/0 nonlinear concave inequality constraints,
0/1 nonlinear concave equality constraints.
0/0 nonlinear nonconvex inequality constraints.
0/1 nonlinear nonconvex equality constraints.
0/0 nonlinear inconclusive inequality constraints.
0/1 nonlinear inconclusive equality constraints.
Finally, based on all the above observations and on a database of optimization
solvers, Dr. Ampl attempts to match the problem with a number of
appropriate solvers.
Stage 10: Solver Recommendation
### First query:: Soft parameters only ###
============================
Database query results
============================
| |
| SBB |
| MINLP |
| Minos |
| Conopt |
| DONLP2 |
| PathNLP |
| |
============================
Retrieved 6 matching records
============================
### Matching general-purpose solvers ###
============================
Database query results
============================
| |
| Loqo |
| Snopt |
| Knitro |
| Lancelot |
| filterSQP |
| |
============================
Retrieved 5 matching records
============================
DrAmpl:: END OF DIAGNOSTICS
In the last piece of information, we collect timing statistics on the run.
Allocation time................: 0.000000s
Convexity proving time.........: 0.000000s
Convexisty disproving time.....: 0.000000s
Total convexity analysis time..: 0.000000s
Total execution time.......... : 0.000000s
Database time................. : 0.000000s
Total time.................... : 0.000000s
|