Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [convex-analysis]

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.

0
votes
0answers
13 views

Question about dual cone

Update: I have solved this problem, thanks to this inspiring post: Polar cone of the Polar cone of $K$ a closed convex cone is again $K$. I will add my solution later. ================================...
3
votes
1answer
54 views

if $f$ convex, $f$ has bounded first derivative iff $f$ uniformly continuous

Formal statement: if $f: \mathbb{R} \rightarrow \mathbb{R}$ is convex and differentiable, it is uniformly continuous iff there exists some $a > 0$ such that $|f'(x)| \leq a$ for all $x$. One ...
-1
votes
0answers
22 views

Limit of convex combinations? [on hold]

Let $x_\alpha \in \mathbb{R}$ be a possibly uncountable set i of extreme points. Take the convex hull of that set. $\sum_{i=1}^n \alpha_i x_i$ with $\sum_{i=1}^n \alpha_i = 1$ and $\alpha_i \geq 0$. ...
1
vote
0answers
13 views

Separation of two cones using hyperplane generate by some facet.

Let $C_1$ and $C_2$ two polyhedral cones (pointed, that is, with an only vertex on $0\in R^n$), we suppose that $\dim(C_1)=\dim(C_2)=n$. If $$\mbox{relative interior}(C_1)\cap \mbox{relative interior}...
-2
votes
0answers
14 views

Minimizing the area under perimeter and convexity constraints [on hold]

I d like to ask a question about shape optimization. Let K a convex of IR^2. Is there a continuous mean to perturb locally K while fixing its perimeter and keeping it convex and making it's volume ...
3
votes
1answer
35 views

How to approximate a 3x3 linear inequality constraint

Let $M$ be a $3\times3$ symmetric matrix (6 independent variables). The following constraint: $$M \succeq 0$$ is a convex linear matrix inequality (LMI), meaning that M is positive semidefinite. I'...
0
votes
0answers
17 views

Projection of Shrinked Vector

Assume $\boldsymbol{e}_1$ and $\boldsymbol{e}_2$ are a set of orthonormal basis for $\mathbb{R}^2$. There is a real vector $\boldsymbol{u}$ such that $|\boldsymbol{e}_2^T\boldsymbol{u}|\le C |\...
0
votes
0answers
22 views

How to prove that the set of all probability distributions is convex set?

Suppose we have a set $X=\{1,...,n\}$ where $n$ is a natural number. Let $\Delta(X)$ be the set of all probability distributions over $X$. Then $\Delta(X)$ is a convex set. How do we interpret ...
0
votes
1answer
22 views

How to show that product over sum function is log concave?

In one of the problem (3.49(c)) of Convex Optimization book (By Boyd and Vandenberghe) it is asked to show that product over sum function $$g(x)=\frac{\prod_{i=1}^nx_i}{\sum_{i=1}^nx_i}$$ is log ...
0
votes
0answers
15 views

level set strongly convex and smooth functions

Let $f: \mathbb{R}^N \to \mathbb{R}$ be a $\alpha$-strongly convex and $\beta$-strongly smooth function, i.e., $$ f(x) + \langle\nabla f(x), y- x\rangle + \frac{\alpha}{2}\|y-x\|^2 \leq f(y) \leq f(x) ...
0
votes
1answer
41 views

Notation: Show that the function $f^2/g$ is convex.

I am afraid I am confused about notation in the following question. Suppose that $f:\mathbb{R}^n \longrightarrow \mathbb{R}$ is nonnegative and convex, and $g:\mathbb{R}^n \longrightarrow \mathbb{R}$ ...
2
votes
1answer
30 views

Characterization of the epigraph of a lower semi continuous fuction

The goal is to prove that if epigraph of a function $f:X \rightarrow \mathbb{R}$ is closed then it is lower semicontinuous. The epigraph of $f$, $\operatorname{epi} f$ is given as $$ \operatorname{epi}...
1
vote
0answers
16 views

Log concavity of product over sum function

