Google Groups

constrained quadratic programming with ALGENCAN


ashish Nov 29, 2011 12:06 PM
Posted in group: TANGO Project - ALGENCAN
Hi,

I would like to use ALGENCAN to optimize many problems of the
following type

minimize 1/2 * X' A X - c X

subject to b<= X <= 1

Sum_i x_i = 1

Also, the matrix A is diagonal but could have negative entries. So I
have a quadratic programming problem with only one linear equality
constraint and upper/lower bounds. In my case X is large. (could have
at most 100k entries)

I had two questions

1. I don't know much about optimization so I was reading around for a
simple polynomial time algorithm to solve my problem exactly. I found
a O(n) time algorithm but the restriction is that matrix A should have
entries > 0. Does anyone know of an algorithm for the general case
where the diagonal elements in A can be any real number.

2. If there isn't a solution to 1, I'd like to use ALGENACN for my
problem. I'm trying it out right now and after reading some of the
messages in the group, I'm using the following options in my
algencan.dat file

TRUNCATED-NEWTON-LINE-SEARCH-INNER-SOL
TRUE-HESSIAN-PRODUCT-IN-CG
ADD-SLACKS
FEASIBILITY-TOLERANCE 1.0d-03
OPTIMALITY-TOLERANCE 1.0d-03

I've compiled ALGENCAN with ma57 as well. Should I be using other
options ? I have to otimize thousands of optimizations of the
aforementioned type so running time is important here.I kept the
tolerances high because I didn't want a very accurate solution at the
expense of time. Is that the right way to go ? Any suggestions are
welcome.

Thanks!

Ashish