Material on Optimization: II

More on:

Bisection Method: Section 9.1 only; and you may ignore the C++ codes

Kuhn-Tucker: For more examples

Constrained Optimization: For a more easy-paced introduction

Quadratic Programming: As applied to the portfolio selection problem

A nice page on a whole lot of Numerical Methods: Even though it gives examples using Mathematica, the description is quite lucid and could be useful.

Material on Optimization: I

The following are essential (and recommended):

1. On Root Finding

2. On Optimization and Constrained Optimization

From the quiz point of view, you need not go through all the pdfs in detail (there is a bit of overlap) as long as you are familiar with the following topics:

• Newton-Raphson: For anyone looking for short-cuts to just pass, here is the wikipedia link (NOT recommended); better idea would be to google and select an expert (preferably academic) source
• Secant Method: wikipedia link ; google
• Bi-section Method: wikipedia link ; google
• Lagrange Multipliers: wikipedia link ; google
• Kuhn-Tucker Conditions: wikipedia link ; google
• The basic notion of Quadratic Programming: wikipedia link ; google

Btw, feel free to use any other source, online or otherwise, that you may find to your liking as long as you cover the topics.

The following is optional:

3. On Optimization in MATLAB

A revision of basic maxima and minima calculation and partial derivatives is here.

Assignment 3

is here.

File I/O

Importing data is something that can be very challenging but need not be, especially if you are the one who created the file containing the data. To the extent possible, it's best to keep things simple (ya, even when importing data!). Have clear/obvious labels for each variable with a separate column for each. 

Reading and Writing to Excel /  CSV Files

The command is:

>> [numData, strData] = xlsread('myExcelFile.xls');

The numeric data is stored in numData and the string/text in strData. The number of columns in strData is bounded below by the number of variables in the sheet. The default sheet is the first sheet.

To upload data from a particular sheet, use:

>> [numData, strData] = xlsread('myExcelFile.xls', sheet);

To upload data from a particular range:

>> [numData, strData] = xlsread('myExcelFile.xls', sheet, range);

Both Excel and MATLAB represent numeric dates as a number of serial days elapsed from a specific reference date. However, Excel uses January 1, 1900 as the reference date while MATLAB uses January 0, 0000. Due t this difference in the way Excel and MATLAB compute numeric date values, any numeric date imported from Excel into MATLAB must first be converted before being used in the MATLAB application.

You can do this conversion after the xlsread completes, as:

>> excelDates = xlsread('filename')

>> matlabDates = datenum('30-Dec-1899') + excelDates

>> datestr(matlabDates, 2)

To write a matrix M to an Excel file, use the syntax:

>> xlswrite(filename, sheet, range)

If one has only data (no labels) in an Excel file, the faster way is to work with the CSV (comma separated value) format. It is faster than xlsread. The syntax is similar. Use help csvread.

Reading and Writing to Text Files

The main command is textread.

More [TBA]

Using the Import Wizard

Use the command uiimport to launch the Import Wizard. I learn that with MATLAB v.7 onwards import wizard has become very powerful and user-friendly. Though I haven't used it, its user-interface should be very much like Excel and should be relatively easy to figure out. I, however, prefer the use of commands to read files. It makes for lesser errors and is generally much faster that way. In any case, most of the coding when working with data is best carried out using M-files and there the import wizard isn't much use.  For most practical purposes commands textread and xlsread are good enough. That said, I admit, for prototyping and doing ad-hoc analysis, using import wizard can save time. 

Btw, a long time ago I was comparing the performance of v.7.01 and v.6.5 and found xlsread to be way slower in v.7 as compared to v.6.5. Have you noticed that too? Just curious.

Low Level File I/O

Other than using the above discussed utilities for accessing files, one can also use MATLAB's low level file I/O functions/handles (as in, for example, C/C++). For most of my work I have been able to get by without using these, but they must be mentioned - if only for the sake of completion. Here is the link. For those new to programming, I suggest you first practice with the (above) more high level functions before getting to play around with these (resulting in shorter and, generally, faster codes).

