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.

learn more… | top users | synonyms (3)

3
votes
2answers
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 ...
15
votes
3answers
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 ...
0
votes
0answers
13 views

How to prove a mixed integer function $f(x,n_1,n_2)$ is convex [on hold]

I have a mixed-integer function (with continous and disceret variables); $f(x,n_1,n_2)$ , $x\in[0,a]$ and $n_1,n_2\in N_{0}$. How can I show for a given $x$, $f(x,n_1,n_2)$ is convex with respect to $...
0
votes
0answers
9 views

Proof Verification: C closed, convex, symmetric in Banach space X and $\cup_{n \in N \setminus 0} n.C= X$ then $B_\epsilon(0) \in C $.

I have an outline of the proof of this which I've expanded (correctly or otherwise) below, I'd appreciate feedback on it. (I think that C has to be closed in order to assert that $\cup_{n \in N \...
1
vote
1answer
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 ...
2
votes
2answers
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 (...
0
votes
0answers
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$. ...
0
votes
1answer
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. ...
0
votes
0answers
9 views

$L^p([0,1])$ stricly convex [duplicate]

Exercise: For which $p\in [1,\infty]$ is $L^p([0,1])$ strictly convex? Solution: For strict convexity we have two equivalent definition: If $x\neq 0\neq y$ and $\Vert x+y\Vert=\Vert x\Vert+\Vert ...
0
votes
1answer
19 views

$C([0,1])$ strictly convex

My question is quite simple: Is the space $C([0,1])$ strictly convex? Where strict convexity is defined as: if $\Vert y+x \Vert=\Vert y\Vert+\Vert x\Vert$ then it implies that is exists an $\lambda&...
3
votes
1answer
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,...
0
votes
0answers
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 ...
3
votes
1answer
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 ...
12
votes
1answer
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?
0
votes
0answers
9 views

Nesterov's bound between quadratic and strongly convex cases?

Are there some examples of simple & strongly convex functions for which the convergence bound of Nesterov’s Accelerated Gradient Method is better than Nesterov’s bound for strongly convex case $\...
2
votes
1answer
29 views

Why isn't $\ell^p$ locally convex for $0<p<1$?

I believe we have to distinguish the finite-dimensional from the infinite dimensional case. Regardless, if $0<p<1$, $\|x\|_p := (\sum |x_i|^p)^{\frac 1 p}$ is not a norm as it fails to satisfy ...
0
votes
2answers
418 views

How to prove the convexity of $f$ if the strict epigraph of $f$ is convex

I have trouble to prove the equivalence of the following two definitions of convex function. For convenience, I list them as follows: Def-A. Let $f : I\to \mathbb{R}$ be a function, where $I$ is (and ...
1
vote
2answers
32 views

How to check whether a given inequality is convex? [on hold]

I have the inequality $$x_1^2+x_2^2\geqslant1$$ How do I check its convexity analytically?
0
votes
1answer
20 views

Convex set equals convex functions within optimization?

Can optimizing a convex function subject to convex constraints be written as optimizing the function subject to a convex set? Does the intersection of convex nonlinear ineualities necessarily describe ...
0
votes
0answers
19 views

Basis of convex and concave functions

Let $g(t)$ be a positive function. I'm trying to show that the set $\{ |t|^ne^{\frac{g(t)}{t^n}}\}_{n\in \mathbb{N}}$ is linearly independent in the space of measurable functions on $\mathbb{R}$ (ie: ...
1
vote
2answers
93 views

Proof of Convexity Using Quasiconvexity

Suppose $f_{1}, \ldots, f_{n},~n\geq 3$, are continuously differentiable functions defined on $\mathbb{R}$ such that for each $i\in \{1,\ldots,n\}$, we have: (i) $f_{i}(v_{i}^{0})=0$ and $f_{i}^{'}(...
6
votes
1answer
235 views

the continuity of argmin on convex funtion

Define $$x'=\text{argmin}_{x_1}f(x_1,\lambda),$$ where $f$ is a strictly convex function on $x_1$ and $\lambda$. I would like to ask if there is any theorem about the continuity of $x'$ w.r.t $\...
1
vote
2answers
28 views

Convexity of Certain Functions

Consider the set of functions: \begin{equation} f_n(t) := t^n e^{(\frac{c}{t^n})}, \end{equation} where $c$ is a non-zero real constant. I know that for $n=1$ $f_1(t)$ is convex on $(0,\infty)$ and ...
0
votes
1answer
20 views

Definitions of intrinsic core of convex set

Let $C$ be a convex subset of a vector space $V$. We consider two definitions of the intrinsic core of $C$. Definition 1. The intrinsic core of $C$ consists all points $c\in C$ such that for every $c^...
-1
votes
0answers
29 views

Definition of space by convex function [closed]

It is well know that it is possible to define a space by norm, e.g. lets say that the norm we are concentrating on is L3 norm, thus $C = \{\theta \in \Re^d \mid \| \theta \|_3 \leq 1\}$ where $d \in \...
0
votes
0answers
17 views

Equality case in the Prékopa-Leindler inequality.

in the paper 'Remarks on the conjectured log-Brunn-Minkowski inequality' by C. Saraoglou, the author uses the result (Lemma A. 3.) about the equality case in the Prékopa-Leindler inequality. For the ...
2
votes
1answer
195 views

Show that the graph of a convex function is above any tangent plane

In proving jensen inequality one use that the graph of a convex function is above any tangent plane. I've been reading Property of convex functions and Tangent line of a convex function. But what ...
5
votes
1answer
91 views

Is the smallest ellipsoid enclosing a convex set unique?

Let $S \subset \mathbb{R}^n$ be a convex set. Assume that it is bounded. We want to find an ellipsoid $E$ of smallest volume such that $S \subset E$. Is $E$ unique?
0
votes
0answers
11 views

Prove that a nest of sets has an empty intersection

Let $f$ be a real convex function and $S$ an arbitrary closed bounded subset of the relative interior of the effective domain of $f$. Let $B$ be a closed Euclidean unit ball. The nest of sets $$(S + \...
1
vote
1answer
1k views

convex hull function in matlab

Is there any way to compute the convex hull of a finite set of points in Matlab and gives the half-space representation as its result? I usually use a toolbox called MPT developed at ETHZ Zurich, but ...
0
votes
1answer
20 views

Convexity versus Strict Convexity

Let $u,v,w\in\mathbb{R}^n$ be three points that are not collinear. We define $$ \triangle(u,v,w):=\{\alpha u+\beta v+\gamma w:\alpha+\beta+\gamma=1, \alpha,\beta,\gamma\geq 0\}, $$ $$ [u,v]=:= \{tu+(...
1
vote
0answers
54 views

Analytical, numerical and graphical approaches to solve convex optimization problems?

I'm wondering if there are analytical approaches to solve these problems(I found these problems in a book by Stephen Boyd): minimize $f_0(x_1,x_2)$ subject to $2x_1+x_2\ge1$ $x_1+3x_2\ge1$ $x_1\...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
2answers
76 views

Easy interpretation of matrix multiplication with a set

I have just started learning convex optimization. I am having little bit difficulties in some notations. Currently I just encountered the following equation: $$ \boldsymbol{epi}(wf) = \left[ \begin{...
1
vote
1answer
76 views

Prove that $u$ is upper semicontinuous on $\Delta(0,\rho)$.

Let $u:\Delta(0,\rho)\rightarrow \mathbb{R}$ be a function such that $u(x+iy)$ is convex in $x$ for each fixed $y$, and convex in $y$ for each fixed $x$. Prove that $u$ is subharmonic on $\Delta(0,\...
0
votes
0answers
26 views

Interior of a solid self dual cone

Let $X$ be a real Hilbert space with a solid self dual positive cone $K$, that is, $\mathrm{int}(K)$ is non-empty and $K^{*}=K$. If $X$ is finite dimensional, I know that the $\mathrm{int}(K)$ = $\...
0
votes
0answers
10 views

Under which conditions discretization of convex\concave function is submodular?

Say, I have $f(x)$ with $x \in [0,1]$, then by discretization I mean $f(x_h)$ with $x_h \in \{0, h, 2h, \dots, 1\}$. I know about Lovasz extension, but it works in other way: given submodular ...
1
vote
0answers
14 views

Measure induced by subgradient of convex functional

I am trying to understand why the following defines a measure. Let $\phi : \mathbb{R}^d \to \mathbb{R}$ be a convex function. Define a measure $\mu$ on $\mathcal{B}(\mathbb{R}^d)$ by $$\mu(E) = \...
0
votes
0answers
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 ...
1
vote
1answer
66 views

Corollary 2.1 in Ekeland and Temam on lower semicontinuity

Why in Corollary 2.1 on page 10 (see the picture) from Ekeland and Temam book Convex Analysis and Variational Problems there is equality in (2.11), i.e why $$\forall u\in V,\quad \overline F(u)=\...
2
votes
0answers
15 views

convexity of a multivariable function

I have a function of the following type: $f(x_1,x_2,...,x_n)$ Each $x_i$ has domain $[0,\infty)$. The function is continuous and differentiable in each variable (It is an expectation of several ...
2
votes
2answers
1k views

proximal operator of infinity norm

What is the proximal operator of $\|x\|_\infty $? I know we have to take the subgradient and compute it but I am a bit stuck. Can anyone show me steps?
1
vote
1answer
28 views

Properties on proximal term

If the equation $x_i$-subproblem showed below is not strictly convex $\arg \min_{x_i}=f_i(x_i)+\frac{\rho}{2}\|A_ix_i+\sum_{j\neq i}A_jx_j^k-c-\frac{\lambda^k}{\rho}\|_2^2$ Why adding the proximal ...
1
vote
1answer
61 views

show the quadratic function $W(x_1,x_2,\ldots,x_n)=A\sum_{i} x_i^2+ \sum_{i\neq j} x_ix_j$ is quasi-concave

I have a quadratic function $W(x_1,x_2,\ldots,x_n)=A\sum_{i} x_i^2+ \sum_{i\neq j} x_ix_j$, with $x_i$ nonnegative and $A \in[0,1)$. And w.l.o.g. we can normalize $x_i's$ to between 0 and 1. In ...
1
vote
2answers
53 views

Optimization with box constraints - via nonlinear function

I have the following convex optimization problem over $\mathbb{R}^n$ with box constraints: $$\begin{align}\text{minimize }&\;f(x)\\ \text{subject to }&\;x \in [-1,1]^n\end{align}$$ I can see ...
3
votes
1answer
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 ...
18
votes
5answers
549 views

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 ...
2
votes
1answer
20 views

Dual polyhedron & dual cone

From Wiki: Def. of dual of polyhedral (polytope): polyhedra are associated into pairs called duals, where the vertices of one correspond to the faces of the other. EX: 2. Def. of dual ...