Hot answers tagged

12

TL;DR: column generation on the dual problem is 100% equivalent to cutting plane on the primal problem. Equivalence between primal and dual form Consider the (primal) LP problem \begin{align} (P) \ \ \ \min_{x \in \mathbb{R}^{n}} \ \ \ & c^{T}x\\ \text{s.t.} \ \ \ & \sum_{j=1}^{n} a_{i, j} x_{j} \geq b_{i}, & i = 1, ..., M, \end{...


7

If strong duality holds, then it also holds when only a subset of the constraints is dualized. We define the following three problems: the original, the partially dualized, and the dual. Problem (P1): \begin{align}\min_x&\quad f(x)\\\text{s.t.}&\quad g_i(x)\leq 0, i \in C\end{align} Problem (P2): \begin{align}\max_{\lambda\ge0} \min_x&\quad f(x) +...


6

You should use the KKT conditions (turning the sign restrictions on $x$ into constraints), but it turns out they will not affect the results. First, let me point out that $\partial L/\partial x_1$ is undefined when $x_1=0$, so you need to deal with the case $x_1=0$ (and the case $x_2=0$) separately. Given the monotonicity of $L$, you can easily show that if $...


5

Use CVX's entr function. $\sum_{i=1}^ 4x_i\ln(x_i)$ can be entered as -sum(entr(x)) entr Scalar entropy. entr(X) returns an array of the same size as X with the unnormalized entropy function applied to each element: { -X.*LOG(X) if X > 0, entr(X) = { 0 if X == 0, { -Inf otherwise. If X ...


4

If I understand your question correctly, I think you can find your answer by considering the following two primal problems. The first is \begin{alignat*}{2} & \max & x_{1}\\ & \textrm{s.t.} & x_{1}+x_{2} & \le1\\ & & x_{1} & \le1\\ & & x & \ge0 \end{alignat*} and the second is \begin{alignat*}{2} & \max &...


4

I find the phrase "true shadow prices" misleading, and the use of "falsified" even more so, since the shadow prices any reputable solver returns are valid shadow prices ... possibly only in one direction, or even for a zero step size in either direction, when degeneracy occurs, but still correct. I can't say why it's "not a larger ...


4

The dual variables represent the marginal effect on the primal objective (total units purchased) per unit change in each primal constraint limit. So increasing (decreasing) the required amount $A_m$ of product $A$ by a small amount will reduce (increase) the total purchase quantity (TPQ to save me future typing) by $y_A$ times the change. The interpretation ...


3

I guess you are assuming that the dual problem was obtained by only dualizing some of the constraints. The answer below makes sense if I am right about my guess. In general, I believe the answer to your problem is no. Take for instance the multi-commodity flow problem. If you dualize the capacity constraints, then the dual problem you will be solving ...


3

It does not look correct, and in particular the dual of an LP is an LP, so it makes no sense to have a binary variable in the dual. I suspect what led you astray was a misunderstanding of the penalty portion of the primal objective. You can rewrite the primal objective as \begin{gather*} \sum_{j=1}^{P}c_{j}x_{j}+P_{Dhd}\left[\sum_{i=1}^{F}\sum_{j=1}^{P}a_{ij}...


2

From duality theory: At each feasible $x$,$f(x)=\sup_{u>0,v}L(x,u,v)$, and the supremum is taken iff $u\geq 0$ satisfying $u_ih(x)=0,i=1,...,m$. The optimal value of the primal problem, named as $f^*$ satisfies: \begin{equation} f^*=\inf_x\sup_{u>0,v}L(x,u,v) \end{equation} This means that if the dual is feasible, the primal has to be feasible as well. ...


2

Primal Problem $$\begin{align} \text{minimize} \quad & \sum_{i=1}^n a_i x_i + \sum_{i=1}^n b_i z_i \\\ \text{subject to} \quad & A\mathbf x-\mathbf d \le C\mathbf z \\ & x_i \ge 0 \quad \forall i=1,\ldots,n \\ & z_i \le 0 \quad \forall i=1,\ldots,n \end{align}$$ The dual formulation of the primal problem can be obtained by writing the ...


2

I've checked my answer and it works. Here is a Matlab code that I've written.


1

$$\min_x\{||x-a_1||+||x-a_2||+||x-a_3||,a_i\in\mathbb{R}^n\}=\min_{x,z_i}\{||z_1||+||z_2||+||z_3||,a_i\in\mathbb{R}^n\,z_i=x-a_i\}$$ and the Lagrangian is:\ $L(x,z,\lambda)= ||z_1||+||z_2||+||z_3||+\sum_{i=1}^3\lambda_i^T(z_i-x+a_i)=\sum_{i=1}^{3}\lambda_i^Tz_i+||z_i||-x\sum\lambda_i+\sum\lambda_i^Ta_i$\ From $-x\sum\lambda_i$ we can deduce that $\sum \...


Only top voted, non community-wiki answers of a minimum length are eligible