NAG C Library Function Document

nag_opt_handle_solve_pennon (e04svc)

1

Purpose

2

Specification

3

Description

3.1

Structure of the Lagrangian Multipliers

3.2

Approximation of the Lagrangian Multipliers

4

References

5

Arguments

1:    $\mathbf{handle}$ – void *Input

On entry: the handle to the problem. It needs to be initialized by nag_opt_handle_init (e04rac) and the problem formulated by some of the functions nag_opt_handle_set_linobj (e04rec), nag_opt_handle_set_quadobj (e04rfc), nag_opt_handle_set_simplebounds (e04rhc), nag_opt_handle_set_linconstr (e04rjc), nag_opt_handle_set_linmatineq (e04rnc) and nag_opt_handle_set_quadmatineq (e04rpc). It must not be changed between the calls.

2:    $\mathbf{nvar}$ – IntegerInput

On entry: $n$, the number of decision variables $x$ in the problem. It must be unchanged from the value set during the initialization of the handle by nag_opt_handle_init (e04rac).

3:    $\mathbf{x}\left[\mathbf{nvar}\right]$ – doubleInput/Output

Note: intermediate stops take place only if $\mathbf{Monitor\; Frequency}>0$.

On entry: if $\mathbf{Initial\; X}=\mathrm{USER}$ (the default), $x^0$, the initial estimate of the variables $x$, otherwise x need not be set.

On intermediate exit: the value of the variables $x$ at the end of the current outer iteration.

On intermediate re-entry: the input is ignored.

On final exit: the final value of the variables $x$.

4:    $\mathbf{nnzu}$ – IntegerInput

On entry: the dimension of array u.

If $\mathbf{nnzu}=0$, u will not be referenced; otherwise it needs to match the dimension of constraints defined by nag_opt_handle_set_simplebounds (e04rhc) and nag_opt_handle_set_linconstr (e04rjc) as explained in Section 3.1.

Constraint: $\mathbf{nnzu}\ge 0$.

5:    $\mathbf{u}\left[\mathbf{nnzu}\right]$ – doubleInput/Output

Note: intermediate stops take place only if $\mathbf{Monitor\; Frequency}>0$.

If $\mathbf{nnzu}>0$, u holds Lagrangian multipliers (dual variables) for (standard) constraints, i.e., simple bounds defined by nag_opt_handle_set_simplebounds (e04rhc) and a set of $m_B$ linear constraints defined by nag_opt_handle_set_linconstr (e04rjc). Either their initial estimates, intermediate approximations or final values, see Section 3.1.

If $\mathbf{nnzu}=0$, u will not be referenced and may be NULL.

On entry: if $\mathbf{Initial\; U}=\mathrm{USER}$ (the default is $\mathrm{AUTOMATIC}$), $u^0$, the initial estimate of the Lagrangian multipliers $u$, otherwise u need not be set.

On intermediate exit: the estimate of the multipliers $u$ at the end of the current outer iteration.

On intermediate re-entry: the input is ignored.

On exit: the final value of multipliers $u$.

6:    $\mathbf{nnzuc}$ – IntegerInput

On entry: the dimension of array uc. If $\mathbf{nnzuc}=0$, uc will not be referenced. This argument is reserved for future releases of the NAG C Library which will allow definition of second order cone constraints. It needs to be set to $0$ at the moment.

Constraint: $\mathbf{nnzuc}=0$.

7:    $\mathbf{uc}\left[\mathbf{nnzuc}\right]$ – doubleInput/Output

uc is reserved for future releases of the NAG C Library which will allow definition of second order cone constraints. It is not referenced at the moment and may be NULL.

8:    $\mathbf{nnzua}$ – IntegerInput

On entry: the dimension of array ua. If $\mathbf{nnzua}=0$, ua will not be referenced; otherwise it needs to match the total number of nonzeros in all matrix Lagrangian multipliers (constraints defined by nag_opt_handle_set_linmatineq (e04rnc) and nag_opt_handle_set_quadmatineq (e04rpc)) as explained in Section 3.1.

