The tag has no usage guidance.

learn more… | top users | synonyms (1)

1
vote
1answer
25 views

Quadratic programing problem and MATLAB

I have a little problem with quadratic programing problem: ${\bf v}^T \Sigma {\bf v} \rightarrow min $, and constrains are $ {\bf v}^T \mu = \mu_*, {\bf v}^T {\bf 1 }= 1, 0 \leq {\bf v}. $ Where ...
0
votes
0answers
20 views

Minimize $\|\mathbf{x-y}\|^2 $ subject to $x \in $ set $S=\{\mathbf{x} \in \mathbb{R}^n \;\;\;\mid \;\;\; \|\mathbf{x-x_c}\|^2\leq r^2 \}$

We are given the set $S=\{\mathbf{x} \in \mathbb{R}^n \;\;\;\mid \;\;\; \|\mathbf{x-x_c}\|^2\leq r^2 \}$ and a point $\mathbf{y} \in \mathbb{R}^n$. Our goal is to find point $\mathbf{\hat{x}}$ ...
0
votes
0answers
17 views

Connection between method of Lagrange multipliers and KKT conditions?

I understand that in general, the KKT conditions are not sufficient for optimality. However, if the primal problem is a convex optimization problem, then the KKT conditions are sufficient for ...
0
votes
0answers
19 views

KKT conditions for nonlinear problem

I need to state the KKT conditions for the following problem: Minimise $x_1^2 + 2x_2^2$ subject to $(x_1-1)^2 + x_2^2 \le 1$ and $x_2 = 1$. I have that these conditions are: $f(x^*) \le 0$ ...
0
votes
1answer
16 views

Can lagrange multiplier(Kuhn tucker multipliers?) change in corner solution?

If we want to maximize $f(x)$ subject to two constraints, one which says that $x< c$ $c>0$, and another that says that $x\geq 0 $. Assume there are no problems with either $x=0, x>0$ or $\mu ...
1
vote
0answers
32 views

KKT conditions for a convex optimization (optimal crowdsourcing with budget constraint)

I am having some troubles deriving the optimal solution of the following convex optimization problem, $w_j$, $c_{ij}$, and $B$ are fixed and non negative. \begin{align} & ...
0
votes
2answers
23 views

Kuhn-Tucker's Conditions for optimization problem with non linear inequalities constraints

My problem is to minimize the function \begin{align*} f(x,y,z,t)=& 3 t \left(2 x^2+4 x z\right) \left(2 t x y+t x z-2 t y^2-2 x z+4 y z\right) \\ &+\left(-t x^2+4 t x y+4 t y z+4 x z-8 y ...
0
votes
0answers
28 views

KKT conditions (equations) for Generalized Assignment Problem or Binary integer programming problem

I have this formulated Generalized Assignment Problem (GAP) or it can also be considered as Binary integer programming problem. Solving this problem can be achieved through Branch and Bound Technique. ...
0
votes
0answers
21 views

Optimization by KKT-method

I need to solve the following problem by KKT method. $$ \text{min} \ \ 2xy + 2yz + 2zx \\ \text{subject to} \ x^2 + y^2 ≤ 2, \ 2x + 2y + z = 0 $$ I have gotten as far as setting up the system of ...
3
votes
0answers
33 views

How to use the Karush–Kuhn–Tucker conditions?

From what I read, the Karush-Kuhn-Tucker conditions are a generalization of the Lagrange Multiplier Method. For the Lagrange Multiplier Method I have been able to find a serie of steps I must do to ...
0
votes
0answers
18 views

General KKT problem

Consider the following problem, where $a_j,b$ and $c_j$ are positive constants: Minimize 􏰀$\sum_{j=1}^n \frac{c_j}{x_j}$, subject to $\sum_{j=1}^n a_j x_j = b, x_j ≥ 0$ for $j= 1,...,n$. Write ...
0
votes
1answer
29 views

Linear programming with kernel

Can anyone please help me with solving the constrained minimization problem below? $$\mathbf{x}^* = \arg\min \sum_{i=1}^m q_i e^{-2x_i} $$ $$s.t.$$ $$\sum_{i=1}^m x_i = c$$ $$x_i\geq0, i = ...
0
votes
0answers
12 views

Kuhn Tucker condition sufficient for global optimum

LL is the variable and s,rs,r are parameters. The question asks to solve maxL≥0rf(L)−wLmaxL≥0rf(L)−wL where f(L)f(L) is twice continuously differentiable, strictly increasing and strictly concave. ...
1
vote
0answers
32 views

Kuhn Tucker condition is sufficient for a global optimum?

$L$ is the variable and $s,r$ are parameters. The question asks to solve $max_{L\geq0}rf(L)-wL$ where $f(L)$ is twice continuously differentiable, strictly increasing and strictly concave. Then how ...
2
votes
1answer
36 views

How to solve this KKT problem?

Given an optimization as follows: \begin{align} \text{minimize}\quad &c^Tx \\ \text{subject to}\quad &Ax = 0 \\ & \|x\|_2^2 \leq 1 \end{align} where $A \in \Re^{m\times n}$ is of ...
2
votes
1answer
37 views

BigPicture Lagrangian, KKT, Duality

I have a question regarding the big-picture in the field: Lagrangian, Duality, KKT, sufficient, necessary conditions. 1) Duality is a concept: “The solution to the dual problem provides a lower ...
2
votes
0answers
24 views

