p**o
发帖数: 3409 | 1 min ( x1^(1/2) + x2^(1/2) + ... + xn^(1/2) )
s.t.
x1 + x2 + ... + xn = C0
0 <= xi <= Ci for all i=1..n
已知前提
0 < Cn <= ... <= C2 <= C1 < C0 <= (C1 + ... + Cn)
目标函数不是凸函数，Lagrange多项式的梯度恒大于零，用不了KKT。
感觉最优点会在边界取得：先是x1=C1, 然后把剩下的尽量依次分给x2, x3, ...
但一时证不出来。。。
不知高手可否赐教大致思路？多谢～ | p**o
发帖数: 3409 | 2 我把我的推导贴一下，还烦高人帮忙看看问题在哪儿～～
\min f(x) = \min \sum_i p(x_i) = \min \sum_i x_i^{1/2}
s.t.
h(x) = \sum_i x_i - C_0 = 0
为减少乘子数量，0\leq xi\leq Ci看作f(x)的定义域而不是优化约束
1. 先找p(x_i)=x_i^{1/2}的convex conjugate:
p^*(y_i) = \sup_{0\leq xi\leq Ci} (y_i x_i - p(x_i))
y_i x_i - p(x_i)对x_i二阶导大于0，上届在两端取到，所以
p^*(y_i) =
C_i y_i - p(C_i), if y_i > p(C_i)/C_i
0, otherwise
2. f(x) = \sum_i p(x_i)各分量独立，所以f(x)的convex conjugate为
f^*(y)
= \sum_i p^*(y_i)
= \sum_{i:y_i>p(C_i)/C_i} (C_i y_i - p(C_i))
3. Lagrangian of f(x)
L(x,v) | s***i
发帖数: 2 | 3 First, because x_i\le C_i for all index i, then the k-th largest (smallest)
element among x_i is smaller than the corresponding k-th largest (smallest)
element in C_i. Therefore if you reorder x_i into decreasing order (x_n\le x
_{n-1}\le \cdots \le x_1) it does not change the objective function, and the
constraints remains feasible. So you can add extra constraint x_n\le x_{n-1
}\le \cdots \le x_1 to the original problem without changing objective value.
Now by first order condition, it is easy | p**o
发帖数: 3409 | 4 非常感谢！没想到就这么搞定了。这个reordering的idea真是让人茅塞顿开！
)
)
x
the
-1
value.
solution
【在 s***i 的大作中提到】
: First, because x_i\le C_i for all index i, then the k-th largest (smallest)
: element among x_i is smaller than the corresponding k-th largest (smallest)
: element in C_i. Therefore if you reorder x_i into decreasing order (x_n\le x
: _{n-1}\le \cdots \le x_1) it does not change the objective function, and the
: constraints remains feasible. So you can add extra constraint x_n\le x_{n-1
: }\le \cdots \le x_1 to the original problem without changing objective value.
: Now by first order condition, it is easy
|
|
