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.
25
questions
3
votes
0
answers
111
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 ...
- 1,208
0
votes
0
answers
45
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 ...
- 1
1
vote
1
answer
66
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 ...
- 13
0
votes
0
answers
26
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 ...
- 1
3
votes
0
answers
68
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 ...
2
votes
2
answers
126
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 ...
- 203
1
vote
0
answers
84
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}) = \...
- 11
2
votes
1
answer
239
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 ...
- 245
3
votes
2
answers
264
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}}\...
- 33
3
votes
2
answers
98
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 ...
- 33
9
votes
2
answers
954
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 =...
- 3,980
3
votes
0
answers
154
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, \\& ...
- 215
1
vote
1
answer
202
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{...
- 2,150
2
votes
0
answers
107
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 ...
- 523
2
votes
1
answer
274
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 ...
- 51
3
votes
1
answer
218
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 ...
- 51
3
votes
1
answer
136
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) + \...
- 193
2
votes
1
answer
520
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 ...
- 193
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$. ...
- 123
3
votes
1
answer
706
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 ...
- 93
1
vote
0
answers
110
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, ...
- 11
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} \...
- 333
2
votes
0
answers
68
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}...
- 793
1
vote
1
answer
159
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 &...
- 381
11
votes
3
answers
349
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 ...
- 540