Tagged Questions

Convex analysis is the study of properties of convex sets and convex functions. For questions about optimization of convex functions over convex sets, please use the (convex-optimization) tag.

70 views

Test if point is in convex hull of $n$ points

I have $n$ points $x_1,\dots,x_n\in\Bbb R^d$, and I would like to check that some other point $y$ lies in their convex hull. How can I do this in some efficient way? I think that there was an ...
4k views

Dual norm intuition

The dual of a norm $\|\cdot \|$ is defined as: $$\|z\|_* = \sup \{ z^Tx \text{ } | \text{ } \|x\| \le 1\}$$ Could anybody give me an intuition of this concept? I know the definition, I am using it ...
13 views

10 views

Geometrical interpretation of Pseudoconvexity?

I see in wolfram that a function $f$ is pseudo convex if it satisfies following, $\nabla f(x)\cdot (y-x) ≥ 0 \Rightarrow f(y) ≥ f(x)$ My question is, with this definition, how come $g(x)=x^3$ is ...
28 views

Why is the Euclidian norm convex, if the square root function is concave?

I have some trouble figuring out if the Euclidean norm is convex. $\left\|{\boldsymbol {x}}\right\|:={\sqrt {{\boldsymbol {x}}\cdot {\boldsymbol {x}}}}$ On one side I read that all norms are convex (...
9 views

The Set of Extremal Point Need not be closed

Exercise: Consider the Convex Hull $C$ of the points $(0,0,\pm 1)$ and the circle $\{(1+\cos\varphi,\sin\varphi,0): 0\leq \varphi \leq 2\pi\}$ in $\mathbb{R}^3$. Determine the extremal point of $C$. ...
9 views

Convex set or not?

This question is related to my previous question Set of all positive definite matrices with off diagonal elements negative I know that the set of all positive definite matrices form a convex set. ...
9 views

27 views

minimum of sum of strictly convex functions

Is the following statement true? If so, how can I find a proof? Suppose that $f_1$ and $f_2$ are strictly convex functions on a convex set $X \subseteq \mathbb{R}^n$. If $f_1$ and $f_2$ have minimum,...
17 views

how to calculate infimum of Augmented Lagrangian?

should any body explain that how do we calculate these step? \begin{align*} L(x,y) &= f(x) + y^T(Ax-b)\\ g(y) &= \inf_x \, L(x,y) \\ &= \inf_x \, f(x) - \langle -A^Ty, x \rangle - \langle ...
65 views

Why is this matrix symmetric?

There is an example in the Convex Optimization lecture notes, Boyd. He just said in the lecture that the matrix which is underlined in red color is symmetric! How can we claim that when there is no ...
448 views

Stochastic gradient descent for convex optimization

What happens if a convex objective is optimized by stochastic gradient descent? Is a global solution achieved?
9 views

235 views

29 views

19 views

Helly theorem application

Let $X$ be a normed space, $dim(X)=d$, let $r>0, A$ and $\subset X$ . Show that if every $d+1$ points of $A$ are contained in a closed ball of radius $r$, then $A$ is contained in a closed ball of ...
18 views

Why are generalized inequalities defined over proper cone?

Why generalized inequality is defined over a proper cone? What property does not hold if we define it over non-convex cone? Same with `pointed'. For example, generalized inequality makes sense in a ...
23 views

Convexity of the composite of convex function by exponential function

Let $\exp : \mathbb{R}^2 \to \mathbb{R}^2$ be the function given by $\exp(x_1,x_2) := (e^{x_1}, e^{x_2})$. Suppose that $f : \mathbb{R}^2 \to \mathbb{R}$ is a smooth (i.e. $\mathcal{C}^2$) convex ...
76 views

12 views

random pursuit without function evaluations

Assume we want to minimize a convex function $f(x)$ with $x\in \mathbb{R}^n$. Function $f(x)$ represents cost of a system which we cannot compute directly but can observe if system is at state $x$. My ...
66 views

39 views

Is there a way to measure how (non)convex a function is, maybe analogous to condition number?

Consider the functions $f(x) = \sin x$ and $g(x) = (x+1)^2 (x-1)^2$. We know that $f$ has an infinite number of local minimizers and is nonconvex on a non-compact subset of $R$. We know that $g$ has ...
How do you prove that $\{ Ax \mid x \geq 0 \}$ is closed?
Let $A$ be a real $m \times n$ matrix. How do you prove that $\{ Ax \mid x \geq 0, x \in \mathbb R^n \}$ is closed (as in, contains all its limit points)? The inequality $x \geq 0$ is ...