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
0
votes
1answer
39 views

Interpretation of this Lagrange Multiplier

I have the following utility maximization problem with inequality constraints: Objective function given by $U(x_1,x_2)=\ln(x_1)+\beta \ln(x_2)$ where $0<\beta<1$, and the constraints are given ...
1
vote
0answers
57 views

KKT multiplier for quadratic minimization over Euclidean ball

I have a question about the minimization problem $$\begin{array}{ll} \text{minimize} & \frac{1}{2} x^T A x + b^T x\\ \text{subject to} & \frac{1}{2}\|x\|^2_2 \leq \frac{1}{2}\delta^2\end{...
0
votes
0answers
37 views

Solution for two equivalent optimization problem based on KKT conditions

Suppose I have the following two optimization problem: \begin{equation} \begin{aligned} & \mathcal{P}_{1}: && \underset{{\bf a}, {\bf b}}{\text{min}} \; \; {\bf 1}_K^T {\bf a} \\ & \...
0
votes
0answers
25 views

Why some constraints can not be optimized in the optimization process.

Assume there are two optimization problems: (1): \begin{align} & y^*=\underset{y}{argmin}~(x^2+y^2)=5, \\ & s.t. \ \ 0\leq x\leq3. \end{align} The constraint in (1) can be optimized ...
1
vote
0answers
39 views

KKT conditions for min-cost flow QP

I'm working on a convex quadratic separable min-cost flow problem with the following structure: $P = \{\min \frac{1}{2}x^tQx + qx : Ex = b, 0 \leq x \leq u\}$ But I'm stuck on deriving the KKT ...
0
votes
0answers
26 views

Redundant Kuhn-Tucker conditions

I am triyng to solve and optimization problem whose Lagrangian is given by: $L=\int_0^1 [\theta+q^b(\theta)-q^s(\theta)][q^s(\theta)-q^b(\theta)]d\theta + \lambda [\int_0^1 (q^s(\theta)d\theta)-\...
2
votes
0answers
45 views

Solve KKT system for Quadratic Constrained Quadratic Program

I'm having trouble solving one of the possible cases that arise when solving the KKT conditions of the following problem: We have the following optimization problem in $ \mathrm x \in \mathbb R^n$, ...
0
votes
1answer
39 views

Lagrange multipliers and the Simplex Algorithm

I am trying to understand the Simplex Algorithm from a gradient perspective, and I am wondering if anyone knows of a method for determining the variables that should both enter and leave the basis of ...
1
vote
0answers
20 views

Calculate minimum of function using KKT theorem

So I have this exercise I found in old exams. Using KKT conditions solve the optimization problem ($, P, min) where f(x,y) = x^2 + (y-4)^2, and $ = {(x,y) from R^2; x + 3y <= 10 and x -2y <= ...
0
votes
0answers
27 views

Why do the KKT conditions become Lagrange multipliers without inequality constraints?

I'm currently taking a convex optimization course at my school using the textbook Convex Optimization (Boyd & Vandenberghe) and had a question regarding KKT conditions and their connection to ...
0
votes
1answer
67 views

Solve using KKT conditions when number of variables is less than number of constraints

$$\begin{align} \text{minimize} \quad & f(x) = x_1^2 + x_2^2 +x_3^2 \\ \text{subject to} \quad & 2x_1+ x_2-5\leq 0 \\ & x_1+x_3-2\leq 0 \\ & 1-x_1 \leq 0 \\ & 2-x_2 \leq 0 \\ & ...
1
vote
1answer
61 views

Solving this problem with Lagrange multipliers method

Hi everyone I want to solve this problem with Lagrange multiplier method This is the problem $$ \operatorname{Min} F(x)=3a x_1+5a x_2 $$ subject to these Constraints : $$ g_1 : (2.16/x_1)+(10/...
0
votes
1answer
38 views

Lagrangian with constraint Greater than Zero (NOT 'greater than or equal to').

Problem statement: $$\underset{D}{\text{argmin} }\lVert D\Sigma - G \rVert_F^2 \text{ with constraint } D>O$$ $D$ and $\Sigma$ are positive diagonal, therefore the constraint interprets $\text{...
2
votes
0answers
30 views

How is this KKT condition derived?

$\text{minimize } ||x-x_0||_2^2$ subject to $x \succeq_K 0$ Where $x_0 \in \Bbb R^n$ and $K$ is a proper cone. If $z$ represents the positive Lagrange multiplier, then: $x-x_0 = z$ is a ...
0
votes
0answers
30 views

Active set method for a simple problem

In my computetional methods course we recently had an algorithm for solving $(P)$ : $\min_{x \in \mathbb{R}^n} f(x) = \frac{1}{2}x^THx + c^Tx $ subject to $a_i \leq x_i \leq b_i$ for $i \in \...
1
vote
0answers
105 views

Dual of linear program with several quadratic constraints

Let $ \mathcal{P}$ be a convex problem with linear objective and quadratic constraints, $$ \eqalign{ \mathcal{P}: & \min_{x,t} -t \\ & \text{s.t.} \\ {\color{blue}{\mu_k}}: & a^H_k x +...
0
votes
1answer
25 views

KKT condition for the proximal algorithm

This slide shows that the KKT condition for the proximal gradient descent is this inequality. I don't know where this comes from. Using KKT , we can only get equality for the stationary condition, ...
1
vote
0answers
39 views

Dual of linear function with convex and non-convex constraints

I would like to compute the dual of the following problem by using the KKT conditions. However, due to form of the first constraint I am not able to obtain the dual. The problem is the following \...
0
votes
0answers
50 views

Optimizing a function under strictly positive constraint

Find x and y that optimise \begin{align} f(x,y) &= (-a-y)(\Psi(y)-\Psi(x+y)) + (b-x)(\Psi(x)-\Psi(x+y)) \\ &-\log \Gamma(x+y) + \log\Gamma(x) + \log\Gamma(y) \end{align} where a, b are ...
0
votes
1answer
63 views

KKT optimisation - condition of inequality constraint being zero

For example, given the following: Minimise $$ f(x_1, x_2) $$ Subject to $$ h(x_1, x_2) = 0 $$ $$ g(x_1, x_2) \leq 0 $$ The KKT conditions are written out as $$ l(x, \lambda, \mu) = f(x_1, x_2) +...
1
vote
0answers
44 views

Derive the KKT conditions for the following problem. [closed]

\begin{align} \min &\ \text{tr}(CX) - \log \det X \\ \text{s.t} &\ \text{tr}(AX) = b \\ &\ Xs = y, X \in S^n_+ \end{align} with $b \in \mathbb{R}, y \in \mathbb{R}^n, s \in \mathbb{R}^n$ ...
4
votes
1answer
27 views

How to project a vector on a set defined by linear inequality constraints through KKT conditions?

I need to find the projection $x \in \mathbb{R}^{k}$ of a vector $z \in \mathbb{R}^{k}$ on the set defined by $Y \cdot x \geq 0$ where $Y$ is a (given but no specific property) matrix of size $m \cdot ...
1
vote
1answer
52 views

General solution to linear program?

Source of the Problem The problem comes from an application in economics concerning trade between agents to maximize aggregate "wealth". More exactly, there are $m$ agents and $n$ groups and we ...
0
votes
1answer
62 views

How to convert constrained optimization problem to non-constrained using lagrangian and kkt

I have a nonlinear objective function with a nonlinear set of inequality constraints and I am trying to reformulate the problem using the Lagrangian function. My goal is to transform a constrained ...
1
vote
2answers
83 views

Solve KKT conditions of the following problem

I'm having problems solving the following $\min f(X) = −3x^2 +y^2 +2z^2 +2(x+y+z) $ subject to $c(X):=x^2+y^2+z^2−1=0$ Now, I get the KKT: $-6x +2 -2\lambda x = 0 $ $2y +2 -2\lambda y = 0 $ $4z +...
0
votes
0answers
14 views

Quadratic problem with non-negativity constraints: substantiate the hardness of analytical solution

I have a quadratic program $$ \underset{V\mathbf{x}=\mathbf{d}, \mathbf{x} \geq \mathbf{0} }{\min} f_{\mu}(\mathbf x)= \sum_{i=1}^{n} \text{Var}\left(R_{i}\right)-\sum_{i=1}^{n}\mu\text{E}(R_i), $$ ...
0
votes
0answers
19 views

KKT conditions and weak duality

KKT conditions are always necessary for optimality and are sufficient under strong duality. Why is strong duality needed for sufficiency? Why is weak duality not sufficient?
0
votes
0answers
25 views

How can we check the convexity of the two variables function?

I am working on the problem of KKT conditions with inequality constraints and at the last stage, it needs to check if the point in question satisfies Slater's constraint qualification. According to ...
1
vote
1answer
17 views

For a Bi-level Mixed Integer Linear Program with integer variables in the lower, can I use KKT conditions to reduce the problem to a single level?

For example, my optimization formulation looks something like this: max $-10y-x$ s.t. $y=$ arg {min $20y-25x\leq 30;2y+x\leq 10;-y+2x\leq 15;10y+2x\geq15$} $y$ integer In order to convert this to ...
2
votes
2answers
66 views

Where am I wrong in my understanding about the activeness of the constraints?

I have following convex optimization problem $$\text{min. }~~ x~\\ \text{s.t.}~~~\frac{y^2}{x}\leq z\\ y+z\leq c$$ where $\{x,y,z\}$ are the non-negative variables and $c$ is some positive ...
0
votes
0answers
37 views

Optimization of $\min{ c^{T}x+b^{T}y}$

I am new to optimization, and whenever we get an LP of the sort: $\min{ c^{T}x+b^{T}y}$ s.t. $Ax\leq b$ $A^{T}y=-c$ $y \geq 0$ Assume that there is a valid point that fulfills the restrictions. ...
1
vote
1answer
57 views

How to handle the case when KKT condition is always false for this toy case?

For the following simple problem: $$\begin{aligned} \min_x & (x-2)^2\\ s.t. \ \ & x^2=0\\ &x^2 \le 0 \end{aligned}$$ Since there is only one feasible point $x=0$, the answer is obvious. ...
1
vote
0answers
29 views

Find minimizer with active constrains

I am trying to find a minimizer for a function $ f : \mathbb R^2 \rightarrow \mathbb R $ with constrains $ c(x) \geq 0, c : \mathbb R^2 \rightarrow \mathbb R^4 $. I also need to find out the correct ...
0
votes
1answer
72 views

Using the KKT Conditions in the Non Convex Case (Quasi Convex)

It is know that if the problem is convex then we can use the KKT conditions to find the solution. However, is it still possible to use the KKT conditions in the same way if the objective function is ...
0
votes
0answers
37 views

Why are mathematical programming problems with equilibrium constraints (MPEC) harder than solving the KKT conditions?

In optimization theory a complementarity problem is a problem, where the constraints include complementarity conditions, such as $$ u^{T}v=0, u_{i}, \geq 0, v_{i}\geq 0, u,v \in \mathbb{R}^{n}. $$ ...
0
votes
0answers
41 views

Linear inequality constraint - in KKT optimisation

I have a query regarding whether KKT is optimal with some linear inequality constraint and non-linear inequality constraint. For KKT to be optimal the inequality constraints must be convex. We know ...
0
votes
0answers
39 views

Non-convex QCQP with embedded variable

I have the following problem whose optimal solution (if possible), I would like to find. $\min_{\mathbf{f}} \left\| \mathbf{L}_1 \mathbf{f} \right\|^2_2 + \left\| \mathbf{L}_2 \mathbf{f} \right\|^2_2 ...
0
votes
1answer
46 views

how to use KKT conditions for an exponential function

our teacher gave us a problem in the exam that I failed to answer it even after passing it, and I ask for an explanation from people here please... this is the problem : let K be a subset of $\Bbb R^...
0
votes
0answers
19 views

Equivalent Convex programs with different solutions

Let $R_\kappa \in \mathbb{R}^{d \times d}_{sym}$, $S_\kappa \in \mathbb{R}^{d \times d}_{sym}$, $\eta_\kappa \in \mathbb{R}^+$, for a set $\{ \kappa \}$. Define a optimization problem $(1)$ as \begin{...
0
votes
0answers
75 views

The operation of KKT condition in lagrange function

Does kkt condition do the partial differential to the lagrange multiplier i wanted,and set the equation become zero? i mean, $L=P_E+\alpha [P_T-\sum\limits _{k=1}^{K}p_k]+\gamma [\sum\limits _{j=1}^{...
0
votes
0answers
56 views

How to correctly use KKT conditions?

Let $A\in \mathbb{R}^{n\times n}$ be a positive definite matrix. Then find \begin{equation} \max_{|x_i|\leq1}x^TAx \end{equation} Here I want to use KKT conditions to show that $|x_i|=1$ is an ...
1
vote
0answers
91 views

KKT conditions - Equality constraints

I have an equality constraints as $\qquad \qquad \min_x f(x) \\ \qquad \qquad s.t. \quad Ax \leq b \\\qquad \qquad \qquad x = h(x)$. The KKT conditions of the minimization without the equality ...
2
votes
1answer
248 views

KKT condition with equality and inequality constraints

find the KKT point of the following problem: $$\min\quad f(x_1,x_2)=(x_1-3)^{2}+(x_2-2)^{2}\\ subject\quad to\qquad \qquad \qquad \qquad \qquad\qquad\\ x_1^{2}+x_2^{2}\le5\\ x_1+2x_2=4\\ x_1\ge0,x_2\...
1
vote
1answer
76 views

How to handle optimization problems when optimization variable is matrix?

Suppose we have the following optimization problem $$ \min_{0\preceq M \preceq I} y^TMy $$ where $y \in \mathbb{R}^n$ and $M \in \mathbb{R}^{n \times n}$ is a positive semi-definite matrix. Notice ...
0
votes
0answers
19 views

Minimize $\left\|BA\right\|_2 $ under these constrain

Minimize $\left\|BA\right\|_2$ while B is a given $m*n$ matrix with rank n and A is an $n*t$ matrix which is not given. Such that $B'*u_{1}*v_{1}' = a*u*v$; $\left\|A\right\|_2 = b$. While ...
0
votes
1answer
34 views

Lagrange duality compared with Lagrange multiplier method

As we all know, Lagrange multiplier method says: in order to find the extremum of $f(x)$ over $x$, s.t. $g(x)=0$, one instead finds the extremum of $f(x)+\lambda g(x)$ over $x$ and $\lambda$. Note ...
1
vote
1answer
57 views

Find KKT point of $\min_{x \in \mathbb{R}^4} x^Tx$ subject to $x^TAx \geq 1$.

onsider the following problem: $$\min_{x \in \mathbb{R}^4} x^Tx$$ over $C=\{x \in \mathbb{R}^4 \mid x^TAx \geq 1\}$ where $A \in \mathbb{R}^{4 \times 4}$ is a symmetric matrix with two distinct ...
0
votes
1answer
262 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
40 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
20 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 ...