The tag has no wiki summary.

learn more… | top users | synonyms (1)

0
votes
0answers
21 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
86 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
30 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
12 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
21 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
56 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
25 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
13 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
14 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
23 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
19 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
40 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
21 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
37 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
21 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) ...
1
vote
1answer
81 views

Is there any way to make the following function convex?

I need to find optimal lagrangian multiplier vectors for a quadratic programming problem subject to three quadratic equality constraints and several other linear inequality constraints. I would like ...
0
votes
0answers
53 views

Karush-Kuhn-Tucker conditions for non-linear optimalization

I have the following problem: solve the local conditions (KKT) and find ALL optimal solutions: $$\min f(x,y)$$ subject to $$g(x,y)\le 0$$ $$x\geq0, y\in\mathbb{R}$$ I have some questions to this ...
0
votes
2answers
29 views

optimization on two “max” function

Anyone knows how to use lagrange multiplier (or KKT conditions) to minimize an objective function such as $L(\beta,\beta_0)=\sum_{i=1}^n[a_i(1-y_if(x_i))_++b_i(1+y_if(x_i))_+$] where $a_i$, $b_i$ ...
0
votes
1answer
64 views

Solving an optimization problem with KKT-conditions

I've been studying about KKT-conditions and now I would like to test them in a generated example. My task is to solve the following problem: $$\text{minimize}:\;\;f(x,y)=z=x^2+y^2$$ ...
0
votes
0answers
33 views

KKT Sufficient condition when optimal solution is intuitively at the boundary

My optimization problem is: $\operatorname{arg\,max}_P \sqrt P$ subject to $P \le \upsilon_\tau$ where $P \in \mathbb{R}^+$ and $\upsilon_\tau \in \mathbb{R}^+$ Intuitively, because $\sqrt P$ is ...
1
vote
2answers
41 views

Kuhn-Tucker conditions

I can not find out when to use positive or negative Lagrange multipliers. Does it depend on if I am looking for MAX or MIN ? or maybe it depends on inequality I mean if it is bigger than zero or ...
0
votes
0answers
29 views

What is the relation between condition number of block of matrices.

I am working on a problem in which linear equations form a symmetric matrix consisting of 2 submatrices. Let that matrix is P. It looks like $$ P =\begin{bmatrix} A & B^T \\ ...
1
vote
1answer
125 views

Optimization over vector spaces. Generalized KKT.

I am looking for the extension of the theorem I found in the book by Luenberger called "Optimization by vector space methods." Here is the statement of that theorem from Luenberger: Generalized ...
1
vote
0answers
70 views

Utility maximization of n goods

I have a question that involves finding the optimal demand of n goods for a consumer. However, I haven't anything like this before and I'm not sure how to proceed. The consumer has a utility ...
2
votes
1answer
44 views

Would I use KKT conditions to solve this optimiztion problem?

my problem (P) is: $$(P) \space \space \text{min} \space x_1x_2$$ $$\text{s.t.} \space x_1-x_2-2 \leq 0$$ $$x_2 \leq 0$$ Prove that $x^* = (1,-1)$ is a strict local minimizer. ...
3
votes
0answers
53 views

Determining active constraints in KKT

Suppose there is a constrained optimization problem having inequality constraints. We can solve it using Karush-Kuhn-Tucker conditions. My question is how do we determine which constraints are active ...
2
votes
1answer
65 views

Formulation of convex constrained optimization problem (SVR)