Constraint: $\mathbf{nnzua}\ge 0$.

9:    $\mathbf{ua}\left[\mathbf{nnzua}\right]$ – doubleInput/Output

Note: intermediate stops take place only if $\mathbf{Monitor\; Frequency}>0$.

If $\mathbf{nnzua}>0$, ua holds the Lagrangian multipliers for matrix constraints defined by nag_opt_handle_set_linmatineq (e04rnc) and nag_opt_handle_set_quadmatineq (e04rpc), see Section 3.1.

If $\mathbf{nnzua}=0$, ua will not be referenced and may be NULL.

On entry: if $\mathbf{Initial\; U}=\mathrm{USER}$ (the default is $\mathrm{AUTOMATIC}$), $U^0$, the initial estimate of the matrix Lagrangian multipliers $U$, otherwise ua need not be set.

On intermediate exit: the estimate of the matrix multipliers $U$ at the end of the outer iteration.

On intermediate re-entry: the input is ignored.

On final exit: the final estimate of the multipliers $U$.

10:  $\mathbf{rinfo}\left[32\right]$ – doubleOutput

On intermediate or final entry: error measures and various indicators (see Section 11 for details) at the end of the current (or final) outer iteration as given in the table below:

$0$	objective function value $f\left(x\right)$
$1$	optimality (12)
$2$	feasibility (13)
$3$	complementarity (14)
$4$	minimum penalty
$5$	relative precision (11)
$6$	relative duality gap (10)
$7$	precision $\left|f\left(x^{\ell }\right)-f\left(x^{\ell +1}\right)\right|$
$8$	duality gap
$9$	minimum penalty for (standard) inequalities $p$
$10$	minimum penalty for matrix inequalities $P$
$11$	feasibility of equality constraints
$12$	feasibility of (standard) inequalities
$13$	feasibility of matrix inequalities
$14$	complementarity of equality constraints
$15$	complementarity of (standard) inequalities
$16$	complementarity of matrix inequalities
$17$–$22$	DIMACS error measures (16) (only if turned on by $\mathbf{DIMACS\; Measures}$)
$23$–$31$	reserved for future use

11:  $\mathbf{stats}\left[32\right]$ – doubleOutput

On intermediate or final exit: solver statistics at the end of the current (or final) outer iteration as given in the table below. Note that time statistics is provided only if $\mathbf{Stats\; Time}$ is set (the default is $\mathrm{NO}$), the measured time is returned in seconds.

$0$	number of the outer iterations
$1$	total number of the inner iterations
$2$	total number of the linesearch steps
$3$	number of evaluations of the augmented Lagrangian $F\left(\right)$, (see (8))
$4$	number of evaluations of $\nabla F\left(\right)$
$5$	number of evaluations of ${\nabla }^{2}F\left(\right)$
$6$	reserved for future use
$7$	total running time of the solver
$8$	total running time of the solver without evaluations of the user's functions and monitoring stops
$9$	time spent in the inner iterations
$10$	time spent in Lagrangian multipliers updates
$11$	time spent in penalty parameters updates
$12$	time spent in matrix feasibility computation
$13$	time of evaluations of $F\left(\right)$
$14$	time of evaluations of $\nabla F\left(\right)$
$15$	time of evaluations of ${\nabla }^{2}F\left(\right)$
$16$	time of factorizations of the Newton system
$17$	time of factorizations of the matrix constraints
$18$–$31$	reserved for future use

12:  $\mathbf{inform}$ – Integer *Input/Output

Note: intermediate stops take place only if $\mathbf{Monitor\; Frequency}>0$.

On initial entry: no effect.

On intermediate exit: $\mathbf{inform}=1$.

On intermediate re-entry: if set to $0$, solving the current problem is terminated and the function returns $\mathbf{fail}\mathbf{.}\mathbf{code}=$ NE_USER_STOP; otherwise the function continues.

On final exit: $\mathbf{inform}=0$.

13:  $\mathbf{fail}$ – NagError *Input/Output

