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.

1
vote
0answers
12 views

How to show convex hull of finitely many vectors in $\mathbb{R^n}$ is a compact set? [duplicate]

Suppose $x_1,x_2,\cdots,x_k$ is any finite set of vectors in $\mathbb{R^n}$. A convex combination of these vectors is $\sum_{i=1}^{k}\lambda_ix_i$ where $\sum_{i=1}^{k}\lambda_i=1$ and $\lambda_1,\...
0
votes
1answer
19 views

maximizing concave function with parameter

We want to maximize the convex function: $$\vec{q} \cdot \vec{x} - \lambda||\vec{x} - \vec{1}||_2^2$$ where $\lambda$ is some parameter. I'm looking at a solution that states that the maximum is a ...
0
votes
1answer
39 views

Question about strong convexity

I don't really know how to begin. I tried substituting $y$ for $x + h$ and taking the Taylor approx. of $f(x + h)$ around $f(x)$. The RHS becomes $h^T \nabla f(x) + \phi(x)$ Where $\phi$ is our ...
0
votes
0answers
23 views

Use simplex method to solve linear programming problem

The problem I am given is max $x_1 + 3x_2$ subject to $x_1 + x_2 \leq 5, 3x_1 - x_2 \geq -3, x_1,x_2 \geq 0$ The first step I took was to put this into standard form: max $x_1 + 3x_2$ subject to $x_1 ...
0
votes
1answer
11 views

positive linear combination of quasi-concave functions

I have a question that I cannot manage to get around. I need to answer the following: Give an example to 2 quasi-concave functions on an interval such that any positive linear combination of ...
0
votes
0answers
7 views

conic hull of a set of points in terms of intersection of half spaces

Convex cones can be characterized in two ways, one as a conic hull of a set of points. Let $\mathbf{X}$ is a $n\times n$ matrix where each column is a vector, then $coni(\mathbf{X})$ defines a convex ...
0
votes
0answers
28 views

How to determine the convexity of multiple matrix variables function?

This formula is : $$f(W,V,B) =\|XW-V\|^2_F +\|Y-VB\|^2_F +\operatorname{tr}(V'LV) +2\operatorname{tr}(W'DW),$$ where $X$, $Y$ are constant matrices and $L$ is constant laplace matrix. Suppose $D$ is a ...
1
vote
1answer
24 views

The shape of a feasible region with equality and inequality constraints

I was wondering if anyone can help me with this (probably basic) question. I want to know how the following feasible region looks like if we have thousands of variables. The constraints are linear. ...
0
votes
2answers
39 views

Conditions on boundedness of a polyhedron which makes it polytope. [on hold]

Let $P=\{x \in \mathbb{R}^n \mid Ax=b, x\geq 0\}$ be a nonempty convex polyhedron (not bounded). Show that $P$ is bounded (i.e., it is a polytope) if and only if the linear inequality $Ax=0, \,\, x\...
0
votes
1answer
31 views

Maximizing $x f(x)$ when $f$ is decreasing but not concave

When $f$ is concave, $f''<0$, the max can be easily found using simply the first order condition. What techniques should I apply if it is not? I'm especially thinking of a function $f$ that has ...
1
vote
1answer
32 views

How to prove this expression of lower semi-continuouss?

