Contents

1 Introduction

The problem is to maximize a function (\(f(\bar {x})\)), \begin {equation} \mathrm {Max~} f(\bar {x}), ~~~ \bar {x}=(x_1,x_2,\dots ,x_n) \end {equation} The necessary condition for an optimal solution is: \begin {equation} \frac {\partial f(\bar {x})}{\partial x_j} \ge 0; ~~~ j=1,2,\dots ,n. \end {equation} The sufficient condition is \(f(\bar {x})\) is concave.

If we cannot solve this analytically, then we go for numercial solution. In single variable case, we have only one direction of improvement, or one dimentional serch. But innumerable directions are possible in the case multi-variable functions.

1.1 Notations

Define the gradient vector as: \begin {equation} \nabla f(\bar {x}) = \left (\frac {\partial f}{\partial x_1},\frac {\partial f}{\partial x_2},\dots ,\frac {\partial f}{\partial x_n}\right ) \end {equation} The gradient at \(\bar {x}=\bar {x}^{k}\) is the gradient vector evaluated at that point. The geometrical understanding of the gradient vector is the direction of the gradient vector (\(\nabla f(\bar {x})\)) from the origin to that point \(\bar {x}^{k}\). The rate at whcih \(f(\bar {x})\) increases is maximized if changes in \(\bar {x}\) are in the direction of the gradient untile it reaches \(\bar {x}^{*}\) where \(\nabla f(\bar {x}^{*})=0\); Ideally, \(\bar {x}\) need to be incremented in the directon of the gradient until it reaches \(\bar {x}^{*}\) where the \(\nabla f(\bar {x}^{*})=0\). It may not be practicall possible to move in the direction of \(\nabla f(\bar {x})\). The better option is to keep moving in the fixed direction from the current trial solution until \(f(\bar {x})\) stops improving. The stopping point will be the next trail solution and the gradient is calulated to determn the new direction. At each iteration: \begin {equation} \bar {x}^{k+1} = \bar {x}^{k} + t \times \nabla f(\bar {x}^{k}) \end {equation} where \(t^*\) is the postive value of the \(t\) such that: \begin {equation} f(\bar {x} + t^* \nabla f(\bar {x}))=\max _{t\ge 0}~[ f(\bar {x}^{'}+t\times \nabla f(\bar {x}^{'}))]. \end {equation}

1.2 Algorithm

1. Step 0. Initilize: select the tolerence \(\epsilon \), set the interation number \(k=0\), and select the starting point \(\bar {x}^{k}\)
2. Step 1. Direction: set \(\bar {x}^{k+1} = \bar {x}^{k} + t^k \times \nabla f(\bar {x}^{k}) \) substitute \(\bar {x}^{k+1}\) in \(f(\bar {x}^{})\) so that \(g(t^{k})=f(\bar {x}^{k}+t^k\times \nabla f(\bar {x}^{k}))\)
3. Step 2. Optimum search: Use one dimentional search (numerical or analytical) to find \(t^{k^{*}}\) that maximizes \(g(t^{k})\), i.e. \(\displaystyle \max _{t^k\ge 0}~[ f(\bar {x}^{k}+t^k\times \nabla f(\bar {x}^{k}))]\).
4. Step 3. Update: reset \(\bar {x}^{k+1} = \bar {x}^{k} + t^{k^{*}} \times \nabla f(\bar {x}^{k})\).
5. Step 4. Stopping rule: evaluate \(\nabla f(\bar {x}^{k+1})\), check if \( \left | \frac {\partial f}{\partial x_j} \right | \le \epsilon , ~~~ \forall ~ j=1,2,\dots ,n\), and if so stop, otherwise set \(k=k+1\), and go to step 1.

1.3 Numerical Illustration

Max \(f(\bar {x})=2x_1x_2+2x_2-x1^2-2x_2^2\). Assume the start point is origin.

Solution:

1. compute \(\frac {\partial f}{\partial x_1}=-2x_1+2x_2\)
2. compute \(\frac {\partial f}{\partial x_2}=2x_1-4x_2+2\)
3. compute \(\frac {\partial ^2 f}{\partial x_1^2}=-2\)
4. compute \(\frac {\partial ^2 f}{\partial x_2^2}=-4\)
5. compute \(\frac {\partial ^2 f}{\partial x_1~x_2}=2\)
6. Hessian is \(\frac {\partial ^2 f}{\partial x_1^2} \frac {\partial ^2 f}{\partial x_2^2} - 2 \frac {\partial ^2 f}{\partial x_1~x_2}=4\)
7. the Hessian is positive definite and hence the function is strictly concave.
8. Step 0: Initial trial solution (given) \(\bar {x}=(0,0)\)
9. hence, \(\nabla f(\bar {x})|_{(0,0)} = (0,2)\)
10. Step 1: \(x_1^1=x_1^0+t^0\times 0=0\) and \(x_2^1=x_2^0+t^0\times 2=2t^0\)
11. substitute in \(f(\bar {x})\) i.e. \(f(0,2t^0)\) to get \(4t^0-8t^{0^2}\)
12. find \(t^{0^*}\) by \(\displaystyle \max _{t^{0} \ge 0} (4t^0-8t^{0^2})\)
13. i.e \(\frac {df}{dt^0}=4-16t^0=0.25\). Hence, \(t^{0^*}=0.25\).
14. Step 2: \(\bar {x}^{1}=(0,0)+0.25\times (\)

Exercises

1. Not Available

References

1. Frederick S Hillier and Gerald J Lieberman. Introduction to Operations Research. Tata McGraw-Hill Publishers, New Delhi, 2001.

Acknowledgments

I wish to thank several of my students and staff of NPTEL for their contribution in this lecture. I also appreciate your constructive feedback which may be sent to tvm@civil.iitb.ac.in. Prof. Tom V. Mathew, Department of Civil engineering, Indian Instiute of Technology Bombay, India.