Questions tagged [kkt-conditions]

For questions on first-order necessary conditions for optimality in non-linear programs due to Karush, Kuhn, and Tucker.

Filter by
Sorted by
Tagged with
2 votes
0 answers
40 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^...
user avatar
  • 353
-1 votes
0 answers
72 views

KKT model of Mixed Integer Model with global optimality

As the Gurobi solver claims, it can provide optimal global solutions to nonconvex quadratic optimization problems. With this in mind, it is possible to write the "KKT" model for "Mixed ...
user avatar
3 votes
1 answer
182 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, ...
user avatar
  • 1,839
1 vote
1 answer
116 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{...
user avatar
  • 2,073
2 votes
0 answers
91 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 ...
user avatar
2 votes
1 answer
158 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 ...
user avatar
3 votes
1 answer
148 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 ...
user avatar
3 votes
1 answer
145 views

Following code doesn't work in matlab with CVX

Given the following problem \begin{align}\min&\quad x_1+2x_2+3x_3+4x_4+\sum_{i=1}^4x_i\ln(x_i)\\\text{s.t.}&\quad e^\top x=1\\&\quad x\geq0\end{align} I was asked to solved the dual ...
user avatar
  • 395
1 vote
1 answer
69 views

KKT for second order approximation of $f(x)$

Let $f: \mathbb{R}^n \rightarrow \mathbb{R}.$ Consider second order approximation $f(x) \approx f_0(x)$ where $$f_0(x) = f(x_0) + \nabla f(x_0)^T (x-x_0) + (\mathrm{H}f(x_0)(x - x_0))^T(x - x_0)$$ ...
user avatar
  • 121
5 votes
1 answer
168 views

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

Let $x^*$ be a feasible solution of the following convex optimization problem \begin{align}\min&\quad f_0(x)\\\text{s.t.}&\quad f_i(x)\leq0,i=1,\ldots,m\end{align} where $f_0$ is $C^1$ and ...
user avatar
  • 395
1 vote
0 answers
102 views

Prove Non-Homogeneous Farkas' Lemma

Let $A\in\mathbb{R}^{m \times n}, c\in\mathbb{R}^{n}, b\in\mathbb{R}^{m}, d\in\mathbb{R}$. Suppose that there exists $y\geq0$ such that $A^Ty=c$. Question: prove that exactly one of the following is ...
user avatar
  • 395
1 vote
0 answers
46 views

Verifying the correctness of KKT conditions

I have a LP problem and derived the corresponding KKT conditions for the same. I simulated the LP and obtained the primal and dual values and manually checked if the KKT conditions hold. Is there any ...
user avatar
  • 793
2 votes
0 answers
67 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}...
user avatar
  • 793
1 vote
1 answer
118 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 &...
user avatar
  • 381
4 votes
0 answers
64 views

Identifying saddle point in constrained optimization

Suppose we are minimizing $f(x)$. The first order necessary condition of $x^*$ being local minmum is: $$\nabla f(x^*)= \mathbf{0}.$$ For sufficiency, we check if also $\nabla^2f(x^*) \succ 0$, i.e., ...
user avatar
5 votes
1 answer
134 views

Dual variables associated with same equation for different time instants

I have three equations that are essentially the same equation defined for three time instants. The equations are basically calculating the state of energy of an energy storage facility. \begin{align} ...
user avatar
  • 793
4 votes
0 answers
95 views

Strong Duality and Slater Condition

I am studying the Duality Chapter of Convex Optimization by Boyd. Is it possible that strong duality holds for non-convex optimization? If yes, is there any specific condition? And, what is the ...
user avatar
  • 2,073
5 votes
1 answer
464 views

Single KKT solution for a simple problem: proof of being minimizer

I have a very simple problem: $$ \begin{align*} \begin{array}{ll} \min\limits_{x_1,x_2} & -x_1x_2 \\ \text{s.t.} & x_1 + x_2 - 2 = 0. \end{array} \end{align*} $$ The KKT system gives me $x_1^*...
user avatar
9 votes
1 answer
599 views

Is there any relationship between KKT and duality?

I noticed the similarities between KKT and complementary slackness, but I do not fully understand it.
user avatar
  • 99
7 votes
0 answers
71 views

KKT conditions validation- one dual variable equating to two values

I have the following optimization problem: \begin{alignat}2\min &\quad A(t)\cdot x(t)-B(t)\cdot y(t)+C(t)\cdot z(t)-D(t)\cdot k(t)\\\text{s.t.}&\quad z(t)+z_1(t)-y(t)-y_1(t)+x(t) = k(t);&...
user avatar
  • 793
11 votes
1 answer
319 views

Example satisfying Mangasarian-Fromovitz CQ but not LICQ

On Wikipedia's page for the KKT conditions, it is stated that Mangasarian-Fromovitz constraint qualification (MFCQ) is weaker than linear independent constraint qualification (LICQ). What is a ...
user avatar
  • 349
8 votes
1 answer
518 views

Do the KKT conditions hold for mixed integer nonlinear problems?

I was wondering if the KKT conditions are applicable for for MINLPs, and if not, why not? What about the case when the integer variables are modeled using constraints involving just continuous ...
user avatar
7 votes
1 answer
429 views

KKT inequality conditions

Let's say I have an objective function $$f(x_1,x_2, \cdots, x_n)$$ and $N$ constraints $$x_i \ge 0. $$ I am trying to solve it with KKT conditions. Now the objective function becomes $$f(x_1,x_2,...
user avatar
  • 1,579