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)

1
vote
2answers
58 views

Jensen's inequality; what's the need for the probability measure?

Jensen's inequality states that if: $\mu$ is a probability measure on $\Omega$, $f$ is integrable function (on $\Omega$) and $\phi$ is convex on the range of f then: $\phi \left( ...
3
votes
1answer
45 views

Is $f(x)$ convex if $\log f(x)$ is convex?

One of the convex composition rules states that $h(g(x))$ is convex if $h(x)$ is convex and non-decreasing, and $g(x)$ is convex. Now I want to go the other way - I know that $\log(f(x))$ is convex ...
0
votes
0answers
51 views

Convex and continuous function on compact set implies Lipschitz

Let the function $f: C \rightarrow \mathbb{R}$ be convex and continuous, where $C \subset \mathbb{R}^n$ is a compact set. Prove or disprove that $f$ is Lipschitz continuous on $C$. Comments: If $f$ ...
2
votes
1answer
51 views

what is the closed form solution for $\min_x ||y-x||^2_2+\lambda ||x||_2$

$y$ and $x$ are vectors. $\|\cdot\|_2$ is Euclidean norm. In one paper I read, they say the closed form solution is $x=\max\{y-\lambda \frac{y}{\|y\|_2}, 0\}$. I don't know why $x$ need to be ...
3
votes
1answer
55 views

$f'$ decreasing everywhere but not defined in one point. Is $f$ concave?

Small issue: Suppose that $f:[a,b] \rightarrow \mathbb{R}$ is a continuous function, differentiable except on a finite set of points, let say in one point $y$. For $x<y$ and $x>y$ we have ...
0
votes
0answers
31 views

Is the set of probability density functions convex?

Given is the set of probability density functions defined as $P:=\left \{ p(x)\mid p(x)\, is\ a\ probability \ density \ function \right \}$ Is $P$ a convex set? I am not sure that here i have to ...
0
votes
1answer
51 views

What is the closed form for this norm $\|Z\|=\sup_{\|u\|=1,\|v\|=1} u^TZv$?

I read a paper, which has the equation above $\|Z\|=\sup_{\|u\|=1,\|v\|=1} u^TZv$. Is this a well known norm and what is the closed form for this norm. Also what does this norm describe? Thanks in ...
1
vote
0answers
19 views

Sufficient condition for self-concordance?

I've revised a previous question that was ill-formed. Consider the following two definitions. Def'n 1 (Lipschitz continuity of Hessian): A function $f:\mathbb{R}^n\to\mathbb{R}$ is said to have a ...
1
vote
0answers
35 views

Log convexity and the gamma function

I am writing an essay on the gamma function. I have learnt and understood convex theory and how the log-convex nature of the gamma function makes it a unique extension of the factorials ...
8
votes
2answers
83 views

Can a “continuous” convex combination not be element of the convex hull?

Short version of question: can a "continuous" convex combination not be element of the convex hull? I am not a mathematician, so please excuse me if I am not precise. I consider first, e.g., 4 ...
1
vote
1answer
31 views

Boundedness of sublevel sets of an integral function

Let $f: \mathbb{R} \rightarrow \mathbb{R}$ be an increasing function, i.e., $x<y \Rightarrow f(x) < f(y)$ for all $x,y$. Assume that $\lim_{|x| \rightarrow \infty} |f(x)| = \infty$ Define ...
3
votes
0answers
53 views

convex polygon triangulation

Suppose we have given a convex polygon on $n$ vertices $P= \{ a_1, \cdots , a_n \}$ in the plane (arranged clockwise). How can we prove that there exist atleast two indices $i$ such that circle ...
1
vote
1answer
52 views

Is this $\underset{x<1,y<1}{\sup}f(x,y) = \underset{x<1}{\sup} \underset{y<1}{\sup}\ f(x,y) $ correct?