In the solution manual of Convex Optimization book (by Boyd and Vandenberghe) the double derivative of product ovee sum function over a line segment is given as follows $$-\sum\frac{v_i^2}{(x_i+tv_i)^...
0
votes
0answers
15 views

Strongly convex with respect to norm of Ellipsoid

In $\mathbb R^n$ with Euclidean norm $\|\cdot\|$, a convex set $\Omega$ is set to be strongly convex with respect to the norm $\|\cdot\|$ if there exists $\alpha>0$ such that for any $x,y\in \Omega$...
0
votes
0answers
15 views

Prove underwhich condition a nondifferentiable function is strictly convex.

I want to know that how to select the parameter of MCP function to make the a $l_2$-norm term add the MCP function is convex. The function $Q(\mathbf{x})=\|\mathbf{y}-\mathbf{A}\mathbf{x}\|_2^2+\sum_{...
1
vote
1answer
54 views

Does projection of a simplicial subdivision of a simplex onto a lower-dimensional face generate a subdivision of that face?

My goal is to prove that any simplicial subdivision (or triangulation) of a simplex generates a simplicial subdivision on the faces of the original simplex. Formally, let $n,k$ be integers such that $...
-1
votes
1answer
32 views

concave, not strictly concave

How can I prove that $\sqrt{xy}$ is concave, not strictly concave? I tried to derivative twice $f''(x)$, but it becomes negative which is the definition for a strictly concave.
0
votes
0answers
27 views

the sum of many polytopes has round shape.?

I generate 1000 polytopes $P_1, \ldots, P_{1000}$ in $\mathbb R^{n}$, each of them has $m$ vertices that are $m$ rows of an $m\times n$ matrix $A_i={\sf rand(m,n)}$. Then I take their sum $P=P_1+\...
0
votes
1answer
28 views

A real-valued continuous function on a convex set $C$ in $\mathbb{R}^{n}$ is convex if it is convex on the relative interior of $C$.

I am self-studying a book named "Geometric methods and Optimization problems" by V. Boltyanski, and this problem is an exercise in page 14 of that book. Let $f$ be a real valued continuous function ...
0
votes
0answers
24 views

Algebra behind equidistant subdivision of unit simplices

Let $k\in\mathbb Z_+$ and define the $k$-dimensional unit simplex: \begin{align*} \bigtriangleup_k\equiv\left\{(\lambda_1,\ldots\lambda_{k+1})\in\mathbb R^{k+1}\,\Bigg|\,\lambda_1,\ldots,\lambda_{k+1}\...
1
vote
1answer
17 views

How to prove that the optimal point for a quasilinear function lies in its extreme points

I was reading an article about the robust optimization of the MNL choice model,and in one of its proofs it uses the point that if we're tring to solve the minimun of a quasilinear function ,which is ...
1
vote
0answers
23 views

Why is the Fenchel conjugate of a piecewise linear function piecewise linear?

Consider the function: $$ f: x \mapsto \begin{cases} a_1 x + b_1 & x \le \frac{b_1 - b_2}{a_2 - a_1} \\ a_i x + b_i & \frac{b_{i-1} - b_i}{a_i - a_{i-1}} \le x \le \frac{b_i - b_{i+1}}...
1
vote
0answers
30 views

Show convexity in two variables

Let $h:\mathbb{R}^n \rightarrow \overline{\mathbb{R}}$ be a convex function. We define $f:\mathbb{R}\times\mathbb{R}^n\rightarrow \mathbb{R}$ as $f(t,x)=\left\{\begin{matrix} t h\left ( x/t \right ) ...
0
votes
1answer
55 views

If the boundary of $C$ is convex, when is the interior of $C$ empty? (Study the boundedness of $C$)

I believe my ideas are correct, but I have a feeling I am expressing them incorrectly in the proof. Any insight, remarks, or corrections are immensely appreciated. Thank you. Note: $\text{cl}(X)$, $\...
2
votes
1answer
48 views

Convex function in $R^n$ - does existence of minimum in every direction imply existence of global minimum?

Let $f:R^n\rightarrow R$ ($n>1$) be a convex function satisfying condition: $\forall x\in R^n \ \exists t_0 = \arg\min\limits_{t\in R} f(tx).$ Is it true that there exists point $x_0\in R^n$ ...
0
votes
0answers
37 views

Show that a ball is contained in at least one overlapping convex set

Consider a convex domain $\Omega\subset\mathbb R^n$ and a collection of convex sets $A_i\in\Omega$, $i=1,2,...,N$, whose union contains $\Omega$. Define the $i$-th overlap $\kappa_i$ as the largest ...
1
vote
1answer
68 views

How to rigorously show that maximum of linear functions is piecewise linear?

Note: This is an extremely basic question, which is why the fact I can't figure out the answer easily concerns me. This problem is from Boyd and Vandenberghe. Consider $f: \mathbb{R} \to \mathbb{R}$...
1
vote
0answers
28 views

Lower approximation of convex function using maximum of hyperplanes

Suppose we are given a convex function $f: \mathbb R^n \rightarrow \mathbb R$ on a bounded domain $\mathcal X$ to approximate using the maximum of supporting hyperplanes at some grid points; denote ...
0
votes
1answer
37 views

Closed-form derivative of a matrix function

Let $A$ be an Hurwitz stable matrix (that is, the real part of the eigenvalues of $A$ is strictly negative) and $Q$ be a positive semidefinite matrix ($Q\ge 0$, for short). Let $P$ denote the solution ...
1
vote
1answer
22 views

An example of infimal convolution for nonconvex functions.

Let $E$ be a normed vectorial space. Given two functions $\phi,\psi:E\to(−\infty, +\infty]$, the inf-convolution of $\phi$ and $\psi$ is defined as follows: for every $x\in E$, let $$ (\phi\nabla\psi)(...
0
votes
0answers
22 views

Properties of Splitting Convex Sets

Say I have a convex set of $n$ dimensional polynomials that satisfy certain properties $P$. I then want to split $P$ into two disjoint sets $P_U, P_S$ such that $P_S\cup P_U = P$ and $P_S \cap P_U = ...
0
votes
0answers
7 views

Extension of concave function definition with 3 non-negative constants: a+b+c=1

I am trying to prove the following: For a concave function $f:\mathbb{R}^3 \to \mathbb{R}$, and $a,b,c \in \mathbb{R}$ such that $a\geq0,b\geq0,c\geq0$ and $a+b+c=1$, the following holds: $f(ax+by+...
1
vote
2answers
64 views

Characteristics of a convex set if its boundary is convex

If $A$ is a convex set in $\mathbb R^n$, when is its boundary convex as well? I think $\partial A$ must be either contained in a hypersurface or must equal $\mathbb R^n$.
1
vote
1answer
28 views

Alternating Projection Convergence Proof

Following the Convergence proof (on page 3) from Alternative Projection paper: https://web.stanford.edu/class/ee392o/alt_proj.pdf I know intuitively how to show that both sequences {$ \left\lVert y_k ...
4
votes
1answer
43 views

Is a positive, monotone and sub-additive function concave?

Consider a function $f : [0, 1] \to \mathbb{R}^+$ such that $f(0) = 0$ and $f(x) \leq f(y)$ for all $ x \leq y$ (i.e $f$ is monotone). Additionally, I also restrict $f$ to be a sub-additive function i....
1
vote
0answers
37 views

Prove that a cone is convex if and only if it is closed under addition.

Let $K \subset \mathbb{R}^n$ be a cone. A cone is defined as: $(\forall x\in K) \wedge (\forall \lambda>0) \Longrightarrow \lambda x\in K$. Prove that: $K$ is convex $\Longleftrightarrow K$ is ...
0
votes
2answers
27 views

Objective function from a set indexed with permutations

The question posed is as follows: Prove that $f: \mathbb{R}^n \to \mathbb{R}$ defined by $f(x) = \operatorname{min}_{\sigma} \sum_{i=1}^{n-1} |x_{\sigma(i)}-x_{\sigma(i+1)}|,$ where the minimum ...
0
votes
0answers
10 views

Affine hull and the subspace

Please clarify a simple doubt that I have. I know that a affine set $X \subseteq \mathbb{R}^n$ contains $0 \in \mathbb{R}^n$ is a subspace in $ \mathbb{R}^n$. So $aff$$\{0,x_1,x_2, ... ,x_n\}$ = $...
0
votes
1answer
25 views

Is the sum of square distance of three surfaces convex?

If I have $3$ convex or concave surfaces $E_0(x,y), E_1(x,y), E_2(x,y)$ that all intersect at $1$ and only $1$ point $(x^*, y^*)$, is it necessary that the function $$d(x,y)=\sum_{0\leq i<j\leq 2} (...
3
votes
1answer
30 views

Jensen's inequality for integral without l.s.c. assumption

I start with the following lemma Lemma 1.(Fundamental inclusion for convex sets) Let $C$ be a closed subset of $\mathbb{R}^n$. Then, $C$ is convex if and only if \begin{equation*} \int_\Omega f\;...
0
votes
1answer
30 views

Boundedness of sublevelsets of strongly convex functions implies boundedness of second-order gradient

In page 460 of Stephen Boyd's "Convex Optimization", he described a property of strongly convex functions: "The inequality (9.8) (i.e. $f(y) \geq f(x) + \nabla f(x)^T (y - x) + \frac{m}{2} \|y - x\|...
3
votes
2answers
44 views

Proving $\max\{f,g\}$, $\sum x_i^2$ and $e^{f(x)}$ are convex functions

Verify if the functions below are convex. a) $f(x) = \max \{g(x),h(x)\}$ where $h$ and $g$ are convex. b) $t(x) = \sum_{i=1}^n x_i^2$ c) $s(x) = e^{f(x)}$, $f:\mathbb{R}^n\to\mathbb{...
1
vote
0answers
20 views

$f\in C^1$ convex, if exists $x^*\in S$ such that $\nabla^t f(x^*)(y-x^*)\ge 0$ then $x^*$ is a global minimizer of $f$

Let $f\in C^1$ convex defined in a convex $S$. If there exists $x^*\in S$ such that for all $y\in S$ it is true that $$\nabla^t f(x^*)(y-x^*)\ge 0$$ then $x^*$ is a global minimizer of $f$ in $S$ I ...
0
votes
0answers
18 views

Applications of Motzkin theorem on convex set?

A theorem attributed to Motzkin states that if $ C \subset \mathbb R^n$ is a nonempty closed set, then the following are equivalent: $C$ is convex The distance function $\mathrm{d}_C$ is ...
2
votes
1answer
143 views
+100

Stable strict local minimum implies local convexity

Let $\bar{x}\in\mathbb{R}^n$ and $f:\mathbb{R}^n\rightarrow\mathbb{R}$ be a $C^2$ function. We have known that if $\nabla f(\bar{x})=0$ and $\nabla^2f(\bar{x})>0$, i.e. $\nabla^2f(\bar{x})$ is ...
1
vote
1answer
88 views

$f$ convex $\iff$ $f(y)\ge f(x)+\nabla f(x)(x-y)$

Prove $f$ convex $\iff$ $f(y)\ge f(x)+\nabla f(x)(x-y)$ $$\rightarrow$$ $$f(\lambda x + (1-\lambda)y) \le \lambda f(x) + (1-\lambda)f(y)$$ $$\nabla f(\lambda x+(1-\lambda)y)(x-y)\le f(x) - f(y)$$ $...
0
votes
1answer
18 views

Convex subset with positive measure.

I guess that the following statement holds true. Let $K$ be a convex subset of $\mathbb R^n$ with a positive Lebesgue measure. Then the interior of $K$ is non-empty. Is a reference or a short proof ...
1
vote
1answer
25 views

Large Deviation Principle

I have been reading Amir Dembo's book, and at the very beginning, I found this result that came across and unfortunately, I cannot derive it by myself. So, I'm looking for some help. It happens that ...
1
vote
1answer
58 views

$f(t)=(\text{det}(A+tB))^{\frac{1}{d}}$ is concave if $f(t)\leq f(0)+tf'(0)$?

Let $A$, $B$ be $d$ by $d$ matrices where $A$, $A+B$ are symmetric positive semi-definite matrices and $\text{det}B=0$. $f(t)=(\text{det}(A+tB))^{\frac{1}{d}}$ is my function where $t\in[0,1]$. If $...
2
votes
3answers
47 views

To be concave on $[0,1]$, $f(t)\leq f(0)+tf'(0)$ is enough?

Suppose $f(t)>0$. $f(t)\leq f(0)+tf'(0)$ if and only if $f$ is concave over $[0,1]$. Is the above stetement true? There must be a counterexample in my opinion.