Let *f: R ^{ny} × R^{nu} → R * and

(1)

has a unique solution

(2)

and consider the imlicitly constrained optimization problem

(3)

(Note: In this html document I use

The paper M. Heinkenschloss: Numerical Solution of Implicitly Constrained Optimization Problems discusses the application of optimization algorithms for the solution of (3). This page contains links to the Matlab code used in that paper.

Download a zip file with all Matlab functions or download individual functions below. The functions are organized into three different subdirectories shown below.

**optimization**

Code for the solution of*min f(x)*, where*f: R*. Note, the optimization algorithms use the generic notation typically found in unconstrained optimization, rather than the notation in (3). That is, in the optimization algorithms the unkowns are denoted by^{n}→ R*x*and the objective function is denoted by*f*.- newton_cg.m:
This is an implementation of the Newton-CG method described, e.g., in Section 7.1 of the book
*J. Nocedal and S. J. Wright: Numerical Optimization, second edition, Springer Verlag, Berlin, Heidelberg, New York, 2006.* - lbfgs.m:
This is an implementation of the limited BFGS method described, e.g., in Section 7.2 of the book
*J. Nocedal and S. J. Wright: Numerical Optimization, second edition, Springer Verlag, Berlin, Heidelberg, New York, 2006.*However, this implementation uses an Armijo linear search or a backtracking line-search. Both, unlike a line search that enforces the so-called Wolfe condition (see the book by Nocedal and Wright), do not guarantee that*y*(here we use notation of Nocedal and Wright). We skip the update if_{k}^{T}s_{k}>0*y*is not satisfied. It is easy to replace the existing line search algorithms with a line search algorithm that satisfies the Wolfe conditions (for details see pages 60-62 in_{k}^{T}s_{k}>0*J. Nocedal and S. J. Wright: Numerical Optimization, second edition, Springer Verlag, Berlin, Heidelberg, New York, 2006*). - mycg.m: Implementation of the conjugate gradient method for computation of approximate Newton steps. Called in newton_cg.m.
- lnsrch_arm.m: Implementation of the Armijo line-search.
- lnsrch_bt.m: Implementation of the
backtracking line-search. This implemetation follows that in
*J. E. Dennis, Jr., and R. B. Schnabel: Numerical Methods for Nonlinear Equations and Unconstrained Optimization, SIAM, Philadelphia, 1996*. - deriv_check.m: Function that, given the user interface described below performs some basic derivative checks.

`usr_par`. The variable`usr_par`is never accessed in the optmization codes, but can be used to pass parameters and other problem specific information to the user provided functions.-
`function [fx] = fval(x, usr_par)`: Evaluate*f(x)*.`usr_par`is a variable that is never accessed in the optmization codes, but can be used to pass parameters and other problem specific information to the function. -
`function [gx] = grad(x, usr_par)`: Evaluate*∇ f(x)*. -
`function [Hv] = Hessvec(v, x, usr_par)`: Evaluate*∇*. (Only used in newton_cg.m.)^{2}f(x) v -
`function [Hv] = H0vec(v, usr_par)`: Compute*H*, where_{0}v*H*is the initial BFGS matrix, which is a replacement of the inverse of the Hessian of_{0}v*f*. (Only used in lbfgs.m.) -
`function [usr_par] = xnew( x, iter, usr_par)`i:`xnew`is called whenever a new*x*is generated and it is called before any of the three functions`fval`,`grad`, and`Hessvec`are called with this new*x*. -
`function [x1x2] = xprod( x1, x2, usr_par)`: All optimization algorithms above are implemented using an arbitrary inner product*< x*between two vectors_{1}, x_{2}>*x*. A properly chosen inner product can substantially improve the performance of the optimization algorithm. This is especially important for problems involving discretizations of differential equations. See Section 2 of M. Heinkenschloss and L. N. Vicente: An Interface Between Optimization and Application for the Numerical Solution of Optimal Control Problems, ACM Transactions on Mathematical Software, Vol. 25 (1999), pp. 157-190 for a relatively elementary exposition and more references._{1}, x_{2}

In both examples below, we use the standard Euclidean inner product*< x*and with this choice, newton_cg.m lbfgs.m, and mycg.m correspond to the Newton-CG, LBFGS and conjugate gradient methods discussed, e.g., in_{1}, x_{2}> = x_{1}^{T}x_{2}*J. Nocedal and S. J. Wright: Numerical Optimization, second edition, Springer Verlag, Berlin, Heidelberg, New York, 2006.*

- newton_cg.m:
This is an implementation of the Newton-CG method described, e.g., in Section 7.1 of the book
**rosenbrock**

The codes in this section apply newton_cg.m and lbfgs.m to minimize the 2D Rosenbrock function, i.e., to solve

*min (1-x*._{1})^{2}+ 100( x_{1}- x_{1}^{2})^{2}

This is not an implicitly constrained problem, but is included to illustrate how to apply the optimization algorithms to a simple model problem.- optimization_driver.m: The main script.
- fval.m, grad.m, Hessvec.m, H0vec.m, xnew.m, xprod.m: Implementation of the interface to the optimizers.

**burgers**

The codes in this section apply newton_cg.m and lbfgs.m to solve the discretized optimal control problem governed by Burgers equation as described in the paper M. Heinkenschloss: Numerical Solution of Implicitly Constrained Optimization Problems.- optimization_driver.m: The main script.
- prob_gen.m: Computes quantities like the
stiffness matrix
*A*. These are stored as global variables._{h} - state.m: Compute a solution of the discretized Burgers equation.
- adjoint.m: Compute a solution of the discre adjopint equation.
- Ny.m, Nyp.m: Evaluate the nonlinearity in the discretized Burgers equation and the Jacobian of the nonlinearity in the discretized Burgers equation, respectively.
- xnew.m: Solve the Burgers equation and solve the adjoint equation. The solution to Burgers equation and to the adjoint equation are stored as global variables so that they can be accessed by fval.m, grad.m, and Hessvec.m. Furthermore, the current control, the state and the adjoint are plotted. (Note that we could have computed the solution to the adjoint equation later in grad.m).
- fval.m, grad.m, Hessvec.m: Implemtentation of function evaluation, gradient evaluation using the adjoint approach, and Hessian-times-vector computation.
- H0vec.m: Compute the
- xprod.m:
For two vectors
*x*this function returns the Euclidean inner product_{1}, x_{2}*x*._{1}^{T}x_{2}