Skip to main content
9 votes
Accepted

"Partial" Lagrangian Dual in LP

Based on the mentioned references, suppose the primal problem is: \begin{align} \begin{array}{cl} \underset{}{\text{minimize}} & c x \\ \text{subject to} & Ax = a \\ & Dx \leq e \\ & x ...
A.Omidi's user avatar
  • 8,940
9 votes

"Partial" Lagrangian Dual in LP

This is called Lagrangian relaxation, no matter what subset of constraints you choose to dualize.
RobPratt's user avatar
  • 32.7k
7 votes
Accepted

Simple nonlinear programming using convexity analysis and KKT

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 ...
prubin's user avatar
  • 39.5k
6 votes

Applicability of Lagrange Multipliers in the analysis of large-scale MILPs?

For an application to very large set covering problems you can see e.g. here This approach can be extended (somehow) to general MILPs and allows one to quickly find a “core” set of variables defining ...
Matteo Fischetti's user avatar
6 votes

Applicability of Lagrange Multipliers in the analysis of large-scale MILPs?

I am not aware of specific algorithmic methods for MIPs that use Lagrangian multipliers directly. However, as for the interpretation of the solution of a MIP: probably one of the nicer applications I ...
Richard's user avatar
  • 3,459
5 votes
Accepted

Simplex Multiplier

It is explained in this link as: Simplex multipliers are essentially the shadow prices associated with a particular basic solution. Those are the multiples of their initial system of equations such ...
Oguz Toragay's user avatar
  • 8,667
5 votes

Applicability of Lagrange Multipliers in the analysis of large-scale MILPs?

Lagrangian relaxation is extremely common as an algorithmic method to solve facility location problems. Because many "minisum"-type problems ($p$-median, uncapacitated facility location problem, etc.) ...
LarrySnyder610's user avatar
5 votes
Accepted

Augmented Lagrangian Function for Semidefinite Programming Problems

My way of reading it is $\langle X, \mathcal{A}^*(y)+S-C\rangle = \langle X, \mathcal{A}^*(y)-C\rangle + \langle X,S \rangle$. The first term is your standard inner product between dual variable and ...
Johan Löfberg's user avatar
4 votes

Augmented Lagrangian Function for Semidefinite Programming Problems

There's a good discussion of this in Convex Optimization by Stephen Boyd and Lieven Vandenberghe. See section 5.9. With an ordinary scalar inequality constraint: $f_{i}(x) \leq 0$, you'll have a term ...
Brian Borchers's user avatar
3 votes
Accepted

Why is the Lagrange Multiplier not equal the Shadow Price (Excel solver, Matlab linprog, Gurobi)?

If you look at the "allowable decrease" in the RHS of the highlighted constraint, it's zero. A number of the binding constraints have either allowable increase or allowable decrease zero. ...
prubin's user avatar
  • 39.5k
3 votes

Constrained Optimization Closed Form Solution Using KKT Gives Wrong Values

For convenience, let $x_j = \gamma_j / n$, $c_j = \gamma_j^\mathrm{priority} / m$, then the problem is $$ \begin{align*} \min_{x_j} \quad&\sum_{j=0}^m(x_j - c_j)^2\\ \mathrm{s.t.} \quad&0\leq\...
xd y's user avatar
  • 1,196
3 votes
Accepted

Related to Lagrangian dual

Dualizing a constraint comes back to the first, the direction of the objective function, and the second, how the dualized constraint would be violated. In your case, the constraint is written as $LHS-...
A.Omidi's user avatar
  • 8,940
3 votes
Accepted

Method of Multipliers: Why is the next iterate always dual feasible?

By dual feasibility, all that the authors mean is that $(x^{k+1}, \lambda^{k+1})$ in Equation (1) satisfies the stationarity equation in the KKT optimality conditions for the problem shown at the top ...
batwing's user avatar
  • 1,583
2 votes

Recovering Primal Solution from Dual solution

A proof that $x^*$ is optimal can be achieved by a Taylor expansion around $x^*$ at optimality. Observe that $$f(x^*+p) = f(x^*) + p^\top f'(x^*) + \frac12p^\top f''(x^*)p$$ Note that at a local ...
mathcomp guy's user avatar
2 votes

KKT conditions analysis for binary constraints

Binary (Boolean) values are integer values. Therefore, optimization problems with boolean constraints are either integer programming or mixed integer programing (MIP). Generally, there is no easy ...
Qurious Cube's user avatar
2 votes

ADMM diverges on L1 regression

I implemented @batwing's suggestion and it works. Let $\phi_1 \geq 0$, $\phi_2 \geq 0$ be slack variables (which we initialise to $0_N$), the Lagrangian becomes: $$\mathcal{L}=\alpha^\top 1_N + \...
Carol Eisen's user avatar
2 votes
Accepted

ADMM diverges on L1 regression

ADMM assumes that the constraints being added as penalties are equality constraints. In your reformulation of the l1 objective into inequality constraints i.e., $X\beta - y \leq \alpha$ and $-X \beta +...
batwing's user avatar
  • 1,583
2 votes

Related to Lagrangian dual

To ease notation, let me use B as (sum_j Beta_ij.x_ij). Then the constraint (1) is B-t <=0... You multiply this with lambda_i (let me use L for short of sum_i Lambda_i) and carry to objective ...
Evren Guney's user avatar
2 votes
Accepted

Lagrangian Multipliers for constraints in nonlinear optimization problems?

Let's assume that you want to minimize $f:\mathbb{R}^n \rightarrow \mathbb{R}$ subject to $g(x)\ge 0$ ($g:\mathbb{R}^n \rightarrow \mathbb{R}^m$) with no particular assumptions on $f$ and $g.$ ...
prubin's user avatar
  • 39.5k
2 votes

Lagrange multiplier associated to an active inequality constraint

It is not true that the Lagrange multiplier, $\lambda$, associated with constraint $g(x) \le 0$ which is active (i.e., satisfies $g(x) = 0$) is necessarily positive at an optimum. Presuming a ...
Mark L. Stone's user avatar
1 vote
Accepted

Knitro dimension of lambda for Hessian

Indeed, there is a bug in the Knitro R interface. The size of the lambda array in the callback input is wrong, and the lambda ...
fontanf's user avatar
  • 2,623
1 vote

How to find the optimal solution of a convex program given all KKT points?

This sounds like parametric programming to me. In short, you can calculate a set of regions, typically called "critical regions", within which the same set of constraints is active. This in ...
Richard's user avatar
  • 3,459
1 vote

Linear Relaxation of Boolean Constraint for Solving Integer Linear Program Using KKT

Minimize $x^2$ where $1 \le x \le 2$. \begin{aligned} \min_{x} \quad & f(x)\\ \textrm{s.t.} \quad & h_{1}(x) \le 0\\ &h_{2}(x) \le 0 \\ \end{aligned} where \begin{align} f(x) &= x^...
Qurious Cube's user avatar

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