What is the logic behind the given optimization problem?

I am following a book which has a part on numerical optimization techniques. In order to elaborate Karush-Kuhn-Tucker theorem, they gave the following example: When the unconstrained solution $x=A^+ ...
0
votes
0answers
26 views

KKT Conditions for Euclidean Distances

Suppose that we have an undirected and edge weighted graph $G = (V,E)$. The weight $w_{ij}$ of an edge $\{i,j\} \in E$ determines the Euclidean distance between the vertices $i$ and $j$ s.t. $i,j \in ...
0
votes
0answers
13 views

Validity of nonlinear optimization with exponential type inequality constraint as KKT / Lagrange multipliers?

Given positive coefficients $h_i, \beta_i$ and $k$ we have the minimization problem $$\displaystyle \min\sum_{i = 1}^n h_{i}s_i\\ \text{subject to} \displaystyle\sum_{i = 1}^n \alpha^{s_i}\beta_i \leq ...
2
votes
2answers
46 views

Minimize $x^2+y^2$, subject to… (optimal points, KKT conditions, dual theories)

I am new to this. I am self learning to get ahead of my next years course and came across this question. I thought it would be a good question to look at due to it touching an many different aspects ...
0
votes
0answers
34 views

dual feasibility of Kuhn-Tucker condition?

minimize $f(x)$ subject to \begin{align} f_i(x) & \le 0, \quad i \in \left\{ 1,\ldots,m \right\} \\ h_i(x) & = 0, \quad i \in \left\{ 1,\ldots,p \right\} \end{align} Then the Lagrange ...
2
votes
1answer
33 views

Some True or False questions on Nonlinear Optimisation (Exam Preparation)

I am currently preparing for a Nonlinear Optimisation exam and am working through some old question papers and came across these True or False questions: When minimizing a convex function over ...
0
votes
0answers
29 views

Solve system with complex fractional equations

