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.

Filter by
Sorted by
Tagged with
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 ...

1
2 3 4 5
9