# Tag Info

## New answers tagged convex-optimization

0

To simplify the exposition, consider the standard case: $\mu = 1$. In any dimensions (your case is 1-dimensional), the Huber function is the infimal convolution of the $\ell_1$-norm $x \mapsto \|x\|_1$ and the half-squared $\ell_2$-norm $x \mapsto \frac{1}{2}\|x\|_2^2$, i.e $h = \|.\|_1 \Box \frac{1}{2}\|.\|_2^2$. For example, see exercise 1 of this ...

0

Is my simple minded argument allowed? The problem of finding $(y,x,z)$ (or $(x,y,z,u,v,w)$) that minimizes $$\min \sqrt{(x-u)^2 +(y-v)^2 + (z-w)^2 }$$ is the same as: $$\min \> (x-u)^2 +(y-v)^2 + (z-w)^2$$ as the square root is a monotonic function. Sum of squares is convex (and $x-u$ etc. is linear). So we are done.

0

No, it's not convex, and no, $z^T H z$ is not positive. Try $z = \pmatrix{1\cr -1}$. Note: in the criterion for convexity involving the Hessian, there's no requirement for the vector $z$ to belong to the domain of $f$. The vector $z$ does not correspond to a point in the domain, but rather to an infinitesimal displacement that can be in any direction. ...

0

The locus of $(x,y,z)$ is a sphere of radius $\sqrt{5}$ The locus of $(u,v,w)$ is a cylinder of radius $1$ , height $4$ and having it's center at $(4,0,6)$ Now consider all the cross sections of the figures which are parallel to the $xz$ plane.The 2 points which minimize this distance is suppose to be in one of these planes.We get the largest cross ...

1

You can use directly the definition of a convex function: $f(tx+(1-t)y)\leq tf(x)+(1-t)f(y),\,\forall t\in [0,1]$. So you have to prove that $$f(x,y,z,u,v,w)=\sqrt{(x-u)^2+(y-v)^2+(z-w)^2}$$ is convex. The whole idea is to see that your function is the second Euclidean norm in $\mathbb R^3$ of the vector $(x-u,y-v,z-w)$ and to use the convexity of the ...

1

This is a special case of Jenathon's et al. "structured sparse pca" model with $r = 1$ component / latent factor. Also, your problem specializes the sparsity inducing $\Omega$ penalty to just an $\ell_1$-norm. The model can be optimizes by block coordinate descent via Algorithm 1 of the aforesaid paper, e.g

1

The problem you mention is closely related to the sparse principal component analysis (Sparse PCA). There is a vast literature on this problem including greedy nonconvex algorithms and semidefinite relaxations. Just google "sparse pca" and you will find "highly cited" papers. For your particular formulation, you might want to look at the recent literature ...

1

Weighted sums of convex sets are always convex, even if the factors are negative. Note that $\alpha C$ is convex for every $\alpha \in \mathbb{R}$, if $C$ is convex. Then use the fact that the Minkowski sum of convex sets is convex.

0

In general, your function $f$ is nonconvex! For example, on $\mathbb R_+^2$ consider $f :(x_1, y_2) \mapsto x_1x_2$. However, the inequality your trying to proof holds for arbitrary $f$ defined as you did. When such an inequality holds, we say $f$ is multiplicatively convex. So then, let's show that your $f$ is multiplicatively convex. Indeed, $$f(x) = ... 2 The inequality for large x implies that \lambda_2\geq1. The function f(x)=\lambda_1+\lambda_3x^2 determines a parabola centered around the Y axis (where in order to cover the case \lambda_3=0 we temporarily agree to call a horizontal line a parabola, as well). Thus for any given \lambda_2\geq1 we look for a parabola centered around the Y axis ... 0 In this lecture there is a proof of this proposition, using arguments from convex analysis. The "meat" of the proof starts in page 28, but you should read all the lecture to understand the notation, definitions and such. 1 It is not necessarily continuous. For example, the function f(x,y)=x^2,\, y\leq 0 and f(x,y)=(x-1)^2,\,y>0, where x\in [-2,2], y\in[-1,1]. You can see that if \,y\to 0^+\quad x^*(y)\to 1 and if \,y\to 0^-\quad x^*(y)\to 0, because x^*(y)=0,\,y\leq 0 and x^*(y)=1,\,y>0 1 EDIT: after posting this I noticed from the tags that this is specifically about convex functions. In this case I don't know that to tell you. I'll just leave this answer up, though, in case someone might find it useful for something. This is far from a complete answer, but here's a counterexample: let$$f(x) = \begin{cases} -1 & x < 1 \\ 0 & x ...

1

