### Need help with least-squares linear-constraint optimization

Posted:

**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 Mx ≤ 0 and x

Or to put it another way, the goal is to minimize f(x) = ½∑x

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.

_{i}≥ 0 and ∑x_{i}= 1.Or to put it another way, the goal is to minimize f(x) = ½∑x

_{i}^{2}subject to h(x) = 1•x - 1 = 0 and g_{k}(x) = m_{k}•x ≤ 0 where m_{k}is the kth row of M, as well as x ≥ 0.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.