Strings: III

Handling Dates and Times

The entire section on the Mathworks site on this is worth going through.

Strings: II

Some Other Useful Functions

disp

is useful to display any comment etc. on the command window as your M-file runs. It's a good idea to keep these in parts of your functions - so that you know at least till that point your code is not 'hanging'.

The syntax is:

>> disp(array)

Another use could be to, perhaps, print output in a fancy form with labels and all. An example :

>> disp(' A B C')

>> disp([1 2 3])

which gives the output:

A B C

1 2 3

warning

As the name suggests, this prints a warning (which can be suppressed). It works similar to the way disp does. This also can be helpful within M-files (say, if you want to be warned when a certain variable takes an unexpected value. Note that it does not stop the execution of the M-file. See its help for more details.

error

This prints on the output screen the custom error message and stops the execution of the M-file. See its help for more details. Works similar to warning. Another cool related command is errordlg.

num2str and str2num

num2str converts an array into their string representations. This function is most useful for playing around with dates and selecting a portion of a string/number to appear in plots or as a variable or file name. 

str2num works the other way around - it converts a character array into its numeric representation. Example:

[TBA]

Related commands include fprintf, int2str & str2int and double2str & str2double.

Strings: I

Handling Strings

Ability to handle strings assumes most importance when 'cleaning' data and saving results.

Most large sized data sets suffer from repetitions, missing values, wrong entries and all kinds of fancy errors. Although one can check for some kind of errors (unexpectedly large or small values) using comparisons with numbers (eps, Inf etc), most others defy any sensible pattern. In most cases, then, string comparison is the only recourse available.

The more obvious uses of string handling are the flexibility it allows in choosing dynamic names for files/variables in which to store results and manipulating data labels.

Let's start with basics.

Character Arrays

The assignment:

>> char1 = 'A';

assigns the value A to the 1 X 1 character array char1 (of size 2 bytes). Similarly,

>> char2 = 'BCDE'

assigns the value BCDE to the 1 X 4 character array char2 (of size 8 bytes).

Now one can play around with char1 and char2 like any other numeric matrix or vector. SoL

>> char3 = [char1 char];

gives

char3 =

ABCDE

Of course, one can access individual elements of arrays too. For example:

>> char4 = [char1 char2(2 : end)];

gives

char4 =

ACDE

The same can also be achieved by the function:

strcat

>> strcat(char1, char2(2:end));

or

>> strcat('A', 'CDE');

Another similar function is:

strvcat

As you would have probably guessed, this concatenates characters one below the other vertically. So:

>> strvcat(char1, char2(2 : end));

gives

ans =

A
CDE

If, however, one is not going to use strvcat, then concatenating requires that each row of the array must be of the same length. Following is an example:

>> x = ['AAA'; 'BBB'; 'CCC']

Another way to write the above command is:

>> x = ['AAA'; ...
'BBB'; ...
'CCC'];

To make an array of strings that are originally of unequal length in the above manner, you must either pad the shorter strings with extra space characters, or use strvcat. Another way is to use:

char

char automatically pads the shorter strings with extra space. For example, while the following gives an error:

>> x = ['AAA'; 'BBBBBB'; 'CCC'];

the following is ok:

>> x = char(['AAA'; 'BBBBBB'; 'CCC']);

Some other useful related functions include:

ischar: determines whether the input is a character array

isletter: finds all the alphabetic letters in the input string

isspace: finds all the blanks in a sentence. For example:

>> x = 'test for blanks';

>> find(isspace(x))

gives:

ans =

5 9

(fifth and ninth 'letter' of the sentence is space).

blanks: allows you to create a string of blank characters

deblank: allows you to remove all the trailing space charcters (at the end of a phrase or a sentence)

Cell Array of Strings

There is another type of MATLAB array, the cell array, can hold different sizes and types of data in an array without padding. Cell arrays provide a more flexible way to store strings of varying length.

cellstr

converts a character array of strings into a cell array of string

iscellstr

checks if the input is a cell array of string, and

char

can be used on a cell array of strings to go back to a character array

There are yet more useful functions to manipulate and play around with strings, in the interest of time, for now I think we can end by these final two commands/functions

strcmp

is a logical command compares two strings if they are exactly equal. If one is comparing arrays, then both arrays should have the same dimension. In that case strcmp compares element of the arrays separately and returns 1 for places where it finds a match. The syntax is:

strcmp('string1', 'string2');

strmatch

has the syntax:

strmatch('string', 'array')

As the name suggests, it looks through the rows of the character array or cell array of strings to find strings that begin with the text contained in string, and returns the matching row indices. For example (taken from Mathworks site), the statement

>> x = strmatch('max', strvcat('max', 'minimax', 'maximum'))

returns

x = [1; 3] since rows 1 and 3 begin with 'max'.

The statement

>> x = strmatch('max', strvcat('max', 'minimax', 'maximum'), 'exact')

returns x = 1, since only row 1 matches 'max' exactly.

MATLAB Tips and Tricks: I

Vectorization

Now would be a good time to talk about how we can optimize performance and write faster codes in MATLAB. The trick is to avoid working on individual elements (as in a for loop) and work on arrays/vectors to the extent possible. This is called vectorization. 

Now while the principle is easily stated, in practice whether a part of the code can be vectorized or not depends on the problem. Even the 'how to' part depends on the nature of the problem. There can be different ways for the same problem and one technique may be better than the other. Vectorization is a skill that develops over time. It helps to be aware that most iterative operations can be (fully or partially) vectorized. 

There are many utilities in MATLAB that makes this task easier (for example, find, end, the colon operator ':', linspace, min, max, cumsum, cumprod etc). The best way to see this is through examples.

Examples

1. Say you have a 3 X 3 matrix and you want to make any value greater than a particular number (say, 4) to be zero. Let:

>> x = magic(3);

% creates a magic square of dimension 3 X 3 which gives:

x =

8 1 6

3 5 7

4 9 2

Now there are two ways of achieving this objective

a) the 'usual' way:

for i = 1 : 3

for j = 1 : 3,

if (x(i, j) > 4),

x(i, j) = - x (i, j);

end

end

end

b) the vectorized version:

index = find(x > 4);

x (index)= - x (index);

The difference is obvious (it's much faster too).

2. Given a set of points, calculate the minimum distance from the origin:

a) without vectorization

function d = minDistance(x, y, z)

% Given a set of of 3-D points specified by columns x, y and z

% compute the minimum distance to the origin

nPoints = length(x);

d = zeros(nPoints, 1);

for k = 1 : nPoints

d(k) = sqrt (x (k)^2 + y (k) ^2 + z (k) ^ 2);

end

d = min(d);

b) with vectorization

function d = minDistance(x, y, z)

% Given a set of of 3-D points specified by columns x, y and z

% compute the minimum distance to the origin

d = sqrt (x .^ 2 + y .^ 2 + z .^ 2);

d = min(d);

3. Tony's Trick: To duplicate a vector of size m X 1 and create a matrix of size m X n

Let 

>> a = [1 2 3];

>> b = a ([1 1 1], :);

gives

>> b = 

1 2 3

1 2 3

1 2 3

Of course, this could have been accomplished by

>> b = a * ones (1, 3)

too. But this requires an unnecessary (and slower) matrix mutliplication.

What is happening here is that the first row of the vector is being indexed n (in this case, 3) times.  In another example, we look at how to manipulate a scalar

>> a = 4;

>> a = a (ones (3, 3));

gives

>> a = 

4 4 4

4 4 4

4 4 4

Again, one avoids the use of matrix multiplication. Similar task, of course, can be achieved by the function repmat too (there is no difference in speed - in fact, repmat employs the Tony's Trick).

I'll stop here on this. You may want to bookmark the Mathworks page on vectorization. Time permitting, we'll cover some more examples of vectorization and, may be, pre-allocation too.