Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
14 views

When is LICQ useful in KKT conditions?

KKT establishes a set of criteria for differentiable optimisation problems related to strong duality (i.e. when primal optimal equals dual optimal). In particular, KKT conditions are necessary for ...
1
vote
1answer
26 views

How to imply the vanishing gradient condition in KKT?

In Boyd's Convex Optimisation, the following optimisation problem is considered $$ \begin{align} \min\quad & f_0(x)\\ \text{s.t.}\quad & f_i(x)\le 0,\quad i=1:m,\quad m\in\Bbb Z_{\ge 0}\\ &...
0
votes
0answers
11 views

Equivalence of two KKT conditions

The KKT conditions are usually defined as follows \begin{align} \nabla_x \cal L(x^*) &= \nabla f(x^*) - \sum_{i\in\cal I}\mu_i g(x^*) - \sum_{i\in\cal E}\lambda_i h(x^*) = 0 \\ g(x^*) &\leq ...
0
votes
0answers
14 views

Linear Program with finite optimal value has strictly complemenetary solution

In my lecture, the following statement was given without any proof: Given a primal-dual linear problem (P) $$\{min~ c'x \mid Ax=b, x \geq 0\}$$ (D) $$\{max~ b'y \mid A'y+s=c, s \geq 0\},$$ it ...
0
votes
0answers
27 views

Solve optimization problem using KKT conditions

I'm trying to understand the solution to Boyd and Vandenberghe Problem 5.30: Boyd and Vandenberghe Problem 5.30 The Lagrangian is $$L(X,\nu)=\text{tr}X-\log\det X+\nu'\left(Xs-y\right),$$ so the ...
0
votes
0answers
14 views

Derive LCP from KKT conditions of a QP

I'm working through this tutorial on LCPs and interior point methods. In it, the authors claim that the following quadratic program $$ \begin{aligned} \min \quad& \frac{1}{2}u^TQu - c^Tu\\ \text{...
0
votes
1answer
25 views

Can KKT be used in minimization s.t to constant param

Can KKT be used : min g(x) s.t x>=constant where constant > 0 I have read this The Kuhn-Tucker method: here says that This is an alternative, and ...
0
votes
1answer
32 views

Local optimality of non-convex quadratic minimization with linear constraints

We are interested in minimizing a quadratic function, which is not convex. The feasible set is a polyhedron. We know that the global minimum is at a vertex when the function is concave. Also, there ...
0
votes
0answers
62 views

How to solve this Non linear optimization problem?

I need to minimize the below-mentioned expression. $ L = min (a_0-b_0*(p_1+p_2))^2 + (p_1*y1+p_2*y)$ ,with s.t p_1 >=0 ,p_2 >=0 Here ...
0
votes
0answers
22 views

Explain what happens if you use KKT to solve this problem

Explain what happens if you use KKT to solve this problem: \begin{equation*} \begin{aligned} & \underset{(x,y)\epsilon \mathbb{R}^2}{\text{minimize}} & & x+y \\ & \text{subject to} &...
0
votes
0answers
14 views

Optimize a strictly decreasing simple function $f(Ax)$ using KKT condition

$f:\mathbb R^n\to \mathbb R$. $A$ is a $n\times n$ matrix. Solve: $$\min_{x=(x_1,x_2,...x_{n})} f(Ax)$$ s.t. $$x_i>0 \ \forall i$$ $$\sum_{i\in \{1,...n\}} x_i=1$$ $f$ satisfies: if $f(Ax)<...
2
votes
0answers
52 views

Can $f(x) = \sqrt{x_1 x_2} + \sqrt{x_3 x_4}$ be solved by Kuhn–Tucker conditions?

Consider $\max_{x_1, x_2, x_3, x_4} f(x) = \sqrt{x_1 x_2} + \sqrt{x_3 x_4}$ s.t. $\; p_1x_1 + p_2x_2 + p_3x_3 + p_4x_4 \le w$ I know we can solve the max problem through separately considering ...
1
vote
1answer
43 views

Find the orthogonal projection of $y \in \mathbb{R}^3$ onto the space $\{x: x_1^2 + 2 x_2^2 + 3 x_3^2 \leq 1\}$

Find a formula for the orthogonal projection of $y \in \mathbb{R}^3$ onto the space $\{x: x_1^2 + 2 x_2^2 + 3 x_3^2 \leq 1\}$. The formula should depend on a single parameter that is a root of a ...
0
votes
0answers
16 views

Critical points (Undefined partial derivatives) and KKT condition

I am going through the contents of KKT conditions. But it seems to deal with only cases that partial derivatives of the Lagrangian function $L$ being nonnegative. Is there any case where the local ...
0
votes
0answers
40 views

Operation Research penalty function and KKT

I have a problem as this. Wish someone could help me! Thanks a lot!
0
votes
0answers
13 views

Does any one know how to derive this KKT condition from the lagrangian function?

(1) uplink sum rate maximization (2) lagrangian function (3)KKT condition As the paper said,$24(a)~24(f)$ is derived from the (2) lagrangian function,i know how to derived them from lagrangian ...
1
vote
2answers
115 views

Minimize the weighted sum of reciprocals

Let $\mathbf{a}_{i} \in \mathbb{R}^{M}$ with $\|\mathbf{a}_{i}\|^{2} = 1$, $\forall i = 1, \ldots, N$. I need to solve the following problem in closed form: \begin{align} \displaystyle \mathrm{...
0
votes
0answers
28 views

How to solve this nonlinear optimisation problem?

I have the following optimization problem where $K>0$. \begin{align*} \min_{y_1,\ y_2\ge 0} 2k(\exp(-y_1)+\exp(-\min(y_1,y_2)))+2y_1+y_2. \end{align*} I divided into two cases: Case 1: $y_1\...
0
votes
0answers
13 views

Strong Duality in Hilbert Spaces for convex problems?

Setting I'm looking for a proof of the following fact, if $f,g$ are lower-semi-continuous and convex function from a Hilbert space $\mathscr{H}$ to $\mathbb{R}$, with $f$ strictly convex continuous. ...
0
votes
1answer
50 views

Silly Quadratic programming

Suppose that I want to minimize the function $x^2$ subject to the contraint $$ ax\leq b, $$ for some $b> 0$. I solved the problem if the contraint is an equality but I'm not sure how to go about ...
1
vote
1answer
39 views

Non linear optimization, KKT

max: $10x_1-2x_1^2-x_1^3+8x_2-x_2^2$ s.t. $x_1+x_2≤2$ $x_1≥0$ $x_2≥0$ I'm supposed to write down the KKT conditions, show that (-1,-1) is not optimal and to find the solution to this problem. ...
0
votes
0answers
45 views

Using kuhn tucker to solve non negativity constraints

George likes breakfast tacos and milk. His utility is given by $u(t, m) = t + 5 \ln(m)$. Suppose tacos and milk both cost 1 dollar a piece. How should George spend the $\$4$ he has set aside for ...
3
votes
1answer
62 views

Reference Request: KKT in Hilbert Space

Are there analogues of Slater's condition and the KKT conditions in separable Hilbert spaces? Does the infinite dimensionality pose a problem?
1
vote
0answers
22 views

SVD for constrained Optimization

Given the following constrained optimization: $argmax_{W_1, W_2} W_1^TMW_2 $ subject to $W_1^TW_1 = I$ and $W_2^TW_2 = I$. The closed form solution $(W_1^*, W_2^*)$ is found through SVD ...
1
vote
0answers
29 views

Applying KKT conditions

This is in relation to this paper I am looking for ways to optimize Recall @ fixed Precision ($R@P$) for a machine learning problem and i didnt want to use accuracy as a proxy for $R@P$. Upon ...
0
votes
0answers
51 views

Explanation of Karush Kuhn Tucker conditions?

Can somebody please explain how we get the Karush Kuhn Tucker conditions, especially the complementary slackness, without using the crutches of jargons? I am not well versed in what dual problems or ...
0
votes
1answer
34 views

Kuhn-Tucker question with two inequality constraints

I've been asked to solve the following problem. max $10x-5x^2+2y-y^2+25$ subject to $1-x-y\ge0$ $1-x^2-y^2\ge0$ Is anyone able to solve this by hand? NB: I've been told that the KT assumptions ...
0
votes
1answer
36 views

When are KKT conditions indeed necessary first order conditions?

Somewhat based on: Reformulation of optimization problem using kkt and lagrange conditions Say I have the following optimization problem: $$ \begin{aligned} \min_{z}\min_{y} \, &\frac{1}{2} y^T \...
0
votes
1answer
64 views

KKT conditions strict inequality constraints

Some people asked questions about KKT conditions with strict inequality constraints, such as Kuhn Tucker conditions with strict inequality constraints? Questions about constraints and KKT conditions ...
1
vote
1answer
93 views

Dual problem of unconstrained linear least squares

The following seemingly simple question is confusing the heck out of me: Take the least squares regression problem (for $X \in \mathbb{R}^{n×p}$ and $y \in \mathbb{R}^n$): $$\min_{\beta \in \...
1
vote
1answer
83 views

Optimization under constraints - unique solution or not

Say we have a problem such as minimize $f(x)$ such that $h(x)=0$ and $g(x) \leq0$. Let the minimum achieved under these constraints be $f(x^*) = p^*$. My question is: If $f(x)$ is convex, are $p^*$ ...
-1
votes
2answers
34 views

Langrarian multiplier [closed]

Consider the following function $$f(x, y)=x^4-y^2$$ And Set $A=\{(x,y)\in R^2: x^2+y^2=1\}$ is required. find the Lagrangian equation that determines the extreme point of $F$ on $A$ and calculates ...
1
vote
1answer
48 views

Reformulation of optimization problem using kkt and lagrange conditions

Following setup: $$ \begin{align} \min_{y} &\frac{1}{2} y^T \bar{H} y \left(=V_k-V_{k+1}\right) \\ \text{s.t. } &x_{k+1}=Ax_k+Bu_k^*\\ &U_k^* = \underset{U_k}{\arg \min} V_k,\...
0
votes
1answer
25 views

Finding global maxima with Kuhn-Tucker conditions (and distinguish them from other critical points)

We want to maximize $(x-1)^2 + (y-1)^2$ restricted to $x + y \le 2$ and $x, y \ge 0$. I tried the following combinations: $x \gt 0, y \gt 0$ This led me to no critical point. $x \gt 0, y = 0$ This ...
1
vote
3answers
110 views

Minimum of the quartic $(x^2-1)^2+y^2$ using KKT conditions

Consider the following optimization problem. $$\begin{array}{ll} \text{minimize} & (x^2-1)^2+y^2\\ \text{subject to} & x^2 - 4 \le 0\\ & x + y \le 0\end{array}$$ Using KKT ...
1
vote
1answer
75 views

Confusion about definition of KKT conditions

In this link https://www.cs.cmu.edu/~ggordon/10725-F12/slides/16-kkt.pdf you can find this: And in the Nonlinear programming book by Bazaraa page 207 you can find this: My question is Are those ...
0
votes
0answers
22 views

Convert function for KKT

I wanted to ask how can I determine when a function should stay as it is or if I should restate it with changing functions and constraints signs? e.g.: $$ f(x) = -(x_1+1)^2 -2(x_2+1)^2 \\ s.t: -x_1-...
0
votes
1answer
39 views

Dual optimization problem, decomposition.

I have the following problem: $\min x_1 ^ 2 + x_2 ^2$ s.t. $x_1 + x_2 \ge 1$ $x_1 \ge 0$ $x_2 \ge 0$ I have three inequality constraints, so my lagrangian would be $L = x_1 ^2 + x_2 ^2 + \lambda_1 (-...
1
vote
2answers
87 views

KKT optimality conditions in optimization exercise

Consider the following problem $$\max \Big(x_1-\frac{9}{4}\Big)^2+\big(x_2-2\big)^2$$ $$s.t.\quad x_2-x_1^2\ge0\\ x_1+x_2\le 6\\x_1,x_2\ge0$$ Write the KKT optimality conditions and verify ...
0
votes
1answer
30 views

How to find if following function is Convex?

I want to optimize the following function $U = ...$ using KKT. I am still learning KKT. However, I cannot understand how I can find if the following function is a convex function? $$U = \frac{(A-1)B\...
1
vote
1answer
59 views

KKT conditions holds true under Cottles's constraint qualifications?

Exercise Solution: Could someone please explain why the reached contradiction solves the exercise? I can understand the solution but I don't know how does that implies that $\overline x$ is ...
2
votes
2answers
45 views

Does a constrained nonlinear program only have one KKT point?

I am just wondering whether or not a constrained nonlinear program has only one KKT point? Intuitively, I think this is wrong and the only thing we can conclude is that any KKT in such program is ...
0
votes
1answer
82 views

How to apply KKT conditions (to minimization) to solve maximization problem?

Consider the following problem $$ \max x_1^2+4x_1x_2+x_2^2 \\ s.t. x_1^2+x_2^2=1 $$ a. Using conditions KKT, find the candidates to be solution. b. Using second order conditions, stablish the ...
0
votes
0answers
46 views

lagrange multipliers of function log

I am using lagrangian multiplier with KKT conditions for the first time. I have an equation : $max \space g(p_f,p_m)= (\frac{h_f p_f}{N})(\frac{h_m p_m}{N})$ subject to : $h_fp_f-Q<0 \\p_f-p^...
2
votes
1answer
96 views

Minimizing a sum of decaying exponentials subject to constraints

Consider the following problem \begin{align*} \min_{x}\quad\sum_i\sum_j&\exp(-a_{ij}x_{ij})\\ \text{subject to}\quad\sum_i\sum_j&x_{ij}=n\\ &x_{ij}\ge0\,\,\forall i,j \end{align*} where $x\...
0
votes
0answers
18 views

Two methods for second order sufficient conditions for constrained optimization

There are at least two methods to verify those type of conditions stated in their weaker form: projected Hessian bordered Hessian In these course notes (section 2.6 Projected Hessians - page 19 in ...
0
votes
0answers
46 views

Skills to solve KKT condition equations.

The problem is $$\begin{aligned} \min ~&\frac{1}{2}\|x\|_2^2\\ \text{s.t.}~ &a^Tx=b\\ &x\ge 0 \end{aligned}$$ How can we find the optimal solution with KKT condition? My thinking: ...
0
votes
0answers
20 views

What is the dual function and solution of this function, subject to a restriction?

I woul like to know what is the dual function and then, what is the solution of the dual problem of: $\begin{align} {\bf x^*} = \arg \min_{{\bf x}\in{\bf X}}f({\bf x}) = \frac{1}{2} {\bf x^t P x} \...
2
votes
1answer
52 views

Optimal distribution using KKT condition

I have following problem \begin{eqnarray} &\min_{p,t}&\quad \sum_{i =1}^n \frac{a_i^2}{p_i} \\ &s.t.& \sum_{i =1}^n p_i = b \\ && 0 \leq p_i \leq 1\quad \forall i \end{...
0
votes
0answers
15 views

First Kuhn-Tucker condition from auxilliary variable

In the optimisationsproblem minimise $f_0(\textbf{x})$ subject to $f_i(\textbf{x})\leq0 \quad (i=1,2,\ldots,m), \quad \textbf{x}=(x_1,x_2,\ldots,x_n)$ this can be rewritten into minimise $f_0(\...