Non-linear Programming
(Indirect methods of multi variable Unconstrained optimization)
• Indirect methods of unconstrained optimization:
an approximate solution is sought by proceeding in an iterative manner by starting from an
initial solution.
The Indirect methods or the descent techniques require, in addition to the function values,
the first and in some cases the second derivatives of the objective function.
Since more information about the function being minimized is used (through the use of
derivatives), descent methods are generally more efficient than direct search techniques.
The descent methods are known as gradient methods.
Non-linear Programming
(Indirect methods of multi variable Unconstrained optimization)
• Examples of Indirect methods:
Non-linear Programming
(Indirect methods of multi variable Unconstrained optimization)
• Steepest Descent (Cauchy) method:
In this method we start from an initial trial point X1 and iteratively move along the
steepest descent directions until the optimum point is found.
The steepest descent method can be summarized by the following steps:
1. Start with an arbitrary initial point X1. Set the iteration number as i = 1.
2. Find the search direction Si as
3. Determine the optimal step length 𝜆∗𝑖 in the direction Si and set
4. Test the new point, Xi+1, for optimality. If Xi+1 is optimum, stop the process.
Otherwise, go to step 5.
5. Set the new iteration number i = i + 1 and go to step 2.
Non-linear Programming
(Indirect methods of multi variable Unconstrained optimization)
Steepest Descent (Cauchy) method
• Convergence criteria (stopping rules):
The following criteria can be used to terminate the iterative process.
1.When the change in function value in two consecutive iterations is small:
2.When the partial derivatives (components of the gradient) of f are small:
3.When the change in the design vector in two consecutive iterations is small:
Non-linear Programming
(Indirect methods of multi variable Unconstrained optimization)
Steepest Descent (Cauchy) method
• Example 1:
Non-linear Programming
(Indirect methods of multi variable Unconstrained optimization)
Steepest Descent (Cauchy) method
• Example 1 (cont.):
Non-linear Programming
(Indirect methods of multi variable Unconstrained optimization)
Steepest Descent (Cauchy) method
• Example 1 (cont.):
Non-linear Programming
(Indirect methods of multi variable Unconstrained optimization)
Steepest Descent (Cauchy) method
• Example 1 (cont.):
Non-linear Programming
(Indirect methods of multi variable Unconstrained optimization)
Steepest Descent (Cauchy) method
• Example 1 (cont.):
Non-linear Programming
methods of multi variable constrained optimization
Frank-Wolf Method
• Solves linearly constrained problems.
• The starting point must be feasible.
• The objective function is linearized about the current solution in each
iteration.
𝜕𝑓 𝜕𝑓
𝑓 𝑥, 𝑦 = 𝑓 𝑥𝑖 , 𝑦𝑖 + 𝑥 − 𝑥𝑖 + 𝑦 − 𝑦𝑖
𝜕𝑥 𝜕𝑦
• Thus, the linearized objective function may be reduced to
𝜕𝑓 𝜕𝑓
z= 𝑥 + 𝑦
𝜕𝑥 𝜕𝑦
Frank-Wolf Method
Frank-Wolf Method
Frank-Wolf Method
Frank-Wolf Method
• Thus, the linearized objective function
about (0,0)
z= 5 𝑥 + 8 𝑦
Frank-Wolf Method
Frank-Wolf Method
Frank-Wolf Method
Frank-Wolf Method
Non-linear Programming
(Direct methods of multi variable constrained optimization)
• Direct methods of constrained optimization:
• Feasible solutions to many realistic n-dimensional optimization problems
• The constraints are usually expressed as equalities or inequalities involving the decision
variables
• Constrained non-linear optimization methods can be classified into two broad
categories: direct methods and indirect methods
Non-linear Programming
(Direct methods of multi variable constrained optimization)
• Examples of Direct methods of constrained optimization:
Non-linear Programming
(Direct methods of multi variable constrained optimization)
Generalized reduced gradient method GRG
• Solution Steps
Non-linear Programming
(Direct methods of multi variable constrained optimization)
Generalized reduced gradient method GRG
• Solution Steps
Non-linear Programming
(Direct methods of multi variable constrained optimization)
Generalized reduced gradient method GRG
• Solution Steps
Non-linear Programming
(Direct methods of multi variable constrained optimization)
Generalized reduced gradient method GRG
• Solution Steps
Non-linear Programming
(Direct methods of multi variable constrained optimization)
Generalized reduced gradient method GRG
• Example 1:
Non-linear Programming
(Direct methods of multi variable constrained optimization)
Generalized reduced gradient method GRG
• Example 1 (cont.):
Non-linear Programming
(Direct methods of multi variable constrained optimization)
Generalized reduced gradient method GRG
• Example 1 (cont.):
Non-linear Programming
(Direct methods of multi variable constrained optimization)
Generalized reduced gradient method GRG
• Example 1 (cont.):
Non-linear Programming
(Direct methods of multi variable constrained optimization)
Generalized reduced gradient method GRG
• Example 1 (cont.):
Non-linear Programming
(Direct methods of multi variable constrained optimization)
Generalized reduced gradient method GRG
• Example 1 (cont.):
Non-linear Programming
(Direct methods of multi variable constrained optimization)
Generalized reduced gradient method GRG
• Example 1 (cont.):
Non-linear Programming
(Direct methods of multi variable constrained optimization)
Generalized reduced gradient method GRG
• Example 1 (cont.):
Non-linear Programming
(Direct methods of multi variable constrained optimization)
Generalized reduced gradient method GRG
• Example 1 (cont.):
Non-linear Programming
(Direct methods of multi variable constrained optimization)
Generalized reduced gradient method GRG
• Example 1 (cont.):
Non-linear Programming
(Direct methods of multi variable constrained optimization)
Generalized reduced gradient method GRG
• Example 1 (cont.):
Non-linear Programming
(Direct methods of multi variable constrained optimization)
Generalized reduced gradient method GRG
• Example 1 (cont.):
Non-linear Programming
(Direct methods of multi variable constrained optimization)
Generalized reduced gradient method GRG
• Example 1 (cont.):
