Questions tagged [kkt-conditions]

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

20 questions
Filter by
Sorted by
Tagged with
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{split} \max_{x} \: & f(x,\mathbf{a})\\ & g_1(x,\mathbf{a})\le 0 \\ & g_2(x,\mathbf{a}) \le 0 \end{...
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 ...
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 ...
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 ...
90 views

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)$$ ...
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 ...
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 ...
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 ...
63 views

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., ...
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} ...
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 ...