Chapter 4 Constrained Optimization: FX XR GX HX U M V PN

Chapter 4 Constrained Optimization
Introduction
The standard form of the constrained optimization problem is as follows: Minimize f ( x)
x Rn u = 1, 2,..., m v = 1, 2,..., p < n
Subject to
gu ( x) 0 hv ( x) = 0
According to the solve algorithm, indirect method and direct method. Direct method: Sequential Linear Programming; Generalized Reduced gradient method, Methods of feasible direction. Indirect method: Penalty function method, Interior and exterior penalty function method. Direct search methods persist for several good reasons. First and foremost, direct search methods have remained popular because they work well in practice. In fact, many of the direct search methods are based on surprisingly sound heuristics( ) that fairly recent analysis demonstrates guarantee global convergence behavior analogous to the results known for globalized quasi-Newton techniques. Direct search methods succeed because many of them can be shown to rely on techniques of classical analysis in ways that are not readily apparent from their original specifications. Second, quasi-Newton methods are not applicable to all nonlinear optimization problems. Direct search methods have succeeded when more elaborate approaches failed. Features unique to direct search methods often avoid the pitfalls() that can plague() more sophisticated approaches. Third, direct search methods can be the method of first recourse, even among well-informed users. The reason is simple enough: direct search methods are reasonably straight forward to implement and can be applied almost immediately to many nonlinear optimization problems. The requirements from a user are minimal and the algorithms themselves require the setting of few parameters. It is not unusual for complex optimization problems to require further software development before quasi-Newton methods can be applied. For such problems, it can make sense to begin the search for a minimizer using a direct search method with known global convergence properties, while undertaking the preparations for the quasi-Newton method. When the preparations for the quasi-Newton method have been completed, the best known result from the direct search calculation can be used as a hot start for one of the quasi-Newton approaches, which enjoy superior local convergence properties. Such hybrid optimization strategies are as old as the direct search methods themselves. Random Search Method: Generates trial solution for the decision variables. Classification: Random jump, random walk, and random walk with direction exploitation.
Random Jump: generates huge number of data points assuming uniform distribution of decision variables and selects the best one. Random Walk: generates trial solution with sequential improvements using scalar step length and unit random vector. Random Walk with Direction Exploitation: Improved version of random walk search, successful direction of generating trial solution is found out and steps are taken along this direction. Univariate search Perform search in one direction at a time using one-dimensional search methods.Go through all variables in a sequence and then repeat the sequence.
Penalty function methods

Penalty function methods are used to convert constrained problems into unconstrained problems. In this class of methods we replace the original constrained problem by a sequence of unconstrained subproblems that minimizes the penalty functions. The penalty function is a function with penalty property
( x, r1 , r2 ) = f ( x ) + r1 G hk ( x ) g j ( x) + r2 H
j =1 k =1
Constructed from the objective function f ( x) and the constraints g , h . The so-called penalty property requires ( x) = f ( x) for all feasible points x X , and ( x) is much larger than f ( x ) when the constraint violations are severe.
Interior Penalty Method

If the penalty function takes values approaching + as x approaches the boundary of the feasible region, it is called the interior point penalty function. The interior point penalty function is suitable only to inequality-constrained problems. Typically, the two most important interior point penalty functions are the inverse barrier function:
( x, r ) = f ( x ) r
and the logarithmic barrier function
j =1 m
g j ( x)
( x, r ) = f ( x ) r ln g j ( x )
where r reduces from a high value to 0 gradually.
j =1
If given an initial point in the interior of the feasible region, the whole sequence generated by the interior point penalty function method is interior points. Since these functions set an infinitely high barrier on the boundary, they are also said to be barrier functions. Selecting r at the start of the optimization procedure:
r1 = ( 0.1 ~ 1 )
f ( x1 ) 1 where x1 is the initial point in the feasible region. g ( x1 )
Flow-chart summarizes the optimization procedure of the interior penalty method. Here the reduction follows: rk +1 = c rk where
is a coefficient less than 1.
Hence ordinary penalty functions generally require the value of some coefficients to be specified at the beginning of optimization. However these coefficients usually have no clear physical meaning. Consequently, it is very difficult to select appropriate values for these coefficients even by experience.
Exterior Penalty Method

The widely used form of in the exterior penalty method is:
( x, r ) = f ( x ) + r max hk ( x ) 0, g j ( x ) + r
2 j =1 k =1
and r is a parameter which is modified at the beginning of each round of optimization. Each optimization round is defined here as a complete optimization of (x, r ) for a fixed value of rk
until the convergence is achieved. The optimum point x* at the end of each round serves as the starting point x1 of the next round of optimization with a larger rk . Flow-chart shows the general optimization procedure of the exterior penalty method for problems with inequality and equality constraints. The selection of appropriate rk values is vital for faster convergence and more precision. In some
cases the user might specify the value of rk at the end of each optimization round. This technique
is very interactive and time consuming and is not generally preferred. Another dominant technique
is to define a function which automatically determines the rk value at the beginning of a new round of optimization. Denoting the optimization steps by k, then k = 1 at the onset of
optimization and rk = r1 . The selection of an appropriate r1 plays a key role in the convergence
behavior of the method. They have also suggested that rk be updated according to: rk +1 = c rk where for most structural problems a value of c = 5 has been found satisfactory. The third
alternative to determine appropriate rk is to use the so called intelligent and adaptive techniques such as fuzzy logic and neural networks.

Chapter 4 Constrained Optimization: FX XR GX HX U M V PN

Uploaded by

Copyright:

Available Formats

Chapter 4 Constrained Optimization: FX XR GX HX U M V PN

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Chapter 4 Constrained Optimization: FX XR GX HX U M V PN

Uploaded by

Copyright:

Available Formats

Chapter 4 Constrained Optimization

x Rn u = 1, 2,..., m v = 1, 2,..., p < n

Penalty function methods

Interior Penalty Method

f ( x1 ) 1 where x1 is the initial point in the feasible region. g ( x1 )

is a coefficient less than 1.

Exterior Penalty Method

You might also like