Questions tagged [kkt-conditions]
For questions on first-order necessary conditions for optimality in non-linear programs due to Karush, Kuhn, and Tucker.
32 questions
2
votes
0
answers
71
views
Importance of differentiable constraints in Lagrange multipliers theory (or KKT)
Concerning the theory of Lagrangian multipliers and more in general of constrained optimization, whether it be via Lagrange or via KKT, I'm trying to understand why is not good (to say so) and what ...
- 141
2
votes
1
answer
133
views
A very good reference for Lagrange Multipliers
I know this question has perhaps been already asked, but what I found so far was arid and not complete at all.
What I'm asking for is for a very good reference that teaches Lagrange multipliers not ...
- 141
2
votes
2
answers
279
views
Decomposition of a non-convex quadratic program with box constraints?
Background
I am a network engineer exploring optimization techniques that lie somewhat outside my formal training. While I have practical experience solving complex problems, my approach tends to be ...
0
votes
0
answers
96
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,292
1
vote
1
answer
115
views
About the mathematical proof of shadow price
I have a LP problem like:
\begin{align}
\min &\quad z = c^T x \\
s.t. &\quad Ax\le b \\
&\quad x\ge 0
\end{align}
Assume the optimal solution of this problem is $x^*$ and the dual optimal ...
- 13
1
vote
1
answer
144
views
How to set up a convex concave procedure (difference of convex programming) for the minimization of multilinear term?
It seems that there are a lot of advantage of approximating nonconvex problem with the convex concave procedure when one is interest in finding local extrema or KKT points only.
Out of curiosity, ...
2
votes
0
answers
236
views
How can I derive the sufficient KKT conditions for an SDP?
$\DeclareMathOperator{\Tr}{Tr}\DeclareMathOperator*{\argmax}{\arg\!\max}$Consider the following semidefinite program (SDP)
$$
\begin{aligned}
\min_V \quad & -\Tr(V) \\
\textrm{s.t.} \quad & \...
- 639
0
votes
0
answers
49
views
Stationarity conditions for IPs
Let's consider the following (MQ)IP:
$\min x^T Q x$
s.t. $g(x) \geqslant 0$
$x_i \in \mathbb{Z}$ $i \in I$
By ignoring the integrality constraints we end up with the QP:
$\min x^T Q x$
s.t. $g(x) \...
- 1,292
3
votes
0
answers
192
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,292
2
votes
1
answer
493
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
0
answers
67
views
Help with the KKT conditions of a SPT problem
Could anyone help me with the KKT conditions of my problem? The different sums and sets confuse me more than a little.
$$
\min_x \sum_{a \in A^1} p_a^1 X_a + \sum_{a \in A^2} p_a^2 X_a + \sum_{a \in A^...
- 517
3
votes
1
answer
549
views
Are the KKT Conditions as Important in Optimization as they were Originally?
It seems like when the KKT conditions were first developed, these were very useful for determining whether the solution to a optimization problem was optimal or not.
However, it seems like nowadays, ...
- 1,771
1
vote
1
answer
268
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,170
2
votes
0
answers
141
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
403
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