eXercise for NonLinear Programming

XNLP ver.1.0.1 (Nonlinear Programming Software)

(February 17, 2008 released)



Table of Contents

1.Introduction
2.Download and install
3.Execution
4.Objective function
5.Initial Values
6.Errors and results
7.Methods and Configuration
8.List of simple problems
9.Constraint conditions
10.Ramsey model

1. Introduction

Xnlp is the program for solving nonlinear optimization problems. It uses the optimization engine that
is incorporated in GRAS. Although it is simple, it has sufficient power to solve ten or twenty periods
dynamic Ramsey model. The problem with a hundred variables is easy for xnlp.

The most important difference between GRAS and xnlp is in the way to incorporate the model structure.
Users can structure the model in xnlp. On the other hand, users can only to accept the model structure
in GRAS.

For xnlp, we set the objective function with variables, then xnlp interprets the equation and executes it.

First, try to download and install xnlp. I will give some explanations about xnlp.

2.Download and install

(1) Download
Save the following setup file. Then execute it.

XnlpSetup102

（Before downloading this software, you should accept following conditions.
Because this software is licensed free of charge, there is no warranty for this software.
The entire risk as to the quality and performance of this software is with you.
Should this software prove defective, you assume the cost of all necessary servicing,
repair or correction.Although you can report the problems of this software, the author
does not have any obligation to fix them. The author of this software does not compensate
any damage or losses due to the use of this software. ）

(2) Install
Click the setup file, installation will starts.

If you have not installed Microsoft .NET Framework (free of charge),
you are required to install it beforehand. (If you have already installed GRAS, it should have
been already installed, this installation will finish in short time.)

If you are prompted to install Microsoft .NET FrameWork in the installation process,
first you have to install it after download from Microsoft .NET framework download site.
Ver2 or later version is required.

Later versions of .NET Framework are also effective. version 3.0 have been installed in Windows VISTA.
Version 3.5 is also available.

(3) Uninstall
There are two methods for uninstalling Xnlp.
* Restart the setup file. Select to remove.
* Open control panel of Windows. Select uninstallation of software. You will be able to find out Xnlp on the list.
Then select to delete.

Generally, you can remove Xnlp without any problem.
However due to the security software or other programs on your machine, you may take time to remove it.

3. Execution

Xnlp will start to click the icon on desktop. Main frame has three text boxes. Upper textbox is for writing
objective function. Middle textbox is for setting initial values. Lower textbox is the console for showing
output of xnlp.



Let's make xnlp to solve a simple nonlinear problem. Copy and paste the following objective function to the
Upper area.

(x-1)^2+(y-2)^2

x and y are variables. The symbol '^' is the 'power' operator.

( In any cases, Xnlp solves a minimization problem. If you want to solve a maximization problem,
you should use the objective function multiplied by -1.)

For the above problem, you must be immediately noticed that this solution is x=1, y=2 and the objective value
is zero. However, computers cannot do such inference. They have to search the solution step by step starting
from initial values.

Then you have to give initial values. Copy and paste the following line into the middle textbox.

2,3

Any values are acceptable for initial values. They have to be delimited with a comma. Any other delimiters are
not acceptable.

Then you press the Run button. You immediately have the solution.

Even if you change the initial values into 2000,3000, you will get the same solution.

Next let us make xnlp to solve a rather complex problem. Following is an objective function for a Ramsey type
economic growth model with six periods. Copy and paste it onto the Upper textbox.

-(c1^(1-0.7)/(1-0.7))-(1/1.1)*(c2^(1-0.7)/(1-0.7))
-(1/1.1)^2*(c3^(1-0.7)/(1-0.7))-(1/1.1)^3*(c4^(1-0.7)/(1-0.7))
-(1/1.1)^4*(c5^(1-0.7)/(1-0.7))-(1/1.1)^5*(c6^(1-0.7)/(1-0.7))
+10000*(1.3*10^0.6-c1-i1)^2
+10000*(1.3*k2^0.6-c2-i2)^2
+10000*(1.3*k3^0.6-c3-i3)^2
+10000*(1.3*k4^0.6-c4-i4)^2
+10000*(1.3*k5^0.6-c5-i5)^2
+10000*(1.3*k6^0.6-c6-i6)^2
+10000*(k2-i1-10)^2
+10000*(k3-i2-k2)^2
+10000*(k4-i3-k3)^2
+10000*(k5-i4-k4)^2
+10000*(k6-i5-k5)^2
+10000*(30-i6-k6)^2

