New answers tagged

1

The property you stated is equivalent to $f$ being strongly monotone and Lipschitz continuous; searching for this combination of terms will bring up a number of papers. It doesn't have a single-word name, since "Lipschitz strongly monotone" is short enough, and self-descriptive. Here's a justification. If $f$ is $L$-Lipschitz and $m$-strongly monotone, ...


2

According to the constraints and objective function, it seems that the objective function can get the maximum value on the boundary of feasible solutions, and since it is an open set, I think the objective function does not have any maximum in this case. Now, let replace the last three constraints as given below. $x_2\geq 0$, $x_3\geq 0$, and $x_4\geq 0$...


1

Let $(x_1,y_1),\, (x_2,y_2) \in \{x,y\in\mathbb{R}_+: (x,y)\ge \alpha\}$. Then $y_1 \ge {\alpha \over x_1}$ and $y_2 \ge {\alpha \over x_2}$. Since ${1\over x}$ is convex. $${\alpha \over \theta x_1 + (1-\theta)x_2} \le \theta {\alpha \over x_1} + (1-\theta){\alpha \over x_2}$$ Then $${\alpha \over \theta x_1 + (1-\theta)x_2} \le \theta y_1 + (1-\theta)y_2 \...


1

Let the vector of differences be given by $C x$, where $C \in \mathbb{R}^{m \times n}$ is the oriented incidence matrix of a graph with $n$ nodes and $m$ edges. Hence, $$f (x) := \sqrt{x^T C^T C x} = \sqrt{\|Cx\|_2^2} = \| C x\|_2$$ where $C^T C$ is the Laplacian matrix of the same graph. Thus, $f$ is convex. It is strictly convex if $C$ has full column ...


1

I refer to the wikipedia page of "Caratheodory's Theorem (convex hull)". They assume that $K>d+1$. $$\left| \left\{ x_i-x_1|i=2,\ldots,K\right\}\right|>d$$ If there are more than $d$ vectors in $\mathbb{R}^d$, they cannot be linearly independent.


1

OK, after struggling with elementary tools for a while and in vain, I had to invoke the "Closed Map Lemma", namely that a proper map (i.e one for which pre-images of compact sets are compact) between locally compact Hausdorff spaces (i.e a space in which every point has a compact neighborhood) is closed. For example, see Theorem 2.6 of this paper. In your ...


0

I think I got the answer by myself but wish some experts can confirm. The confusion is that, in CVX book we are converting one optimization problem with constraints to another optimization problem without constraints and solve the dual problem. But in PCA optimization we cannot. For example, page 227, we convert $$ \underset{x}{\text{minimize}}~~ x^\top ...


0

A polyhedron can be defined as a finite intersection of halfspaces and hyperplanes. Halfspaces and hyperplanes are convex sets, the intersection of convex sets is a convex set, and thus all polyhedrons are convex.


0

according to the abstract here: http://link.springer.com/article/10.1007%2Fs11222-014-9455-3 (non-interesting) local optima or singularities


0

You could look into integer programming which can be used to solve linear problems (yours is quadratic) where the variables are restricted to be integers. Please beware that this is not a convex problem and that it's NP-hard. GLPK can be used to solve these problems.


1

You could check out Boyd's monograph called Proximal Algorithms. Also, Vandenberghe's 236c notes are very helpful. Nesterov's textbook Introductory Lectures on Convex Optimization is another good resource for this material.


0

