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.
31 questions
2
votes
1
answer
160
views
If the Lagrangian dual function is always concave, why aren't we "just" solving dual problems optimally?
Let $\mathcal{P}$ be the following primal optimization problem
\begin{align}
\mathcal{P}: \text{minimize}_x \quad & f_0(x)\\
\text{subject to} \quad & f_i(x) \leq 0, \quad i = 1, ..., m \\
...
- 163
0
votes
0
answers
71
views
From Minimax to MILP
Definitions
Let
$S = \{ (x, y) | Ax + Dy \leqslant b\}$, and $\pi$ be its dual; And
$P_2(x) = \min_{(x, y) \in S} c^T_2 y$;
Problem
We aim to solve the following MILP.
$P = \max_{(x, y) \in S} c^T_1 ...
- 1,282
0
votes
0
answers
42
views
Understanding the logic of ADMM for a multi-agent/consensus optimization
I have an ILP that consists of 3 binary decision variables: $x_1, x_2, x_3 \in {0,1}$. The system consists of N agents, each wanting to make their own decision for variables $x_2$ and $x_3$, while all ...
- 1
3
votes
2
answers
251
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 ...
- 559
0
votes
1
answer
71
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?
- 419
0
votes
0
answers
39
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 \...
- 419
3
votes
0
answers
136
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,282
0
votes
0
answers
86
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
85
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
40
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
77
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 ...
- 31
2
votes
2
answers
171
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 ...
- 213
1
vote
0
answers
99
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
370
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
290
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
133
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
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 =...
- 4,030
3
votes
0
answers
161
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
222
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,160
2
votes
0
answers
123
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
340
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
232
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
154
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) + \...
- 233
2
votes
1
answer
634
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 ...
- 233
7
votes
0
answers
123
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
898
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
124
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} \...
- 343
2
votes
0
answers
72
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}...
- 803
2
votes
1
answer
175
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 &...
- 391
11
votes
3
answers
387
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 ...
- 550