Skip to main content

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
3 votes
2 answers
130 views

Lagrangian Multipliers for constraints in nonlinear optimization problems?

Suppose I want to optimize some function of continuous variables and the objective is nonlinear; in this context, gradient-based methods are quite popular. To my knowledge, soft constraints can be ...
jbuddy_13's user avatar
  • 551
0 votes
1 answer
52 views

Lagrange multiplier associated to an active inequality constraint

Why is the Lagrange multiplier associated to an active inequality constraint is positive. How can we see this from the KKT conditions?
DSPinfinity's user avatar
0 votes
0 answers
32 views

Unclear points in derivation of Lagrange duality for a quadratic optimization problem

Problem0: $\displaystyle \min_{\mathbf{u} \in \mathbf{R}^L}\frac{1}{2}\mathbf{u}^TQ\mathbf{u}+\mathbf{p}^T\mathbf{u}$ $\,$ subject to $\,$ $\mathbf{a}^T\mathbf{u} \ge c$ Problem1: $\displaystyle \...
DSPinfinity's user avatar
3 votes
0 answers
120 views

From Quadratic to MILP?

I am playing around with some Quadratic Programs (QPs), and I want to check if my reasoning is right concerning a re-modeling from QP to MILP. So, let's consider the below QP: (QP) $\min c^T x + x^T Q ...
Matheus Diógenes Andrade's user avatar
0 votes
0 answers
70 views

Lagrange relaxation / subgaradient algorithm Sensivity to input data

I am implementing a Lagarange relaxation with subgradient method to find a lower bound for a minization problem, I tried to find the complicating constraints. I found an upper bound with relatively ...
ABDE's user avatar
  • 1
1 vote
1 answer
77 views

Knitro dimension of lambda for Hessian

I'm trying to supply knitro with a Hessian but struggle to understand the dimension of the Lagrangian multiplier $\lambda$. From my general education and knitro's ...
Frank's user avatar
  • 13
0 votes
0 answers
36 views

Error while using subgradient method to update lagrange multipliers

I am trying to implemet the subgradient method in Lagragian relaxation to update the multiplier lamda which has three dimension, I have ecountered an Except error, it looks the is bugs in the code. it ...
ABDE's user avatar
  • 1
3 votes
0 answers
72 views

constrained optimization with decreasing constraint thresholds -Literature tips

consider a constrained optimization problem (typically c=0), with f highly nonlinear: \begin{equation} \text{minimize}_x f(x) \\\\ s.t \ \ \ \ g(x) \leq c \end{equation} I experimented a bit and found ...
L208's user avatar
  • 31
2 votes
2 answers
140 views

ADMM diverges on L1 regression

TLDR: Why does ADMM diverge when solving $\ell_1$ regression? Introduction I am learning about convex optimisation and wanted to solve a simple exercise that I am having issues with. I want to solve a ...
Carol Eisen's user avatar
1 vote
0 answers
93 views

Optimization with two constraints using Lagrange multipliers

As a part of an problem where i deploy the EM-algorithm i got stuck with the m-step that can be summarized into the below problem: Consider the following function: $$f(\alpha_{k,l}, \theta_{n, m}) = \...
steward's user avatar
  • 11
2 votes
1 answer
298 views

Constrained Optimization Closed Form Solution Using KKT Gives Wrong Values

I have a (I guess) simple constrained optimization problem that I'm hoping to find a closed-form solution for using Lagrangian analysis and KKT conditions. I figured out the solution but there is one ...
Ibrahim Amer's user avatar
3 votes
2 answers
282 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}}\...
chaaru's user avatar
  • 33
3 votes
2 answers
115 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 ...
benebrue's user avatar
9 votes
2 answers
1k 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 =...
independentvariable's user avatar
3 votes
0 answers
156 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, \\& ...
Apprentice's user avatar
1 vote
1 answer
208 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{...
Amin's user avatar
  • 2,160
2 votes
0 answers
112 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 ...
Qurious Cube's user avatar
2 votes
1 answer
304 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 ...
amr zaki's user avatar
3 votes
1 answer
227 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 ...
amr zaki's user avatar
3 votes
1 answer
142 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) + \...
user56202's user avatar
  • 233
2 votes
1 answer
582 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 ...
user56202's user avatar
  • 233
7 votes
0 answers
120 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$. ...
Pete S's user avatar
  • 123
3 votes
1 answer
811 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 ...
Mitch's user avatar
  • 93
1 vote
0 answers
117 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, ...
SmallFish's user avatar
5 votes
2 answers
2k 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} \...
Jonn's user avatar
  • 333
2 votes
0 answers
70 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}...
S_Scouse's user avatar
  • 803
2 votes
1 answer
167 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 &...
Edward's user avatar
  • 391
11 votes
3 answers
366 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 ...
Mark H's user avatar
  • 550