Quadratic Programming

Moving along in the Mathematical Programming section.

The problem: Quadratic Programming.  This is problem MP2 in the appendix.

The description: Given a set of pairs (\bar{x},b) of constraints, similar to those in Integer Programming, except the numbers can be rationals instead of integers.  Instead of the single objective vector \bar{c}, we’re also given a second vector \bar{d}, both of rationals.  Our objective bound B is also a rational.

Can we find a vector of rationals \bar{y} that meets all of the constraints and sets the objective function \sum_{i=1}^{m} (c_{i}*y_{i}^{2} + d_{i}*y_{i}) \geq B?

Example: I’ll again try to write a simple example in a format closer to what I think is used in practice:

Maximize 2x_{1}^{2} + 3x_{1} + 4x_{2}^{2} + 5x_{2} such that:

x_{1} \geq 0

x_{2} \geq 0

x_{1} + x_{2} \leq 2

I’m pretty sure this has a trivial solution of x_{1} = 0 and x_{2} = 2, for an objective score of 26.

Reduction: It’s worth mentioning that this is a “Not known to be in NP” problem, I think because the range of possible rational solutions is too large to nondeterministically guess.  Sahni’s paper reduces from Sum of Subsets.  So we’re given a set S= {s_{1}..s_{n}} and a bound M.  Our QP instance will be have the following objective function: \sum_{i=1}^{n} x_{i}*(x_{i}-1) + x_{i}*s).   Our constraints will be that each x_{i} has to be between 0 and 1 (inclusive) and also \sum_{i=1}^{n} x_{i}*s_{i} \leq M.  Our bound B will be equal to M.

The first half of the objective function makes its contribution to the sum negative if x_{i} is not 0 or 1 (and 0 if it is 0 or 1).  So the only way to get the objective to exactly M is to choose 0/1 values for each x_{i}. The second half of the objective function and the summation constraint force us to create a sum that is as large as possible but not larger than B.   In this case the objective function value is the sum of the subset chosen, which is equal to B if and only if we have a SOS solution.

Difficulty: 5.  The hack to make fractional variable assignments negative is very cool, and easy to explain, but hard to find on your own.  I also think that worrying about quadratics and fractional values for your variables makes this problem harder to handle.

Leave a Reply

Your email address will not be published. Required fields are marked *