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 ...
user avatar
11 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 ...
user avatar
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 ...
user avatar
  • 3,034
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}\\...
user avatar
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 &...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 29.7k
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 ...
user avatar
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)) ...
user avatar
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$. ...
user avatar
  • 29.7k
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 3,034
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^...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible