Questions tagged [lagrange-multipliers]

For questions related to Lagrange (or Lagrangian) multipliers, coefficients used to penalize violations of constraints that have been relaxed from an optimization problem.

Filter by
Sorted by
Tagged with
11 votes
3 answers
246 views

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

Qualitatively, in my experience in the solving of large scale MILPs, it is common that binary variables corresponding to "edge possibility" components are frequently chosen. Intuitively, these seem ...
user avatar
  • 530
9 votes
2 answers
598 views

"Partial" Lagrangian Dual in LP

Consider the optimization problem \begin{align}\label{opt-lp}\tag{Primal} \begin{array}{cl} \underset{x \in \mathbb{R}^n}{\text{minimize}} & c^\top x \\ \text{subject to} & Ax = a \\ & Bx =...
user avatar
7 votes
0 answers
108 views

Estimate lagrangian multiplier based on instance characteristics

Assume we have a simple resource allocation problem, where all players have the same cost, but a different utility $a_s$. The resources assigned to a certain player must be between $L$ and $M$. ...
user avatar
  • 123
5 votes
1 answer
1k views

Simplex Multiplier

I am reading through a book which provides an example of a linear program given by \begin{align}\min&\quad-24y_{1}-28y_{2}\\\text{s.t.}&\quad6y_{1}+10y_{2} \leq 2400\\&\quad8y_{1}+5y_{2} \...
user avatar
  • 253
3 votes
2 answers
73 views

Augmented Lagrangian Function for Semidefinite Programming Problems

I am currently reading the paper "Alternating direction augmented Lagrangian methods for semidefinite programming" and was wondering about how one comes up with the Augmented Lagrangian ...
user avatar
3 votes
2 answers
204 views

Related to Lagrangian dual

In my research class our professor discuss a paper wherein the solution is obtained via a Lagrangian duality. The original problem is given below: minimize $t$ subject to $\sum_{j \in \mathcal{M_i}}\...
user avatar
  • 33
3 votes
1 answer
114 views

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

I am reading this expository paper on ADMM by Boyd, et. al. Consider the problem \begin{align*} &\min f(x)\\ & \ \text{s.t.} \ \ \ Ax = b \end{align*} with Lagrangian $L(x, \lambda) = f(x) + \...
user avatar
  • 193
3 votes
1 answer
364 views

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

I have a LP with equality and inequality constraints. When solving the LP with the excel-solver (GRG Nonlinear) the sensitivity report returns the lagrange multiplier for all constraints. When solving ...
user avatar
  • 83
3 votes
1 answer
161 views

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

I am trying to convert a boolean LP to LP using LP relaxation by converting $x \in {0,1}$ to both $x \ge 0$ and $x \le 1$. Then to use it in my problem analysis, I am trying to build the KKT ...
user avatar
3 votes
0 answers
85 views

Convex Optimization Problem with norm inequality constraint

Consider the following optimization problem: \begin{align} \inf_{x,y}&\quad(x-x_0)^\top A(x-x_0) + (y-y_0)^\top B(y-y_0) \\\text{s.t.}&\quad x^\top a\geq0,\\ & \quad y^\top b\geq0, \\& ...
user avatar
2 votes
1 answer
173 views

KKT conditions analysis for binary constraints

I am wondering if boolean constraints in a linear program can be solved (after linear relaxation from $x\in\{0,1\}$ to both $x\ge0$ and $x\le1$) using KKT analysis. Most of the algorithms that I have ...
user avatar
2 votes
1 answer
179 views

Recovering Primal Solution from Dual solution

Consider the problem \begin{align*} &\min f(x)\\ & \ \text{s.t.} \ \ \ Ax = b \end{align*} In this expository paper, Boyd claims (top of page $8$) that if: $\lambda^*$ is a dual optimal ...
user avatar
  • 193
2 votes
0 answers
93 views

Geometric interpretation of KKT conditions

I can explain why Lagrange multipliers work for scalar functions by vector calculus. Consider optimizing $f(\vec{x})$ subjected to the constraint $g(\vec{x}) = c$. At the optima, we can move ...
user avatar
2 votes
0 answers
67 views

Deriving KKT Conditions for time-step equations

I have a variable $e(h)$, and below is the part of the Lagrangian equation where I am taking the derivative with respect to $e(h)$. $$\frac{\partial }{\partial e(h)} \hspace{.2cm}\mu_1(h)(e(h)-\bar{E}...
user avatar
  • 793
1 vote
1 answer
120 views

Simple nonlinear programming using convexity analysis and KKT

I want to solve the following two-variate nonlinear programming using KKT conditions: $$ \begin{align} \begin{split} \max \quad & 15 \sqrt{x_{1}} + 16 \sqrt{x_{2}} \\ \text{s.t.} \quad &...
user avatar
  • 381
1 vote
1 answer
123 views

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

Suppose we have a parametric convex program with some constraints. \begin{equation} \begin{split} \max_{x} \: & f(x,\mathbf{a})\\ & g_1(x,\mathbf{a})\le 0 \\ & g_2(x,\mathbf{a}) \le 0 \end{...
user avatar
  • 2,073
1 vote
0 answers
76 views

How to solve this problem by Lagrange duality?

This is a convex problem and although it can be well solved by CVX, I want to know how it can be solved by the Lagrange duality method. The derivations with regard to $L_k$ and $B_k$ are constants, ...
user avatar