I'm trying to figure out where I'm going wrong with my formulation of a certain problem, as all other instances of it were formulated slightly differently. The problem (SVR problem, If you're ...
1
vote
1answer
41 views

KKT for not convex problems

In my optimization course we learned something about KKT for not konvex problems: $$min \; f(x)$$ $$s.t. \; c(x)=0$$ $$d(x)\geq 0$$ $$f(x): \mathbb{R}^n\rightarrow \mathbb{R}$$ $$c(x): ...
0
votes
0answers
73 views

How does this optimization problem satisfy Karush-Kuhn-Tucker Conditions?

I am following Andrew Ng's course notes on Support Vector Machines at: http://cs229.stanford.edu/notes/cs229-notes3.pdf There is something in these notes which I do not understand. SVM's basic ...
1
vote
2answers
107 views

Local optimality of a KKT point.

Consider the problem \begin{equation} \min_x f(x)~~~{\rm s.t.}~~~ g_i(x)\leq 0,~~i=1,\dots,I, \end{equation} where $x$ is the optimization parameter vector, $f(x)$ is the objective function and ...
1
vote
1answer
56 views

Optimization using Karush-Kuhn-Tucker conditions

min $y^Tx$ subject to $\|x\|^2 \le 1$ where y is a nonzero vector in $\mathbb R^n$ I rearrange the constraints so that the RHS is $0$. New constraint: $x_1^2 + \cdots + x_n^2 - 1 = \|x\|^2 - 1 \le ...
1
vote
1answer
37 views

Linear independence of equality constraint gradients in constraint qualifications

I'm, trying to get an intuitive feel for the various constraint qualifications for KKT points. Most of them seem to rely on the linear independence of $\nabla g_i(x^*)$ where $g_i$ are the equality ...
2
votes
1answer
152 views

Is there a nice representation for KKT conditions for matrix constraints?

I have a convex programming problem: $\min \left\lVert J - R \right\rVert _F$ $J,R$ are matrices. $J$ is given for the problem. One of the constraints is: $R = KQ$ Here, $R,K,Q$ are matrices. $K$ ...
0
votes
0answers
65 views

Bordered Hessian for Kuhn-Tucker

With Lagragian problems, you are often asked to solve for a stationary point and use the bordered Hessian to determine whether it is a maximum or minimum. I have noticed with Karush-Kuhn-Tucker ...
1
vote
0answers
38 views

Explain KKT conditions without reference to duality.

Is it possible to explain (not derive) KKT necessary conditions without reference to the concept of Lagrangian duality?
1
vote
1answer
82 views

Optimization: KKT conditions statement

I'm currently following this material Optimization Theory: Chapter 2 Theory of Constrained Optimization And I can't understand why the following statement is true, between the equations (2.9) and ...
2
votes
0answers
96 views

Kuhn-Tucker constraint qualification, overdetermined?

I have a question about the constraint qualification for KKT. As I've seen the theorem stated if $G(x^*)=(g_1(x^*),\dots,g_n(x^*))$ are the binding constraints at a local max $x^*$ then the jacobian ...
1
vote
1answer
37 views

Quadratic Problen with 2 constraints

Could someone help me to solve the following: $\min x^Tx$ s.t. $x^T a=1$ $x^T b=0$ where $x$,$a$ and $b$ are $(N\times1)$ vectors and $1$ and $0$ scalars. Thank you!
0
votes
0answers
104 views

KKT Conditions and Convexity

min $x^2 -xy +y^2 -5x+6y$ subject to $1 \leq y$, $y^3 \leq 2x$, and $x \leq 8$ Write out the KKT conditions for this problem. Show that $(x,y) = (4,2)$ is a KKT point, and is therefore a global ...
0
votes
0answers
114 views

Lagrange dual method and KKT condition

Consider the following optimization problem \begin{equation}\notag \begin{split} \max & x^2+y^2 \\ \mathrm{s.t.} & x^2 \leq 1 \\ & 0\leq y\leq 2 \end{split} \end{equation} Obviously, the ...
0
votes
1answer
86 views

Lagrange condition and second-order conditions

Given a function to minimize or maximize with equality and/or inequality constraints, I can use Lagrange multiplier and/or KKT to solve such problems. So I understand how it works. My problem is ...
2
votes
1answer
251 views

Optimization Problem: Karush-Kuhn-Tucker Condition

I am working on the question displayed below. I know that the method of Lagrange Multipliers is used to find the solution for optimization problems constrained to one or more equalities and when our ...
0
votes
1answer
262 views

KKT maximization problem

$x^2y \rightarrow$ max, such that $x^2 + 4xy \leq 1, x \geq 0$ and $y \geq 0$. I think I need to use the KKT conditions here. I did however not yet succeed in solving it, so could someone ...
0
votes
1answer
185 views

KKT conditions on minimization problem

I am trying to get an explicit solution to the following problem with the help of KKT conditions. But I am stuck. The problem: $ min_x 1/2 ||y-x||^2_2 + \lambda||x||_1 $ This is what I have done ...
0
votes
1answer
68 views

Kuhn-Tucker conditions: why does $\lambda$ $\dfrac{\partial L}{\partial \lambda}=0$?

Satifying Kuhn-Tucker conditions. Given $\lambda$ is a row, and $\dfrac{\partial L}{\partial \lambda}$ is a column, why does $\lambda$ $\dfrac{\partial L}{\partial \lambda}=0$ ?
1
vote
1answer
31 views

Non linear programming please HELP

Hey guys, I never do that but just found out that I have an assignment due in a few hours..thought it was for later, any help/solutions for this one?
0
votes
1answer
211 views

KKT Conditions for Minmax Problem

Let $\mathbf{x}\in\mathbb{R}^n$ and $\mathbf{y}\in\mathbb{R}^m$. Now $$f\left(\mathbf{x}, \mathbf{y}\right):\mathbb{R}^n\times\mathbb{R}^m\rightarrow\mathbb{R}$$ is convex in $\mathbf{x}$ and concave ...
6
votes
1answer
755 views

Help me organize these concepts — KKT conditions and dual problem

This is a long question in which I explain my current understanding of certain ideas. If anyone is interested in reading this and would like to provide any commentary/feedback that may help me ...
4
votes
2answers
2k views

Simple explanation of lagrange multipliers with multiple constraints

I'm studying support vector machines and in the process I've bumped into lagrange multipliers with multiple constraints and Karush–Kuhn–Tucker conditions. I've been trying to study the subject, but ...
1
vote
2answers
130 views

Determine the points where $f$ is has a local minimum/maximum. Multivariable calculus question.

This is not homework, but it is in my book and I find it hard to solve: Determine the points where $f$ is has a local minimum/maximum. Determine if it strong/weak and absolute/relative and ...