DMI Technical ReportsDMI Technical Reports Archive for the Department of Computer Sciences at the University of Wisconsin-Madisonhttp://digital.library.wisc.edu/1793/642352021-05-10T02:23:20Z2021-05-10T02:23:20ZPrivacy-Preserving Linear and Nonlinear Approximation via Linear ProgrammingMangasarian, OlviFung, Glennhttp://digital.library.wisc.edu/1793/643622019-04-24T14:10:24Z2011-01-01T00:00:00ZPrivacy-Preserving Linear and Nonlinear Approximation via Linear Programming
Mangasarian, Olvi; Fung, Glenn
We propose a novel privacy-preserving random kernel approximation based on a data matrix
A ? Rm�n whose rows are divided into privately owned blocks. Each block of rows belongs to
a different entity that is unwilling to share its rows or make them public. We wish to obtain an
accurate function approximation for a given y ? Rm corresponding to each of the m rows of A. Our
approximation of y is a real function on Rn evaluated at each row of A and is based on the concept of
a reduced kernel K(A,B?) where B? is the transpose of a completely random matrix B. The proposed
linear-programming-based approximation, which is public but does not reveal the privately-held data
matrix A, has accuracy comparable to that of an ordinary kernel approximation based on a publicly
disclosed data matrix A.
2011-01-01T00:00:00ZAbsolute Value Equation Solution via Dual ComplementarityMangasarian, Olvihttp://digital.library.wisc.edu/1793/643602019-04-24T14:10:27Z2011-01-01T00:00:00ZAbsolute Value Equation Solution via Dual Complementarity
Mangasarian, Olvi
By utilizing a dual complementarity condition, we propose an iterative method for solving the NPhard
absolute value equation (AVE): Ax?|x| = b, where A is an n�n square matrix. The algorithm
makes no assumptions on the AVE other than solvability and consists of solving a succession of linear
programs. The algorithm was tested on 500 consecutively generated random solvable instances of
the AVE with n =10, 50, 100, 500 and 1,000. The algorithm solved 90.2% of the test problems to an
accuracy of 10?8 .
2011-01-01T00:00:00ZEquivalence of Minimal L0 and Lp Norm Solutions of Linear Equalities, Inequalities and Linear Programs for Sufficiently Small pMangasarian, OlviFung, Glennhttp://digital.library.wisc.edu/1793/643582019-04-24T14:10:26Z2011-01-01T00:00:00ZEquivalence of Minimal L0 and Lp Norm Solutions of Linear Equalities, Inequalities and Linear Programs for Sufficiently Small p
Mangasarian, Olvi; Fung, Glenn
For a bounded system of linear equalities and inequalities we show that the NP-hard ?0 norm minimization problem min
||x||0 subject to Ax = a, Bx ? b and ||x||? ? 1, is completely equivalent to the concave
minimization min ||x||p subject to Ax = a, Bx ? b and ||x||? ? 1, for a sufficiently small p. A local solution to the latter problem can be easily obtained by solving a provably finite number of linear programs. Computational
results frequently leading to a global solution of the ?0 minimization problem and often producing sparser solutions
than the corresponding ?1 solution are given. A similar approach applies to finding minimal ?0 solutions of
linear programs.
2011-01-01T00:00:00ZPrimal-Dual Bilinear Programming Solution of the Absolute Value EquationMangasarian, Olvihttp://digital.library.wisc.edu/1793/643562019-04-24T14:10:26Z2011-01-01T00:00:00ZPrimal-Dual Bilinear Programming Solution of the Absolute Value Equation
Mangasarian, Olvi
We propose a finitely terminating primal-dual bilinear programming algorithm for the solution of
the NP-hard absolute value equation (AVE): Ax ? |x| = b, where A is an n � n square matrix. The
algorithm, which makes no assumptions on AVE other than solvability, consists of a finite number of
linear programs terminating at a solution of the AVE or at a stationary point of the bilinear program.
The proposed algorithm was tested on 500 consecutively generated random instances of the AVE with
n =10, 50, 100, 500 and 1,000. The algorithm solved 88.6% of the test problems to an accuracy of
1e ? 6 .
2011-01-01T00:00:00Z