It may be lengthy, I will give some details at later section. The number 10000 means a penalty for unsatisfying
constraint equations.

Next, the following initial values are set on the Middle textbox.

1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1

Then, press Run button, you will have the following solution after some lines.

Optimal Solution!
iteration = 213
ObjectValue = -23.47526427
c1 = 2.34391066
c2 = 2.91418448
c3 = 3.52654984
c4 = 4.17803129
c5 = 4.86855381
c6 = 5.58595450
i1 = 2.83151010
k2 = 12.83153764
i2 = 3.09633663
k3 = 15.92789577
i3 = 3.31633895
k4 = 19.24425182
i4 = 3.48719100
k5 = 22.73145663
i5 = 3.60216548
k6 = 26.33363338
i6 = 3.66635730

At the last part of those output, you will see the following lines.
-------
Encountered following errors, but it may not affect the result.
Error : 6 : Power Arith. Error : ( 9004 times )
-------
You can ignore those lines. See here..

c1-c6 are the optimal consumption. i1-i6 are the optimal investments. k2-k6 are the optimal capital
stocks. k0 is 10 given beforehand as the initial capital stock. It is required to leave 30 units of capital
stock in 7th period.

I have confirmed this optimality by the famous package GAMS having solved same problem. About three
figures after the decimal fractions are coincident.

Let us finish the example section.

4. Objective function

Let me explain how to write objective functions.

(1) The character length of an optimal function should be less than 10000. For example, if one
line is written in 80 characters, you can write the function up to 125 lines.

(2) All spaces, tabs, carriage returns, new line codes are skipped. So if you write a large function,
you had better to write the function with separated lines for good looking. However, you cannot
insert the such spaces in the variable names or function names. "xvar" and "xv ar" are treated as
different variables. The latter is to be two different variables.

(3) A variable should be begin with an alphabetical character, and consist of alphabetical characters
or numbers. The name of length of a vairable should be less than 256 words. Variables are registered
with the order of its appearance in the function.


(4) The maximum number of variables is 1000 in each function. Maybe it is too large.

(5) The operators '+' and '-' function ordinarily. Multiplication is expressed by '*'. Power operator
is '^' as mentioned before.

(6) Parenthesis '( )' is used to prioritize the operation compared with any other operations.

(7) Following mathematical functions can be used.
　　"sin", "cos", "tan", "sqrt", "log", "exp","abs"
Basically, you should give them values with a pare of parenthesis. For example, you should write
"log(x)" instead of "log x". (In this case, if 'x' is written as that it can be recognized as just the
operand of the 'log', this expression is normally operated. But you should avoid this expression
for your confidence. )

(8) The highest priority of the calculation is given to the single term '-' operation(e.g. -3, -xvar),
mathematical functions, then, power operator, and then multiplication and division, finally addition
and subtraction. Since single term minus has highest priority, -2^2 has the value plus 4. If you
try to avoid this ambiguity, you should write it as (-2)^2. To avoid this ambiguity, write(-2)^2.

5. Initial Values

Initial values should be given corresponding to each variable in order of appearance in the
objective function. The separator of the values is comma. Spaces and carriage returns are
ignored. If you give plausible values, the probability that xnlp solves the problem will be improved.

If the number of variables and the initialized values are different, xnlp aborts its execution.
This will help you to notice the mistakes in the objective function.

6. Errors and results

(1) Compile errors
Xnlp first compiles the objective function, transforms it into statements of intermediate language.
If the objective function is not written in accordance with its rule, xnlp will output errors and abort.

(2) Execution errors
If xnlp encounters the errors on the way of execution, xnlp tries to manage that errors, and
after the execution, write the list of errors in the tail of outputs. For example,
----------------
Encountered following errors, but it may not affect the result.
Error : 6 : Power Arith. Error : ( 9004 times )
----------------
If you see this error messages, first you should doubt the solution. If the solution is not reasonable one.
You have to discard the solution, and improve the model. If the solution is reasonable, then check the solution,
and think the reason why the error messages appear. If necessary, improve the model.

(3) Error messages
Followings are the xnlp error messages

7. Method and configuration

In some cases, xnlp cannot reach to the optimal solution. You have to change the situation. There are some adjustment
methods.

(1) Change linear optimization method
Xnlp has two linear optimization method. Default is Armijo method. It is faster than Wolfe method. However, it is less
stability. So it may change the convergence to change the method.

