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
1
vote
1answer
97 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
votes
0answers
86 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 ...
2
votes
1answer
92 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 ...
3
votes
1answer
119 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 ...
3
votes
1answer
90 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 ...
1
vote
1answer
64 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)$$ ...
5
votes
1answer
96 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 ...
1
vote
0answers
94 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 ...
1
vote
0answers
43 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 ...
2
votes
0answers
63 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}...
1
vote
1answer
95 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 &...
4
votes
0answers
56 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., ...
5
votes
1answer
129 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} ...
3
votes
0answers
77 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 ...
5
votes
1answer
420 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^*...
9
votes
1answer
348 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.
7
votes
0answers
59 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);&...
11
votes
1answer
210 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 ...
8
votes
1answer
355 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 ...
7
votes
1answer
372 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,...