The NLPC Nonlinear Optimization Solver: Infeasibility :: SAS/OR(R) 9.2 User's Guide: Mathematical Programming

The NLPC Nonlinear Optimization Solver

Infeasibility

Like any iterative algorithm, an optimization algorithm is carried out in finite-precision arithmetic and is subject to numerical rounding errors. Thus, when an algorithm terminates, the constraints might not be satisfied exactly. Instead we consider a constraint to be satisfied if the violation is within some prescribed tolerance. Such a violation can be measured in an absolute or relative sense.

For an optimization problem of the general form described in the section "Overview", we rewrite the constraints (including bound constraints) in the form

$c_i(x) = b_i, & i \in {\cal e} \ c_i(x) \ge b_i, & i \in {\cal i}$

where $\cal e$ and $\cal i$ denote the sets of equality and inequality constraints, respectively. We define the absolute infeasibility $\nu_1^k$ at

to be the maximum constraint violation in absolute measure as follows:

$\nu_1^k=\max_{i\in{\cal e},j\in{\cal i}}\{| c_i(x^k)-b_i|,b_j-c_j(x^k)\}$

We define the relative infeasibility $\nu_2^k$ at

to be the maximum constraint violation in relative measure as follows:

$\nu_2^k=\max_{i\in{\cal e},j\in{\cal i}}\{\frac{| c_i(x^k)-b_i|}{\max\{1,| b_i|\}}, \frac{b_j-c_j(x^k)}{\max\{1,| b_j|\}}\}$

For feasibility control, we choose $\epsilon$ to be the tolerance for the relative infeasibility. For a solution

to be considered feasible, we require that the following hold for the relative infeasibility:

$\nu_2^k\le\epsilon$

In the NLPC solver, we set $\epsilon=1.0$ E-6.

Associated with the infeasibility is the conditional optimality. A solution is considered to be conditionally optimal if satisfies the optimality criteria described in the section "Optimality Control" and if the following is true:

$\epsilon\lt\nu_2^k\lt 1.0{\rm e}\!-\!3$

That is, the default tolerance for the relative infeasibility is not satisfied, but the relative infeasibility is not too large. This is useful for problems whose constraints are not well scaled.

Top of Page