Hint Note that $$\dfrac{\partial f}{\partial x}=\dfrac{y^{\alpha+1}}{(x+y)^2}>0.$$ Thus, if $x>x_0$ then $f(x,y_0)>f(x_0,y_0).$ So, the maximum point is of the form $(b,y).$ But, on those points it is $$g(y)=f(b,y)=\dfrac{by^{\alpha}}{b+y}.$$ You only need to maximize the function $g(y)$ in $[0,c].$

1

A function $f$ is called log-convex if $\ln f$ is convex. It is not that difficult to show that a sum of two log-convex functions is log-convex. All you need to do is to notice that the function $\exp g_i$ is log-convex. Another approach would be to show by definition for the case $m=2$ and then generalise to an arbitrary $m$.

0

Say you have an optimal solution to the primal. You now wish to find an optimal solution to the dual. If such a dual solution exists, then it must satisfy complementary slackness by strong duality. You can employ this to find optimal dual solution(s). See the Complementary Slackness section of the wiki article on Linear Programming: ...

3

No, that conclusion does not hold because generally, the product of two convex functions need not be convex. As an example, $f(x, y) = x y^{-1}$ (for $x, y > 0$) is a posynomial function, but not convex: $$f(\frac{1+5}{2}, \frac{1+3}{2}) = \frac 32 > \frac 43 = \frac 12 \left( f(1, 1) + f(5, 3)\right)$$

1