$\underset{x<1,y<1}{\sup}f(x,y) = \underset{x<1}{\sup} \underset{y<1}{\sup}\ f(x,y).$ Intuitively, I think the above equation holds for all $f(x,y)$. Am I right?
0
votes
0answers
30 views

A supremum problem

Let $a=\underset{\|u\|_c\leq 1, \|v\|_r\leq 1}{\sup}v^TY^Tu$. If $\lambda<a$, $\underset{u_m, v_m}{\sup}v_m^TY^Tu_m-\lambda\|u_m\|_c\|v_m\|_r=+\infty$. While if $\lambda > a$, then ...
1
vote
0answers
58 views

A power inequality with convexity / majorization flavor

Let $a,b,c,d\in\mathbb R_+$ be nonnegative reals. Define the function $f:\mathbb N_+\to\mathbb R$ as $$ f(k):=\left(\frac{(a+b+c+d)^k+(a-b+c-d)^k-(a+b-c-d)^k-(a-b-c+d)^k}{4}\right)^{1/k} $$ Is it ...
2
votes
0answers
20 views

Duality between $Ax<b$ and another system, but Gordan's just misses

I am trying to show that $$Ax < b$$ Is feasible iff $$ A^T y =0 , b^Ty + s = 0, (y,s) \ge 0, (y,s) \ne 0$$ Is infeasible. Work So Far Now when I try to hit this with Gordan's Lemma I seem ...
0
votes
0answers
34 views

How can the ADMM algorithm be distributed?

I am reading Boyd's tutorial paper on ADMM. One question I had after I reached the formulation of the algorithm on pp.14 is: how can the alternating or sequential fashion of x-minimization step and ...
1
vote
3answers
39 views

$sup_x [ f(x)+sup_x g(x)]= sup_x[f(x)+g(x)]$?

$sup_x [ f(x)+sup_x g(x)]= sup_x[f(x)+g(x)]$ is the statement correct? Can I prove like this: $sup_x [ f(x)+sup_x g(x)] = sup_x[f(x)] + sup_x[g(x)] = sup[f(x)+g(x)]$.
0
votes
1answer
17 views

Showing that $ye^{x/y} = \max_{\alpha>0} \left[ \alpha(x+y) - y\alpha \log(\alpha) \right]$

In my optimization textbook, the author states without proof that $$ ye^{x/y} = \max_{\alpha>0} \left[ \alpha(x+y) - y\alpha \log(\alpha) \right]. $$ To be honest, this does not seem very obvious ...
0
votes
0answers
17 views

convex envelop on a unit ball

What does that exactly mean by "the function $g$ (continuous) is the convex envelop of the function $f$ (discrete) on a unit $\ell_\infty$ ball". I understand the part of "a function being the convex ...
8
votes
2answers
119 views

Opening and closing convex sets

It seems true that, given $K \subseteq \mathbb{R}^n$ a convex set with $K^\circ \neq \emptyset$, then $\overline{K^{\circ}} = \overline{K}$ and $\left ( \overline{K} \right )^\circ = K^\circ$. I am ...
1
vote
2answers
31 views

Tangents of a Strictly Convex Fuction

Let $f:\mathbb R \rightarrow \mathbb R$ be differentiable and strictly convex. Is it true that $x,y \in \mathbb R$ and $x \neq y$ imply \begin{equation} f'(x)(y-x) <f(y) - f(x) \end{equation} If ...
0
votes
1answer
35 views

Smallest convex body inscribed in $n$-cube with all its symmetries? [closed]

Consider the cube $[-1,1]^n$ and convex bodies inscribed in it, such that all these bodies have the symmetries of the cube. Is there a lower bound on the volume? Which shapes attain it?
0
votes
0answers
19 views

Smallest volume of a centrally symmetric convex body inscribed in $n$-cube

We consider several centrally symmetric convex bodies inscribed (intersecting all its facets) in an $n$-cube , $[-1,1]^n$, with volume $2^n$. For instance, such a crosspolytope (its polar dual) has ...
2
votes
2answers
27 views

Strictly Convex Implies Invertible Gradient?

