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
0answers
20 views

Help with Quadratic Programming

Any idea how to solve this using MATLAB? I know about quadprog. However, because of the presence of $x^*$ and $x_0$, I am not able to define single coordinate transformation that will include both the ...
-2
votes
0answers
23 views

Maximum volume with given surface area [closed]

How to prove that a given closed (smooth continuous two dimensional) surface area encloses a maximum volume for the sphere?
0
votes
1answer
14 views

Karush-Kuhn-Tucker in Quadratic Program

I read an paper on Quadratic Programming: Paul A. Jensen, Jonathan F. Bard: Operations Research Models and Methods Nonlinear Programming Methods.S2 Quadratic Programming Available here: https://www.me....
1
vote
0answers
21 views

Proper explanation of KKT equations and Basic constraint qualification works?

I am learning Non-Linear optimisation. Last time I read about KKT (Prof notes and some googling) and Basic constraint qualification and somehow tried to convince myself this and that but now when I am ...
0
votes
0answers
56 views

Maximize $x^2 + y^2$ subject to $1 \leq 2 x^2 + 4 y^2 \leq 4$

$$\begin{array}{ll} \text{maximize} & x^2 + y^2\\ \text{subject to} & 1 \leq 2 x^2 + 4 y^2 \leq 4\end{array}$$ I don't know how to apply the KKT conditions here, maybe there is other method ...
0
votes
0answers
38 views

Confusion in understanding a simple convex optimization problem's solution

I am learning optimization through a course on Youtube. I have one confusion in solving the following problem. As per my understanding, the objective function is not convex. The problem is a ...
0
votes
0answers
6 views

NDCQ Explanation

Can someone explain the non degenerate constraint qualification intuitively? I don’t understand why it needs to be full rank or match number of variables in objective function
1
vote
0answers
21 views

Constraint Qualification and Non Linear Optimization

Why is the objective function a linear combination of gradient of constraints at optimal point for non linear inequality optimizarion under KKT? Intuitive answers please as only in process of masters ...
1
vote
0answers
30 views

KKT and Constraint Qualification

Have studied lagrangian and optimization primarily via Khan academy, as got bogged down with Simon and Blume Mathematics for Economists/Chiang and Wainwright Fundamental Methods of Mathematical ...
2
votes
1answer
30 views

$ f(x)+ \sum \lambda_ig_i(x) \geq f(\bar x), \forall x \in \mathbb{R}^n.$

Suppose that $f,g_i : \mathbb{R}^n \to \mathbb{R}$ $(i=1,\ldots,m)$ are convex functions and $\exists x$ such that $$g_i(x)<0 , \qquad i=1,\ldots,m.$$ Show $\bar x$ is optimized solution of $$\min ...
0
votes
1answer
28 views

Minimization with Trace of Hadamard Product

I have the following minimization problem, where I want to find $ X $ $$ \min_{X \succeq 0} \mathrm{tr}(A X) ~~~ \mathrm{s.t.} ~ X \circ I = I $$ Assume that $ A $ is Hermitian positive definite, $ I $...
2
votes
2answers
57 views

Minimize $\sum_i w_i^2 x_i^2$ subject to $Ax = b$

I have the following problem in an example test for a course in optimization: $$\begin{array}{ll} \text{minimize} & \sum_{i=1}^n w_i^2 x_i^2\\ \text{subject to} & Ax = b\end{array}$$ where $A \...
0
votes
0answers
9 views

Multipliers of KKT solutions

Let $(x^{*},\mu^{*})\in\mathbb{R}^{n}\text{ x }\mathbb{R}^{m}_{+}$ and $(\hat{x},\hat{\mu})\in\mathbb{R}^{n}\text{ x }\mathbb{R}^{m}_{+}$ two points that satisfy the KKT conditions for the problem $$\...
1
vote
1answer
21 views

KKT conditions with equality max(|x1|,|x2|)

I'm learning how to solve optimization problems with constraints, but im confused about applying the KKT conditions for the following problem $$\begin{array}{ll} \text{minimize} & f(x_1, x_2)\\ \...
2
votes
2answers
72 views

Given $\min \{a^Tx\mid x^TQx+2b^Tx+c\leq0\}$ and $Q\succ0$ find conditions for $Q,b,c$

