The tag has no wiki summary.

learn more… | top users | synonyms (1)

0
votes
0answers
14 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
53 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
25 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
25 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
29 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
24 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
33 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
24 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
107 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
69 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
41 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. ...
2
votes
0answers
34 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
63 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
29 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
66 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
88 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
43 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 ...
0
votes
0answers
30 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
114 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
61 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
36 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?
0
votes
1answer
59 views

Optimization: KKT conditions statement

I'm currently following this material http://www.math.uh.edu/~rohop/fall_06/Chapter2.pdf And I can't understand why the following statement is true, between the equations (2.9) and (2.10): "The ...
1
vote
0answers
76 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
36 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
24 views

Threshold in a maximisation problem (with KKT conditions)

I'm looking to maximise with respect to $x_i$ $$L = \sum_{i= 1}^n y_i \frac {x_i^{1 - \epsilon}}{1 - \epsilon}$$ subject to $ \sum_{i= 1}^n x_i = B $ and $x_i \ge 0$ for all $i$, where $y_i$, $B$ ...
0
votes
0answers
91 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
105 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
82 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
240 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
227 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
181 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
63 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
191 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
722 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
128 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 ...
0
votes
1answer
70 views

KKT formulation

How to reformulate the following problem $$min \frac{1}{2} (x_1-a_1)^2+ \frac{1}{2} (x_2-a_2)^2$$ $$s.t. \mathbf{1}^Tx=1$$ $$ ||x||_2\leq2$$ as the following system of KKT conditions: $$(1 + ...
1
vote
1answer
205 views

Check Kuhn-Tucker conditions

How to check if $(0,1)$ point is the solution of this optimization problem using Kuhn-Tucker Theorem. Find the min of $e^{x_1-x_2}-x_1-x_2$ where $x_1+x_2\le1,\ x_1\ge 0,\ x_2\ge0$ I am thinking ...
1
vote
0answers
81 views

KKT: Explain visually the optimality condition $F_0\cap G_0\cap H_0=\emptyset$

I am trying to understand visually what this condition actually mean. It is the optimality condition in KKT. It means something like that constraint -set, objective -set and hyperplane -set has no ...
1
vote
1answer
949 views

Linear least squares with non-negativity constraint

I am interested in the linear least squares problem: $$\min_x \|Ax-b\|^2$$ Without constraint, the problem can be directly solved. With an additional linear equality constraint, the problem can be ...
1
vote
2answers
264 views

How can I infer a result using primal feasibility, dual feasibility, and complementary slackness?

I am trying to find the minimum of $-x_1$ with restrictions $\bar g\leq\bar 0$ so that $$\bar g=\begin{pmatrix} (x_1+2)^2+(x_2-4)^2-20\\ (x_1+2)^2+x_2^2-20\\ -x_1\end{pmatrix}\leq ...
1
vote
2answers
213 views

What does the statement “Optimality condition for convex problem” mean? KKT or other condition?

I am stuck to the problem 4 here, course Mat-2.3139, the due day was yesterday. The hint is "Optimality-condition for a convex-problem". I have asked this now from 3 assistants and everyone with ...