If $f:\mathbb R^n \rightarrow \mathbb R$ is strictly convex and continuously differentiable, does this imply that $\nabla f$ is a one-to-one mapping? To be precise, can we say that $x, y \in \mathbb ...
0
votes
0answers
19 views

Applying homogeneity for a norm to prove triangle inequality

I am hoping to have someone help explain to me the steps of this proof of the triangle inequality for $L^p$ spaces, $p\ge 1$. Specifically the first two applications of the homogeneity property don't ...
0
votes
0answers
50 views

Computing Direction of Descent for General Fermat Problem

Suppose that $k \geq 3$, and let $X_1, \dots , X_k$ be $k$ points in $\mathbb{R}^2$, and let $w_1, \dots , w_k$ be $k$ positive real-valued constant weights. Given this, consider the function $g(p) = ...
1
vote
0answers
48 views

Show Direction of Steepest Descent is Unique

If f is a proper convex function and x is in the interior domain(f), how would one go about proving that the direction of steepest descent at x is unique? I intuitively get it, but don't get how one ...
0
votes
1answer
19 views

Functions with convex/concave potential

A function $f:A\to A$ has convex/concave potential if there is $F:\mathbb{R}^n\to \mathbb{R}$ such that $\nabla F=f$, and $F$ is convex/concave. Let $A\subset \mathbb{R}^n$ be a compact set. Are ...
0
votes
0answers
30 views

Supremum of a Sequence of convex and closed functions {f_i} is also closed [closed]

I feel like this is an obvious question, but I am having difficulty formally proving it. Given a set of convex and closed functions {f_i(x)} and f(x) is defined as the sup f_i(x), then how does one ...
1
vote
0answers
29 views

Conflict with definition of “face”

I am given this definition of face from Convexity: An analytic viewpoint: Definition: A face of a convex set $P$ is a set $F\subsetneq \overline{P}$ such that for every $x,y\in\overline{P}$ and for ...
0
votes
0answers
15 views

Convexity of Maximum Inscribed Ellipsoid Problem

I am confused about the problem of finding the ellipsoid of maximum volume inscribed in a polyhedron as discussed in section 8.4.2 of Convex Optimization by Boyd and Vandenberghe. I've followed the ...
3
votes
2answers
33 views

A caracterization of convexity in $\mathbb R^n$

Let $C$ be a closed subset of $\mathbb R^n$ such that $$\forall x,y \in C, (x,y)\cap C \neq \emptyset$$ where $(x,y)=\{(1-t)x+ty, t\in (0,1)\}$ Prove that C is convex A quick drawing shows ...
1
vote
1answer
16 views

Convex and Symmetric subset of a Banach space

Let X be a Banach space and A be a convex and symmetric subset of X. Is it true then that the closure of A will be a subset of 2A=A+A? I doubt that this always holds, but can't seem to find a ...
0
votes
1answer
34 views

Is there a geometric interpretation for a function's $\alpha$-sublevel set?

In Boyd and Vandenberghe's "Convex Optimization": The $\alpha$-sublevel set set of a function $f:\mathbb{R}^n \rightarrow \mathbb{R}$ is defined as $$C_\alpha=\{x \in \mathbf{dom} ...
3
votes
1answer
44 views

Jensen's inequality in measure theory

Here cites its original claim from http://www.math.tau.ac.il/~ostrover/Teaching/18125.pdf. Theorem 3.1 Jensen's Inequality Let $(X,\mathcal{M},\mu)$ be a probability space (a measure space ...
0
votes
1answer
40 views

Prove an inequality through convexity

I'm trying to prove $-hp + ln(1 - p + pe^h) \le (1/8)h^2$ for all $h > 0$ and $0 \le p \le 1$. After moving the term $-hp$ to the RHS and exponentiating we get $1 - p + pe^h \le e^{(1/8)h^2 + ...
0
votes
1answer
18 views

Proving inequality from convexity of function

