Unit 3.2: Direct Methods

Direct methods handle constraints by explicitly keeping the search point within the feasible region (the area where all constraints are satisfied). If a search step lands outside, the algorithm corrects the path.

A. Random Search Method

A brute-force probabilistic approach.

1. Generate a random point X.
2. Check if it satisfies all constraints.

• If Yes: Calculate f(X) and see if it's the best so far.
• If No: Discard the point.

1. Repeat for N iterations.

• Pros: Simple, works on any function. Cons: Very inefficient for high precision.

B. Complex Method (Box’s Method)

An extension of the Simplex method for constrained problems. It uses a "complex" (a geometric figure with n+1 vertices) that moves, expands, or contracts to find the optimum.

Procedure:

1. Generate an initial set of k feasible points.
2. Identify the "worst" point (highest function value).
3. Reflection: Replace the worst point by reflecting it through the centroid of the remaining points.
4. Correction: If the new point violates constraints, retract it halfway toward the centroid until it becomes feasible.

C. Sequential Linear Programming (SLP)

This method approximates the non-linear objective function and constraints using Taylor series expansions to convert the problem into a Linear Programming (LP) problem.

Procedure:

1. Linearize f(X) and constraints g(X) at the current point Xᵢ.
2. Solve the resulting LP problem using the Simplex method to find a new search direction.
3. Move to the new point and repeat the linearization.