24
votes
Is there any relationship between KKT and duality?
KKT and duality are indeed closely related. To demonstrate this, I will look at a convex minimization problem in which all functions are convex and smooth. I will make use of Lagrange duality. Linear ...
- 5,982
12
votes
Accepted
Do the KKT conditions hold for mixed integer nonlinear problems?
No, the KKT conditions aren't applicable to mixed-integer programming problems with integer variables. The theory behind the KKT conditions depends on the objective and constraint functions being ...
- 726
10
votes
Accepted
KKT inequality conditions
If you want to use the KKT conditions for the solution, you need to test all possible combinations. This is why in most cases, we use the KKT's to validate that something is an optimal solution, since ...
- 3,409
9
votes
Accepted
Dual variables associated with same equation for different time instants
You do not have $3$ constraints, you have $T$ constraints.
For example, if $T=5$, then we have
\begin{align}e(1)&=e(0)-d(1)+\eta\cdot c(0)\tag{1}\\e(2)&=e(1)-d(2)+\eta\cdot c(1)\tag{2}\\...
- 912
8
votes
Accepted
Example satisfying Mangasarian-Fromovitz CQ but not LICQ
Consider the following minimization problem
\begin{eqnarray}
\min &&\quad f(x) ~&= -x &\\
\text{s.t.} &&\quad g_1(x) & =x &\le 0\\
&&\quad g_2(x) & = 2x &...
- 5,982
6
votes
Accepted
Single KKT solution for a simple problem: proof of being minimizer
You have shown that KKT is necessary for a local minimum. Also that it is necessary for a local maximum. But you have not shown that a local minimum or local maximum exists. Indeed, there is no local ...
- 12.2k
6
votes
Accepted
Simple nonlinear programming using convexity analysis and KKT
You should use the KKT conditions (turning the sign restrictions on $x$ into constraints), but it turns out they will not affect the results. First, let me point out that $\partial L/\partial x_1$ is ...
- 35.5k
5
votes
Are the KKT Conditions as Important in Optimization as they were Originally?
Much (most?) of Deep Neural Network training (optimization) has been unconstrained optimization. The KKT condition(s) for unconstrained optimization is that the gradient of the objective function is ...
- 12.2k
5
votes
Accepted
Following code doesn't work in matlab with CVX
Use CVX's entr function.
$\sum_{i=1}^ 4x_i\ln(x_i)$ can be entered as -sum(entr(x))
...
- 12.2k
3
votes
Accepted
KKT for second order approximation of $f(x)$
The gradient and Hessian of $f$ at $x=x_0$ are constants (vector and matrix respectively), so $f_0(x)$ is a quadratic function of $x$. If it helps, write it as $f_0(x) = c_0 + c^Tx + x^T D x$. ...
- 35.5k
3
votes
Accepted
Prove that $x^*$ is an optimal solution where $f_0$ is $C^1$ and convex and $f_i$ are $C^1$ and strictly convex functions
Note that by assumption, there must be some $i \in I(x^*) \cup \{0\}$ with $y_i \ne 0$. Let $\mathcal I = \{i \in I(x^*) \cup \{0\} \mid y_i \ne 0\}$ be the set of such indices.
Let $u$ be any unit ...
- 146
3
votes
Constrained Optimization Closed Form Solution Using KKT Gives Wrong Values
For convenience, let $x_j = \gamma_j / n$, $c_j = \gamma_j^\mathrm{priority} / m$, then the problem is
$$
\begin{align*}
\min_{x_j} \quad&\sum_{j=0}^m(x_j - c_j)^2\\
\mathrm{s.t.} \quad&0\leq\...
- 1,016
2
votes
KKT conditions analysis for binary constraints
Binary (Boolean) values are integer values. Therefore, optimization problems with boolean constraints are either integer programming or mixed integer programing (MIP).
Generally, there is no easy ...
- 523
1
vote
How to find the optimal solution of a convex program given all KKT points?
This sounds like parametric programming to me.
In short, you can calculate a set of regions, typically called "critical regions", within which the same set of constraints is active. This in ...
- 3,409
1
vote
Linear Relaxation of Boolean Constraint for Solving Integer Linear Program Using KKT
Minimize $x^2$ where $1 \le x \le 2$.
\begin{aligned}
\min_{x} \quad & f(x)\\
\textrm{s.t.} \quad & h_{1}(x) \le 0\\
&h_{2}(x) \le 0 \\
\end{aligned}
where
\begin{align}
f(x) &= x^...
- 523
Only top scored, non community-wiki answers of a minimum length are eligible