The NAG error argument (see Section 3.7 in How to Use the NAG Library and its Documentation).

6

Error Indicators and Warnings

NE_ALLOC_FAIL

Dynamic memory allocation failed.
See Section 2.3.1.2 in How to Use the NAG Library and its Documentation for further information.

NE_ALREADY_DEFINED

A different solver from the suite has already been used.

NE_BAD_PARAM

On entry, argument $〈\mathit{\text{value}}〉$ had an illegal value.

NE_DIM_MATCH

On entry, $\mathbf{nnzu}=〈\mathit{\text{value}}〉$.
nnzu does not match the size of the Lagrangian multipliers for (standard) constraints.
$\mathbf{nnzu}=0$ or $〈\mathit{\text{value}}〉$.

On entry, $\mathbf{nnzu}=〈\mathit{\text{value}}〉$.
nnzu does not match the size of the Lagrangian multipliers for (standard) constraints.
$\mathbf{nnzu}=0$ when there are no (standard) constraints.

On entry, $\mathbf{nnzua}=〈\mathit{\text{value}}〉$.
nnzua does not match the size of the Lagrangian multipliers for matrix constraints.
$\mathbf{nnzua}=0$ or $〈\mathit{\text{value}}〉$.

On entry, $\mathbf{nnzua}=〈\mathit{\text{value}}〉$.
nnzua does not match the size of the Lagrangian multipliers for matrix constraints.
$\mathbf{nnzua}=0$ when there are no matrix constraints.

On entry, $\mathbf{nnzuc}=〈\mathit{\text{value}}〉$.
nnzuc does not match the size of the Lagrangian multipliers for second order cone constraints.
$\mathbf{nnzuc}=0$ when there are no second order conde constraints.

NE_FAILED_START

The current starting point is unusable.

The starting point $x^0$, either provided by the user (if $\mathbf{Initial\; X}=\mathrm{USER}$, the default) or the automatic estimate (if $\mathbf{Initial\; X}=\mathrm{AUTOMATIC}$), must not be extremely infeasible in the matrix constraints (infeasibility of order ${10}^6$ and higher) and all the functions used in the problem formulation must be evaluatable.

In the unlikely case this error is triggered, it is necessary to provide a better estimate of the initial values.

NE_HANDLE

The supplied handle does not define a valid handle to the data structure for the NAG optimization modelling suite. It has not been initialized by nag_opt_handle_init (e04rac) or it has been corrupted.

NE_INFEASIBLE

The problem was found to be infeasible during preprocessing.

One or more of the constraints (or its part after preprocessing) violates the constraints by more than ${\epsilon }_{\mathrm{feas}}$ ($\mathbf{Stop\; Tolerance\; Feasibility}$).

NE_INTERNAL_ERROR

An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact NAG for assistance.
See Section 2.7.6 in How to Use the NAG Library and its Documentation for further information.

NE_MAYBE_INFEASIBLE

The problem seems to be infeasible, the algorithm was stopped.

Whilst the algorithm cannot definitively detect that the problem is infeasible, several indirect indicators suggest that it might be the case.

NE_MAYBE_UNBOUNDED

The problem seems to be unbounded, the algorithm was stopped.

Whilst the algorithm cannot definitively detect that the problem is unbounded, several indirect indicators (such as a rapid decrease in the objective function and a lack of convergence in the inner subproblem) suggest that this might be the case. A good scaling of the objective function is always highly recommended to avoid situations when unusual behavior triggers falsely this error exit.

NE_NO_IMPROVEMENT

Unable to make progress, the algorithm was stopped.

This error is returned if the solver cannot decrease the duality gap over a range of iterations. This can be due to the scaling of the problem or the problem might be close to primal or dual infeasibility.

NE_NO_LICENCE

Your licence key may have expired or may not have been installed correctly.
See Section 2.7.5 in How to Use the NAG Library and its Documentation for further information.

NE_REF_MATCH

On entry, $\mathbf{nvar}=〈\mathit{\text{value}}〉$, expected $\mathrm{value}=〈\mathit{\text{value}}〉$.
Constraint: nvar must match the value given during initialization of handle.

