naginterfaces.library.opt.handle_​solve_​pennon

naginterfaces.library.opt.handle_solve_pennon(handle, x, inform, u=None, uc=None, ua=None, io_manager=None)

handle_solve_pennon is a solver from the NAG optimization modelling suite for problems such as, Quadratic Programming (QP), linear Semidefinite Programming (SDP) and semidefinite programming with bilinear matrix inequalities (BMI-SDP).

Note: this function uses optional algorithmic parameters, see also: handle_opt_set(), handle_opt_get().

For full information please refer to the NAG Library document for e04sv

https://support.nag.com/numeric/nl/nagdoc_30.3/flhtml/e04/e04svf.html

Parameters

handleHandle

The handle to the problem. It needs to be initialized (e.g., by handle_init()) and to hold a problem formulation compatible with handle_solve_pennon. It must not be changed between calls to the NAG optimization modelling suite.

xfloat, array-like, shape $\left(\text{nvar}\right)$

Note: intermediate stops take place only if $\text{‘Monitor Frequency'}>0$.

If $\text{‘Initial X'}=\text{'USER'}$ (the default), $x^0$, the initial estimate of the variables $x$; otherwise, $x$ need not be set.

On intermediate entry: the input is ignored.

informint

Note: intermediate stops take place only if $\text{‘Monitor Frequency'}>0$.

On initial entry: no effect.

On intermediate entry: if set to $0$, solving the current problem is terminated and the function returns $errno$ = 20; otherwise, the function continues.

uNone or float, array-like, shape $\left(\text{nnzu}\right)$, optional

Note: intermediate stops take place only if $\text{‘Monitor Frequency'}>0$.

Note: if $\text{nnzu}>0$, $u$ holds Lagrangian multipliers (dual variables) for (standard) constraints, i.e., simple bounds defined by handle_set_simplebounds() and a set of $m_B$ linear constraints defined by handle_set_linconstr(). Either their initial estimates, intermediate approximations or final values, see Structure of the Lagrangian Multipliers.

Note: if $\text{nnzu}=0$, $u$ will not be referenced.

If $\text{‘Initial U'}=\text{'USER'}$ (the default is ‘AUTOMATIC’), $u^0$, the initial estimate of the Lagrangian multipliers $u$; otherwise, $u$ need not be set.

On intermediate entry: the input is ignored.

ucNone or float, array-like, shape $\left(\text{nnzuc}\right)$, optional

$uc$ is reserved for future releases of the NAG Library which will allow definition of second-order cone constraints.

It is not referenced at the moment.

uaNone or float, array-like, shape $\left(\text{nnzua}\right)$, optional

Note: intermediate stops take place only if $\text{‘Monitor Frequency'}>0$.

If $\text{nnzua}>0$, $ua$ holds the Lagrangian multipliers for matrix constraints defined by handle_set_linmatineq() and handle_set_quadmatineq(), see Structure of the Lagrangian Multipliers.

If $\text{nnzua}=0$, $ua$ will not be referenced.

If $\text{‘Initial U'}=\text{'USER'}$ (the default is ‘AUTOMATIC’), $U^0$, the initial estimate of the matrix Lagrangian multipliers $U$; otherwise, $ua$ need not be set.

On intermediate entry: the input is ignored.

io_managerFileObjManager, optional

Manager for I/O in this routine.

Returns

xfloat, ndarray, shape $\left(\text{nvar}\right)$

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

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

ufloat, ndarray, shape $\left(\text{nnzu}\right)$

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

ucfloat, ndarray, shape $\left(\text{nnzuc}\right)$

$uc$ is reserved for future releases of the NAG Library which will allow definition of second-order cone constraints.

It is not referenced at the moment.

uafloat, ndarray, shape $\left(\text{nnzua}\right)$

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

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

rinfofloat, ndarray, shape $\left(32\right)$

On intermediate or final entry: error measures and various indicators (see Algorithmic Details 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 (2)
$2$	feasibility (3)
$3$	complementarity (4)
$4$	minimum penalty
$5$	relative precision (1)
$6$	relative duality gap (0)
$7$	precision $|f\left(x^{\ell }\right)-f\left(x^{\ell +1}\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 [equation] (only if turned on by ‘DIMACS Measures’)
$23$–$31$	reserved for future use

statsfloat, ndarray, shape $\left(32\right)$

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 ‘Stats Time’ is set (the default is ‘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.

informint

Note: intermediate stops take place only if $\text{‘Monitor Frequency'}>0$.

On intermediate exit: $inform=1$.

On final exit: $inform=0$.

Other Parameters

‘Defaults’valueless

This special keyword may be used to reset all options to their default values. Any value given with this keyword will be ignored.

‘DIMACS Measures’str

Default $=\text{'CHECK'}$

If the problem is a linear semidefinite programming problem, this argument specifies if DIMACS error measures (see Stopping Criteria) should be computed and/or checked. In other cases, this option reverts to ‘NO’ automatically.

Constraint: $\text{‘DIMACS Measures'}=\text{'COMPUTE'}$, $\text{'CHECK'}$ or $\text{'NO'}$.

‘Hessian Density’str

Default $=\text{'AUTO'}$

This option guides the solver on how the Hessian matrix of augmented Lagrangian $F(x,u,v,U,p,P)$ should be built. Option ‘AUTO’ leaves the decision to the solver and it is the recommended option. Setting it to ‘DENSE’ bypasses the autodetection and the Hessian is always built as a dense matrix. Option ‘SPARSE’ instructs the solver to use a sparse storage and factorization of the matrix if possible.

Constraint: $\text{‘Hessian Density'}=\text{'AUTO'}$, $\text{'DENSE'}$ or $\text{'SPARSE'}$

‘Infinite Bound Size’float

Default $={10}^{20}$

This defines the ‘infinite’ bound $\text{bigbnd}$ in the definition of the problem constraints. Any upper bound greater than or equal to $\text{bigbnd}$ will be regarded as $+\infty$ (and similarly any lower bound less than or equal to $-\text{bigbnd}$ will be regarded as $-\infty$). Note that a modification of this option does not influence constraints which have already been defined; only the constraints formulated after the change will be affected.

Constraint: $\text{‘Infinite Bound Size'}\ge 1000$.

‘Initial P’str

Default $=\text{'AUTOMATIC'}$

This option defines the choice of the penalty options $p^0$, $P^0$, see Algorithm 1.

$\text{‘Initial P'}=\text{'AUTOMATIC'}$

The penalty options are chosen automatically as set by option ‘Init Value P’, ‘Init Value Pmat’ and subject to automatic scaling. Note that $P^0$ might be increased so that the penalty function ${\Phi }_P\left(\right)$ is defined for all matrix constraints at the starting point.

$\text{‘Initial P'}=\text{'KEEP PREVIOUS'}$

The penalty options are kept from the previous run of the solver if possible. If not, this options reverts to ‘AUTOMATIC’. Note that even if the matrix penalty options are the same as in the previous run, they are still subject to a possible increase so that the penalty function ${\Phi }_P\left(\right)$ is well defined at the starting point.

Constraint: $\text{‘Initial P'}=\text{'AUTOMATIC'}$ or $\text{'KEEP PREVIOUS'}$.

‘Initial U’str

Default $=\text{'AUTOMATIC'}$

This argument guides the solver on which initial Lagrangian multipliers are to be used.

$\text{‘Initial U'}=\text{'AUTOMATIC'}$

The Lagrangian multipliers are chosen automatically as set by automatic scaling.

$\text{‘Initial U'}=\text{'USER'}$

The values of arrays $u$ and $ua$ (if provided) are used as the initial Lagrangian multipliers subject to automatic adjustments. If one or the other array is not provided, the choice for missing data is as in ‘AUTOMATIC’.

$\text{‘Initial U'}=\text{'KEEP PREVIOUS'}$

The Lagrangian multipliers are kept from the previous run of the solver. If this option is set for the first run or options change the approach of the solver, the choice automatically reverts to ‘AUTOMATIC’. This might be useful if the solver is hot started, for example, to achieve higher precision of the solution.

Constraint: $\text{‘Initial U'}=\text{'AUTOMATIC'}$, $\text{'USER'}$ or $\text{'KEEP PREVIOUS'}$.

‘Initial X’str

Default $=\text{'USER'}$

This argument guides which starting point $x^0$ is to be used.

$\text{‘Initial X'}=\text{'AUTOMATIC'}$

The starting point is chosen automatically so that it satisfies simple bounds on the variables or as a zero vector. Input of argument $x$ is ignored.

$\text{‘Initial X'}=\text{'USER'}$

Initial values of argument $x$ are used as a starting point.

Constraint: $\text{‘Initial X'}=\text{'AUTOMATIC'}$ or $\text{'USER'}$.

‘Init Value P’float

Default $=1.0$

This argument defines the value $p^0$, the initial penalty option for (standard) inequalities. A low value of the penalty causes the solution of the inner problem to be closer to the feasible region and thus to the desirable result. However, it also increases ill-conditioning of the system. It is not advisable to set the penalty too low unless a good starting point is provided.

Constraint: $\sqrt[4]{4ϵ}\le \text{‘Init Value P'}\le {10}^4$.

‘Init Value Pmat’float

Default $=1.0$

The value of this option suggests $P^0$, the initial penalty option for matrix inequalities. It is similar to ‘Init Value P’ (and the same advice applies), however, $P^0$ gets increased automatically if the matrix constraints are more infeasible than the actual penalty option.

Constraint: $\sqrt[4]{4ϵ}\le \text{‘Init Value Pmat'}\le {10}^4$.

‘Inner Iteration Limit’int

Default $=100$

The maximum number of the inner iterations (Newton steps) to be performed by Algorithm 2 in each outer iteration. Setting the option too low might lead to $errno$ = 23. Values higher than $100$ are unlikely to improve convergence.

Constraint: $\text{‘Inner Iteration Limit'}>0$.

‘Inner Stop Criteria’str

Default $=\text{'HEURISTIC'}$

The precision $\alpha$ for the solution of the inner subproblem is determined in Algorithm 1 and under typical circumstances Algorithm 2 is expected to reach this precision within the given ‘Inner Iteration Limit’. If any problems are detected and $\text{‘Inner Stop Criteria'}=\text{'HEURISTIC'}$, Algorithm 2 is allowed to stop before reaching the requested precision or the ‘Inner Iteration Limit’. This usually saves many unfruitful iterations and the solver may recover in the following iterations. If you suspect that the heuristic problem detection is not suitable for your problem, setting $\text{‘Inner Stop Criteria'}=\text{'STRICT'}$ disallows such behaviour.

Constraint: $\text{‘Inner Stop Criteria'}=\text{'HEURISTIC'}$ or $\text{'STRICT'}$.

‘Inner Stop Tolerance’float

Default $={10}^{-2}$

This option sets the required precision ${\alpha }^0$ for the first inner problem solved by Algorithm 2. The precison of the solution of the inner problem does not need to be very high in the first outer iterations and it is automatically adjusted through the outer iterations to reach the optimality limit ${ϵ}_2$ in the last one.

Setting ${\alpha }^0$ too restrictive (too low) causes an increase of the number of inner iterations needed in the first outer iterations and might lead to $errno$ = 23. In certain cases it might be helpful to use a more relaxed (higher) ${\alpha }^0$ and increase ‘P Update Speed’ which should reduce the number of inner iterations needed at the beginning of the computation in exchange for a possibly higher number of the outer iterations.

Constraint: $ϵ<\text{‘Inner Stop Tolerance'}\le {10}^3$.

‘Linesearch Mode’str

Default $=\text{'AUTO'}$

This controls the step size selection in Algorithm 2. If $\text{‘Linesearch Mode'}=\text{'FULLSTEP'}$ (the default for linear problems), unit steps are taken where possible and the step shortening takes place only to avoid undefined regions for the matrix penalty function ${\Phi }_P\left(\right)$ (see (6)). This may be used for linear problems but it is not recommended for any nonlinear ones. If $\text{‘Linesearch Mode'}=\text{'ARMIJO'}$, Armijo backtracking linesearch is used instead which is a fairly basic linesearch. If $\text{‘Linesearch Mode'}=\text{'GOLDSTEIN'}$, a cubic safe guarded linesearch based on Goldstein condition is employed, this is the recommended (and default) choice for nonlinear problems.

Constraint: $\text{‘Linesearch Mode'}=\text{'AUTO'}$, $\text{'FULLSTEP'}$, $\text{'ARMIJO'}$ or $\text{'GOLDSTEIN'}$.

‘List’str

Default $=\text{'NO'}$

This argument may be set to ‘YES’ if you wish to turn on printing of each option specification as it is supplied.

Constraint: $\text{‘List'}=\text{'YES'}$ or $\text{'NO'}$

‘Monitor Frequency’int

Default $=0$

If $\text{‘Monitor Frequency'}>0$, the solver returns to you at the end of every $i$th outer iteration. During these intermediate exits, the current point $x$ and Lagrangian multipliers $u$, $ua$ (if requested) are provided as well as the statistics and error measures ($rinfo$, $stats$). Argument $inform$ helps to distinguish between intermediate and final exits and also allows immediate termination.

If $\text{‘Monitor Frequency'}=0$, the solver stops only once on the final point and no intermediate exits are made.

Constraint: $\text{‘Monitor Frequency'}\ge 0$.

‘Monitoring File’int

Default $=-1$

If $i\ge 0$, the unit number for the secondary (monitoring) output. If set to $-1$, no secondary output is provided. The following information is output to the unit:

• a listing of the options;

• problem statistics, the iteration log and the final status as set by ‘Monitoring Level’.

Constraint: $\text{‘Monitoring File'}\ge -1$.

‘Monitoring Level’int

Default $=4$

This argument sets the amount of information detail that will be printed by the solver to the secondary output. The meaning of the levels is the same as with ‘Print Level’.

Constraint: $0\le \text{‘Monitoring Level'}\le 5$.

‘Outer Iteration Limit’int

Default $=100$

The maximum number of the outer iterations to be performed by Algorithm 1. If $\text{‘Outer Iteration Limit'}=0$, no iteration is performed, only quantities needed in the stopping criteria are computed and returned in $rinfo$. This might be useful in connection with $\text{‘Initial X'}=\text{'USER'}$ and $\text{‘Initial U'}=\text{'USER'}$ to check optimality of the given point. However, note that the rules for possible modifications of the starting point still apply, see $u$ and $ua$. Setting the option too low might lead to $errno$ = 22.

Constraint: $\text{‘Outer Iteration Limit'}\ge 0$.

‘P Min’float

Default $=\sqrt{ϵ}$

This controls $p_{min}$, the lowest possible penalty value $p$ used for (standard) inequalities. In general, very small values of the penalty options cause ill-conditioning which might lead to numerical difficulties. On the other hand, very high $p_{min}$ prevents the algorithm from reaching the requested accuracy on the feasibility. Under normal circumstances, the default value is recommended.

Constraint: $ϵ\le \text{‘P Min'}\le {10}^{-2}$.

‘Pmat Min’float

Default $=\sqrt{ϵ}$

This is an equivalent of ‘P Min’ for the minimal matrix penalty option $P_{min}$. The same advice applies.

Constraint: $ϵ\le \text{‘Pmat Min'}\le {10}^{-2}$.

‘Preference’str

Default $=\text{'SPEED'}$

This option affects how contributions from the matrix constraints (6) to the system Hessian matrix are computed. The default option of $\text{‘Preference'}=\text{'SPEED'}$ should be suitable in most cases. However, dealing with matrix constraints of a very high dimension may cause noticable memory overhead and switching to $\text{‘Preference'}=\text{'MEMORY'}$ may be required.

Constraint: $\text{‘Preference'}=\text{'SPEED'}$ or $\text{'MEMORY'}$.

‘Presolve Block Detect’str

Default $=\text{'YES'}$

If $\text{‘Presolve Block Detect'}=\text{'YES'}$, the matrix constraints are checked during preprocessoring to determine if they can be split into smaller independent ones, thus speeding up the solver.

Constraint: $\text{‘Presolve Block Detect'}=\text{'YES'}$ or $\text{'NO'}$.

‘Print File’int

Default $=\text{advisory message unit number}$

If $i\ge 0$, the unit number for the primary output of the solver. If $\text{‘Print File'}=-1$, the primary output is completely turned off independently of other settings. The default value is the advisory message unit number at the time of the options initialization, e.g., at the initialization of the handle. The following information is output to the unit:

• a listing of options if set by ‘Print Options’;

• problem statistics, the iteration log and the final status from the solver as set by ‘Print Level’.

Constraint: $\text{‘Print File'}\ge -1$.

‘Print Level’int

Default $=2$

This argument defines how detailed information should be printed by the solver to the primary output.

$i$	Output
$0$	No output from the solver
$1$	Only the final status and the objective value
$2$	Problem statistics, one line per outer iteration showing the progress of the solution, final status and statistics
$3$	As level $2$ but detailed output of the outer iterations is provided and brief overview of the inner iterations
$4$, $5$	As level $3$ but details of the inner iterations are printed as well

Constraint: $0\le \text{‘Print Level'}\le 5$.

‘Print Options’str

Default $=\text{'YES'}$

If $\text{‘Print Options'}=\text{'YES'}$, a listing of options will be printed to the primary output.

Constraint: $\text{‘Print Options'}=\text{'YES'}$ or $\text{'NO'}$.

‘P Update Speed’int

Default $=12$

This option affects the rate at which the penalty options $p,P$ are updated (Algorithm 1, step (3)) and thus indirectly influences the overall number of outer iterations. Its value can be interpretted as the typical number of outer iterations needed to get from the initial penalty values $p^0$, $P^0$ half-way to the $p_{min}$ and $P_{min}$. Values smaller than $3$ causes a very agressive penalty update strategy which might lead to the increased number of inner iterations and possibly to numerical difficulties. On the other hand, values higher than $15$ produce a relatively conservative approach which leads to a higher number of the outer iterations.

If the solver encounters difficulties on your problem, a higher value might help. If your problem is working fine, setting a lower value might increase the speed.

Constraint: $1\le \text{‘P Update Speed'}\le 100$.

‘Stats Time’str

Default $=\text{'NO'}$

This argument turns on timings of various parts of the algorithm to give a better overview of where most of the time is spent. This might be helpful for a choice of different solving approaches. It is possible to choose between CPU and wall clock time. Choice ‘YES’ is equivalent to ‘WALL CLOCK’.

Constraint: $\text{‘Stats Time'}=\text{'YES'}$, $\text{'NO'}$, $\text{'CPU'}$ or $\text{'WALL CLOCK'}$.

‘Stop Criteria’str

Default $=\text{'SOFT'}$

If $\text{‘Stop Criteria'}=\text{'SOFT'}$, the solver is allowed to stop prematurely with a suboptimal solution, $errno$ = 50, if it predicts that a better estimate of the solution cannot be reached. This is the recommended option.

Constraint: $\text{‘Stop Criteria'}=\text{'SOFT'}$ or $\text{'STRICT'}$.

‘Stop Tolerance 1’float

Default $=max({10}^{-6},\sqrt{ϵ})$

This option defines ${ϵ}_1$ used as a tolerance for the relative duality gap (0) and the relative precision (1), see Stopping Criteria.

Constraint: $\text{‘Stop Tolerance 1'}>ϵ$.

‘Stop Tolerance 2’float

Default $=max({10}^{-7},\sqrt{ϵ})$

This option sets the value ${ϵ}_2$ which is used for optimality (2) and complementarity (4) tests from KKT conditions or if $\text{‘DIMACS Measures'}=\text{'Check'}$ for all DIMACS error measures instead. See Stopping Criteria.

Constraint: $\text{‘Stop Tolerance 2'}>ϵ$.

‘Stop Tolerance Feasibility’float

Default $=max({10}^{-7},\sqrt{ϵ})$

This argument places an acceptance limit on the feasibility of the solution (3), ${ϵ}_{feas}$. See Stopping Criteria.

Constraint: $\text{‘Stop Tolerance Feasibility'}>ϵ$.

‘Task’str

Default $=\text{'MINIMIZE'}$

This argument specifies the required direction of the optimization. If $\text{‘Task'}=\text{'FEASIBLE POINT'}$, the objective function (if set) is ignored and the algorithm stops as soon as a feasible point is found with respect to the given tolerance. If no objective function was set, ‘Task’ reverts to ‘FEASIBLE POINT’ automatically.

Constraint: $\text{‘Task'}=\text{'MINIMIZE'}$, $\text{'MAXIMIZE'}$ or $\text{'FEASIBLE POINT'}$.

‘Transform Constraints’str

Default $=\text{'AUTO'}$

This argument controls how equality constraints are treated by the solver. If $\text{‘Transform Constraints'}=\text{'EQUALITIES'}$, all equality constraints $h_k\left(x\right)=0$ from (4) are treated as two inequalities $h_k\left(x\right)\le 0$ and $h_k\left(x\right)\ge 0$, see Solution of the inner problem. This is the default and the only option in this release for equality constrained problems.

Constraint: $\text{‘Transform Constraints'}=\text{'AUTO'}$, $\text{'NO'}$ or $\text{'EQUALITIES'}$.

‘U Update Restriction’float

Default $=0.5$

This defines the value ${\mu }_g$ giving the bounds on the updates of Lagrangian multipliers for (standard) inequalities between the outer iterations. Values close to $1$ limit the changes of the multipliers and serve as a kind of smoothing, lower values allow more significant changes.

Based on numerical experience, big variation in the multipliers may lead to a large number of iterations in the subsequent step and might disturb the convergence due to ill-conditioning.

It might be worth experimenting with the value on your particular problem. Mid range values are recommended over the more extremal ones.

Constraint: $ϵ<\text{‘U Update Restriction'}<1$.

‘Umat Update Restriction’float

Default $=0.3$

This is an equivalent of ‘U Update Restriction’ for matrix constraints, denoted as ${\mu }_A$ in Overview. The advice above applies equally.

Constraint: $ϵ<\text{‘Umat Update Restriction'}<1$.

Raises

NagValueError

(errno $1$)

$handle$ has not been initialized.

(errno $1$)

$handle$ does not belong to the NAG optimization modelling suite, has not been initialized properly or is corrupted.

(errno $1$)

$handle$ has not been initialized properly or is corrupted.

(errno $2$)

This solver does not support the model defined in the handle.

(errno $3$)

The problem is already being solved.

(errno $4$)

On entry, $\text{nvar}=⟨value⟩$, expected $value=⟨value⟩$.

Constraint: $\text{nvar}$ must match the current number of variables of the model in the $handle$.

(errno $5$)

On entry, $\text{nnzu}=⟨value⟩$.

$\text{nnzu}$ does not match the size of the Lagrangian multipliers for (standard) constraints.

$\text{nnzu}=0$ or $⟨value⟩$.

(errno $5$)

On entry, $\text{nnzu}=⟨value⟩$.

$\text{nnzu}$ does not match the size of the Lagrangian multipliers for (standard) constraints.

$\text{nnzu}=0$ when there are no (standard) constraints.

(errno $5$)

On entry, $\text{nnzua}=⟨value⟩$.

$\text{nnzua}$ does not match the size of the Lagrangian multipliers for matrix constraints.

$\text{nnzua}=0$ or $⟨value⟩$.

(errno $5$)

On entry, $\text{nnzua}=⟨value⟩$.

$\text{nnzua}$ does not match the size of the Lagrangian multipliers for matrix constraints.

$\text{nnzua}=0$ when there are no matrix constraints.

(errno $5$)

On entry, $\text{nnzuc}=⟨value⟩$.

$\text{nnzuc}$ does not match the size of the Lagrangian multipliers for second-order cone constraints.

$\text{nnzuc}=0$ when there are no second-order cone constraints.

(errno $21$)

The current starting point is unusable.

(errno $51$)

The problem was found to be infeasible during preprocessing.

(errno $52$)

The problem was found unbounded during preprocessing.

(errno $53$)

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

(errno $54$)

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

Warns

NagAlgorithmicWarning

(errno $50$)

The algorithm converged to a suboptimal solution.

The full accuracy was not achieved. The solution should still be usable.

NagAlgorithmicMajorWarning

(errno $20$)

User requested termination during a monitoring step.

(errno $22$)

Outer iteration limit has been reached.

The requested accuracy is not achieved.

(errno $23$)

The inner subproblem could not be solved to the required accuracy.

Inner iteration limit has been reached.

(errno $23$)

The inner subproblem could not be solved to the required accuracy.

Limited progress in the inner subproblem triggered a stop (heuristic inner stop criteria).

(errno $23$)

The inner subproblem could not be solved to the required accuracy.

Line search or another internal component failed.

(errno $24$)

Unable to make progress, the algorithm was stopped.

Notes

handle_solve_pennon serves as a solver for compatible problems stored as a handle. The handle points to an internal data structure which defines the problem and serves as a means of communication for functions in the NAG optimization modelling suite. First, the problem handle is initialized by calling handle_init(). Then some of the functions handle_set_linobj(), handle_set_quadobj(), handle_set_simplebounds(), handle_set_linconstr(), handle_set_linmatineq() or handle_set_quadmatineq() may be used to formulate the objective function, (standard) constraints and matrix constraints of the problem. Once the problem is fully set, the handle may be passed to the solver. When the handle is no longer needed, handle_free() should be called to destroy it and deallocate the memory held within. See the E04 Introduction for more details about the NAG optimization modelling suite.

Problems which can be defined this way are, for example, (generally nonconvex) Quadratic Programming (QP)

$$\begin{array}{c}\begin{array}{ccc}{minimize}_{x\in R^n}& \frac{1}{2}{x}^{T}Hx+c^{T}x& \text{(a)}\\ \text{subject to}& l_B\le Bx\le u_B\text{,}& \text{(b)}\\ & l_x\le x\le u_x\text{,}& \text{(c)}\end{array}\end{array}$$

linear semidefinite programming problems (SDP)

$$\begin{array}{c}\begin{array}{ccc}{minimize}_{x\in R^n}& c^{T}x& \text{(a)}\\ \text{subject to}& {\sum }_1^n{x}_i{A}_i^k-A_0^k⪰0\text{,}k=1,\dots ,m_A\text{,}& \text{(b)}\\ & l_B\le Bx\le u_B\text{,}& \text{(c)}\\ & l_x\le x\le u_x\text{,}& \text{(d)}\end{array}\end{array}$$

or semidefinite programming problems with bilinear matrix inequalities (BMI-SDP)

$$\begin{array}{c}\begin{array}{ccc}{minimize}_{x\in R^n}& \frac{1}{2}{x}^{T}Hx+c^{T}x& \text{(a)}\\ \text{subject to}& {\sum }_1^n{x}_i{x}_j{Q}_{ij}^k+{\sum }_1^n{x}_i{A}_i^k-A_0^k⪰0\text{,}k=1,\dots ,m_A\text{,}& \text{(b)}\\ & l_B\le Bx\le u_B\text{,}& \text{(c)}\\ & l_x\le x\le u_x\text{.}& \text{(d)}\end{array}\end{array}$$

Here $c$, $l_x$ and $u_x$ are $n$-dimensional vectors, $H$ is a symmetric $n\times n$ matrix, $l_B$, $u_B$ are $m_B$-dimensional vectors, $B$ is a general $m_B\times n$ rectangular matrix and $A_i^k$, $Q_{ij}^k$ are symmetric matrices. The expression $S⪰0$ stands for a constraint on eigenvalues of a symmetric matrix $S$, namely, all the eigenvalues should be non-negative, i.e., the matrix should be positive semidefinite. See relevant functions in the suite for more details on the problem formulation.

The solver is based on a generalized Augmented Lagrangian method with a suitable choice of standard and matrix penalty functions. For a detailed description of the algorithm see Algorithmic Details. Under standard assumptions on the problem (Slater constraint qualification, boundedness of the objective function on the feasible set, see Stingl (2006) for details) the algorithm converges to a local solution. In case of convex problems such as linear SDP or convex QP, this is the global solution. The solver is suitable for both small dense and large-scale sparse problems.

The algorithm behaviour and solver strategy can be modified by various options (see Other Parameters) which can be set by handle_opt_set() and handle_opt_set_file() anytime between the initialization of the handle by handle_init() and a call to the solver. Once the solver has finished, options may be modified for the next solve. The solver may be called repeatedly with various starting points and/or options.

There are several options with a multiple choice where the default choice is ‘AUTO’ (for example, ‘Hessian Density’). This value means that the decision over the option is left to the solver based on the structure of the problem. Option getter handle_opt_get() can be called to retrieve the choice of these options as well as on any other options.

Option ‘Task’ may be used to switch the problem to maximization or to ignore the objective function and find only a feasible point.

Option ‘Monitor Frequency’ may be used to turn on the monitor mode of the solver. The solver invoked in this mode pauses regularly even before the optimal point is found to allow monitoring the progress from the calling program. All the important error measures and statistics are available in the calling program which may terminate the solver early if desired (see argument $inform$).

Structure of the Lagrangian Multipliers

The algorithm works internally with estimates of both the decision variables, denoted by $x$, and the Lagrangian multipliers (dual variables) for standard and matrix constraints, denoted by $u$ and $U$, respectively. You may provide initial estimates, request approximations during the run (the monitor mode turned on) and obtain the final values. The Lagrangian multipliers are split into two arrays, the multipliers $u$ for (standard) constraints are stored in array $u$ and multipliers $U$ for matrix constraints in array $ua$. Both arrays need to conform to the structure of the constraints.

If the simple bounds were defined (handle_set_simplebounds() was successfully called), the first $2n$ elements of $u$ belong to the corresponding Lagrangian multipliers, interleaving a multiplier for the lower and for the upper bound for each $x_i$. If any of the bounds were set to infinity, the corresponding Lagrangian multipliers are set to $0$ and may be ignored.

Similarly, the following $2m_B$ elements of $u$ belong to multipliers for the linear constraints, if formulated by handle_set_linconstr(). The organization is the same, i.e., the multipliers for each constraint for the lower and upper bounds are alternated and zeroes are used for any missing (infinite bound) constraint.

A Lagrangian multiplier for a matrix constraint (one block) of dimension $d\times d$ is a dense symmetric matrix of the same dimension. All multipliers $U$ are stored next to each other in array $ua$ in the same order as the matrix constraints were defined by handle_set_linmatineq() and handle_set_quadmatineq(). The lower triangle of each is stored in the packed column order (see the F07 Introduction). For example, if there are four matrix constraints of dimensions $7$, $3$, $1$, $1$, the dimension of array $ua$ should be $36$. The first $28$ elements $(d_1\times (d_1+1)/2)$ belong to the packed lower triangle of $U_1$, followed by six elements of $U_2$ and one element for each $U_3$ and $U_4$.

Approximation of the Lagrangian Multipliers

By the nature of the algorithm, all inequality Lagrangian multiplier $u,U$ are always kept positive during the computational process. This applies even to Lagrangian multipliers of inactive constraints at the solution. They will only be close to zero although they would normally be equal to zero exactly. This is one of the major differences between results from solvers based on the active set method (such as qpconvex2_sparse_solve()) and others, such as, handle_solve_pennon or interior point methods. As a consequence, the initial estimate of the multipliers (if provided) might be adjusted by the solver to be sufficiently positive, also the estimates returned during the intermediate exits might only be a very crude approximation to their final values as they do not satisfy all the Karush–Kuhn–Tucker (KKT) conditions.

Another difference is that qpconvex2_sparse_solve() merges multipliers for both lower and upper inequality into one element whose sign determines the inequality because there can be at most one active constraint and multiplier for the inactive is exact zero. Negative multipliers are associated with the upper bounds and positive with the lower bounds. On the other hand, handle_solve_pennon works with both multipliers at the same time so they are returned in two elements, one for the lower bound, the other for the upper bound (see Structure of the Lagrangian Multipliers). An equivalent result can be achieved by subtracting the upper bound multiplier from the lower one. This holds even when equalities are interpreted as two inequalities (see option ‘Transform Constraints’).

References

Ben–Tal, A and Zibulevsky, M, 1997, Penalty/barrier multiplier methods for convex programming problems, SIAM Journal on Optimization (7), 347–366

Fujisawa, K, Kojima, M, Nakata, K, 1997, Exploiting sparsity in primal-dual interior-point method for semidefinite programming, Math. Programming (79), 235–253

Hogg, J D and Scott, J A, 2011, HSL MA97: a bit-compatible multifrontal code for sparse symmetric systems, RAL Technical Report. RAL-TR-2011-024

Kočvara, M and Stingl, M, 2003, PENNON – a code for convex nonlinear and semidefinite programming, Optimization Methods and Software (18(3)), 317–333

Kočvara, M and Stingl, M, 2007, On the solution of large-scale SDP problems by the modified barrier method using iterative solvers, Math. Programming (Series B) (109(2–3)), 413–444

Mittelmann, H D, 2003, An independent benchmarking of SDP and SOCP solvers, Math. Programming (95), 407–430

Stingl, M, 2006, On the Solution of Nonlinear Semidefinite Programs by Augmented Lagrangian Methods, PhD thesis, Institute of Applied Mathematics II, Friedrich–Alexander University of Erlangen–Nuremberg

See also

naginterfaces.library.examples.opt.handle_solve_pennon_bmi_ex.main()

naginterfaces.library.examples.opt.handle_solve_pennon_lmi_ex.main()