# Tag Info

0

Let $A$ be the matrix with columns $a_i$, $\lambda$ is a vectors of $\lambda_i$, $\alpha$, and so on. The condition $$\mu^T \cdot (b - \sum_j \alpha_j a_j I_{\mu^T \cdot a_j < 0} ) \geq 0$$ is equivalent to the following matrix inequality: $$\left( \begin{array}{c} \mu \\ z \\ \end{array} \right) ^T\cdot \left( \begin{array}{cc} A & 0 \\ ... 0 Pseudo Code for Steepest Descent using Armijo's Rule: Given x_k, maxiter, other conditions Compute \nabla F(x_k) objold \leftarrow 0 Define \sigma \ \& \beta [between (0,1)] while (iter < maxiter) && (other conditions) flag \leftarrow 0 s_k \leftarrow 1 while flag \neq 1 ... 0 Because those are the individual constraints that are imposed in the Lagrangian definition. Therefore, they are individually required to be equal to zero. If the sum of them is required to be zero only, then clearly this doesnt imply that the constraints are satisfied. 0 You are minizing the sum of a smooth function F, and a non-smooth function i_D (the indicator function of the domain D) for you can compute the proximal operator, which in fact equals the projection operator onto D (D is an ellipsoid, so this is an easy business). Projected gradient methods like ISTA, FISTA, etc. are your friends here. You may ... 0 Given \alpha \ge 0 (lookup the definition of mixed norms), you have$$\alpha\|u\|_{TV} = \alpha \|Du\|_{2,1} = \|\alpha D u \|_{2,1}.$$So, to smooth g := \alpha \|.\|_{TV}, simply replace the linear operator D by the scaled version \alpha D. In particular, you don't need convex conjugates, etc. 1 what about considering using gradient projection method, after each step, project your current result onto your constraint set. 0 I have to methods for proving the boundedness. The first one uses a contradiction, as proposed by the authors. However, the second method seems to be more elegant and even yields the convergence of the coefficients. Method 1: Assume \{\alpha_k\} is not bounded. Then,$$\frac{\sum_{i=1}^m \alpha_{ki} \, a_i}{\max_{i} \alpha_{ki}} = \sum_{i=1}^m ...

2

One of your conditions is $(x-2)^2+(y-3)^2\le 4$. This leaves two cases: either $(x-2)^2+(y-3)^2=4$ or $(x-2)^2+(y-3)^2<4$. (That is, the point $(x,y)$ is either in the interior or at the boundary of the disc. Treat these separately.) In the first case you have two conditions for two variables. Therefore there is no need to use Lagrange's method. ...

0

Solution By enforcing $\sum_i x_i = 1$ it follows that $\sum_i \frac{a_i}{\lambda} = 1$ which leads to $\lambda = \sum_i a_i$ and $x_i = \frac{a_i}{\sum_j a_j}$

2

Actually, the Lagrange multiplier method is used to find critical points, so you can use the same sign for both. The distinction between minima, maxima and saddle points is given by the Hessian matrix.

0

There are several problems with your proof: You do not prove the assertion. Indeed, if your proof would be correct, you would have shown that $f$ has a at least a minimizer. I do not get the point of your last sentence. Indeed, $\mu$ is always unique, by definition, independently of the properties of $f$. Your proof is wrong: Indeed, your minimizing ...

2

Recall the definition of strict convexity: $$f(\lambda x + (1-\lambda)y) < \lambda f(x) + (1-\lambda) f(y) \quad \forall x,y\in\mathop{\textrm{dom}}(f), ~ x\neq y, ~\lambda\in(0,1)$$ The strictly convex functions $f(x)=e^x$ and $f(x)=x^2$ have exactly zero and one minimizers, respectively. Now suppose we claim that a strictly convex function $f$ has two ...

1

Since $\bar{z}$ is fixed, the above problem is minimizing a quadratic function $f$ with a single affine constraint. In general, the optimality condition tells us that the gradient of $f$ at the optimal solution is orthogonal to the null space of the affine constraint (or equivalent,lies in the image of the dual of that affine map). Now the gradient of the ...

1

It's not clear to me under what principle we could have expected "multiplying $A^T$ on both sides" to lead to a proper answer. For one thing, since $m<n$, $A^TA$ is not invertible. (As it is, the correct answer assumes that $A$ has full row rank so that $AA^T$ is invertible; this is of course not always true.) The right way to do this is to use a ...

1

You need the hypothesis that $A$ has rank $m$ so that $AA^T$ is invertible. Since $x^*=A^T(AA^T)^{-1}b$ we have $Ax^*=b$, so for every $x$ such that $Ax=b$ we have $x-x^*\in {\rm ker}A$ and clearly $x^*\in {\rm Im}A^T$, but it is well-known that ${\rm Im}A^T=({\rm ker}A)^\bot$. Thus, by Pythagoras theorem $$\Vert x\Vert^2=\Vert x-x^*\Vert^2+\Vert ... 0 It's quite obvious this is not convex. After all, it is undefined whenever \langle b, x \rangle = 0. So its domain is the complement of that hyperplane, and therefore a non-convex set. All convex functions have convex domains, so this is definitely non-convex. I really can't see a way to define the domain of this function in a sensible way that preserves ... 1 In fact, the convex hull \mathrm{conv}\{x_1,\ldots,x_k\} := \{\sum_{1 \le j \le k}t_kx_k | t \in \mathbb{R}^n, t \ge 0, \sum_{1 \le j \le n}t_j = 1\} is compact (in the usual euclidean topology)! Step 1: The simplex \Delta_n := \{t \in \mathbb{R}^k | t \ge 0, \sum_{1 \le j \le k}t_j = 1\} is compact. Indeed it closed, being the intersection of closed ... 0 Here's an example on \mathbb R: f(x) = x^2-\cos x. A way to make lots of examples: Let f be any positive bounded continuous function on [0,\infty). For x\ge 0, set$$g(x) =\int_0^x \int_0^t f(s)\, ds\,dt.$$Extend g to an even function on all of \mathbb R. Then g satisfies the requirements. 4 Why are these models equivalent? What does it mean for two models to be equivalent? Here's my answer: two models are "equivalent" if the solution to one model readily leads to the solution of the other, and vice versa. Suppose you have a solution to (1) above: that is, you have an (a,b) pair that satisfies$$a^Tx_i+b>0 ~~ \forall i=1,\dots, M, \quad ...

3

Just compute the second derivative, we have, by the chain rule $$\def\norm#1{\left|#1\right|} Df(x)h = \frac 1{(1 + \norm{x}^2)^{1/2}} \cdot \def\<#1>{\left<#1\right>}\<x, h>$$ Hence, $$D^2f(x)[h,k] = -\frac 1{(1 + \norm x^2)^{3/2}}\<x,h>\<x,k> + \frac{1}{(1 + \norm x^2)^{1/2}}\<h,k>$$ So, we have \begin{align*} D^2 ...

1

In general, there is a decomposition of square matrices into a symmetric part and anti-symmetric part: $$A=M+N$$ where $M$ is symmetric and $N$ is anti-symmetric. This is a very general result, and this decomposition is in fact a Hilbert space decomposition so that $M$ is the "closest" symmetric matrix to $A$. It is easy to derive the forms of $M,N$: ...

1

The right way to do this is not to treat the symmetry of $X$ as a constraint. Rather, it is to make the space of symmetric matrices the domain of the function. So for example, treat this not as a function of $X\in\mathbb{R}^{n\times n}$, but rather as a function of $X\in\mathcal{S}^n$, the set of $n\times n$ symmetric matrices. The most important ...

0

What makes the model interesting is that the variance is proportional to the data $x_i$. This implies that $x_i\geq 0$. I am going to start by assuming that $x_i>0$. But once we've found the answer in that case I'll discuss the situation when that assumption does not hold; i.e., that $x_i=0$ for at least one $i$. Let us define the following quantities: ...

0

This is entirely possible, and happens all the time. In order to guarantee that the subproblem solution obtained at the dual optimum corresponds to the true primal optimum, you need the dual to be differentiable which is equivalent to the primal problem being strictly convex. In the context of linear programming, this is called the "problem of ...

0

Every $p_{ij}$ is a vector $\in \mathbb{R}^2$ that contains the discrete gradient at pixel $(i,j)$. The projection operation (the proximal operator) is decomposable at every pixel because $$p^{k+1} = \arg \min_{p \in P} \Vert p^k - p \Vert^2 = \arg \min_{ \Vert p_{ij} \Vert \le 1} \sum_{ij} \Vert p_{ij}^k - p_{ij} \Vert^2$$ as the $\ell_\infty$ norm ...

1

I'll just write down the solution and hope you catch a few tricks from the manipulations :) i) Define $g = f + \langle c, .\rangle$. For any $x \in X$, we habe \begin{split} g^*(x) &:= \sup_{z \in X}\langle x, z\rangle - g(z) = \sup_{z \in X}\langle x, z\rangle - \langle c, z\rangle - f(z) = \sup_{z \in X}\langle x - c, z \rangle - f(z) ...

0

Try to plot $V(x)$ as function of $u$. Then you'll realize that minimum is attained at some $x_k$. So, $$\min_{u\in\mathbb{R}} V(x) =\min_{k=1,\ldots,n}V(x_k) =\min_{k=1,\ldots,n}\sum_{i=1}^n w_i|x_i-x_k|$$

2

I'll just write down the solution and hope that you catch some tricks from the manipulations :) Define $\mathbb{R}^n_+ := \{x \in \mathbb{R}^n | x \ge 0\}$ (the nonnegative $n$th orthant), and $\mathbb{R}^n_- := \{x \in \mathbb{R}^n | x \le 0\}$ (the nonpositive $n$th orthant). From these definitions, it's clear that $-\mathbb{R}^n_+ = \mathbb{R}^n_-$. Now, ...

0

For this type of problem you typically want to choose some element you know to exist on the left hand side and algebraically show it must also be contained on the right hand side. For this problem specifically we want to chose $v\in\partial^{\infty}(\lambda f)(\bar{x})$ and conclude that $v\in\lambda\partial^{\infty}f(\bar{x}).$ This can be done entirely ...

3

The function $f$ can be written as $\max\{1, x^2\}$. Minimising a maximum of two functions is equivalent to minimising an upper bound $z$ to both functions. The modified problem reads: Minimise $g(x)+z$ subject to the additional constraints $$z\ge 1,\quad z\ge x^2.$$

0

This statement is false. Let $b\in \mathbb R^n$ be nonzero and let $f$ be the indicator function of the set $S=\{b\}$. Then $f^*(z) = \langle z, b\rangle$. So $f^*$ is unbounded below, but $f(b)$ is finite. (I'm using the term "indicator function" in the convex analysis sense.)

1

Here is a pdf of a very good clear book on an introductory level: Operations Research by Wayne L. Winston. Another, more advanced source, would be Chvatal's Linear Programming (Amazon link)

2

There are two relevant geometric observations. Consider the following drawing of a quadrilateral with $\theta_1, \theta_2 \geq \frac{\pi}{2}$: Then $|w_2 - w_1| \leq |z_2 - z_1|$. In order to prove it algebraically, we have $$\left< w_2 - w_1, w_2 - w_1 \right> = \left< (z_1 - w_1) + (z_2 - z_1) + (w_2 - z_2), w_2 - w_1 \right> = \\ ... 0 This is a very good question that I can sort of answer, but not in a 100% satisfactory way. Since a problem with a piece-wise affine objective function can always be expressed as an equivalent linear program, the dual of this program will fulfill the criteria. However, this type of duality doesn't have any sort of injectivity - since a nonlinear C^1 ... 0 Ok, with Michael Grant's hint, the solution should be the following: Let A\in \mathbb{R^{n\times n}} be the upper triangular matrix consisting of 1's. Then K=A\cdot \mathbb{R^{n}_+}. A is invertiable, and the following proposition can be easily shown:$$(MX)^* = M^{-T}X^*\hspace{1mm} where \hspace{1mm} M\in \mathbb{R^{n\times n}} \hspace{1mm} ...

1

Assume that $\mathcal{X}$ is a vector space. Your condition easily implies $\nabla f(x^*) = 0$ (in $\mathcal{X}^*$). Indeed, for any $x \in \mathcal{X}$, you have $x + x^* \in \mathcal{X}$. Hence, $$\langle \nabla f(x^*), x\rangle = \langle \nabla f(x^*), (x + x^*) - x^* \rangle \ge 0.$$ Similarly, you can show $$\langle \nabla f(x^*), -x\rangle \ge 0.$$ ...

1

You can do it from "first principles". First note that because $f$ and $g$ are convex lcm, $f = f^{**}$ and $g = g^{**}$. Now, for any $x \in X$, we have \begin{split} f(x) = f^{**}(x) := \sup_{z \in Y}\langle x, z \rangle - f^*(z) \ge \sup_{z \in \text{Im }A^*}\langle x, z \rangle - f^*(z) &= \sup_{y \in Y}\langle x, A^*y\rangle - ...

1

It depends on whether $v\ge0$ or $v<0$. First, note $$f^*(v)=\sup_x \langle x,v\rangle -f(x)=\sup_{x>0} \langle x,v\rangle +\ln(x)$$ as $\langle x,v\rangle -f(x)$ equals $-\infty$ when $x\leq 0$. Second, indeed, when $v\ge 0$, $\ln(-1/v)$ is not defined. But in that case, note, for $x>0$, $$\frac{d}{dx}[\langle x,v\rangle+\ln ... 1 Kuifje is on the right track, but it's not quite there. It's true that |x|+|y|=1 can be expressed as |x|+|y|\leq 1 and |x|+|y|\geq 1. The first of these is convex so we don't need to do anything special convert it to linear inequalities. There are a variety of ways to do this but let's do it this way:$$x+y\leq 1, \quad -x+y\leq 1, \quad x-y\leq 1, ...

2

Think of what $S$ represents graphically: the lines of a square with corners at (-1,0), (0,1), (1,0), (0,-1), so you can write $S$ as follows: $$S=\{y= 1-x, 0\le x \le 1,0\le y \le 1 \}\cup\{y= x+1,-1\le x \le 0,0\le y \le 1\}\cup\{y= -1+x,0\le x \le 1,-1\le y \le 0 \}\cup \{ y= -x-1,-1\le x \le 0,-1\le y \le 0 \}$$ Now introduce boolean variables to ...

0

One goes through a process of analysis when programming. Numerical methods help with finding out an expression for the desired result in a given language.

2

It helps to look at the Taylor expansions of $f$ and $\tilde{f}$: $$f(z+\Delta z) \approx f(z) + \langle \nabla f(z), \Delta z \rangle + \tfrac{1}{2}\langle \nabla^2 f(z) \Delta z, \Delta z \rangle$$ \tilde{f}(y+\Delta y) \approx \tilde{f}(y) + \langle \nabla \tilde{f}(y), \Delta y \rangle + \tfrac{1}{2}\langle \nabla^2 \tilde{f}(y) \Delta y, \Delta y ...

0

For the converse direction, if $0 \in C$, then by definition of the convex hull, there exists $\{\lambda_i\}$ such that $\lambda_i \ge 0$ for all $i$, $\sum \lambda_i = 1$, and $\sum \lambda_ia_i = 0$. But then $\lambda = (\lambda_1, ... \lambda_n)$ is a solution the system, and therefore the system must be consistent. Edit: Whether the statement above is ...

0

Background and notation: First we need some background on taking derivatives in a multivariable setting, using matrix notation. Let $h:\mathbb R^n \to \mathbb R^m$ be differentiable at $x$. Then $h'(x)$ is an $m \times n$ matrix. (Intuitively, $h(x+\Delta x) \approx h(x) + h'(x) \Delta x$, when $\Delta x$ is a small $n \times 1$ column vector.) Suppose ...

2

Your're almost there... Recall the definition of convex conjugates. Recall that the convex conjugate of a norm $\|.\|$ is the indicator function of the unit ball of the dual norm $\|.\|_*$. Now, \begin{split} g(\nu) &:= \underset{x}{\inf }L(x,\nu) = \underset{x}{\inf }\|x\| + \nu^T Ax - \nu^T b = \nu^Tb -\underset{x}{\sup }x^T(-A^T\nu) ...

2

I don´t see from this single constraint, that it is a MILP or can be transformed into one. But you can remove the absolute value signs. Let´s define $x=x^+-x^-$, where $x^+,x^- \geq 0$ Then $|x|=x^++x^-$ Similar transformation for $y$. In total you get $x^++x^- + y^++y^- = 1$ $x^+,x^- , y^+,y^- \geq 0$ This could be a part of the standard form of a ...

1

If $x \in C^\perp$, then $x^Tv = 0$ for all $v \in C$ and so $i_C^*(x) = 0$. If $x \not \in C^\perp$, then $x^Tv_0 \not = 0$ for some $v_0 \in C\setminus\{0\}$. Now, it is clear that $v \mapsto x^Tv$ is unbounded on the line $L := \{tv_0 | t \in \mathbb{R}\} \subseteq C$. Thus $i_C^*(x) = +\infty$. Putting things together, we have $i_C^* = i_{C^\perp}$, as ...

1

$\sigma_C=\iota_{C^\perp}$ where $C^\perp$ is the orthogonal of $C$ and $\iota_K$ is the indicator function of $K$

1

Your feeling is right. Try to figure out a counterexample. Think of something simple like one-dimensional parabolic. True, but explanation is unclear to me. How do you know that the KKT is a local minimum? The sufficiency of KKT for convex problems is typically proved via Lagrangian $L$, which turns out to be convex too, so KKT point is a stationary point ...

2

Let $X$ and $Y$ be euclidean spaces (for simplicity of the exposition), $g: X \rightarrow (-\infty, +\infty]$ be convex and $A : Y \rightarrow X$ be affine, say $Ax \equiv Lx + \text{cte}$, where $L : Y \rightarrow X$ is linear. Finally, let $x \in Y$. We'll show that $\partial (g \circ A)(x) \supseteq L^* \partial g(A(x))$. Indeed, let \$v \in \partial ...

Top 50 recent answers are included