Need help with least-squares linear-constraint optimization

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
The Cheshirest Catamount
Posts: 3022
Joined: Sat May 09, 2009 11:55 pm UTC

Need help with least-squares linear-constraint optimization

Postby Qaanol » Fri Sep 09, 2016 12:15 am UTC

Given a square skew-symmetric matrix M, I need to find the vector x with minimal magnitude satisfying Mx0 and xi ≥ 0 and ∑xi = 1.

Or to put it another way, the goal is to minimize f(x) = ½∑xi2 subject to h(x) = 1x - 1 = 0 and gk(x) = mkx ≤ 0 where mk is the kth row of M, as well as x0.

I can write down the KKT conditions, but I am not sure how to solve them.

The idea here is to solve the symmetric game specified by M, and if more than one optimal strategy is available then to pick the one which minimizes the sum-of-squares of its probabilities. I can get *a* vector y satisfying all the constraints by running the simplex algorithm on M+1, but I don’t see how to find the SSQ-minimizing one.

My specific motivation is to implement the GT election method, which is game-theoretically optimal among all ranked voting systems in the sense that no other ranked system will pick winners who are preferred by more voters (in the long-term average) than those elected by GT.

Of course any optimal strategy has that property, but I am trying to implement the system described in the linked paper. More info on it is available here.
wee free kings

Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 7 guests