Questions tagged [kkt-conditions]
For questions on first-order necessary conditions for optimality in non-linear programs due to Karush, Kuhn, and Tucker.
27
questions
1
vote
1
answer
99
views
How to set up a convex concave procedure (difference of convex programming) for the minimization of multilinear term?
It seems that there are a lot of advantage of approximating nonconvex problem with the convex concave procedure when one is interest in finding local extrema or KKT points only.
Out of curiosity, ...
2
votes
0
answers
118
views
How can I derive the sufficient KKT conditions for an SDP?
$\DeclareMathOperator{\Tr}{Tr}\DeclareMathOperator*{\argmax}{\arg\!\max}$Consider the following semidefinite program (SDP)
$$
\begin{aligned}
\min_V \quad & -\Tr(V) \\
\textrm{s.t.} \quad & \...
- 639
0
votes
0
answers
34
views
Stationarity conditions for IPs
Let's consider the following (MQ)IP:
$\min x^T Q x$
s.t. $g(x) \geqslant 0$
$x_i \in \mathbb{Z}$ $i \in I$
By ignoring the integrality constraints we end up with the QP:
$\min x^T Q x$
s.t. $g(x) \...
- 1,240
3
votes
0
answers
124
views
From Quadratic to MILP?
I am playing around with some Quadratic Programs (QPs), and I want to check if my reasoning is right concerning a re-modeling from QP to MILP. So, let's consider the below QP:
(QP) $\min c^T x + x^T Q ...
- 1,240
2
votes
1
answer
310
views
Constrained Optimization Closed Form Solution Using KKT Gives Wrong Values
I have a (I guess) simple constrained optimization problem that I'm hoping to find a closed-form solution for using Lagrangian analysis and KKT conditions. I figured out the solution but there is one ...
- 245
3
votes
0
answers
47
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^...
- 517
3
votes
1
answer
445
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, ...
- 1,841
1
vote
1
answer
212
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,160
2
votes
0
answers
113
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 ...
- 523
2
votes
1
answer
322
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 ...
- 51
3
votes
1
answer
229
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 ...
- 51
4
votes
1
answer
234
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 ...
- 405
1
vote
1
answer
85
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)$$ ...
- 121
5
votes
1
answer
257
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 ...
- 405
1
vote
0
answers
165
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 ...
- 405