Given $\min \{a^Tx\mid x^TQx+2b^Tx+c\leq0\}$ and $Q_{n\times n}\succ0,b\in\mathbb{R}^n,c\in\mathbb{R},a\in\mathbb{R}^n\backslash\{0\}$ find conditions for $Q,b,c$ for which the problem is feasible ...
0
votes
1answer
39 views

an optimization question

Consider a consumer who is trying to maximize: max $\sum_{t=1}^{M}\left(\frac{1}{2}\right)^{t} (x_{t})^{1/2}$ s.t. $\sum_{t=1}^{M} x_{t} \leq 1$ ($\forall x_{t} \geq 0, t=1, \ldots, M$ $(t < \infty)...
0
votes
1answer
24 views

Find the min value of $\min\{x_1x_2x_3:a^2x_1^2+x_2^2+x_3^2\leq1\},a>0$

Find the min value of $\min\{x_1x_2x_3:a^2x_1^2+x_2^2+x_3^2\leq1\},a>0$ using KKT So my try is: if we set $L(x,\lambda)=x_1x_2x_3+\lambda(a^2x_1^2+x_2^2+x_3^2-1)$ and differentiating wrt to all ...
0
votes
1answer
28 views

KKT $\min x_1^2+2x_2^2+x_1$

Given $\min x_1^2+2x_2^2+x_1$ s.t : $x_1+x_2\leq a$ Prove: a)for every $a\in\mathbb{R}$ the problem has a unique solution. b)find the optimal solution as a function of $a$. c)let f(a)be optimal ...
0
votes
0answers
19 views

How should I apply Fritz John to problems with non-linear constraits?

Good afternoon. I am trying to solve this optimization problem: $$min\text{ }6(x_1-10)^2+4(x_2-12.5)^2\text{ s.t}$$ $$x_1+(x_2-5)^2\leq 50$$ $$x_1^2+3x_2^2\leq200$$ $$(x_1-6)^2+x_2^2\leq37$$ I have ...
0
votes
1answer
22 views

Slaters conditions for a convex optimisation problem

I have the following convex optimisation problem which is assumed to give an optimal solution: $max: f(x)$ $ a_{i}\leq x \leq b_{i}$ for $i=1,...,n$ and $a_{i}< b_{i}$ where $a_{i}, b_{i} \in \...
0
votes
1answer
39 views

How to use the KKT-conditions for a not-differentiable function using subdifferentials.

First some notation. Let $\dfrac{\partial}{\partial \textbf{x}} f(\textbf{x})$ determine the gradient for a funcion $f:\textbf{R}^n \rightarrow \textbf{R}$, and let the subdifferential be determined ...
0
votes
0answers
16 views

Show that if this nonbinding constraint is deleted, it is possible that $\bar{x}$ is not even a local minimum

Hello guys I am looking for some help for this nonlinear problem Let $\bar{x}$ be an optimal solution to the problem of minimizing $f(x)$ subject to $g_{i}(x)\leq0, i=1,...,m$ and $h_{i}(x)=0, i=1,.....
1
vote
0answers
15 views

Analytical derivation of linear optimization problem with KKT conditions possible at all?

I would like to find an analytical solution to a linear optimization problem optimizinig over multiple time steps. Following a reduced version of the LP with variables denoted in capital letters and ...
0
votes
0answers
96 views

Tucker Nearness Problem

I'm still not very confident with tensor calculus and I came across a paper that was solving an optimization problem based on Tucker decomposition; I don't understand how, from the initial formulation,...
0
votes
0answers
29 views

Which decision variables to consider in the KKT transformation of a bilevel optimization problem into a single-level one when collocation is used?

I am currently dealing with a dynamic bilevel optimization problem, that is, the variables are changing in time as described here: general problem formulation. To address the dynamics of the system, ...
0
votes
1answer
37 views

How to minimize $ x $ subject to $ y \le x^3$ and $y \ge 0 $

I have been getting into NLP, the Karush Kuhn Tucker theorem and the Linear Independence Constraint Qualification and I came across this problem. My first attempt was to solve graphically and I ...
1
vote
1answer
37 views

One dimensional constrained optimization: KKT conditions versus irregular points