NE_SETUP_ERROR

This solver does not support fixed variables.

This solver does not support general nonlinear objective and constraints.

NE_SUBPROBLEM

The inner subproblem could not be solved to the required accuracy.
Inner iteration limit has been reached.

The inner subproblem could not be solved to the required accuracy.
Limited progress in the inner subproblem triggered a stop (heuristic inner stop criteria).

The inner subproblem could not be solved to the required accuracy.
Line search or another internal component failed.

A problem with the convergence of the inner subproblem is typically a sign of numerical difficulties of the whole algorithm. The inner subproblem might be stopped before reaching the required accuracy because of the $\mathbf{Inner\; Iteration\; Limit}$, a heuristic detected no progress in the inner iterations (if $\mathbf{Inner\; Stop\; Criteria}=\mathrm{HEURISTIC}$, default) or if an internal component failed (for example, line search was unable to find a suitable step). The algorithm tries to recover, however, it might give up after several attempts with one of these error messages. If it occurs in the very early iterations, consider increasing $\mathbf{Inner\; Stop\; Tolerance}$ and possibly $\mathbf{Init\; Value\; P}$ or $\mathbf{Init\; Value\; Pmat}$ which should ease the first iterations. An occurrence in later iterations indicates numerical difficulties typically due to scaling and/or ill-conditioning or the problem is close to infeasible. Reducing the tolerance on the stopping criteria or increasing $\mathbf{P\; Update\; Speed}$ might be of limited help.

NE_TOO_MANY_ITER

Outer iteration limit has been reached.
The requested accuracy is not achieved.

If $\mathbf{Outer\; Iteration\; Limit}$ is left to the default, this error indicates numerical difficulties. Consider whether the stopping tolerances ($\mathbf{Stop\; Tolerance\; 1}$, $\mathbf{Stop\; Tolerance\; 2}$, $\mathbf{Stop\; Tolerance\; Feasibility}$) are set too low or optional parameters affecting the behaviour of the penalty updates ($\mathbf{P\; Update\; Speed}$, $\mathbf{P\; Min}$ or $\mathbf{Pmat\; Min}$) have been modified inadvisedly. The iteration log should reveal more about the misbehaviour. Providing a different starting point might be of help in certain situations.

NE_UNBOUNDED

The problem was found unbounded during preprocessing.

The objective function consists of an unrestricted ray and thus the problem does not have a solution.

NE_USER_STOP

User requested termination during a monitoring step.

NW_NOT_CONVERGED

The algorithm converged to a suboptimal solution.
The full accuracy was not achieved. The solution should still be usable.

This error may be reported only if $\mathbf{Stop\; Criteria}=\mathrm{SOFT}$ (default). The solver predicted that it is unable to reach a better estimate of the solution. However, the error measures indicate that the point is a reasonable approximation. Typically, only the norm of the gradient of the Lagrangian (optimality) does not fully satisfy the requested tolerance whereas the others are well below the tolerance.

Setting $\mathbf{Stop\; Criteria}=\mathrm{STRICT}$ will disallow this error but it is unlikely that the algorithm would reach a better solution.

7

Accuracy

8

Parallelism and Performance

9

Further Comments

9.1

Description of the Printed Output

E04SV, NLP-SDP Solver (Pennon)
---------------------------------------------------------------------------
Number of variables             2                 [eliminated            0]
                           simple  linear  nonlin
(Standard) inequalities         3       0       0
(Standard) equalities                   0       0
Matrix inequalities                     1       1 [dense    2, sparse    0]
                                                  [max dimension         3]

Outer Iteration Limit         =                  20 * U
Stop Tolerance 1              =         1.00000E-06 * d
Stop Tolerance 2              =         1.00000E-07 * d
Hessian Density               =               Dense * S

-----------------------------------------------------------------
 it |  objective |  optim  |   feas  |  compl  | pen min  | inner
