Hot answers tagged

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^*) \...


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_{\|...


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 ...


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

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


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 ...


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

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.


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).


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

The cone $C=\{y\colon Ax=y,x\ge 0\}$ is finitely generated (by finitely many columns of $A$) and convex. By Minkowsky-Weyl theorem (en easy proof via Fourier-Motzkin eliminations can be found here, Theorem 1) it is a polyhedral cone, that is, $C=\{y\colon By\le 0\}$. From the last representation it is clear that $C$ is closed as an intersection of closed ...


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 ...


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 ...


1

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

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 ...


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 ...


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 ...


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 ...


1

First of all, ADMM stands for Alternating Direction Method of Multipliers. ADMM for nonconvex functions is a current hot research topic. I recommend the following theoretical papers: Convergence Analysis of Alternating Direction Method of Multipliers for a Family of Nonconvex Problems by Hong et al. Global Convergence of ADMM in Nonconvex Nonsmooth ...


1

In your case \begin{align} N_C(0,0) &= \{ (y_1,y_2)\in \mathbb{R}^2|y_1c_1+y_2c_2\le 0, \forall (c_1,c_2)\in C\}\\ &=\{ (y_1,y_2)\in \mathbb{R}^2|y_1c_1\le 0, \forall\, c_1\in [0,1]\}\\ &= \{ (y_1,y_2)\in \mathbb{R}^2 | y_1\le 0\} \end{align}


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

Your problem has no finite minimum. To see this, consider the ray $R := \{(x, 0) | x \ge 5 / 3\}$. It is clear that this ray is contained in the constraint set. However, along $R$, the objective function simplifies to $-2x$, which gets cranked to $-\infty$ as you increase $x$. Hint: All we've done is let the point $(x, y)$ vary along an appropriately chosen ...


1

The image shows the constraints, the feasible region and a couple of isolines $Z=\text{const}$. From bottom to top: $Z = 10, Z=0, Z=-10, Z=-20$. We see that the higher the isoline, the lower its value. The feasible region is the dark purple region in the first quadrant, which is not bounded from above. This means there is no finite minimum to this ...


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 ...



Only top voted, non community-wiki answers of a minimum length are eligible