The definition of lower semi-continuous in wiki (https://en.wikipedia.org/wiki/Semi-continuity) is \begin{equation} \mathop{\lim\inf}_{x\to x_{0}} f(x)\ge f(x_0). \end{equation} However, in some books,...
0
votes
1answer
13 views

Understanding step in proof that $|J(v)-J(u)-\langle \nabla J(u),v-u\rangle|\leq \frac{\mu}{2}||v-u||^2$ involviing integral of inner-product.

In this proof that: For $J:\mathbb{E}\to\mathbb{R}$ $\mu$-lipschitz differentiable. Have $\forall u,v \in \mathbb{E}$ $$|J(v)-J(u)-\langle \nabla J(u),v-u\rangle|\leq \frac{\mu}{2}||v-u||^2$$ The ...
2
votes
0answers
36 views

Show that the affine transformation of a polyhedron is a polyhedron.

Let $P=\{x \in \mathbb{R}^n \mid Ax \geq b\}$ be a nonempty polyhedron for a matrix $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^{m}$. Let $F:\mathbb{R}^m \rightarrow \mathbb{R}^n$ be an ...
0
votes
0answers
22 views

Projection on convex sets with equality and inequality constraints

I want to find the projection of a vector called "a" on a closed and convex set with linear constraints. The set is in the following form: \begin{array}{ll} & Ax = b \\ & Bx \le d \\ &x \...
2
votes
2answers
179 views

Show that the union of convex sets does not have to be convex.

The following is an example that I've come up with: Suppose that $p\in A$ and $q\in B$ so that $p,q \in A\cup B$, where $A$ and $B$ are two mutually disjoint, convex, unit circles centered at $x=0,2$ ...
1
vote
1answer
23 views

Show that intersection of a polyhedron and affine set is a polyhedron.

Let $P=\{x \in \mathbb{R}^n \mid Ax \geq b\}$ be a nonempty polyhedron for a matrix $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^{m}$. Show that a nonempty intersection of $P$ and an affine ...
1
vote
0answers
32 views

Prove that the dual of the norm approximation problem has the given form.

Consider the norm approximation: $$ (P) \begin{cases} \min_{x \in \mathbb{R}^n} \Vert Ax - b \Vert \end{cases} $$ where $A \in \mathcal{M}_{m \times n}(\mathbb{R})$ and $b \in \mathbb{R}^m$. ...
2
votes
1answer
45 views

Proof of positive homogeneity of risk measure

I am stuck with a proof about positive homogeneity and have tried now for several days. Hopefully someone can help me out. Thanks in advance. I am considering a risk measure $p=(x)$, where $x$ ...
3
votes
1answer
78 views

does there exist a smooth function which is nowhere convex/concave?

Consider $g\in {\rm C}^1[0,1]$. We say that $g$ is nowhere convex (concave, resp.) on $[0,1]$ if there is no open interval $I\subseteq [0,1]$ on which $g$ is convex (concave, resp.) Is it possible to ...
0
votes
0answers
8 views

Is an ambiguity set with Wasserstein distance of order 1 is convex?

I have a question about the convexity of an Wasserstein ambiguity set. Let $W_1(\mu, \nu)$ be Wasserstein distance of order 1 between $\mu$ and $\nu$ defined as $$W_1(\mu, \nu) := \min\limits_{\...
0
votes
0answers
10 views

Why can $X=qq^T \in S^n_+$ prove $Y \notin \mathbf K^*$?

$\mathbf K = S^n_+$ (nxn real symmetric positive semidefinite matrix). Show that the dual of $\mathbf K$ $\mathbf K^*=\{\mathbf Y | Tr(\mathbf X \mathbf Y) >0, \forall \mathbf X \ge \mathbf 0\}$ ...
0
votes
0answers
28 views

Conditions for $\Vert f \Vert_2^2$ to be convex

Question: I am currently looking for general conditions for the function $\Vert f \Vert_2^2$ to be convex, where $f:C \to C$ and $C \subset \mathbb{R}^n$ is compact. References on this problem or ...
2
votes
0answers
40 views

Finding the maximum value of the following equation

For $N\in \mathbb{N}$, $M\in \mathbb{N}$, and $K\in \mathbb{N}$, $f(K)$ is given by \begin{equation} f(K) = \sum\limits_{i = 1}^{K} {\left( {\frac{{\left( {M - K} \right)!\left( {M - i} \right)!}}{{\...
-2
votes
1answer
19 views

Closed bounded convex set in $\mathbb{R}^n$

Let the set $B \subset \mathbb{R}^n$ be convex, bounded and closed. We want to show that set $B$ is equal to convex hull of its boundary?
3
votes
0answers
24 views

Approximation of arbitrary convex function

I am currently studying Jürgen Moser's "A New Proof of de Giorgi's Theorem Concerning the Regularity Problem for Elliptic Differential Equations". During the proof of the first lemma, he claims that ...
1
vote
0answers
23 views

Why is convex conjugate defined on functions taking values on extended real line?

Recall a definition of convex conjugate (taken from Wiki): Let $X$ be a real topological vector space, and let $X^*$ be the dual space to $X.$ Denote the dual pairing by $$\langle \cdot,\cdot \...
8
votes
0answers
174 views
+100

Potential for Monotone Operator

I have a question about understanding the proof of Theorem 4.11 in the paper A Potential Theory for Monotone Multivalued Operators (accessible here). The authors claim to construct a convex ...
0
votes
0answers
20 views

What does the $d^*$ and $P^*$ mean in the Slater's condition?why when they are equal means the strong duality holds?

Here is question and solution,but i didn't understand the solution,can anyone help me to understand it? min $-3x_1^2+x_2^2+2x_3^2$ $s.t. x_1^2+x_2^2+x_3^2=1$ Does the strong duality hold? ...
0
votes
0answers
30 views

Equivalence of convex function

Let $I \subseteq \mathbb{R}$ be an interval. Then a function $f:I \rightarrow \mathbb{R}$ is convex on the interval $I \subseteq \mathbb{R}$ when: $$\forall a,b \in I, a < x < b \Rightarrow f(x)...
0
votes
0answers
49 views

Stability in convex optimization

Let $f:\mathbb{R}^n\to(-\infty,\infty]$ be a lower semicontinuous, proper, convex function such that $f(x)\ge 0$ for all $x\in\mathbb{R}^n$. Let $C\subseteq\mathbb{R}^n$ be a convex set, either ...
0
votes
0answers
16 views

Strongly convexity of a nonlinear functional

I got the following nonlinear functional $$J\left(u\right)=\frac{1}{2}\int_{\Omega}\left[H\left(\nabla u\right)\right]^2\;dx-\int_{\Omega}f\cdot u\;dx,\;\forall\;v\in X$$, where $H$ is a Finsler norm, ...
0
votes
0answers
18 views

prove that the functional is $\alpha$-elliptic

I got a nonlinear functional who is convex and Gâteaux differentiable. Is there some property of these two that can bring me that the functional is $\alpha$-elliptic???
2
votes
1answer
43 views

why is $\sum\limits_{i=1}^{n}v_ix_i(1-x_i)=v^Tx+x^T diag(v)x?$ and its dual function

I saw the solution of this question,but i have some problem Q: min$_x c^T \mathbf x$ $s.t. \mathbf A \mathbf x \le \mathbf b,\mathbf x_i(1-\mathbf x_i)=0,i=1,...,n,$ where $\mathbf x =[x_1,...,x_n]^...
0
votes
1answer
11 views

Integral of Quasi-concave function is Quasi-concave

Let $X$ be a Banach space and $\mu$ be a finite measure on $X$. If $f$ is concave on a Banach-Space $\mathbb{R}$, then $ f(tx + (1-t)y) \leq tf(x) + (1-t)f(y). $ Taking integrals on both sides ...
2
votes
1answer
29 views

Show that a translated subspace, i.e., $D=\{Ev+d \mid v \in \mathbb{R}^p\} \subseteq \mathbb{R}^n$ is a convex set. [closed]

Show that a translated subspace, i.e., $D=\{Ev+d \mid v \in \mathbb{R}^p\} \subseteq \mathbb{R}^n$ is a convex set where $E \in \mathbb{R}^{n \times p}$ and $d \in \mathbb{R}^n$.
0
votes
0answers
23 views

Property of a n-simplex?

Let $A \subseteq \mathbb{R}^n$ a open set. Then there exists a subset $B \subseteq A$ where $B$ is a $n-$ simplex?. Is the condition that $A$ is open necessary?
1
vote
2answers
43 views

Is $f(x,y) = x\log(x)+y\log(y)$ a coercive function?

From Peressini, Sullivan, Uhl, the mathematics of nonlinear programming, A function is coercive if $\lim\limits_{\|x\| \to \infty} f(x) \to \infty$ and super-coercive if, $\lim\limits_{\|x\| \to \...
2
votes
0answers
37 views

Show that $\prod_K(x)+\prod_{-K^*}(x)=x$ $\forall x \in \mathbb{R}^n$where $K$ is a cone in $\mathbb{R}^n$.

Let $K$ be a closed convex set in $\mathbb{R}^n$, $K^*$ be the dual cone of $K$, and $\prod_K(x)$ denote the Euclidean projection onto $K$. Show that $\prod_K(x)+\prod_{-K^*}(x)=x$ $\forall x \in \...
1
vote
1answer
25 views

Show minimum distance to a convex set is a convex function.

Show that $$ g(x)=\inf_{z \in C}\|x-z\| $$ where $g:\mathbb{R}^n \rightarrow \mathbb{R}$, $C$ is a convex set in $\mathbb{R}^n$ (nor close neither bounded), and $\|\cdot\|$ is a norm on $\mathbb{R}^...
1
vote
0answers
24 views

Maximizing a strictly concave function over a compact convex set

Let $f: S \to \mathbb{R}$ be a (strictly) concave function, where $S := \{y \in \mathbb{R}^m: y\geq 0,\, \sum_{i=1}^m y_i=1 \}$. I want to show that there is a $y^*\in S$, which maximizes $f$. $S$ ...
1
vote
1answer
22 views

A property of the n-simplex

Let $\Delta ^{n}$ a n-simplex and $\Delta_{0}^{n-1}, \Delta_{1}^{n-1}, \cdots , \Delta_{n}^{n-1}$ be the $(n-1)$ - faces of $\Delta^{n}$. The subsets $\Delta^{n} \backslash \Delta_{i}^{n-1}$ are ...
0
votes
1answer
17 views

Understanding about $S^n_+=\cap_{z \in R^n}S_z$,so it is convex.

A set $S^{+}$ of positive semi-definite matrices (PSD) is defined as $S^+=\{\mathbf X \in S^n |\mathbf z^T \mathbf X \mathbf z \ge 0,\forall z \in R^n,\mathbf X^T=X \}$ Use the property of which ...
3
votes
3answers
57 views

Connection/Consistency Between Different Definitions of Polyhedron? And How Does This Proof Apply to This Definition?

My textbook gives the following definition of a polyhedron: A polyhedron is defined as the solution set of a finite number of linear equalities and inequalities: $$\mathcal{P} = \{ x \mid a^...
1
vote
1answer
25 views

Prove point is in closure of set

Consider the set $M=\{ (1,x,x^2):x \in \mathbb{R}\}$. We define $\text{cone}(M)$ as the conic hull of $M$, which admits conic combinations of its points, i.e. $\sum_i \lambda_i(1,x_i,x_i^2)\in M$ ...
0
votes
1answer
24 views

Is minimizing the norm of a vector equivalent to minimizing the square of the norm?

Are the following two problems equivalent? $$ \arg \min_{y} || A \vec{x} - \vec{y} || $$ and $$ \arg \min_{y} || A \vec{x} - \vec{y} ||^2 $$ I feel like they are equivalent as it is just the ...
0
votes
0answers
11 views

Convex and Lower semi-continuous function [closed]

Let $V$ be a real Banach space and $G \colon V \to \mathbb{R} \cup \{ + \infty \}$ be a convex and lower semi-continuous function. Then there exists a set $L_G$ of continuous affine maps such that $G(...
0
votes
0answers
28 views

Do $|f'|$ and $f$ have the same minimisers for strictly convex functions?

Call the differentiable function $f: \mathbb K \to \mathbb R$ on some compact convex $K \subset \mathbb R^n$strictly convex to mean $f(\lambda x + (1- \lambda)y) < \lambda f(x) + (1-\lambda)f(y)$ ...
0
votes
1answer
24 views

What are some weird examples of convex sets?

What are some weird examples of convex sets? Maybe sets which intuitively seem non-convex. Or sets not similar to polyhedra, balls, ellipsoids, etc.
0
votes
1answer
60 views

Prove that set is convex. [closed]

How to prove that these two sets are convex for certain $p$? And for what p they will not be convex? $$A= \{(x,y) \in \Bbb R^2 : |x|^p+|y|^p \le 1, p \in \Bbb R\}$$ $$B = \{(x,y) \in \Bbb R^2 : x>0,...
0
votes
1answer
45 views

why can we use this $x^\theta y^{1-\theta} \le \theta x+(1-\theta)y$ to prove the $\prod \limits_{i=1}^{n}x_i \ge 1$ is convex set?

Show that $\{x \in R^n_+|\prod \limits_{i=1}^{n}x_i \ge 1\}$ is convex set Hint : if $x ,y \ge 0$ and $0\le \theta \le 1$,then $x^\theta y^{1-\theta} \le \theta x+(1-\theta)y$ I don't understand the ...