-----------------------------------------------------------------
  0   0.00000E+00  7.34E+00  1.23E-01  4.41E+01  1.00E+00   0
  1  -3.01998E-01  2.54E-03  0.00E+00  1.89E+00  1.00E+00   6
  2  -2.53008E+00  1.06E-03  1.30E-01  3.22E-01  3.17E-01   8
  3  -2.08172E+00  6.52E-03  1.85E-02  4.54E-02  1.01E-01   7
  4  -2.01060E+00  6.47E-03  4.10E-03  1.02E-02  3.19E-02   3

 ----------------------------------------------------------------
  it |  objective |  optim  |   feas  |  compl  | pen min | inner
 ----------------------------------------------------------------
   0  0.00000E+00  1.46E+03  5.01E+01  1.46E+03  6.40E+01   0
   1  3.78981E+02  3.86E+01  0.00E+00  1.21E+04  6.40E+01   5 M
   2  9.11724E+02  1.46E-02  0.00E+00  9.24E+02  4.45E+01   5

--------------------------------------------------------------
Status: converged, an optimal solution found
--------------------------------------------------------------
Final objective value                2.300000E+01
Relative precision                   5.873755E-09
Optimality                           1.756062E-10
Feasibility                          9.048738E-08
Complementarity                      1.855566E-08
DIMACS error 1                       8.780308E-11
DIMACS error 2                       0.000000E+00
DIMACS error 3                       0.000000E+00
DIMACS error 4                       4.524369E-08
DIMACS error 5                       4.065998E-10
DIMACS error 6                       3.948012E-10
Iteration counts
  Outer iterations                             13
  Inner iterations                             82
  Linesearch steps                             95
Evaluation counts
  Augm. Lagr. values                           96
  Augm. Lagr. gradient                         96
  Augm. Lagr. hessian                          82
Timing
  Total time                    0 h  0 min  3 sec
    Evaluations + monitoring             0.04 sec
    Solver itself                        3.09 sec
  Inner minimization step                2.72 sec   ( 87.1%)
    Augm. Lagr. value                    0.28 sec   (  9.0%)
    Augm. Lagr. gradient                 0.67 sec   ( 21.6%)
    Augm. Lagr. hessian                  1.11 sec   ( 35.4%)
    system matr. factor.                 0.64 sec   ( 20.5%)
    const. matr. factor.                 0.40 sec   ( 12.8%)
  Multiplier update                      0.01 sec   (  0.3%)
  Penalty update                         0.02 sec   (  0.5%)
  Feasibility check                      0.15 sec   (  4.7%)
--------------------------------------------------------------

9.2

Internal Changes

10

Example

10.1

Program Text

Program Text (e04svce.c)

10.2

Program Data

Program Data (e04svce.d)

10.3

Program Results

Program Results (e04svce.r)

11

Algorithmic Details

11.1

Overview

11.2

Stopping Criteria

11.3

Choice of penalty functions ${\phi }_g$ and ${\phi }_A$

11.4

Solution of the inner problem

12

Optional Parameters

• Defaults
• DIMACS Measures
• Hessian Density
• Infinite Bound Size
• Initial P
• Initial U
• Initial X
• Init Value P
• Init Value Pmat
• Inner Iteration Limit
• Inner Stop Criteria
• Inner Stop Tolerance
• Linesearch Mode
• List
• Monitor Frequency
• Monitoring File
• Monitoring Level
• Outer Iteration Limit
• Pmat Min
• P Min
• Preference
• Presolve Block Detect
• Print File
• Print Level
• Print Options
• P Update Speed
• Stats Time
• Stop Criteria
• Stop Tolerance 1
• Stop Tolerance 2
• Stop Tolerance Feasibility
• Task
• Transform Constraints
• Umat Update Restriction
• U Update Restriction

12.1

Description of the Optional Parameters

• the keywords, where the minimum abbreviation of each keyword is underlined;
• a parameter value, where the letters $a$, $i$ and $r$ denote options that take character, integer and real values respectively;
• the default value, where the symbol $\epsilon$ is a generic notation for machine precision (see nag_machine_precision (X02AJC)).