User manual MATLAB OPTIMIZATION TOOLBOX 5

[. . . ] Optimization ToolboxTM 5 User's Guide How to Contact The MathWorks Web Newsgroup www. mathworks. com/contact_TS. html Technical Support www. mathworks. com comp. soft-sys. matlab suggest@mathworks. com bugs@mathworks. com doc@mathworks. com service@mathworks. com info@mathworks. com Product enhancement suggestions Bug reports Documentation error reports Order status, license renewals, passcodes Sales, pricing, and general information 508-647-7000 (Phone) 508-647-7001 (Fax) The MathWorks, Inc. 3 Apple Hill Drive Natick, MA 01760-2098 For contact information about worldwide offices, see the MathWorks Web site. Optimization ToolboxTM User's Guide © COPYRIGHT 1990­2010 by The MathWorks, Inc. The software described in this document is furnished under a license agreement. The software may be used or copied only under the terms of the license agreement. [. . . ] To use a trust-region strategy, a merit function is needed to decide if xk + 1 is better or worse than xk. A possible choice is min f (d) = d 1 T F ( xk + d ) F ( xk + d ) . 2 But a minimum of f(d) is not necessarily a root of F(x). The Newton step dk is a root of M(xk + d) = F(xk) + J(xk)d, and so it is also a minimum of m(d), where 6-174 Equation Solving min m(d) = d 1 1 2 2 M ( xk + d ) = F ( xk ) + J ( xk ) d 2 2 2 2 1 1 T T T = F ( xk ) F ( xk ) + dT J ( xk ) F ( xk ) + dT J ( xk ) J ( xk ) d. (6-120) 2 2 Then m(d) is a better choice of merit function than f(d), and so the trust-region subproblem is 1 1 T T T min F ( xk ) F ( xk ) + dT J ( xk ) F ( xk ) + dT J ( xk ) J ( xk ) d , 2 d 2 (6-121) such that D·d . This subproblem can be efficiently solved using a dogleg strategy. For an overview of trust-region methods, see Conn [4], and Nocedal [31]. Trust-Region Dogleg Implementation The key feature of this algorithm is the use of the Powell dogleg procedure for computing the step d, which minimizes Equation 6-121. For a detailed description, see Powell [34]. The step d is constructed from a convex combination of a Cauchy step (a step along the steepest descent direction) and a Gauss-Newton step for f(x). The Cauchy step is calculated as dC = ­J(xk)TF(xk), where is chosen to minimize Equation 6-120. The Gauss-Newton step is calculated by solving J(xk)·dGN = ­F(xk), using the MATLAB \ (matrix left division) operator. The step d is chosen so that d = dC + (dGN ­ dC), 6-175 6 Optimization Algorithms and Examples where is the largest value in the interval [0, 1] such that d . If Jk is (nearly) singular, d is just the Cauchy direction. The dogleg algorithm is efficient since it requires only one linear solve per iteration (for the computation of the Gauss-Newton step). Additionally, it can be more robust than using the Gauss-Newton method with a line search. Trust-Region Reflective fsolve Algorithm Many of the methods used in Optimization Toolbox solvers are based on trust regions, a simple yet powerful concept in optimization. To understand the trust-region approach to optimization, consider the unconstrained minimization problem, minimize f(x), where the function takes vector arguments and returns scalars. Suppose you are at a point x in n-space and you want to improve, i. e. , move to a point with a lower function value. The basic idea is to approximate f with a simpler function q, which reasonably reflects the behavior of function f in a neighborhood N around the point x. A trial step s is computed by minimizing (or approximately minimizing) over N. This is the trust-region subproblem, min {q(s), s N } . s (6-122) The current point is updated to be x + s if f(x + s) < f(x); otherwise, the current point remains unchanged and N, the region of trust, is shrunk and the trial step computation is repeated. The key questions in defining a specific trust-region approach to minimizing f(x) are how to choose and compute the approximation q (defined at the current point x), how to choose and modify the trust region N, and how accurately to solve the trust-region subproblem. This section focuses on the unconstrained problem. [. . . ] If you do not supply x0, or x0 is not strictly feasible, quadprog chooses a new strictly feasible (centered) starting point. If an equality constrained problem is posed and quadprog detects negative curvature, the optimization terminates because the constraints 11-231 quadprog are not restrictive enough. In this case, exitflag is returned with the value -1, a message is displayed (unless the options Display option is 'off'), and the x returned is not a solution but a direction of negative curvature with respect to H. Algorithm Large-Scale Optimization The large-scale algorithm is a subspace trust-region method based on the interior-reflective Newton method described in [1]. Each iteration involves the approximate solution of a large linear system using the method of preconditioned conjugate gradients (PCG). [. . . ]