View source for Scilab---FOSSEE-Optimisation-Toolbox/C2/Quadratic-Optimisation-using-FOT/English

'''Title of the script''': '''Quadratic Optimization'''

'''Author: Siddharth Agarwal and Mankrit Singh'''

'''Keywords: FOSSEE Optimization Toolbox, Integer Quadratic optimization, Quadratic optimization, OR, quadprog, intquadprog .'''

{| border=1
! '''Visual Cue'''
! '''Narration'''
|-
|
Show Slide

'''Title Slide'''
| Hello and welcome to the Spoken tutorial on '''Quadratic optimization.'''
|-
|
Show Slide

'''Learning Objectives'''
|
In this tutorial, we will learn how to:

<ul>
<li><blockquote><p>Use '''fot underscore quadprog''' and '''fot underscore intquadprog functions''' in '''Scilab'''</p></blockquote></li>
<li><blockquote><p>Solve quadratic '''optimization''' problems using, '''fot underscore quadprog''' and '''fot underscore intquadprog functions'''</p></blockquote></li></ul>
|-
|
Show Slide

'''System Requirement'''
|
To record this tutorial, I am using

<ul>
<li><blockquote><p>'''Ubuntu 18.04'''</p></blockquote></li>
<li><blockquote><p>'''Scilab 6.1.0''' and</p></blockquote></li>
<li><blockquote><p>'''FOSSEE Optimization Toolbox''' version '''0.4.1'''</p></blockquote></li></ul>
|-
|
Show Slide

'''Pre-requisites'''

'''https://spoken-tutorial.org'''
|
To follow this tutorial, you should

<ul>
<li><blockquote><p>Install '''FOSSEE Optimization Toolbox''' version '''0.4.1''' or above</p></blockquote></li>
<li><blockquote><p>Have basic understanding of '''Scilab''' and '''optimization theory'''</p></blockquote></li>
<li><blockquote><p>If not, for relevant tutorials please visit this site.</p></blockquote></li></ul>
|-
|
Show Slide

'''Code Files'''
|
<ul>
<li><blockquote><p>The files used in this tutorial have been provided in the '''Code files''' link.</p></blockquote></li>
<li><blockquote><p>Please download and extract the files.</p></blockquote></li>
<li><blockquote><p>Make a copy and then use them while practising.</p></blockquote></li></ul>
|-
|
Show Slide

'''What is the Quadratic optimization problem?'''
|What is the '''Quadratic optimization''' problem?
A '''function''' is '''quadratic''' if it has a degree of two.

A '''quadratic optimization''' problem is a mathematical '''optimization model'''.
|-
|
Show Slide

'''What is the Quadratic optimization problem?'''
|
It has:

<ul>
<li><blockquote><p>'''Quadratic objective function'''</p></blockquote></li>
<li><blockquote><p>'''Bounds''' on the '''decision variables'''</p></blockquote></li>
<li><blockquote><p>Linear constraints on '''decision variables'''</p></blockquote></li></ul>
|-
|
Show Slide

'''Mathematical Formulation'''
| A general form of the '''quadratic optimization''' problem is as shown.
|-
|
Show Slide

'''Example'''
|
We will now solve this example to illustrate the use of '''fot underscore quadprog'''

In this example, we will learn how to minimize the given '''function'''.

Note that the '''objective function''' is '''quadratic.'''

Note that there are '''bounds''' and linear constraints on the '''variables'''.
|-
|
Show Slide

'''Example'''
|
We will use the '''toolbox''' to solve this example.

I have downloaded the required files to my '''Downloads''' folder
|-
| Cursor on the Scilab console.
| Now open the '''Scilab console.'''
|-
|
Type '''editor''' &gt;&gt; press '''Enter'''.

Point to the '''editor''' window.
|
In the '''Scilab console,''' type '''editor''' and press '''Enter.'''

'''Editor''' window opens.
|-
|
Click on Open button &gt;&gt; locate the file '''opt_quadprog .sce'''.

|
Click on the '''Open''' button on the '''toolbar''' and locate the file '''opt_quadprog .sce'''.

Then click the '''Ok''' button.

'''opt_quadprog.sce''' file opens in the '''editor'''
|-
| Show '''opt_quadprog .sce''' in scilab editor.
| Now we will see the '''input arguments''' for '''fot underscore quadprog.'''
|-
| Highlight '''‘nbVar’'''
| '''nbVar''' is an '''integer''' denoting the number of '''decision variables'''.
|-
| Highlight '''‘nbCon’'''
| '''nbCon''' is an '''integer''' denoting the number of constraints.
|-
| Highlight '''‘H’'''
| '''H''' is a '''symmetric matrix,''' representing the '''Hessian''' of the '''quadratic''' problem'''.'''
|-
| Highlight '''‘f’'''
| '''f''' is a '''vector,''' representing '''coefficients''' of the '''linear terms''' in the '''quadratic''' problem.
|-
| Highlight '''‘x0’'''
| '''x0''' is a '''vector''' containing the starting values of the '''decision variables'''.
|-
| Highlight the line with '''‘A’'''
|
'''''A''''' is a '''matrix''' of '''coefficients''' of inequality constraints.
|-
| Highlight the line with '''‘conUB’'''
| '''conUB''' is the '''vector''' of the '''upper bounds''' of the constraints.
|-
| Highlight the line with '''‘conLB’'''
| '''conLB''' is the '''vector''' of the lower '''bounds''' of the constraints.
|-
| Highlight '''lb''' and '''ub'''
|
'''lb''' and '''ub''' are row '''vectors'''.

They contain the lower and upper '''bounds''' of the '''decision variables''' respectively.
|-
| Point to the Output arguments.
|
Now we will see the '''output arguments'''.

'''Output arguments''' are '''xopt,''' '''fopt''', '''exitflag, output''' and '''lambda.'''
|-
| Highlight '''‘xopt’'''
| '''xopt''' is the optimal value of '''x'''.
|-
| Highlight '''‘fopt’'''
| '''fopt''' is the optimal '''objective function''' value.
|-
| Highlight '''‘exitflag’'''
| '''exitflag''' is the status of '''execution'''.
|-
| Highlight '''‘output’'''
| '''output''' is a '''structure''' containing detailed information about the '''optimization'''.
|-
| Highlight '''lambda'''
| '''lambda''' is a structure containing the '''Lagrange multipliers''' at the '''optimal solution.'''
|-
|
Highlight

'''[xopt,fopt,exitflag,output,lambda]='''

'''fot_quadprog(nbVar,nbCon,H,f,lb,ub,A,conLB,conUB,x0)'''
|
Here we see the '''Scilab''' code to define and solve the example.

We call the '''fot underscore quadprog function''' to solve the given problem.
|-
|
Press '''CTRL + S'''


Click on the Execute button on scilab.

Select file with echo from the drop-down.
|
Save the file by pressing '''Control''' and '''‘S’''' keys simultaneously.

To '''run''' the file, click on the '''Execute''' menu.

Then click on the '''File with echo''' from the drop down.
|-
|
Point to the Confirmation box.

Click Yes to confirm.
|
A confirmation box to clear the '''Console''' appears.

Click on the '''Yes''' button to confirm.
|-
| Change the window to Scilab console
|
Switch to the '''Scilab console''' to see the '''output'''.

The result displays “'''Optimal Solution Found.”'''

We see that it prints the '''fopt''' value, '''xopt''' values, '''exitflag, output,''' and '''lambda''' in the '''Scilab console'''.
|-
|
Show Slide

'''Integer Quadratic Programming'''
|
<ul>
<li><blockquote><p>We will now look at '''integer quadratic programming''' problems.</p></blockquote></li>
<li><blockquote><p>These are problems where some '''decision variables''' are constrained to be '''integers'''.</p></blockquote></li></ul>
|-
|
Show Slide

'''Mathematical Formulation'''
| A general form of the '''integer''' constrained '''quadratic optimization''' problem is as shown.
|-
|
Show Slide

'''Example'''
|
We will now solve this example to illustrate the use of '''fot underscore intquadprog'''.

In this example, we will learn how to minimize the given '''function'''.

Note that the '''objective function''' is '''quadratic.'''

Note that some of the '''decision variables''' are constrained to be '''integers'''.
|-
| Show '''opt_intquadprog.sce''' in scilab editor.
|
We will use the '''toolbox''' to solve this example.

Open the '''Scilab console'''.

Type '''editor''' on the '''Scilab console''' and press '''Enter'''.

Open '''opt_intquadprog.sce''' in the '''Scilab editor.'''
|-
| Highlight '''‘H’'''
| '''H''' is a '''symmetric matrix,''' representing the '''Hessian''' of the '''quadratic''' problem.
|-
| Highlight '''‘f’'''
| '''f''' is a '''vector,''' representing '''coefficients''' of the linear terms in the '''quadratic''' problem.
|-
| Highlight the line with '''‘A’'''
|
'''''A''''' is a '''matrix''' of '''coefficients''' of inequality constraints.
|-
| Highlight the line with '''b'''
| '''b''' is the '''vector''' of the RHS of the inequality constraints.
|-
| Highlight the line with '''Aeq'''
| '''Aeq''' is the '''matrix''' of the LHS of the equality constraints.
|-
| Highlight the line with '''beq'''
| '''beq''' is the '''vector''' of the RHS of the equality constraints.
|-
| Highlight '''‘intcon’'''
| '''intcon''' is a '''vector''' of the '''indices''' of '''integer variables'''.
|-
|

|Now we will see the '''output arguments'''.

'''Output arguments''' are '''xopt, fopt, exitflag, output'''
|-
| Highlight '''‘xopt’'''
| '''xopt''' is the optimal value of '''x'''.
|-
| Highlight '''‘fopt’'''
| '''fopt''' is the optimal '''objective function''' value.
|-
| Highlight '''‘exitflag’'''
| '''exitflag''' is the status of '''execution'''.
|-
| Highlight '''output'''
| '''Output''' is a '''structure''' containing detailed information about the '''optimization'''.
|-
|
Highlight

'''[xopt,fopt,exitflag,output]='''

'''fot_intquadprog(H,f,intcon,A,b,Aeq,beq)'''
| This is how we '''call fot underscore intquadprog.'''
|-
|
Press '''CTRL + S'''



Click on the Execute button on scilab.

Select file with echo from the drop-down.
|
Save the file by pressing '''Control''' and '''‘S’''' keys simultaneously.

To '''run''' the file, click on the '''Execute menu'''.

Then click on the '''File with echo''' from the drop down.
|-
|
Point to the Confirmation box.

Click Yes to confirm.
| In the confirmation box, click the '''Yes''' button to clear the '''Console'''.
|-
| Change the window to Scilab console
|
Switch to the '''Scilab console''' to see the '''output'''.

The result displays “'''Optimal Solution Found.”'''

We see that it prints the '''fopt''' value, '''xopt''' values, '''exitflag''' and '''output''' in the '''Scilab console'''.
|-
|
Show Slide

'''Summary'''
|
This brings us to the end of this tutorial. Let us summarise.

In this tutorial, we have learnt how to:

<ul>
<li><blockquote><p>Use '''fot underscore quadprog''' and '''fot underscore intquadprog functions''' of the '''FOSSEE Optimization Toolbox'''.</p></blockquote></li>
<li><blockquote><p>Solve '''quadratic programming''' problems in '''Scilab'''.</p></blockquote></li></ul>
|-
|
Show Slide

'''Assignment I'''
|
As an assignment:

<ul>
<li><blockquote><p>Minimise the following '''objective function'''.</p></blockquote></li>
<li><blockquote><p>Use '''fot underscore quadprog function''' subjected to the given constraint</p></blockquote></li></ul>
|-
|
Show Slide

'''Assignment I'''
|
The optimum value will be -8.22.

The optimum solution will be the '''vector''' [0.66 1.33].
|-
|
Show Slide

'''Assignment II'''
|
Here is another assignment problem:

<ul>
<li><blockquote><p>Minimise the following '''objective function'''.</p></blockquote></li>
<li><blockquote><p>Use '''fot underscore intquadprog function''' subjected to the given constraints.</p></blockquote></li></ul>
|-
|
Show Slide

'''Assignment II'''
|
The optimum value will be -20.

The optimum solution can be either '''vector''' [4 1 1 0 1] or [4 1 2 0 1].
|-
|
Show Slide

'''About Spoken Tutorial Project'''
|
The video at the following link summarises the '''Spoken Tutorial''' project.

Please download and watch it.
|-
|
Show Slide

'''Spoken Tutorial Workshops'''
|
The '''Spoken Tutorial''' Project Team conducts workshops and gives certificates.

For more details, please write to us
|-
|
Show Slide

'''Answers for THIS Spoken Tutorial'''
| Please post your timed queries in this forum.
|-
|
Show Slide

'''FOSSEE Forum'''
| Please post your general and technical queries on '''Scilab''' in this forum.
|-
|
Show Slide

'''Textbook Companion project'''
|
The '''FOSSEE''' team coordinates the '''Textbook Companion project'''.

We give '''Certificates''' and '''Honorarium''' to the contributors.

For more details, please visit this site..
|-
|
Show Slide

'''Lab Migration'''
|
The '''FOSSEE''' team coordinates the '''Lab Migration project'''.

For more details, please visit this site.
|-
|
Show Slide

'''Acknowledgement'''
| '''Spoken Tutoria'''l and FOSSEE projects are funded by '''MoE, Government of India'''.
|-
|
Show Slide

'''Thank you'''
|
This is '''Mankrit Singh''', a '''FOSSEE''' intern 2021, '''IIT Bombay''' signing off

Thanks for joining.
|}