# Tagged Questions

22 views

### dual feasibility question in augmented Lagrangians and the method of multipliers

I am going through Boyd's tutorial on ADMM. My question is basically from Sec 2.3. Consider the optimization problem $$\min.~f(x)~~~~\text{s.t.}~~~Ax = b.$$ Then the Lagrangian is ...
35 views

### How to obtain primal problem from Lagrangian?

If you're trying to optimize $\min_x f_0(x)$ subject to $f_i(x) \leq 0$ then the Lagrangian would be $$L(x, \lambda) = f_0(x) + \sum_i \lambda_i f_i(x)$$ The dual problem is $\max_\lambda g(y)$ ...
83 views

### The convex conjugate of a quadratic form with positive semi definite matrix

I want to find the convex conjugate (Legendre transform) of a quadratic for $1/2x^{t}Qx$ when $Q$ is positive semi-definite. If Q is non-singular, the solution is easy - the gradient is $y-Qx=0$ so ...
96 views

### Lagrange dual of a sum of convex functions

Given a set of convex functions $f_i(x)$ and convex sets $X_i$ in $\mathbb R^n$ I need to find the Lagrange dual problem for the problem $\min \sum{f_i(x)} , x \in X_i \forall i$. There is of course ...
61 views

### Lagrangian dual for the sum of norms

I would like some help in deriving the Lagrangian dual function of a sum-of-norms minimization problem : $\sum{||A_{i}x-b_{i}||}$ when $A_{i}$ are matrices, and $b_{i},x$ vectors. I understand I can ...
164 views

### Recovering the solution of optimization problem from the dual problem

In the context of (most of the times convex) optimization problems - I understand that I can build a Lagrange dual problem and assuming I know there is strong duality (no gap) I can find the optimum ...
87 views

### how to construct the Lagrangian dual problem?

The primal optimization problem is, \begin{align*}\min_x\;&f_0(x)\\ \text{s.t.}\;&f_i(x)\le0\\ &h_j(x)=0\end{align*}, to construct the dual problem, I form the Lagrangian, ...
71 views

### Dual of this primal optimization problem?

How would one find the dual of the following problem? $min_x 1/2 ||y-x||_2^2 + \lambda||x||_1$ Can someone please explain to me how to do this since there are no specific constraints?
273 views

### Dual to the dual norm is the original norm (?)

I have the following questions about dual norms : How do you prove that the dual of the dual norm is in fact the original norm? This is what I have so far: If I have $\|y\|_*$ as the norm dual of ...
383 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 ...
19 views

### Confusion related to how the dual of a problem is derived

I have this confusion about how the dual was derived of an optimization problem Here is the primal problem It's dual is like this I didn't get how the $\lambda^{max}$ appeared there. I mean ...
49 views

### Duality in Chebychev approximation

I got messed up with this problem and can't find any clue to solve this. Hope some one here can help me. Let $A$ be an $m \times n$ matrix an let $b$ be a vector in $R^{m}$. We consider the ...
161 views

### What is the dual of this optimization problem?

Consider the points $x_1, \ldots, x_N \in \mathbb{R}^n$, and a (locally bounded, convex) function $f: \mathbb{R}^n \rightarrow \mathbb{R}$. I am looking for the dual of the following optimization ...
159 views

### Are these convex optimization problems equivalent?

Consider the optimization problem $$\mathcal{P}_1: \qquad \min_{x \in \mathbb{R}^n} c^\top x \quad \text{sub. to } \ g(x,y_i) \leq 0 \ \ \forall i = 1,2,...,M$$ where $c \in \mathbb{R}^n$, and ...
288 views

### Dual cone of a L1 norm cone?

I am listening to convex optimization lectures and I hear that dual cone of a $L1$ norm cone is a $L-\infty$ norm cone. Can anybody please explain how? I understand that every point in the dual cone ...
58 views

### Closed form for Lagrange dual

Can Lagrange dual always be computed in closed form? Can you give me a simple example where the dual is not analytically computable?
When is $$\min_X \max_Y f(X,Y)$$ globally solvable? (i.e. we can find global solution for the optimization problem?) I am not looking for reformulations. Is it only when ...
### Is it possible to solve the argument maximization problem $\arg\max_x \langle x,l\rangle - f_1(x) - f_2(x)$ via convex duality?
I am attemping to solve the argument maximization problem $$\arg\sup_x \{\langle x,l\rangle - f_1(x) - f_2(x)\}\qquad\qquad\qquad\qquad (1)$$ where the functions $f_1$ and $f_2$ are concave but ...