Serving the Quantitative Finance Community

Olga1597
Topic Author
Posts: 8
Joined: February 19th, 2016, 12:40 pm

### Scaling input data to make QP problem stable

Is there some theory about how  inputs data should be scaled to make QP problem numerical stable?
I have coded QP solver. To make this solver work stable for different input data I scale input values. I use several heuristics and they almost always works. But I cannot find books and papers with proofs of stability in different cases. And it makes me unhappy.

Alan
Posts: 10610
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

### Re: Scaling input data to make QP problem stable

Pretty vague description. In any event, you might google for discussions about "making a covariance matrix positive definite" (when it is only positive semidefinite) and "preconditioning a  matrix".

A more complete answer (by anybody) would require:
1. Explain your QP problem
2. Explain your algorithm to solve it.
3. Explain your 'stability' issues and exactly what you mean by 'scaling your data'.
4. Give an example.

Please use the LaTeX

Cuchulainn
Posts: 64433
Joined: July 16th, 2004, 7:38 am
Location: Drosophila melanogaster
Contact:

### Re: Scaling input data to make QP problem stable

0. What is "QP"?
quadratic programming?
"Compatibility means deliberately repeating other people's mistakes."
David Wheeler

http://www.datasimfinancial.com
http://www.datasim.nl

Olga1597
Topic Author
Posts: 8
Joined: February 19th, 2016, 12:40 pm

### Re: Scaling input data to make QP problem stable

0. What is "QP"?
quadratic programming?
Yes. This problem https://en.wikipedia.org/wiki/Quadratic_programming

Cuchulainn
Posts: 64433
Joined: July 16th, 2004, 7:38 am
Location: Drosophila melanogaster
Contact:

### Re: Scaling input data to make QP problem stable

0. What is "QP"?
quadratic programming?
Yes. This problem https://en.wikipedia.org/wiki/Quadratic_programming
I see. And now questions 1 to 4.
"Compatibility means deliberately repeating other people's mistakes."
David Wheeler

http://www.datasimfinancial.com
http://www.datasim.nl

Olga1597
Topic Author
Posts: 8
Joined: February 19th, 2016, 12:40 pm

### Re: Scaling input data to make QP problem stable

1. I want to find minimum of function

$$0.5y^TWy - a^TWy$$
with constraints
$$C_1B^{-1}y >= b_1, C_2y>=b_2$$
Input values: x (for matrix B), a (initial approximation), W diagonal matrix of positive weights.

2. It's an iterative dual space algorithm with active constraints set. I use some precision (one constant for all cases 1e-7) in my algorithm to detect if all constraints are satisfied with given precision.
3. I'm looking for solution that is not far from initial approximation (a). Dimension of problem (n) can be very different (from 5 to 3000), number of constraints is big enought (may be ~5*n), input values can be too small (~1e-5) and too big (~1e5). Usually I had same order of values inside x and a. And I normalized initial problem to make norms of initial vectors near to 1. Without such normalization algorithm frequently behaves unstable and can return solution that is very far from initial approximation and obviously wrong.
Now I have inputs with x vector with values of order 1e5 and a values of order 1e-5. I'm thinking about scalling x and a separately. But I'm looking for some theory about this stuff.

Cuchulainn
Posts: 64433
Joined: July 16th, 2004, 7:38 am
Location: Drosophila melanogaster
Contact:

### Re: Scaling input data to make QP problem stable

Let me paraphrase: you are working on a problem with very large and very small data, yes?

When these two worlds clash we can probably expect all kinds of problems, such as

. Catastrophic subtraction cancellation
. Machine overflow/underflow. One brute force solution is to use multiprecision library,
. Ill_conditioned systems

Maybe this is an area to start looking,
"Compatibility means deliberately repeating other people's mistakes."
David Wheeler

http://www.datasimfinancial.com
http://www.datasim.nl

Alan
Posts: 10610
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

### Re: Scaling input data to make QP problem stable

With general non-linear constrained optimization, it sometimes helps to move to $z = \log y$ for some or all of the unknowns. You might try that by moving to a general non-linear optimizer. For example, Mathematica has FindMinimum, with lots of documentation online. In the end, it's somewhat of a black-box but, in my experience, a pretty reliable black box.

Cuchulainn
Posts: 64433
Joined: July 16th, 2004, 7:38 am
Location: Drosophila melanogaster
Contact:

### Re: Scaling input data to make QP problem stable

M.J. Box has it for these; there might be a trick in there..
https://academic.oup.com/comjnl/article/9/1/67/348150
"Compatibility means deliberately repeating other people's mistakes."
David Wheeler

http://www.datasimfinancial.com
http://www.datasim.nl