h***r
发帖数: 726 | 1 【 以下文字转载自 Mathematics 讨论区 】
发信人: haier (no nickname), 信区: Mathematics
标 题: karmarkar's paper
发信站: BBS 未名空间站 (Wed Mar 3 17:00:58 2010, 美东)
after the ellipsoid paper, Karmarkar developed the interior point method for
LP.
Does anyone understand why the canonical form, on the first page, is the
following? (WHY Z, not R?)
min x' x
s.t. Ax = 0
\sum xi = 1
x >= 0
x \in R^n, c \in Z^n, A \in Z^(mn)
x' means x transpose
R^n means R to the nth
So, Why c, A in Z, not R???
Thanks! | i******t
发帖数: 370 | 2 If A, c are in Z, FFT-based algorithms can be used to speed up matrix
multiplication. This makes the gaussian elimination step faster (see page 5)
. For FFT-based multiplication, check:
http://en.wikipedia.org/wiki/Sch%C3%B6nhage-Strassen_algorithm
You can ignore this if you are working with small numbers in A and c.
for
【在 h***r 的大作中提到】
: 【 以下文字转载自 Mathematics 讨论区 】
: 发信人: haier (no nickname), 信区: Mathematics
: 标 题: karmarkar's paper
: 发信站: BBS 未名空间站 (Wed Mar 3 17:00:58 2010, 美东)
: after the ellipsoid paper, Karmarkar developed the interior point method for
: LP.
: Does anyone understand why the canonical form, on the first page, is the
: following? (WHY Z, not R?)
: min x' x
: s.t. Ax = 0
| h***r
发帖数: 726 | 3 谢谢萝卜的回答。
问题是，这样会不会失去generality?
In another word, if A c is in Z, can the cananical form still represent all
general LP problems?
Thanks again!
5)
【在 i******t 的大作中提到】
: If A, c are in Z, FFT-based algorithms can be used to speed up matrix
: multiplication. This makes the gaussian elimination step faster (see page 5)
: . For FFT-based multiplication, check:
: http://en.wikipedia.org/wiki/Sch%C3%B6nhage-Strassen_algorithm
: You can ignore this if you are working with small numbers in A and c.
:
: for
| i******t
发帖数: 370 | 4 I mean for A, c in R (general LP), the algorithm is still the same. The only
difference is, when A, c in Z, you can do better in solving the linear
system (gaussian elimination).
all
【在 h***r 的大作中提到】
: 谢谢萝卜的回答。
: 问题是，这样会不会失去generality?
: In another word, if A c is in Z, can the cananical form still represent all
: general LP problems?
: Thanks again!
:
: 5)
|
|