I need to maximize a function with equality constraint, so I made the Lagrangian function and I found the partial derivatives, which are these: $$ \frac{|h_1|^2}{\sigma^2(\frac{x ...
0
votes
0answers
23 views

KKT condition and linear program

Since all linear program all convex, and the Slater's condition always hold for linear programs. Is it always possible to solve the linear programs with KKT conditions? because it will convert the ...
0
votes
0answers
14 views

Maximize using KKT conditions.

Let $T\ge1$ be some finite integer. Maximize $\sum_{t=1}^{T} (\frac{1}{2})^t \sqrt(x_t)$ Subject to $\sum_{t=1}^{T} x_t \le 1 $ and $ x_t \ge 0, t = 1,...,T$. I believe that constraints $ x_t ...
1
vote
1answer
26 views

Karush-Kuhn-Tucker NLP

Consider the nonlinear program Minimize: \begin{align}f(x,y) = \frac{1}{2}x^2 - 10xy + 10y^2\end{align} Subject to: \begin{align}2x +y^2 &\le 5 \implies g_1(x,y)=2x + y^2 -5 \le0 \\ ...
2
votes
1answer
51 views

KKT condition - minimization problem

$y^2-8 \ln(x+4)\rightarrow$ min, such that $-x^2 -y^2+9 \geq 0, y \geq 0$ *I have to find all possible optimal points.* Lagragian function is: $L(x,y,γ_1,γ_2) = y^2 - ...
0
votes
1answer
46 views

optimisation with inequality constraints

I'm struggling with this question: $ \max \{ \ln(y) - (x-1)^2 \} $ s.t. $x + y \leq t$ and $y > 0$ I'm trying to use the Lagrange/Kuhn-Tucker method but don't know how to progress after getting ...
1
vote
1answer
43 views

applying KKT to non-convex optimization

I am trying to find a solution for following \begin{eqnarray} \text{minimize }~~ -\sum_{i=1}^K \frac{1}{a_i+b_i2^{(-2x_i)}} \\ \text{s.t.} ~~~ \sum_{i=1}^Kx_i=C \end{eqnarray} where ...
0
votes
0answers
28 views

Solving the Lagrange dual problem

If we have a convex constraint problem $$ \text{min}\quad f_0(x)\\ f_i(x)\le0\\ h_i(x)=0, $$ where $f_1,\ldots,f_n$ are convex and $h_1,\ldots,h_r$ are affine. Assuming Slater's conditions we know ...
3
votes
1answer
63 views

KKT conditions for a maximization problem

I have an optimization problem \begin{equation} \mathbf{w}^*= \text{argmax} ...
0
votes
0answers
40 views

Sufficiency of KKT problem

I have a continuous, twice differentiable function $f:\mathbb{R}^2\rightarrow \mathbb{R}$. My objective is to maximise the function $f$ subject to quasiconcave function $g_i(x,y)\le 0,\, i\in\{1,2\}\, ...
3
votes
1answer
66 views

Kuhn Tucker conditions, and the sign of the Lagrangian multiplier

I was under the impression that under the Kuhn-Tucker conditions for a constrained optimisation, with inequality constraints the multipliers must follow a non-negativity condition. i.e. $$\lambda ...
1
vote
0answers
12 views

Regularity for the Feasible region

I have this problem $min -x +y $ $x-y^2\leq0 $ $\frac {(x-1)^2}{4} +y^2 \leq 1$ $y \geq -1/2$ Say if the feasible region is regular or not, analitically. I know that to check the KKT ...
0
votes
1answer
51 views

Finding KKT conditions for nonlinear optimization problem.

I have an optimization like below: $\text{ minimize } \sum_k - \log_2 x_k $ $\text{subject to: } x_k \leq q , k =1,2, \cdots, N .$ I can form the Lagrange of the problem as below: $L(x, ...
0
votes
0answers
33 views

KKT system with rank-deficient constraints

I have an optimization problem of the following form: $$ \begin{aligned} \operatorname*{minimize}_x & \quad \frac{1}{2}||x - a||^2 \\ \operatorname{subject~to} & \quad ...
4
votes
1answer
97 views

Is this a known result?

I heard the following result and I am wondering if anyone can verify its correctness and also provide a source to cite. If the Lagrangian $L(x,\lambda)$ is convex in $x$ at the optimal Lagrange ...
0
votes
0answers
34 views

optimization of a function with inequality constraint

I have a function to be maximized subject to constraints. I can write the primal Lagrange function as the following: (objective function WITH two constraints in the last two terms) $$L_P = ...
1
vote
0answers
19 views

projection KKT optimal condition

Using the KKT optimality condition find the orthogonal projection of an arbitrary point $c \in$ to the closed convex set $C$ (non empty) defined by: (a) $C=\{x \in R^n : Ax\leq a\}$ where $A\in ...
1
vote
0answers
34 views

KKT Optimality Conditions

I am working with the following optimization problem: $$ \min_{\Delta} \boldsymbol{\theta}^T\boldsymbol{\Delta} \\ \text{Such that:} ~~~0 \leq \mu_i + \Delta_i \leq 1 ~~\forall~~ i\in\{1,2,\ldots, n\} ...
1
vote
2answers
95 views

Do we really need the constraint qualification?

I can't keep my fingers off Nocedal/Wright's Numerical Optimization (1999,1E) and I apologize. But maybe YOU can shed light on the question: Why does a point $x \in \mathbb{R}^n$ need to satisfy the ...
0
votes
1answer
36 views

Eliminate cases before calculting all KKT conditions

I have the following non linear programming to solve: $$\left\{\begin{matrix} \min & (x-3)^2 + (y-2)^2 \\ s.t. & x^2 +y^2 \leq 5 \\ & x+y\leq 3 \\ & x \geq 0\\ & y\geq 0 ...
0
votes
0answers
14 views

For which values of $c_1, c_2$ and $c_3$ is (1, 2, -2) a local minimum

Consider the problem $$\left\{\begin{matrix} \min & x^2 -2xy + 2xz +y^2 + 4yz + z^2 + c_1x + c_2y + c_3z \\ s.t & g(x,y,z)=-x^2 -4xy - 4xz -2y^2 -4yz - 2z^2 + x -y+z+4 =0 \\ \; & ...
0
votes
1answer
20 views

Constrained Optimization: $\min x_1$

Consider the problem $$\left\{\begin{matrix}\min & x_1 \\ s.t & x_2 \geq 0 \\ \; & x_2 \leq x_1^3 \end{matrix}\right.$$ It is asked to find the minimum and show why this does not satisfy ...
1
vote
0answers
31 views

Is there only one set of KKT conditions for a given optimization problem?

Consider an optimization problem $$ \begin{align} \max_{x}&\quad f(x)\\ \nonumber \text{subject to } \quad & g_i(x) \le0,\,i=1,\ldots,m\\ \quad & h_j(x)=0,\,j=1,\ldots,l\\ \end{align} $$ ...
0
votes
1answer
24 views

Nocedal/Wright: Numerical Optimization, Lemma 12.3.(ii)

In the above given monograph (1999, 1E) the following parametrized system of equations $R:\mathbb{R}^n \times \mathbb{R} \rightarrow \mathbb{R}^n$ is introduced: $$ R(z,t) := \left[ \begin{array}{c} ...
0
votes
1answer
78 views

KKT conditions for a convex optimization problem with a L1-penalty and box constraints

I am having some trouble deriving / understanding optimality conditions for a convex optimization problem of the form: $$\begin{align} \min_{x\in\mathbb{R}^d}~ & f(x) + C.\|x\|_1 &\\ &x_i ...
0
votes
0answers
51 views

How to obtain the optimal lagrange multiplier vectors if the globally optimal solution for a nonconvex QCQP is found.?

I am using a blackbox solver to solve the following nonconvex QCQP to global optimality. $$ \min_x x^TQ_0x + c^T x \\ s.t. \quad x^TQ_1x+c_1^Tx=b_1 \\ Ax=b \\ l\leq x\leq u $$ where $Q_0$ is ...
0
votes
1answer
56 views

Why is one of the KKT conditions the same as one of the constraints?

I'm working through an SVM tutorial (from Andrew Ng Stanford course notes). In the brief coverage of Lagrange duality. The primal optimization problem is stated $$ \min_{w} \theta_{\mathcal{P}}(w) = ...
0
votes
0answers
33 views

Justifying the “Dual feasibility”, one of the Karush-Kuhn-Tucker conditions

I am having difficulty of interpreting the KKT conditions in a general setting where we have $M$ equality and $N$ inequality constraints defined as: Minimize $f(x)$ subject to $g_i(x) \leq 0 , h_j(x) ...