I am having trouble proving the following inequality for all $x,y>0$ from "The Mathematics of Nonlinear Programming" by Pressini, Uhl. The book states that it follows from the convexity of an ...
0
votes
0answers
32 views

What algorithms are applicable to solve a inequality constraint Quadratic Optimization?

Suppose that we have a quadratic optimization problem $$(QP) \qquad \min \lbrace\frac{1}{2}x^TQX+ q^TX\rbrace $$ s.t. $$AX=a;$$ $$BX\le b;$$ $$X \ge 0;$$ where $Q \in \mathbb{R}^{n \times n}$ ...
3
votes
1answer
41 views

A convex real function is continuous - can we generalize?

There is a well-known theorem $\newcommand{\RR}{\mathbb{R}}$ Let $f: (a,b) \rightarrow \RR$ be a convex function. Then $f$ is continuous on $(a,b)$ The proof I know makes use of the fact that ...
2
votes
1answer
39 views

Convolution of convex function and Gaussian is convex

Let $f:\mathbb{R}\to\mathbb{R}$ be a convex function, i. e., for all $x_1, x_2 \in \mathbb{R}$ and $t \in [0, 1]$, $$ \qquad f(tx_1+(1-t)x_2)\leq t f(x_1)+(1-t)f(x_2).$$ I want to prove that the ...
4
votes
1answer
36 views

Classification of boundary points of convex sets in $R^n$

I'm trying to prove the following: Let $P\neq R^n$ be a convex set containing an $R^n$ neighborhood of $0$. Then $x\in\partial P\iff (\lbrace tx: 0\leq t < 1\rbrace\subset P^\circ)\wedge(x\not\in ...
0
votes
1answer
55 views

Given a convex function $f(x)$, is $xf'(x)$ also convex?

Given a convex function $f(x)$, I'm trying to proof that $g(x) = xf'(x)$ is also convex. I have found neither a proof nor a counterexample so far. A function $g(x)$ is convex iff $g''(x) \ge 0$. ...
0
votes
0answers
32 views

Question regarding “distance function” in convex spaces.

Assume that we have a convex space $K < \mathbb{R}^n$ and a point $a \not\in K$. I need to show that there is a function in the dual, $f\in \mathbb{R}^n$ such that $f(a)\geq f(x)$ for all $x\in K$. ...
1
vote
0answers
41 views

non negativity of an sequence alternating series

Assume we have the positive real number $a_1,...,a_n$, and variable $x \in \Bbb R^+$, I am trying to prove the following to be positive (or at least non negative): $$ \frac{1}{x^3} - \sum_{i=1}^{n} ...
0
votes
0answers
15 views

The $d$-skeleton of a polytope is strongly connected

A polytope is the convex hull of a finite set of points in $\mathbb R^n$. The $d$-skeleton of a polytope is the set consisting of faces of dimension at most $d$. I would like to show that every ...
0
votes
0answers
31 views

hyperbolic constraint in SOCP

I learned that any hyperbolic constraint can be transformed as second order cone constraints. Such as if the constraint is, $x^2\leq w$ the second order constraint would be $$ ||[2x,w-1]||_2 \leq w+1 ...
0
votes
0answers
12 views

Decomposition of convex functions

Under what conditions is it possible to decompose a convex real-valued function $f$ and write it as an integral of the simple functions $g(x;w)=\max(x-w,0)$ and $h(x;v)=\max(v-x,0)$, where the ...
1
vote
0answers
46 views

why dual of $l_1$ norm is $l_\infty$ and vice versa

This might be a very dumb question but I am having a hard time to understand why dual of $l_1$ norm is $l_\infty$ and vice versa. The dual of a norm is denoted $\lVert\cdot\rVert_*$, defined as $$ ...
1
vote
0answers
27 views

Efficiency of quasiconvex optimization

Summary: Could we minimize quasiconvex objectives in polynomial time? Whenever an objective function of an optimization problem can be formed as a convex function, this is considered as victory. ...