(2) Change initial value.
Sometimes, initial values play a important role. The change of initial values affect considerably the result. So set more
reasonable initial values.

(3) Change configuration
Press Config button. On the configuration frame, you can change optimization parameters. The explanations of those
parameter are given in the GRAS pages.

(4) Check the objective function
There may be no feasible solution of the objective function. Or there may be no lower bound of the objective function.
Then, any above changes are ineffective.

8. List of simple problems

All problems following are very simple. However, some do not converge. Try them by your self.

(sin(x)-0.5)^2+(cos(y)-0.5)^2

((sin(x)-0.5)^2+(cos(y)-0.5)^2)+y/x
need to change linear method

((sin(x)/y-0.5)^2+(cos(y)/x-0.5)^2)

(sqrt(sin(x))-0.5)^2+(cos(y)-0.5)^2

(x-1)^2+(y-2)^2

(sqrt(x)-0.5)^2+(sqrt(y)-0.8)^2

(x-0.5)^0.5+(y-0.8)^0.5+100*(xp^2-x+0.5)+100*(yp^2-y+0.5)
not converge

(abs(x-0.5))^0.5+(abs(y-0.8))^0.5
need to change linear method

-abs(x)^1*abs(y)^1+10*abs(x+2*y-10)
need to change linear method

-0.2*log(x)-0.8*log(y)+1000000*(x+2*y-10)^2
utility maximization problem

9. Constraint conditions

I think you see how to attach the constraint conditions shown in the first example of Ramsey model.
Let me add some explanations.

(1) Equality constraint
If you would like to add a constraint equation, e.g. 2.0x+3.2y=10.0, you have to add the following penalty
function to the primal objective function.

1000*(2.0x+3.2y-10.0)^2

There are many forms for the penalty function. See some appropriate books.
10000 is the weight of the function. If you make larger this weight, you can get rigorous solution.

1000*abs(2.0x+3.2y-10.0)

is the one of alternatives. But results are not so good. because of the linearity.

(2) Inequality constraints
Let us consider to add the inequality constraint, e.g., 2.0x+3.0y <= 10.0. "<=" means that it should satisfy
"<" or "=". In this case, you have to add a slack variables, e.g., s and change this inequality equation into
the following equality equation.

2.0x+3.2y+s^2=10.0

Since s^2 >= 0 for any s, this equation is equivalent to the above inequality equation. Then add,

1000*(2.0x+3.2y+s^2-10.0)^2

to the primal objective function. Since to add slack variables makes computational load increase, there are
other methods without additional variables. GRAS employs one of such methods based on Lagrangean multiplier
methods.

10. Ramsey model

Let me add some explanations for the Ramsey model that I have shown in the beginning of this page.
For this type of economic dynamic model, I have released a software that have written in JAVA.
In that page, I have shown a document that explains mathematical structure. Please refer that document.

Above model is a six periods model. I show you the model again.

-(c1^(1-0.7)/(1-0.7))-(1/1.1)*(c2^(1-0.7)/(1-0.7))
-(1/1.1)^2*(c3^(1-0.7)/(1-0.7))-(1/1.1)^3*(c4^(1-0.7)/(1-0.7))
-(1/1.1)^4*(c5^(1-0.7)/(1-0.7))-(1/1.1)^5*(c6^(1-0.7)/(1-0.7))
+10000*(1.3*10^0.6-c1-i1)^2
+10000*(1.3*k2^0.6-c2-i2)^2
+10000*(1.3*k3^0.6-c3-i3)^2
+10000*(1.3*k4^0.6-c4-i4)^2
+10000*(1.3*k5^0.6-c5-i5)^2
+10000*(1.3*k6^0.6-c6-i6)^2
+10000*(k2-i1-10)^2
+10000*(k3-i2-k2)^2
+10000*(k4-i3-k3)^2
+10000*(k5-i4-k4)^2
+10000*(k6-i5-k5)^2
+10000*(30-i6-k6)^2

First three lines show the original objective function. Total utility is given by six periods consumption and
10% discount rate. One period utility function has the form that the elasticity of marginal utility is constant 0.7.

Nest six lines show supply and demand equation. That is, t-th (t=1,2,3,4,5,6) period equations are give as follows.

1.3*kt^0.6-ct-it

1.3 is the total factor productivity (constant). 0.6 is elasticity of production to capital stock.

Last six equations mean the capital accumulation. Depreciation of capital is not considered.

Try various simulation by changing parameters, e.g. discount rate.

(C) Toyoaki WASHIDA 2008