Figured it out! As Erwin pointed out, the formulation above is valid (save the fact that it should be optimized over x and t together). In order to write it in the form suggested by the problem, I needed to stack x and t: $$\min_{u=[x^T\;t^T]^T}\begin{bmatrix}0\\1\end{bmatrix}^T\begin{bmatrix}x\\t\end{bmatrix} \quad \text{subject to}\; \begin{bmatrix}I ... 1 rank(M) = \min\{r|\exists V \in L(m,r), W \in L(n,r). M = V^TW \} where L(m,n) is the space of n\times m matrices is my rewriting of the (intended) meaning of your definition. You should verify that it is equivalent. I think this definition (particularly compared to your definition of rank as the dimension of the image) makes it much easier to answer ... 2 No I don't think so. Taking log x = p & log y = q. You can write it as f(ap + bq) \leq f(p)^a f(q)^b Now replace p and q by x and y. 0 Since it is a two-variable linear programming and as OP said, I can try to answer this using the graphical technique mentioned. Here is the depicted feasible region (bounded by the red line) for the given constraints. And we know that the optimal solution must be located at one of the five corners. and now the desired solution is on the top right hand ... 0 The point-wise maximum of a set of convex functions is convex.$$g(x) = \max_i f_i(x) $$The corresponding epigraph$$\{(x,t) | t > \max_i f_i(x)\}$$is convex which could also be visualized as the insertion of a family of convex spaces,$$\cap_i \{(x ,t)| t > f_i(x)\}$$The lagrangian could be rewritten as the negative of the supremum, ... 0 Nothing is said, so I assume a 3D space. We have positions P_i of the towers and of a vehicle at x. We measure distances r_i(t), which correspond to the radii of spheres around the towers. The intersection of two spheres is a circle, three circles can intersect in a point. (Large Version) We need to determine the trajectory of the vehicle, which ... 1 You have \nabla(f\circ g)(x) = f'(g(x)) \, \nabla g(x). Consequently$$\nabla^2(f \circ g)(x) = f''(g(x)) \, \nabla g(x) \, \nabla g(x)^\top + f'(g(x)) \, \nabla^2 g(x).$$Then, it is easy to check the definiteness of the Hessian. 0 The function x \mapsto x^3 is quasiconvex, quasiconcave, but neither convex nor concave. 0 In general, no. The function x \mapsto x^2 is quasiconvex but not concave. The function x \mapsto x is quasiconvex and concave. 1 Perhaps this situation is analogous to the derivative versus directional derivative (as might be familiar from multi-variable calculus). Recall, given a function say f:R^n \to R, the gradient is defined as \nabla f = \sum_{i = 1}^n \frac{\partial f}{\partial x_i} dx_i or alternatively \left(f_{x_1}, f_{x_2}, \dots, f_{x_n}\right) while the ... 1 I do not agree. It looks correct to me. First of all, if variables x and y are unconstrained, it is correct to have = type constraints in the dual. Authors are not required to specify that a variable is unconstrained, they only have to specify which ones are not, and how. This makes sense. If your primal is a minimization problem and constraints are ... 1 If A is non-symmetric, there is no f : \mathbb{R}^n \to \mathbb{R}^n, such that f'(x) = A \, x + c. Indeed, this would imply that the Hessian f''(x) = A is non-symmetric. (However, there are other methods to deal with problem (1).) 2 In my understanding (and in a very large generality), an optimization problem$$\min\{f(x), \;\;x\in C\}$$is convex if C is convex, and f:C\to\mathbb{R} is convex. As an example, we often give the following framework, where C is described by equality and inequality constraints:$$\min\{f(x), \;\;\forall 1\leq i \leq n, g_i(x)=0, \;\;\forall 1\leq ...

2

We need the $\lambda_i$s positive in order to penalize a violation of the constraints $f_i(x)\leq 0$. More precisely, if they were negative, minimizing $L$ would likely give $x$s for which $f_i(x)>0$ (because then $\lambda_if_i(x)<0$ making $L$ smaller) which is in violation to our primal problem. The final inequality holds by construction of the $L$. ...

4

You additionally need that your set is bounded, otherwise it may have too few extreme points: any convex, closed cone has only one extreme point For any closed, convex $C$, consider $C \times \{0\}$: no extreme points. If your set is bounded, it is (assuming that the ambient space is finite-dimensional) compact. By Krein-Milman, the set is the convex ...

0

Yes, you need the regularity, otherwise the theorem may fail. It is quite insightful if you try to construct counterexamples. If all $K_i$ are also closed, you have $$K^\circ = \operatorname{cl}(K_1^\circ + \ldots +K_m^\circ)$$ without further assumptions. It also helps to construct examples where the closure on the right-hand side is needed.

2

Second derivate is $-\dfrac{e^x}{(1+e^x)^2}<0$. So the correct answer is in your book: $f$ is not convex. Indeet, it is concave.

0

You are missing $y$ (the label) in your proposed formulation. You should fix that. Hint: $$\|w_a\|^2 + \|w_b\|^2 = \|[w_a : w_b]\|^2$$ Also, $$y_i(\beta w_a^{\top}x_i + (1-\beta)w_b^{\top}x_i) \geq 1 - \xi_i$$ is same as, $$y_i([w_a:w_b]^{\top}[\beta x_i : (1-\beta)x_i]) \geq 1 - \xi_i$$ Based on the edited question: Since, you have two separate labels ...

0

If $f$ is convex, it has just one minimum and at this minimum its gradient is zero. So the third criteria should work fine. If $f$ is not convex, you may reach a local minimum so this criterion is not really justified. If you are using a gradient method, the second criteria is very similar to the third because each step (or the difference $x^{k+1}-x^{k}$) ...

0

David has offered the correct answer geometrically, and I'd say he deserves the checkmark :-) But I did want to address this from a computational point of view. The computational complexity of computing either the minimum volume circumscribed ellipsoid (MinVCE) or the maximum volume inscribed ellipsoid (MaxVIE) depends greatly on the way the underlying ...

0

Here is a synthetic (i.e non-analytic) response to guide you. The projection operator $P_C$ onto a closed convex set $C \subseteq \mathbb R^n$ is the resolvent of the normal cone $N_C : x \mapsto N_C(x) := \{g \in \mathbb R^n | \langle v, z - x\rangle \le 0\} = \partial i_C(x)$. That is, $P_C = (Id + N_C)^{-1}$. $N_C = \partial i_C$ is maximally monotone ...

0

Here is a reasonable conjecture in dimension $2$: For an equilateral triangle $T$ the smallest circumscribed ellipse is the circumcircle, and the largest inscribed ellipse is the incircle. The area ratio between these two is $4$. Conjecture: Let $K\subset{\mathbb R}^2$ be convex and compact, and let $A_{\rm circum}(K)$, resp $A_{\rm inscr}(K)$, be the ...

2

Consider the yellow and orange convex figures, which have the same bounding ellipsoid but different bounded ellipsoids. Therefore, given just the bounding ellipsoid you cannot determine the bounded ellipsoid. (Nor vice versa.) You must know the figure $K$. A better, limiting, example: Suppose $K$ is an ellipsoid. Then the bounding ellipsoid and the ...

1

Note your terminology error. You asked if the function was convex--but you gave us an entire optimization model. You should be asking instead if your model is a convex optimization problem, not a convex function. And in fact, your objective function is concave---but it needs to be. So it's all the more important to get that terminology correct. The ...

0

Computing the Hessian of $$(y_2-\gamma y_1)-(y_3-\gamma y_2)e^{x\cdot\beta}$$ we get  \begin{align} H &=\frac{\partial\nabla f}{\partial(\gamma,\beta)}\\[12pt] &=\frac{\partial\left(-y_1+y_2e^{x\cdot\beta},(\gamma y_2-y_3)xe^{x\cdot\beta}\right)}{\partial(\gamma,\beta)}\\[6pt] &=\begin{bmatrix}0&y_2x\\[3pt]y_2x'&(\gamma ...

4

What I have found is that looking at the dual problem with a custom prox function is almost always helpful. To derive it, I first rewrite the problem as follows: \begin{array}{ll} \text{minimize} & \tfrac{1}{2} \| x - \hat{x} \|_2^2 + t \\ \text{subject to} & \| x \|_2 \leq t \\ & x \succeq 0 \end{array} where $t$ is a new variable. To ...

Top 50 recent answers are included