If I am not mistaken, the projected gradient descent should converge towards the minimizer of $f$ over $C$. In general, this minimizer is not the projection of the unconstrained minimizer onto the set $C$ if $n > 1$. It is easy to construct a counterexample and I advice you to do it yourself. [Another reasoning to see that this cannot hold: The Euclidean ...


1

In my opinion, it is sufficient that the objective is quasi-convex. Indeed, this ensures that all local minimizers are global minimizers and the set of global minimizers is convex. Thus, you do not have to fight against local minimizers (which are not global minimizers).


0

Let $(x^*, y^*) = \arg\min_{x\geq 0, y\geq 0}f(x,y)$ such that $x^*>0$. Define $\alpha$ as the solution of the following equation $$-5\alpha + (1-\alpha)x^*=0.$$ Then $f$ attains a smaller value at $(0, 2\alpha+(1-\alpha)y^*)$ than $f(x^*, y^*)$. In fact, we obtain $$f(x^*, y^*) > \alpha f(-5,2)+(1-\alpha)f(x^*, y^*)\geq f(0, 2\alpha+(1-\alpha)y^*),$$ ...


1

We denote by $a_i \in \mathbb R^m$, $i = 1, \ldots, n$ the columns of $A$. By a conic variant of Carathéodory's theorem, each conic combination of $\{a_i\}$ can be written as a conic combination of a linearly independent subset of $\{a_i\}$. Since there are only finitely many linearly independent subsets of $\{a_i\}$, it is sufficient to prove the claim for ...


0

Finding a minimum volume covering ellipsoid is helpful in building probability distributions in the presence of outlying data points. For instance, suppose we have a data set $X \subset \mathbb{R}^N$ that is sampled from a normal distribution, $N(0, \Sigma)$. As you said, a reasonable way to estimate this normal distribution is to use the maximum likelihood ...


0

Let $E$ be a complement of $\ker A$, i.e. $\;\mathbf R^n=\ker A\oplus E$. $E$ is closed in $\;\mathbf R^n$ since we're in a finite dimensional space, and likewise, $\;\operatorname{Im} A$ is a closed subspace of $\;\mathbf R^m$. Now, the restriction of A to $E$ is an isomorphism of $E$ onto $\;\operatorname{Im} A$. On the other hand $\;\{x\in E\mid x\ge 0\...


-1

Let $e_1,...,e_n$ be a basis of $R^n$, you can suppose that $A(e_1),...,A(e_l)$ generate the image of $A$, and $(e_{l+1},...,e_n)$ is a basis of $ker(A)$. if $y$ is an element of the adherence of $C=\{A(x),x\geq 0\}$, $y$ is in the vector subspace generated by $(A(e_1),...,A(e_l)$. You can write $y=y_1A(e_1)+...+y_lA(e_l)$. There exists $(x_m)=A(x_1^me_1+.....


1

By introducing the Lagrange multiplier, you are converting if from a minimization problem to a saddle-point problem. One seeks: $$\min_w \max_\lambda w^T C w + \lambda(w^Tw - 1).$$ The following is not correct: $$\min_w \min_\lambda w^T C w + \lambda(w^Tw - 1)$$ The saddlepoint is still a location where the gradient is zero, just like a minimum - perhaps ...


1

It seems, everything is a bit simpler. By the definition of the directional derivative we have: $$0>f'(x;v) = \lim_{t\to 0}\frac{f(x+tv)-f(x)}{t} =\inf_{t>0}\frac{f(x+tv)-f(x)}{t},$$ where the latter equality holds due to the convexity of $f$. Now by the definition of $\inf$ we got that for $t$ small enough $$f(x+tv)-f(x)\leq 0,$$ which means that $v$ ...


1

If you have constraints where you turn on/off things by multiplying continuous variables with binary variables, you are typically not going to end up with convex (as in convex relaxations etc) models. Instead, you should model this using big-M strategies. For instance, if you want to model $xy\geq 1$ where $x$ is continuous and $y$ is binary, you introduce ...


0

Here's a start: The gradient of $\|x_i - y\|_2$ with respect to $y$ (if $y \ne x_i$) is the unit vector in the direction of $y - x_i$. At a minimum that is not one of the $x_i$, those unit vectors will add to $0$. The minimum might also be one of the $x_i$: if that happens, then the sum of the unit vectors for the other $x_i$ has norm $\le 1$.


0

Why use Fourier-Motzkin? The conjunction of the two equality constraints defines the intersection of two planes in $\mathbb R^3$. As these two planes are not parallel, their intersection is a line. Given the nonnegativity constraints, we intersect this line with the nonnegative octant, which produces a line segment in $(\mathbb{R}_0^+)^3$. From the two ...


1

The first summand $$f(x,y) = \dfrac{a}{bxy + cd} e^{\frac{a}{bxy+cd}} H$$ is not convex. Its Hessian at $(0,0)$ is $$ \left[ \begin {array}{cc} 0&-{\frac {Hab \left( a+{\it cd} \right) }{ {{\it cd}}^{3}}{{\rm e}^{{\frac {a}{{\it cd}}}}}}\\ -{\frac {Hab \left( a+{\it cd} \right) }{{{\it cd}}^{3}}{{\rm e}^{{ \frac {a}{{\it cd}}}}}}&0\end {array} \...


1

N.B.: The problem can / should be solved using elementary geometry. You don't need KKT or other "heavy machinery". Indeed, in $\mathbb R^n$ the $\ell_\infty$ unit-ball is a cartesian product of $n$ identical pieces, namely $\mathbb B_\infty = [-1,1]^n$. Thus the projection can be computed piece-wise (minimization of a separable function on a cartesian ...


1

By Moreau Decomposition: $$ {\text{Prox}}_{f} \left( x \right) + {\text{Prox}}_{ {f}^{\ast} } \left( x \right) = x $$ For $ f \left( x \right) = \left\| \cdot \right\| $ the conjugate is given by the Projection onto the Dual Norm $ {f}^{\ast} \left( x \right) = {\mathcal{P}}_{ { \left\| \cdot \right\| }_{\infty} \leq 1 } \left( x \right) $. Hence, for $ f ...


2

The "common sense" answer is that you simply want to get each $y_i$ as close as possible to $x_i$ without causing $y$ to leave the unit ball. That is, take $$ y_i = \begin{cases} -1 & x_i < -1\\ y_i & -1 \leq x_i \leq 1\\ 1 & x_i > 1 \end{cases} $$ In a sense, this is a greedy optimization at each coordinate. This works for this problem ...


0

Let $\mathcal{X}$ and $\mathcal{Y}$ be abstract sets and consider any real-valued function $f:\mathcal{X}\times \mathcal{Y}\rightarrow\mathbb{R}$. For any $(x,y) \in \mathcal{X}\times \mathcal{Y}$ we get: \begin{align} f(x,y) &\geq \inf_{a \in \mathcal{X}} f(a,y) \\ &\geq \inf_{b \in \mathcal{Y}}\left[ \inf_{a \in \mathcal{X}} f(a,b)\right] \end{...


1

Your intuitions are right. Indeed, $g: \alpha \mapsto x + \alpha p_k$ is affine whilst $f$ is convex. Therefore $f \circ g$ is convex.


0

OK, here's a deal: (a) The ray $\{\lambda v | \lambda \ge 0\}$ is closed. This is rather easy. Nothing to do here. (b) In finite dimensions, the convex hull of a compact set is compact. I've proven this for another question here. (c) The Minkowski sum of a compact set and closed set is again closed. This has been neatly shown here. Conclude that your set ...


1

This is a special case of computing the distance between two convex sets (a point by itself is a convex set). This paper A fast procedure for computing the distance between complex objects in three-dimensional space was brought to my attention by Joseph O'Rourke and it references an $\mathcal{O}(\log M)$ algorithm for the two dimensional case. Here $M$ is ...


1

If the convex polygon is represented by the intersection of finitely many half-planes $$P := \{ x \in \mathbb R^2 \mid A x \leq b \}$$ then we can find the point $x^* \in P$ closest to a given $y \in \mathbb R^2$ by solving the quadratic program $$\begin{array}{ll} \text{minimize} & \|x - y\|_2^2\\ \text{subject to} & A x \leq b \end{array}$$ If ...


1

You could do something that is somewhat like binary search indeed: To find the closest point on $P_1P_2P_3\ldots P_n$, find the closest point on $P_1P_3P_5\ldots P_{\lceil n/2\rceil}$. If it is between $P_k$ and $P_{k+2}$ then we need only test vertex $P_{k+1}$ and its adjacent edges for the original polygon. If it is exactly at $P_k$, we also need only ...


3

The key is the dual relationship $\|x\|_\infty = \max_{\|z\|_1 \le 1} z^T x$. Note \begin{eqnarray} K^* &=& \{ (y,s) | x^T y + st \ge 0 \text{ for all } (x,t) \in K \} \\ &=& \{ (y,s) | -x^T y + s \ge 0 \text{ for all } (-x,1) \in K \}\\ &=& \{ (y,s) | x^T y \le s \text{ for all } \|x\|_1 \le 1 \}\\ &=& \{ (y,s) | \max_{\|...


0

I've worked this problem out before, and from what I remember, you should get from your optimality conditions that $y^*= \min(\max(x+\mu 1,0),1)$, where $\mu$ is chosen so that $1^Ty^* = k$. In words, to project onto the intersection of a box ($0\le y \le 1$) and a plane ($1^Ty = k$), move in the direction normal to the plane until the projection onto the ...


1

The claim is false. In general, the conjugate of $g-h$ is not even finite: e.g., $g\equiv 0$, $h(x)=x^2$. And when it is finite, the equality has no reason to hold. Let $g(x)=Ax^2$ and $h(x)=Bx^2$ with $A>B>0$. Then $g^*(x)=\frac{1}{4A}x^2$, $h^*(x)=\frac{1}{4B}x^2$, and $(g-h)^*(x)=\frac{1}{4(A-B)}x^2$. Obviously, we should not expect $1/(A-B)$ to be ...


1

Complementarity problems is simply optimization problems with a special kind of constraints. Essentially orthogonality constraints between two non-negative vectors, $x\geq 0, y\geq 0, x^Ty = 0$. This arise, for example, in purely geometric applications (orthogonality constraints), or in situations where you want to encode either-or conditions ($x_i$ is zero ...


0

Just for example, let $X\subset \mathbb{R}^2$ be a closed convex set and let $y$ be a point outside $X$. As you should know, there exists only one point $x^*\in X$ which has the least distance from $y$ (such a point is usually called orthogonal projection of $y$ onto $X$); more formally, $x^*$ satisfies the following inequality: $$\tag{1}|x-y|\geq |x^*-y|\...


0

My explanation below follows from varitional inequalities (VI) by Rockafeller. The definition of VI says that $\langle F(x),x-x^*\rangle \geq 0$. Where F is some function from $C \rightarrow R^n$, C is a convex set; $x,x^* \in C$.The more general definition of VI is called varitional condition defined as: \begin{equation} 0 \in F(x) + N_C(x) \end{...


0

No. Take for example $f(x)=\sqrt{|x|}$. While $f(x)$ decreases monotonically at each step under the assumption that steps are small enough (or if you apply backstepping to enforce monotonicity), the gradient $(2 \, \mathrm{sign}(x) \, f(x))^{-1}$ gets larger in modulus as the current iterate $x$ approaches the solution $x=0$. If you don't like the kink in 0 ...


1

We have a convex quadratic program $$\begin{array}{ll} \text{minimize} & \|A X - A\|_F^2\\ \text{subject to} & (1 - \delta) 1_n \leq X^T 1_n \leq (1 + \delta) 1_n\\ & X \geq 0\\ & X \in \mathbb{R}^{n \times n}\end{array}$$ Vectorizing $X$, this QP can be written in a more standard form $$\begin{array}{ll} \text{minimize} & \|(I_n \...


1

First of all, in the first solution, the correct condition on $\lambda$ is $\lambda \ge 0$, not $\lambda > 0$. I have no idea why the solution has to decompose $c$ in that way (no other choice? why not decompose $a$?) Not sure how the author came up with the second solution, but when reading it, I immediately saw that it just follows from the ...


0

This is a Community Wiki Solution. Feel free to edit and add. I will point up and mark solution for any other solution made by the community. KKT The Lagrangian is given by: $$ L \left( y, \lambda \right) = \frac{1}{2} {\left\| y - x \right\|}^{2} + \mu \left( {e}^{T} y - k \right) - {\lambda}_{1}^{T} y + {\lambda}_{2}^{T} \left( y - e \right) $$ The KKT ...


1

Minimizing $|w|$ is the same as minimizing $|w|^2$. As I understand it, the reason we choose the latter is purely for convenience. Would you rather deal with partials of $\sqrt{x^2+y^2}$ or $x^2+y^2$? The latter, obviously, because it's easier.


3

If $f$ is continuous, the implication $\|x^k-x^*\|_2 \rightarrow 0 \implies f(x^k)-f(x^*) \rightarrow 0$ holds; this is known as a sequential characterization of continuous functions. To prove the converse, additional hypotheses on $f$ are needed. Suppose $f$ is strictly convex and $x^*$ is the point of its minimum. Then it is true that $f(x^k)-f(x^*) \...


0

I would like to expand what I have said as a remark. And we can be helped in this by having a graphical view of what happens. An essential thing is that you are working with what is called the (positive) convex cone generated by the $v_k$s. A geometrical view of it is the inside of a prismatic cone whose edges are directed by some of the $v_k$s (maybe not ...


0

Suppose we are given a target $\mathrm{y} \in \mathbb{R}^d$ and vectors $\mathrm{b}_1, \mathrm{b}_2, \dots, \mathrm{b}_n \in \mathbb{R}^d$. Let $$\mathrm{B} := \begin{bmatrix} | & | & & |\\ \mathrm{b}_1 & \mathrm{b}_2 & \ldots & \mathrm{b}_n\\ | & | & & | \end{bmatrix}$$ We would like to find a vector $\mathrm{x} \in (\...


0

The minimal ellipsoid (with respect to area) centered at the lower dot and containing the upper dot in your figure is the degenerate ellipsoid with smaller semiaxis $=0$ and one apex at the upper dot; in short: a segment covered twice. The ${\cal E}_2$ in your figure has no minimal properties whatsoever.


1

I think the thing to do is to make a modified version of tfocs_N83.m where the variables x_old, z_old, apply_projector, and apply_linear are updated (to account for the pruning) every 50 iterations. Note that the variables affineF and projectorF do not need to be updated; rather, apply_linear and apply_projector should be updated. I tried this and it's ...


1

We have a quadratic program $$\begin{array}{ll} \text{minimize} & \|\mathrm{x} - \mathrm{k}\|_2^2\\ \text{subject to} & 1_n^T\mathrm{x} = c\end{array}$$ where $c = -1 + \displaystyle\prod_{i=1}^n (k_i+1)$. Using a Lagrange multiplier, $$\mathcal{L} (x,\lambda) := \frac{1}{2}\|\mathrm{x} - \mathrm{k}\|_2^2 + \lambda (1_n^T \mathrm{x} - c)$$ Taking ...



Top 50 recent answers are included