Questions tagged [karush-kuhn-tucker]
In mathematical optimization, the Karush–Kuhn–Tucker (KKT) conditions are first order necessary conditions for a solution in nonlinear programming to be optimal, provided that some regularity conditions are satisfied.
417
questions
1
vote
1answer
42 views
Sufficient conditions for non-convex constrained optimization (KKT)
I am trying to solve an inequality-constrained minimization problem. My objective and constraints are infinitely differentiable but not necessarily convex.
I found exactly 1 point $\mathbf{x}^{*}$ ...
1
vote
0answers
16 views
Stationarity condition for non-convex functions
Suppose I have an objective function
$$
\min_{\bf x} f({\bf x}) + \lambda \|{\bf x}\|_1
$$
where $f({\bf x})$ is a differentiable non-convex function. I am trying to derive an upper bound for $\lambda$...
0
votes
0answers
45 views
KKT conditions for linear program where $\sum_{i=1}^{n}x_i=1$
I want to find the optimal $x$ for the optimization problem: minimize $c^Tx$ subject to $x\geq0$ and $\sum_{i=1}^{n}x_i=1$?
I have calculated:
$c_i-\lambda_i+v=0$
$\sum x_i=1$
$\lambda_ix_i=0$
$x_i\...
6
votes
1answer
52 views
Understanding Karush-Kuhn-Tucker conditions
Suppose we may want to use the K–T conditions to find the optimal solution to:
\begin{array}{cc}
\max & (\text { or } \min ) z=f\left(x_{1}, x_{2}, \ldots, x_{n}\right) \\
\text { s.t. } & g_{...
4
votes
1answer
240 views
Uniform convergence of objective function implies convergence of minimizers
Let $A,A_h\in M_{n\times m}(\mathbb{R})$ be $n\times m$ matrices with $\Vert (A-A_h)x\Vert\leq h^2 \Vert x\Vert$ for $h\in (0,1)$ and $e\in \mathbb{R}^n$.
Now consider for a fixed $\lambda>0$ the ...
0
votes
0answers
14 views
How do you solve a convex minimization problem with affine linear constraints?
I am studying KKT conditions and I got a bit confused about how to solve the following problem:
\begin{align*}&\min f(x) \\
s.t. &l \leq x_i \leq u \qquad \forall i=1, \dots n\\
&c^Tx \leq ...
2
votes
0answers
60 views
Strong duality and KKT for SDP with inequality constraints
The standard form of semidefinite program (SDP) is
\begin{align*}
p^* = \inf C \bullet X\\
s.t. A_i \bullet X = b_i\\
X \succeq 0
\end{align*}
where $C, A_i$ are symmetric matrices. The dual SDP is
\...
0
votes
0answers
26 views
A proper definiton for constraint qualification for nonlinear programming
Despite all good books on optimization, there seems to be no practical definition on what a constraint qualification actually is. The best I could find is the definition that states that
Constraint ...
0
votes
0answers
16 views
Nonlinear optimization with constraint on y? How to deal with divergent derivatives in the Stationarity KKT condition?
I've got an exercise which has me pretty confused.
I need to find $min_{x\in\!R^{2}} \overrightarrow{1^T}x$
s.t. $x^2-1\leq0, \text{and } y^2-x\leq0$
So, if I understand correctly, I need to find the ...
0
votes
0answers
13 views
problem about The KKT condition of convex optimization problem that comes by making the gradient of the lagrangian equal to zero.
the problem is
$$ minimize \ \ tr\textbf{X}-logdet\textbf{X}\\subject \ to\ \ \ \textbf{X}s = y$$
the variable is X $\in S_{++}^n$ (symmetric positive definite matrix). $y \ and\ s$ are given and they ...
1
vote
1answer
56 views
Minimizing the squared distance from a line to a hyperbola?
Consider the minimization problem:
Minimize $$|(z-x, w-y)|^2$$,
Where $(x, y) \in \mathbb{R}^2$ is on a straight line defined by the equation $ax + by = c$,
and $(z, w) \in \mathbb{R}^2$ is on the ...
0
votes
1answer
73 views
Use the Karush-Kuhn-Tucker conditions to find the optimal solution
Use the Karush-Kuhn-Tucker conditions to find the optimal solution to the following non-linear programming problem.
$$
\begin{gathered}
\min z=\left(x_{1}-1\right)^{2}+\left(x_{2}-2\right)^{2} \\
\...
1
vote
0answers
103 views
Calculus of Variation with inequality constraints - Lagrange multiplier approach does not work
This is related to a question I asked several years ago, see here.
I want to find the functon $y$ which maximizes the functional
$$J[y]= \int_{a}^{a+1} (2x- 1-a)y(x) \left(1+B\left[y(x)-1\right]\right)...
2
votes
0answers
32 views
How the KKT conditions change when we replace the equality constraint $g(x)=0$ to $||g(x)||^2=0$?
Consider the following optimization problem:
$$ \min_{x \in \mathbb{R}^n} f(x) \text{ subject to } g(x)=0 , $$
where $f$ and $g$ are smooth functions from $\mathbb{R}^n$ to $\mathbb{R}$. This is ...
5
votes
1answer
168 views
Minimization problem with solutions on boundary
I am trying to solve the following optimization problem. I do not care about the particular values of the $x$'s, I just care about the optimal value of the function.
\begin{equation}
\min_{x\geq0} z_{...
1
vote
0answers
42 views
How or which solver find solution that holds strictly complementary slackness condition
So as theoretical I know interior point generate a solution in which the solution satisfies strictly complementary slackness condition. but when i use solver like linprog (by specifying 'interior-...
0
votes
0answers
58 views
How to use complementary slackness condition in KKT condition
Consider the complementary condition $u^T g(x^*) = 0$ in the KKT conditions for the following problem.
\begin{equation}
\begin{aligned}
\min_{x} \quad & f(x) \\
s.t. \quad & g(x) \leq 0 \\
\...
2
votes
0answers
50 views
KKT conditions , inequality constraints
I am having trouble finding finding the KKT points of the following problem.
$$
\begin{array}{ll}
\min \max &{\tau^2}
\\
\text{subject to} & \tau \leq 3 l_u ^2\\
& \tau \geq \gamma + l_u + ...
0
votes
0answers
21 views
How can I solve the circle packing problem for 2 unitary radius circles using KKT?
I am trying to solve the packing circle problem for two circles with unitary radius using Karush Kuhn Tucker KKT conditions. But I am stuck with the following equations:
Is it possible to solve the ...
0
votes
0answers
70 views
Solve the following two dimensional problem for all possible values of $a$ and $b$
This is exercise 3.3.1 in the book Nonlinear Programming by Dimitri Bertsekas:
Solve the problem
$$\min \hspace{0.2cm}(x-a)^2+(y-b)^2+xy \quad \text{s.t.} \quad 0\leq x,y\leq 1$$ for all possible ...
1
vote
0answers
16 views
Connections between two quadratic programming problems with same constraints (over a simplex)
Assume that we have the following two optimization problems with exactly the same constraints but different objective:
P1: $\min_{{\bf u}} {\bf u}^\text{T} {\bf T}_1 {\bf u}$ subject to C1: ${\bf 1}^...
2
votes
2answers
102 views
How to solve a Karush-Kuhn-Tucker example
This is a problem example taken from professor Robert Israel:
$$\max f(x,y)=xy \quad \text{subject to }\quad x+y^2\leq2, \quad x,y\geq0 \quad \quad (1)$$
The solution begins by writing the KKT ...
0
votes
0answers
126 views
Could anyone tell me how to find optimal conditions in more details from here?
\begin{align*}
\max Y&=R_1X_1+R_{2}X_{2}+R_3X_3+R_4X_4+R_5X_5+R_6X_6,\\
\text{s.t}:&F_1(X_1,X_{2}, \dots, X_{6})=X_1+X_3+X_5-1\le 0,\\
&F_2(X_1,X_{2}, \dots, X_{6})=X_2+X_4+X_6-1\le 0,\\
&...
0
votes
0answers
41 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{...
0
votes
0answers
32 views
How would I solve the following convex optimization problem?
I have the following optimization problem:
\begin{equation} \label{eq:iso_exp}
\begin{array}{ll}
\underset{q}{\operatorname{minimize}} & (\rho-a) \circ (q - \mu) + (q - \mu)^Tb(q - \mu)\\
\text { ...
1
vote
1answer
96 views
Prove $(xyz)^{1/3}\geq \frac{3}{1/x+1/y+1/z}$
For $x,y,z>0$ Prove $(xyz)^{1/3}\geq \frac{3}{1/x+1/y+1/z}$
Attempt:
setting $f(x,y,z)=(xyz)^{1/3}$ and $h(x,y,z)=\frac{3}{1/x+1/y+1/z}$ we can see that $f,h$ are homog. function with degree of 1....
0
votes
1answer
95 views
Slater's condition for non-convex problem
As wee known, in convex optimization problem, we get strong duality if Slater's condition holds. I often use Slater condition to indicate whether an optimal solution of primary problem satisfies KKT ...
0
votes
2answers
99 views
how to optimize this function $f(x,y,z)=x+y+z$ by kuhn tucker
Can someone help me optimize the function
$$f(x,y,z)=x+y+z$$ subject to
$$(y-1)^2 +z^2\leq 1$$
$$x^2 +(y-1)^2 +z^2\leq 3?$$
I was trying to solve by the Kuhn Tucker method and I still don't get it.
...
1
vote
1answer
57 views
KKT points for minimization problem?
I have the following problem:
$$\begin{array}{ll} \text{minimize} & \frac{1}{2} \|x \|_4^4\\ \text{subject to} & \| x \|_2^2 - 1 = 0\end{array}$$
and I don't know how to start. Maybe I can ...
1
vote
2answers
75 views
Minimum of a quadratic restricted to a hyperplane
I am trying to solve the following optimization problem
$$
\begin{cases}
\min f(x_1, \dots, x_n) = \sum_{i = 1}^na_ix_i^2, \quad a_i \ge 0 \\[0.4em]
\!\text{s.t.}: \\
\begin{cases}
...
2
votes
1answer
64 views
Maximization under constraints - can't find algebraic/closed form solution even though know it exists
I want to solve the following Constrained optimization program:
$\begin{equation}
\begin{split}
\max_{\{F\}} F \cdot P\left(v \geq -\alpha \cdot \ln\left(1-\frac{F}{\alpha}\right)\right)\\
\...
0
votes
1answer
33 views
Convexity study and KKT poinf for $f(x,y)= \alpha x^2-y$
Let $f:\mathbb{R^2}\to \mathbb{R}$ be defined by
$$f(x,y)= \alpha x^2-y$$
I am trying to find the values of $\alpha $ such that $f(x,y)$ is convex over
$$X=\{(x,y)\in\mathbb{R^2}:y\geq x^2-1\, , y\leq ...
0
votes
1answer
32 views
Example of a KKT point that is not optimal
I know that for convex problems, the KKT point is optimal. So to show that KKT points are not always optimal, I have to consider a non-convex problem. But I can't find an example for that!
0
votes
0answers
20 views
How to find out if a point is a local min when no constraint is active?
I want to solve an optimization problem with some constraints and we know that the problem is non-convex, Abadie constraint qualifications hold in any feasible point and the point is a solution of KKT ...
1
vote
1answer
166 views
What if we found many points satisfying KKT conditions
I have the following convex optimization problem:
\begin{equation}
\begin{aligned}
\max_{x} & \quad f(X)\\
s.t. &\quad \sum\limits_{j=1}^N A_{ij}X_{ij} - \sum\limits_{j=1}^N A_{ji}X_{ji}= 0, \...
0
votes
1answer
48 views
Minimize $x^2-y^2-z^2$ subject to $x^4+y^4+z^4\leq1$ using KKT Conditions
I am having trouble finding finding the KKT points of the following problem.
$$
\begin{array}{ll}
\min&{x^2-y^2-z^2}
\\
\text{subject to} & x^4+y^4+z^4\leq1
\end{array}
$$
The Lagrangian is
$$
...
0
votes
1answer
48 views
Constrained maximization problem with linear function
I have the following problem. Given this function
$E[\pi] = (1-r)[\alpha b- (1-p)C-K]+T $
I would like to find the maximum w.r.t. $r$ given this constraint:
$U = (1-r)b-T \geq 0$.
It is an economic ...
1
vote
2answers
99 views
Non-linear optimization problem using Lagrange's method/K.K.T. conditions
We are given the following problem:
$$\text{minimize }
2x_1^2 + x_2^2 + 3x_3^2
\text{ subject to }
x_1+x_2+x_3=10,
x_1\le5,
\text{ and }
x_1,x_2,x_3\ge0$$
I understand that I have to check all ...
0
votes
1answer
37 views
what's the condition of the complex convex problem?
In most books or papers, the convex problems are usually defined on the Real field. However, there are also a lot of works focus on the problem defined on the Complex field but also use the KKT ...
0
votes
0answers
17 views
Convex NLP problem with inequality constraints: is convexity enough to say that points that solve KKT conditions are globally optimal?
Let’s say that we have an NLP problem with inequalities, and we solve the KKT conditions and then find several points that satisfies the KKT conditions. It seems like if the problem is convex and both ...
1
vote
1answer
65 views
Optimization problem Kuhn Tucker
i'm stuck on this problem because i don't know what to do next
$$\begin{cases} \text{maximize } &f(x,y) = -(x-2)^2-(y-1)^2 \\ \text{subject to } &g_1(x,y) = -x-y+1 \leq0,\\&g_2(x,y) = x^2+...
0
votes
1answer
42 views
Convex optimization problem with similarity constraint between variables
Let $x_i,y_i\in\mathbb{R}$, $a_i\in[0,1]$, with $y_1>y_2$ and $y_3>y_4$. We also have $(y_1-y_3)^2 + (y_2 -y_4)^2 <\varepsilon $. I need to solve the following constrained optimization ...
1
vote
2answers
96 views
Lagrange multiplier does not find global minimum
I want to minimize the function
$$f(r_1,r_2,r_3)=\frac{1}{6}(r_1^2+r_2^2+r_3^2)-(\frac{1}{r_1^3}+\frac{1}{r_2^3}+\frac{1}{r_3^3})$$
subject to the conditions:
$$g(r_1,r_2,r_3)=\frac{1}{3}(r_1^2+r_2^2+...
2
votes
0answers
63 views
Orthogonal projection into a sparse subspace with $s$ dimension
Traditional orthogonal projection of a given point $y \in \mathbb{R}^n$ into a closed and convex set $D\in \mathbb{R}^n$ is defined as the follwing:
$$
P_D(y)=\arg\min_{x \in D}||x-y||_2^2
$$
Now ...
0
votes
2answers
55 views
KKT optimisation problem
I want to find the minimum of the following function
$$\min \limits_{x}c^{T}x$$
$$\sum_{i=1}^nx_i=1$$
$$x_i \geq 0$$
Let's define Lagrangian function:
$$L(x,\lambda,\mu) = \sum_{i=1}^nc_ix_i - \sum_{i=...
1
vote
0answers
9 views
Strict pseudoconvexity and unicity in constrained optimization
In the Nonlinear programming textbook (Bazaraa et al.), the Theorem 4.2.16 (p. 195) states that, if $y$ is a KKT solution, and the objective $f$ is pseudoconvex at $y$, and the constraints $g_k$ are ...
0
votes
1answer
46 views
Kuhn-Tucker Conditions for finding minimum
I need to minimise $$\begin{split}f(x,y)=2x+xy+3y\\ s.t.\begin{cases} x^2+y\geq3\\ x+0.5\geq 0\\ y\geq0\end{cases}\end{split}$$
I get my lagrangian,
$$L(x,y,\lambda,\mu) = -\lambda x^2 - \lambda y + 3\...
0
votes
0answers
32 views
How to solve the KKT condition directly?
According to my understanding, consider a convex optimization problem where the strong duality hold
$$\min f(x)$$
$$\text{s.t.}\quad g(x) \leq 0,$$
if a point $x^*$ satisfies its KKT condition,
$$
\...
0
votes
1answer
53 views
Minimum maximum first and second derivative curve between two points
How could the following problem be tackled?
Find the curve $v$ between two points $v(0)=p \neq q=v(1)$ with minimum velocity and acceleration (in the $L^\infty$ sense), such that $v'(0)=v'(1)=0$
I ...
0
votes
0answers
8 views
Does strong duality imply primal and dual solutions exist?
For an optimization problem, we may have an optimal value, but do not have an optimal solution. E.g.,
minimize 1/x
s.t. x>=1
...
