SERVING THE QUANTITATIVE FINANCE COMMUNITY

 
User avatar
Archimedean
Topic Author
Posts: 19
Joined: November 21st, 2003, 3:33 am

Initial Starting Point for Non-Linear Optimization

July 2nd, 2004, 5:41 am

Hi.I am working on optimal portfolio selection of an CBO.I have created an optimiation problem with linear objective function and all linear constraints, and only one non-linear constraint (corresponding to Diversity Score)I have chosen the successive linear programming technique (http://www.mpri.lsu.edu/textbook/Chapter6-b.htm). But this technique requires an initial feasible point to start the optimization process. Can you please help me with finding an initial feasible point in an efficient manner, where the problem contains one non-linear constraint, and all other constraints, and the objective function are linear, and the size of the problem (no of decision variables, and also number of constraints in this case) is of the order of 100-200.Thankyou
 
User avatar
Maelo
Posts: 1243
Joined: July 28th, 2002, 3:17 am

Initial Starting Point for Non-Linear Optimization

July 2nd, 2004, 8:50 am

I really don't know if there is a way to actually ensure you got an initial feasible solution in that algorithm but I will propose an idea:why don't you define the possible feasible space and then, make like 10,000 random points inside that space and make the algorithm get a solution for all of them? You can then compare the algorithm's proposed solutions by graphing the distributions and, perhaps if anything "regualr" comes from it, even proposed a way to ensure teh solotion. Are you using matlab?Success!!
Last edited by Maelo on July 1st, 2004, 10:00 pm, edited 1 time in total.
 
User avatar
cg
Posts: 16
Joined: September 25th, 2003, 12:43 pm

Initial Starting Point for Non-Linear Optimization

July 9th, 2004, 8:09 am

There is a free non-linear constained optimisation solver (donlp2) on Peter Spellucci'shomepage: http://www.mathematik.tu-darmstadt.de/a ... en.htmland other optimization software. I have used donlp2 several times for nonlinear least-squares problems with linear/non-linear equality/inequalityconstraints and it has worked very well. Unfortunaltey the C-code available on that site requires that the problem be defined within the main program (as it was directly converted from the original FORTRAN code) but it is easy to wrap itup in an interface where you can pass in the objective and constraint functions.cg
 
User avatar
zak
Posts: 52
Joined: September 5th, 2003, 3:47 pm

Initial Starting Point for Non-Linear Optimization

July 9th, 2004, 4:20 pm

Archmediean see your private messages
 
User avatar
luculus
Posts: 3
Joined: March 26th, 2002, 1:47 pm

Initial Starting Point for Non-Linear Optimization

July 12th, 2004, 12:47 am

How nonlinear is the constraint? Did you try non-feasible interior point methods? For these ones you don't need a feasible starting point. If the nonlinear constraint is quadratic or involves norms/distances then you might be able to formulate your problem in a 'Conic Programming' form and solve it using an interior-point solver.
 
User avatar
caroe
Posts: 123
Joined: July 14th, 2002, 3:00 am

Initial Starting Point for Non-Linear Optimization

July 12th, 2004, 11:45 am

LP-solvers often generate an initial feasible solution by a Phase I algorithm, which basically involves setting up additional (nonnegative) variables and and replacing the original constraint by . This constraint can be trivially satisfied, and if the objective is then set to e.g. you can apply the algorithm itself. If a feasible solution to the original exists, then the Phase I algorithm has optimal value 0 and an optimal solution of this problem will be a feasible solution of the original problem.Have you considered whether ideas along this path can be used for your problem ?
Last edited by caroe on July 11th, 2004, 10:00 pm, edited 1 time in total.
 
User avatar
ScilabGuru
Posts: 297
Joined: October 16th, 2001, 2:14 pm

Initial Starting Point for Non-Linear Optimization

July 12th, 2004, 9:41 pm

To get a feasible solution you can first to minimise the distance from your parameter x to the set defined by consttraint - nonequalities. If this set is not empty you shoud get finally the distance zero and the optimal x into the set. It can be done via optimization routine without constraints that is pretty standard.
 
User avatar
Baltazar
Posts: 37
Joined: January 21st, 2004, 4:27 pm

Initial Starting Point for Non-Linear Optimization

July 13th, 2004, 5:41 am

my optimisation knowledge is rusty,but for linear constraint and linear objectives, does not the solution lie at the border of the domain limited by the constraints?and the simplex method, used in operational research, tries every corners of the domain.so my suggestion: start from a point that is at on the bondaries.depending on the non linearity of the constraint, why not approximate it with a line, optimize that stuff and see if the constraint is active? than making it piecewise linear can yield better solutions. (haven't tried it, just suggesting)
ABOUT WILMOTT

PW by JB

Wilmott.com has been "Serving the Quantitative Finance Community" since 2001. Continued...


Twitter LinkedIn Instagram

JOBS BOARD

JOBS BOARD

Looking for a quant job, risk, algo trading,...? Browse jobs here...


GZIP: On