In a constrained optimization problem, we search local solutions in the regular points that satisfy the KKT solutions as well as the irregular points. All the local solutions are included in these ...
0
votes
0answers
8 views

Necessity of non negativity conditions of slack variable in KKT

I have the following question: $\min \frac{1}{2}w\cdot w + \frac{C}{2}\sum_i\xi_i^2$ subject to $y_i(w\cdot x_i + b)\ge1-\xi_i \; \; \forall i $ Where $\xi_i$ are slack variables. Show that the ...
0
votes
0answers
47 views

KKT after epigraph

$\mathbf{P1}:$ $\max_{\mathbf{x}} \sum_{i}\textrm{min}(~f_i^1(\mathbf{x}),~f_i^2(\mathbf{x}))$ s.t $\sum_i x_i \leq a ~\forall ~i$ Applying epigraph the equivalent problem $\mathbf{P2}:$$\max_{\...
0
votes
0answers
22 views

Frizt John and KKT with optimization problem

I am trying to find all candidates for a local minimizer in $min\{ -x_1| x_2-(1-x_1)^3\leq 0 , -x_2\leq 0\}$. Denote $g_1(x)= x_2-(1-x_1)^3$, $g_2(x)= -x_2$, and $I(\bar x)=\{ i|g_i(\bar x)=0\}$ I ...
0
votes
1answer
50 views

Minimize function subject to inequality constraints using KKT conditions

Task: $$f(x)=x_1^2-2x_2+x_3^2\to \min$$ $$x_1+x_3=1$$ $$2x_1+x_2-x_3\le 2$$ $$x_1\ge0$$ Wolfram Mathematica result: $x_1=0, x_2=3, x_3=1, F(x)=-5$. GNU Octave result: $x_1=0, x_2=3, x_3=1, F(x)=-5$. ...
0
votes
0answers
37 views

Minimizing quadratic form with quadratic and linear constraints

I am trying to solve the following optimization problem $$\begin{array}{ll} \text{minimize} & \mathbf{x}^T \mathbf{A} \mathbf{x}\\ \text{subject to} & \left(\mathbf{x}-m\mathbf{1}\right)^T \...
3
votes
1answer
108 views

Question about KKT conditions and strong duality

I am confused about the KKT conditions. I have seen similar questions asked here, but I think none of the questions/answers cleared up my confusion. In Boyd and Vandenberghe's Convex Optimization [...
0
votes
1answer
31 views

Quadratic programming: KKT Optimality conditions

I am struggling with an exercice with the following quadratic program: $$min:x_{1}x_{2} + x^{2}_{1} + \frac{3}{2}x^{2}_{2} + 2x^{2}_{3} + 2x_{1} + x_{2} + 3x_{3}$$ subject to $$x_{1} + x_{2} + x_{3} ...
0
votes
1answer
83 views

Optimization using KKT of a 3 variable function

I want to maximize the function : $$\sum_{i=0}^n x_i*ln(1+ \frac{ c*y_i*z_i }{x_i})$$ subject to : $$\sum_{i=0}^n x_i \le X_0 \;\;\;\;\;\;\; and \;\;\;\;\;\;\; \sum_{i=0}^n y_i \le Y_0 $$ $$ x_i \;...
1
vote
1answer
44 views

Karush Kuhn Tucker and Optimal Minimum

I am a little not clear on the solutions of KKT Conditions. Suppose we have a convex function $f(x)$ and at a specific $x$ are our KKT conditions fulfilled. Does this make this point a global minimum ...
0
votes
1answer
30 views

Why use Primal-dual Methods for Linear Programs

We know we can solve an LP directly using KKT matrix method, even for QPs this works, for an example problem $$ \min_{x_1,x_2} x_1^2 + x_2^2 \quad \textrm{s.t.} $$ $$ x_1 + x_2 = 5 $$ KKT matrix is ...
1
vote
1answer
29 views

Minimize $\sum_{i=1}^p (y_i-x_i)^2 $ such that $\sum_{i=1}^{p'} y_i^2 - R^{2} \le 0$

I'm solving the following optimization problem. Could you please verify if my proof is correct or contains logical mistake? Thank you so much! Let $x = (x_1,\ldots,x_p) \in \mathbb R^p$, $p' \le p$,...
1
vote
0answers
54 views

Minimize $\frac{1}{2}\sum_{i=1}^p (y_i-x_i)^2$ such that $\sum_{i=1}^p y_i - 1=0$ and $\forall i \in [\![ p ]\!]: -y_i \le 0$ by KKT method [duplicate]

I asked how to solve this optimization here. I found this approach by combining @Royi's idea in his answer with KKT's conditions. Personally, I feel my formulation is clearer and easier to understand. ...
1
vote
1answer
77 views

How to minimize $\sum_{i=1}^p (y_i-x_i)^2$ with constraints $\sum_{i=1}^p y_i - 1 =0$ and $\forall i=\overline{1,p}:-y_i \le 0$?

Let $x = (x_1,\ldots,x_p) \in \mathbb R^p$. I'm solving the constrained optimization problem $$\begin{align*} \text{min} &\quad \sum_{i=1}^p (y_i-x_i)^2 \\ \text{s.t} &\quad \sum_{i=1}^p ...
2
votes
0answers
45 views

How to solve this maximization problem | KKT conditions

Maximize the objective function $f(x)=\sum_{i=1}^n (1-e^{-k_ix_i})$, where $(k_i >0) \in \mathbb{R}, (0\leq x_i \leq 1) \in \mathbb{R} $ . $\max\sum_{i=1}^n (1-e^{-k_ix_i})$ Subject to i) $\...
3
votes
0answers
36 views

Question about Lagrange multipliers, optimization problems and KKT-points.

I am having some difficulties with optimization problems with inequality constraints. In general the problems I am given will look something like this: $$\min f(x,y,z) \\ \text{s.t.} \space \space \...
0
votes
0answers
29 views

Question about KKT-conditions and inequality constraints.

I have two questions regarding the application of KKT conditions. Let's say I am given the following optimization problem: $$\min f(x,y,z) \\ \text{s.t.} \space h(x,y,z)=0 \\ g_1(x,y,z) \color{red}{\...
0
votes
0answers
39 views

First order Karush-Kuhn-Tucker optimality conditions: non-differentiable points in feasibility set

Background: Consider the optimization problem \begin{align}&\min_{\mathbf x\in \mathbb X} f(\mathbf x)\\ &\text{ subject to } g_i(\mathbf x)\leq 0, i=1,2\ldots,I,\end{align} where $f(\mathbf ...
2
votes
0answers
37 views

KKT-Conditions in a functional setting

Let $F:L^2([0,1])\rightarrow \mathbb{R}$ be a convex functional. Consider the minimization problem \begin{align} \underset{f(\cdot) \in L^2([0,1])}{\min} F(f)\,\,\text{ subject to } \|f(\cdot)...
2
votes
3answers
54 views

How to prove the harmonic-geometric mean inequality by solving an optimization?

The harmonic-geometric mean inequality is defined as follows $$ \frac{n}{\sum_{i=1}^n \frac{1}{x_i}} \leq (\Pi_{i=1}^{n}x_i)^{\frac{1}{n}}\tag{1} $$ Given the following linear programming problem $$ ...
1
vote
1answer
38 views

How to solve linear program $\min \langle c, x \rangle$ using Lagrangian?

Given the following linear programming problem $$ \min \langle c, x \rangle\\ \begin{align} \text{s.t} \,\,\,\,\,\,\,& \sum_{i=1}^{n}x_i=1\\ &x\geq0 \end{align} $$ where $x \in \mathbb{R}^n$. ...
1
vote
1answer
206 views

KKT multipliers and “active” and “inactive” constraints on the generalized Lagrangian $L$

The textbook Deep Learning by Goodfellow, Bengio, and Courville, says the following in a section on constrained optimization: The inequality constraints are particularly interesting. We say that a ...
0
votes
0answers
20 views

Identity of particular KKT points

$\renewcommand{\vec}{\mathbf}$ Consider a non-linear minimization problem $\mathcal{P}$ and suppose to have found a point $\vec{x}$ satisfying the first order KKT conditions. Suppose further that ...
1
vote
0answers
50 views

Constraint qualification in actual algorithm: are they ever checked?

I have a hard time to understand the interest of constraint qualification in actual algorithm for optimization. I know that there are many questions already about constraint qualification but they ...

1
2 3 4 5
7