03ImprovingSearch.ppt

TP SHUAI * * * * * * * 3.3 Algebraic conditions for improving and feasible directions Gradients Gradients show graphically as vectors perpendicular to contours of the objective function and point in the direction of most rapid objective value increase. Gradient conditions for improving directions Suppose that our search of objective function f has arrived at current solution x. Then the change associated with a step of size ? in direction ?x can be approximated as Theorem: Direction ?x is improving for maximize objective function f at point at x if ?f(x)??x0. On the other hand, if ?f(x)??x0, ?x does not improve at x Case where dot product ?f(x)??x=0 cannot be resolved without further information! Theorem: Direction ?x is improving for minimize objective function f at point at x if ?f(x)??x0. On the other hand, if ?f(x)??x0, ?x does not improve at x Note that We then need only choose ?x=??f(x) Theorem: When objective function gradient ?f(x)?0 Direction ?x= ?f(x) ( ?x=??f(x)) is an improving direction for a maximize (minimize)objective f. Active constraints and feasible direction Turning now to conditions for feasibility of directions, we focus our attention on constraints. Constraints define the boundary of the feasible region for an optimization model, so they will be the source of conditions for feasible directions. Not all the constraints of a model are relevant to whether a direction ?x is feasible at a particular solution x. For example, in Two Crude model, at point x=(4,4), any direction is feasible, but for point x=(7,0), any feasible direction ?x=(x,y) must satisfy y?0 because constraint x2?0 limits the feasibility of directions. Whether a direction is feasible at a solution x depends on whether it would lead to immediate violation of any active constraint(or tight constraints/ binding constrains) at x, i.e., any constraint satisfied as equality at x. Equality constraints are always active at every feasible point. Conditions for feasible dire