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 (1)

0
votes
0answers
28 views

Extreme points by intersection of extreme rays and hyperplane

I just met one question and have no idea about the proof, hope someone can give me some ideas on how to attack this question. Given a graph $G=(V,E)$ with $|E|=n$. Define a set $S$: ...
1
vote
1answer
36 views

$\mathrm{Prox}_{f}(x)$ and $\mathrm{Prox}_{af}(x)$

Let $a\in \mathbb{R}$, and $f$ is a convex function $f: \mathbb{R}^n\rightarrow \mathbb{R}$. $\mathrm{Prox}_{f}(x)=y_1$ and $\mathrm{Prox}_{af}(x')=y_2$. Because I know $\mathrm{Prox}_{f}(x)$. And ...
0
votes
0answers
15 views

Effect of proximal projection using a divergence measure, on the maximizer of the function

Suppose we have a probability distribution $p(\mathbf{x})$ and we know : $$ \mathbf{x}^* = \arg\max_{\mathbf{x}} p(\mathbf{x}) $$ Suppose we do a projection of this distribution onto another family ...
0
votes
1answer
23 views

Dual of dual cone of nonconvex closed cone

let $K$ be a nonconvex closed cone, then $K^{**}=conv(K)$ should this hold? I am not quite sure about it. Thanks.
1
vote
1answer
33 views

convex closed and unclosed functions and (lower semi)continuity

I'm grappling a bit with lower semicontinuity and convex functions. Let me consider convex functions as functions to $\mathbb{R}$ and not to $\mathbb{R}\cup \{\pm\infty\}$. By Rockafellar's book ...
0
votes
1answer
60 views

The conjugate relation between two functions.

Suppose $K\in \mathbb{R}^{m\times n}$, $x\in \mathbb{R}^n$ and $y\in \mathbb{R}^m$. Let a function $F: \mathbb{R}^m \rightarrow \mathbb{R}$, $F(y)$. Let $y=Kx$, $G(x)=F(Kx)$. Suppose $G(x)=F(Kx)$, ...
1
vote
0answers
40 views

How to show this converges in probability

$A_n(s)$ is a sequence of convex random functions defined on an open set $S\in \mathbb{R}^p$ which converges in probability to some $A(s)$ for each $s$. I'm trying to show that $\sup_{s\in K} \big| ...
1
vote
1answer
29 views

Equality constrained Quadratic Program

Consider the QP $$ x^* = \arg \min_{\displaystyle x \in \mathbb{R}^n{\geq 0}} \ \frac{1}{2} x^\top P x + q^\top x \ \text{ sub. to: } A x = b, $$ where $P \succ 0$. Without the non-negativity ...
0
votes
1answer
31 views

Are there necessary and sufficient conditions for Krein-Milman type conclusions?

This, the third of three self-answered questions, contains a proof of necessary and sufficient conditions for Krein-Milman type conclusions. The first question is here. The second question is here. ...
0
votes
1answer
16 views

Conditions for augmenting a collection of sets so that the new sets are small but the hull is large?

This is the second of three self-answered questions which will culminate in a proof of necessary and sufficient conditions for Krein-Milman type conclusions. The first question is here. The third ...
0
votes
1answer
62 views

Convexity of LASSO

I would like to know if some variables in design matrix are correlated then LASSO is convex or not. If you give me a proof for convexity of LASSO and ADAPTIVE lasso, I will be thankful. LASSO is ...
1
vote
0answers
66 views

When do partial subgradients give a subgradient?

I'm looking for sufficient conditions that guarantee that partial subgradients of a convex, lower-semicontinuous functional $f:X_1\times X_2\rightarrow\overline{\mathbb{R}}$ form a subgradient of $f$. ...
0
votes
1answer
35 views

Are there necessary and sufficient conditions so that every element in a partially ordered set is either the least element or in the upset of an atom?

This is the first of three self-answered questions which will culminate in a proof of necessary and sufficient conditions for Krein-Milman type conclusions. The second question is here. The third ...
1
vote
1answer
70 views

Strictly convex unit balls in $L^p$

I need to show that if $1<p<\infty$, then the unit ball is strictly convex in $L^p$, that is, $||\lambda x+(1-\lambda)y|| < 1$ whenever $||f|| = ||g||=1$ and $\lambda \in (0,1)$. I tried ...
3
votes
2answers
164 views

Gradient-descent algorithm always converges to the closest local optima?

Assume $f(\vec x)$, which is Lipschitz continuous, has two local optima $\vec x_1^*$ and $\vec x_2^*$( $\vec x_1^*$ is the global minimum). We start the gradient-descent algorithm from $\vec x_0$ and ...
0
votes
1answer
20 views

On the Composition of simple Projections

Consider the compact convex set $X = \{ x \in \mathbb{R}^n \mid x \geq 0, \ \underline{1}^\top x = 1 \}$. I am wondering if the projection onto $X$ is the composition of the projection on $[0,1]^n$ ...
0
votes
0answers
16 views

Show that E(g(T-p)) < E(g(S-P) for any convex function g if T and S are estimators of p

The more detailed question. I'm kinda having some trouble starting out with answering this question. My initial approach would be to g(x)= x^2 since that is a convex function and find the expected ...
1
vote
1answer
38 views

Quadratic programs: is the projection onto constraints optimal?

Consider the Quadratic Program $$ x^* := \arg \min_{ x \in X } \ \{ x^\top x + c^\top x \} \ \text{ sub. to: } Ax=b $$ where $X \subset \mathbb{R}^n $ is a non-empty, convex, bounded polyhedron. ...
0
votes
1answer
18 views

something about convex set

Let $M$ be a convex subset in $\mathbb R^n$ and $\partial M=\emptyset$. Then $M=\emptyset$ or $\mathbb R^n$. This can be deduced by Theorem Let $M\subset X$ with $\partial M=\emptyset$ and $X$ is ...
0
votes
1answer
16 views

Establishing convexity of a function

Let $\theta \in \Theta \subset \mathbb{R}^k$. I have the following objective function $$ F(\theta):=||\max(0,f_1(\theta)),...,\max(0,f_n(\theta))||^2 $$ where $||\cdot||$ is the Euclidean Norm and ...
2
votes
1answer
22 views

Proving that $0 \in A \implies h_A = j_{A^\circ}$

Where $h_A$ is the support function of $A$ and $j_{A^\circ}$ the Minkowski functional of the polar set of $A$ There is a "proof" in my course which I don't understand: " Let $x \in A$ and $t>0$ ...
1
vote
1answer
34 views

Projection onto convex set defined by $\|\mathbf{t} -\mathbf{W}^T\mathbf{y}\|^2 \leq k$

I want to use the method of Projections Onto Convex Sets, and for the problem at hand I need to find a closed form solution for $\mathbf{P}_C$, the projection onto set $C$, defined as: $$C = \{ ...
2
votes
1answer
59 views

Existence of global minimum

Could someone help me with this problem? Let $C$, $D$ convex and closed sets such that the intersection is empty. I want to show that the function $f: \mathbb{R^n} \to \mathbb{R}$ defined by $f(x) = ...
4
votes
1answer
46 views

Is the set of convex bodies include in a closed ball compact?

I consider the set $\mathcal{K}_B$ of convex bodies (convex and compact) which are include inside the unit closed ball of $\mathbb{R}^d$. I endow this set with the Hausdorff distance. Is it compact?
0
votes
3answers
63 views

A convex function has a lower bound?

Suppose that $f=f(x)$ is strictly convex for $x\in\mathbb{R}$, i.e. there exists $\epsilon>0$ such that $f''(x)\geq\epsilon>0$ for $x\in\mathbb{R}$. Does there exist $\delta>0$ such that ...
0
votes
1answer
201 views

convex hull function in matlab

Is there anyway 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 ...
2
votes
0answers
51 views

Mid-point convexity does not imply convexity

A function $f: X \rightarrow \mathbb{R}$ is said to be mid-point convex if for all $x, y \in X$, we have $f(\frac{x + y}{2}) \leq \frac{f(x) + f(y)}{2}$. Can you please give an example of a function ...
1
vote
1answer
32 views

Is a constrained optimization problem equalivant to its Lagrangian form?

For the following problem: $\text{min:}\ f(x)\\ s.t. \ g(x)\leq t$ Is the above problem equalivant to the following problem? $\text{min:}\ f(x) + \lambda g(x) \\ s.t. \ \lambda\geq0$ where $t$ and ...
0
votes
1answer
44 views

What's the solution for $\max_{x\in(0,1]}: \{-1-x\}$

What's the solution for the following optimization problem? Is the constraint set convex? $$\max_{x\in(0,1]}:\{-1-x\}$$
2
votes
0answers
130 views

Projection and Pseudocontraction on Hilbert space

Let $H$ be a real Hilbert space with inner product $\langle\cdot, \cdot \rangle: H \times H \rightarrow \mathbb{R}$, and induced norm $\left\| \cdot \right\|: H \rightarrow \mathbb{R}_{\geq 0}$. Let ...
0
votes
1answer
20 views

Confusions of Convex Set

I am interested in the properties of convex set in $\mathbb R^n$ and want to clarify the three statements below $A$ is an open convex set. Can we get the conclusion that $\bar{A}$ is convex? ...
0
votes
0answers
24 views

Sum of quasi-concave function and linear function

Let $F(k)$ have the following properties: $$ F(k) \in C^1 \\ F'(k) > 0 \\ F(0)=0 \\ \lim_{k \to \infty} F'(k) = 0, \lim_{k \to 0} F'(k) = \infty \\ F ~\text{strictly quasi-concave}. $$ Then, let ...
0
votes
2answers
35 views

Critical points and Convexity?

Function $f(x)$ has no critical points in $M$, can we say $f(x)$ is either convex or concave over $M$?
1
vote
0answers
36 views

Formal definition of convexity for multivariate function?

Let $M\in R^{M\times N}$, a function $f: M\rightarrow R$ is called convex on $M$ if $f\big((1-\lambda)X1+\lambda X2, (1-\lambda)Y1+\lambda Y2\big) \leq (1-\lambda)f(X1,Y1) + \lambda f(X2,Y2)$ For ...
0
votes
1answer
44 views

Analog of Birkhoff's theorem for doubly stochastic matrices

Birkhoff's theorem states that extreme point of the set of doubly stochastic matrices are permutation matrices. An $n \times n$ matrix $A$ is doubly stochastic if each row and column sums to 1. What ...
0
votes
1answer
26 views

Certain property of convex functions…

I come to you with yet another qualifying problem we can't seem to solve... Let $f:$ $(0,\infty) \to \Bbb R$ be convex, and let $\lim_{x \to 0}f(x)=0$. Show that $g(x)$ = $f(x) \over x$ is increasing ...
0
votes
1answer
32 views

Compact and convex discrete set

I am working with discrete sets but I have a doubt: is the set $\{ 0,1\}$ compact and convex? And the set $\{ 0,1\}^2=\{(0,0), (1,0), (0,1), (1,1) \}$?
0
votes
1answer
21 views

Redefine a discrete compact set

I need to find twice continuously differentiable functions $g_i: \mathbb{R}^2 \rightarrow \mathbb{R}$ $i=1,\ldots,I$ such that the set $\{ 0,1\}^2=\{(0,0), (1,0), (0,1), (1,1) \}$ can be written as ...
0
votes
1answer
23 views

Define a compact and convex set through inequality constraints

I need to find twice continuously differentiable functions $g_i: \mathbb{R}^2 \rightarrow \mathbb{R}$ $i=1,...,I$ such that the set $\{ 0,1\}^2=\{(0,0), (1,0), (0,1), (1,1) \}$ can be written as $\{x ...
0
votes
0answers
29 views

Convex cones and positively homogenous and subadditive functional

Let $V$ be a linear topological space, $K \subsetneq V$ a convex, closed cone with $0 \in K$ and $k \in K \setminus (-K)$. Show that the functional $\varphi : V \to \mathbb R \cup \{ \pm \infty \}$ ...
1
vote
1answer
65 views

How to use Markov-Kakutani fixed point theorem to show that abelian groups are amenable?

Recall that a group $\Gamma$ is amenable if there exists a state $\mu$ on $l^{\infty}(\Gamma)$ which is invariant under the left translation action: for all $s\in \Gamma$ and $f\in ...
4
votes
2answers
100 views

On the convexity of a particular form of integrals

EDIT: I made some critical corrections below. Let $\mathcal{H}\colon\mathbf{w}\cdot\mathbf{x}+c=0$ be a hypeplane in $\mathbb{R}^n$. Also, let $g\colon\mathbb{R}^n\to\mathbb{R}_+$, be a non-negative, ...
0
votes
1answer
43 views

Motivating convex sets.

I am kind of TAing for a class of real analysis, and I would like to speak a little about convex sets tomorrow, and explain why they are important. What kind of examples could I give? I was thinking ...
0
votes
2answers
53 views

The Fundamental Theorem of Matrix Games, and the “indifference” method of solving games

In the following we will consider two-person zero-sum games. Let $A = (a_{ij})$ be the payoff-matrix of such a game. In this book the fundamental theorem of such games is states as: Theorem: Given ...
1
vote
3answers
82 views

Is convex hull of a finite set of points in $\mathbb R^2$ closed?

Is the convex hull of a finite set of points in $\mathbb R^2$ closed? Intuitively, yes. But not sure how to show that. Thanks!
6
votes
3answers
230 views

Isoperimetric inequality, isodiametric inequality, hyperplane conjecture… what are the inequalities of this kind known or conjectured?

Question: Which inequalities similar to the famous isoperimetric inequality is known? conjectured? I recently learned about some inequalities which are all similar to the famous isoperimetric ...
0
votes
1answer
49 views

Min of concave symmetric function on a convex set

Consider the convex set $$C=\left\{ \mathbf{x}\in \mathbb{R}^N :0\le x_1\le x_2\le\dots\le x_i\le x_{i+1}\le \ldots\le x_N\le \frac 1{N-1}\text{ and } \sum_{k=1}^{N}x_k=1\right\}$$ I need to minimize ...
0
votes
0answers
9 views

Pseudoconcavity of a fractional function q(x)=f(x)/g(x) if f(x) is nonnegative concave and g(x) is positive convex?

I know from Chandra that $q(x)=\frac{f(x)}{g(x)}$ is strong pseudoconcave if $f(x)$ is nonnegative concave and $g(x)$ is strictly positive convex. Is there a theorem that states $q(x)$ is ...
2
votes
1answer
82 views

Relation between mean width and diameter

Question: Let $A$ be a compact set in $\mathbb R^n$. Is it always true that $\text{mean-width}(A) \ge C \cdot \text{diam}(A)$ for some constant $C$ depending only on the dimension? If not, is it ...
1
vote
0answers
34 views

Quickly checking if an inequality holds on a convex region

Let $C$ be a given convex polygon in $\mathbb{R}^2$ containing the origin and let $a$, $\mathbf{b}$, and $Q\succeq0$ be a given scalar, vector, and matrix respectively. Is there a fast way to verify ...