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)

0
votes
1answer
20 views

Proving that the following is a convex subset

It is given that $I(S)=\{z|\exists x,y \in \mathbb{R}$ such that $(x,y,z)^t \in S$}$\subseteq \mathbb{R}$. How do I show that I(S) is a convex subset? We know that $S \subseteq \mathbb{R}^3$ is ...
1
vote
1answer
30 views

If y is not an exterior point of $K$, then there exists a $x$ in $K$. Is it true?

For a vector $v = (x_1,\ldots,x_d)^t \in \mathbb{R}^d$, we let the function $f$ be $f(v)=|v|^2=v^tv=x_1^2+\cdots+x_d^2$. Is it possible to show that there exists a x $\in K$ which satisfies $f(x)>...
0
votes
0answers
19 views

Show that argmax of this function is softmax

Problem: $x^* = \text{argmax}_{x \in X} \quad \sum\limits_{i = 1}^n x_i y_i - \sum\limits_{i = 1}^n x_i \ln(x_i)$ where $X = \{x \in \mathbb{R}^n: \sum\limits_{i = 1}^n x_i = 1 ,x_i \geq 0\}$ ...
0
votes
0answers
7 views

References on Rogers-Shephard inequality

If $K\subset \mathbb{R}^n$ is a convex body, let $K'$ be the convex hull of $K$ and $-K$. One of Rogers-Shephard inequalities asserts: $$\operatorname{vol}(K') \le 2^n \operatorname{vol}(K).$$ ...
0
votes
1answer
12 views

Continuous, midpoint (strictly) quasi-concave function is (strictly) quasi-concave?

It is known that Midpoint-Convex and Continuous Implies Convex. I am wondering can midpoint quasi-concavity and continuity implies quasi-concavity? If not, what conditions are required instead?
0
votes
1answer
44 views

Does being Nonempty Compact Set on $\mathbb{R^+_2}$ imply being Convex set?

Look at the domain of a function $y=x-2$ where $x\in\mathbb{R_+}$. Then, the triangle produced by x and y-intercepts is bounded and closed. So it is compact. Suppose it is also nonempty. Does this ...
0
votes
0answers
27 views

Convexity of the weighted norm

We all know that $f(x)=\|x\|^2$, with $x\in\mathbb{R}^n$, is a strictly convex function of $x$. But know let's spicy up the problem. Let $v\in\mathbb{R}^n$ be a unit vector, i.e., $\|v\|=1$. We want ...
0
votes
0answers
8 views

Is this constraint convex? Determinant of the Hessian is 0.

$a\leq e p_a D A (1-\Theta)$ $a,A$, and $\Theta$ are nonnegative decision variables and all others are positive parameters. Checking the Hessian tells me all of the leading principal minors are zero....
3
votes
0answers
94 views

Convexity of difference of log-sum-exp: $f(x_1, x_2, x_3, x_4) = \log(e^{x_1} + e^{x_2}) - \log(e^{x_1} + e^{x_2} + e^{x_3} + e^{x_4})$

I would like to know whether the following function $f: \mathbf{R}^4 \to \mathbf{R}$ is concave or not: $$ f(x_1, x_2, x_3, x_4) = \log(e^{x_1} + e^{x_2}) - \log(e^{x_1} + e^{x_2} + e^{x_3} + e^{x_4})...
2
votes
1answer
33 views

Upper bound for $\sum_{i=1}^{N}{x_i^{\beta_i}}$

$\{x_i\}_{i=1}^{N}$ a sequence of positive real numbers and $\{\beta_i\}_{i=1}^{N} $ are real numbers such that $\underset{1 \leq i \leq N}\min{\beta_i}$ > 1. Is it possible to find an upper bound of ...
-1
votes
0answers
14 views

Convex subset and linear equalities

Let S denote the set of $(a,b,c)$ $\in$ ${\mathbb{R^3}}$ which satisfies the following equalities: $-2a+b+c \leq 4 $ $a-2b+c \leq 1 $ $2a+2b-c \leq 5 $ $ a \geq 1 $ $ b \geq 2 $ $ c \geq 3 $ ...
3
votes
5answers
234 views

Sum of real powers: $\sum_{i=1}^{N}{x_i^{\beta}} \leq \left(\sum_{i=1}^{N}{x_i}\right)^{\beta}$

Let $\{x_i\}_{i=1}^{N}$ be positive real numbers and $\beta \in \mathbb{R}$. Can we say that: $$ \sum_{i=1}^{N}{x_i^{\beta}} \leq \left(\sum_{i=1}^{N}{x_i}\right)^{\beta}$$ I know that this holds if $...
1
vote
0answers
17 views

Interpolating polynomial such that it is convex in specified region

The problem I have is that I have data at two points $x_1,x_2$ and $x_2>x_1>0$. At these two points, I know that the function $f$ has values $f(x_1)$ and $f(x_2)$ respectively. It is also ...
0
votes
2answers
41 views

A linear map from $ R^3$ into $R^2$

Suppose $a\in (0,1)$ and $$X=\{(x_1,x_2,x_3)\in R^3: a x_1+(1-a) x_2+ x_3\leq 3, x_i\geq 1, i=1,2,3.\}.$$ Define a linear map $\Gamma$ by $(x_1,x_2,x_3)\to (a x_1+(1-a) x_2, x_3)$ . Do we ...
1
vote
2answers
33 views

Inequality involving a convex function

I am stuck, showing the following inequality in an easy way (using only inequalities or something): Let $x\in [-a,a]$ for some $a>0$ and $p\in (1,2)$. I want to show that there then exists a ...
0
votes
0answers
18 views

To prove some of the allegations.

Good day to all! Please help me with the solution of problems in convex analysis. I have tried to use the Hahn-Banach theorem, and theorems about the basic functions, but I unfortunately can't do ...
3
votes
5answers
87 views

Feasible point of a system of linear inequalities

Let $P$ denote $(x,y,z)\in \mathbb R^3$, which satisfies the inequalities: $$-2x+y+z\leq 4$$ $$x \geq 1$$ $$y\geq2$$ $$ z \geq 3 $$ $$x-2y+z \leq 1$$ $$ 2x+2y-z \leq 5$$ How do I find an interior ...
0
votes
1answer
7 views

Strongly monotone and cocoercive

A map $f:\mathbb{R}^n\rightarrow\mathbb{R}^n$ is $m$-strongly monotone if $$ (x-y)^{\sf T}((f(x)-f(y)) \geq m \|x-y\|_2^2 $$ for $m > 0$ and is $\delta$-cocoercive if $$ (x-y)^{\sf T}((f(x)-f(y)) \...
1
vote
0answers
23 views

Gradient Descent and Scale of Data and Objective Function

One way to tune step size in gradient descent is via backtracking line search. backtracking line search (with parameters α ∈ (0, 1/2), β ∈ (0, 1)) starting at $t = 1$, repeat $t := \beta t$ ...
1
vote
1answer
21 views

Is the root of a sum of squared differences convex?

Let $x \in \mathbb{R}^n$. Let there be a collection of functions $d_i = (x_j - x_k)^2$ (note that the subscripts $j$ and $k$ are fixed for each $d_i$, and there can be repeated use of subscripts on ...
0
votes
1answer
34 views

Related to Caratheodary theorem

If $P$ is a set of vectors $\textbf{x}_i$'s where every $\textbf{x}_i$ is of dimension $d$ and $|P|=K$. In this case at many places I have seen that the vectors $\textbf{x}_2-\textbf{x}_1,\textbf{x}...
0
votes
1answer
34 views

Needing help with convex analysis

If $f$ is a closed proper convex function defined on $\mathbb{R}^n$, prove that the function $\varphi$ defined by $\varphi(\lambda)=f((1-\lambda)x+\lambda y)$, where $x \in \text{dom}f, y \in \mathbb{...
1
vote
0answers
18 views

Does the (strict) concavity of a function depends on the space in which we consider it?

For instance, $f(x)=\sqrt{x}$ is clearly strictly concave in $\mathbb{R}_+$ but if we consider that function in two dimensions, i.e. $f(x,y)=\sqrt{x}$ with $(x,y)\in\mathbb{R}^2_+$, it seems that it ...
1
vote
0answers
14 views

Demonstrating convexity of a convex optimization problem

I am working on the following problem. Consider the following function $\textit{f}: \mathbb{R^n}$ × $\mathbb{R^n}$ → $\mathbb{R}$. $$f(\vec{z},\vec{d}) := \min_{t \in \mathbb{R},\vec{v} \in \mathbb{...
1
vote
1answer
21 views

On accelerated Proximal Gradient Methods

I am working on accelerated optimization scheme, which unified in the paper by Paul Tseng, "On Accelerated Proximal Gradient Methods for Convex-Concave Optimization". But unfortunately, it is ...
1
vote
1answer
52 views

A spectrahedron is a quadric cone when matrices in LMI are in $\mathbb{R}^{2\times 2}$

I am watching a lecture (just at the beginning around 0:50-0:57). The note says when $n=2$, $\mathcal{S}$ is a quadric cone; however, it seems that the professor says "a quadratic cone". On ...
1
vote
1answer
21 views

The gradient of a convex function is controlled by its oscillation on a larger ball

My problem is Let $f:\mathbb R^n\longrightarrow R$ be a convex function. Knowing that $$|\nabla f(x)|=\sup_{y\neq x}\frac{[f(x)-f(y)]^+}{|x-y|}$$ ($[f(x)-f(y)]^+$ represents $\max\{[f(x)-f(y)],...
2
votes
0answers
61 views

Optimal convex hull that maximizes # points from set A and minimizes # points from set B

This problem arose in a computer vision hobby project. Say I have two sets of points in three dimensional Cartesian space: A and B. The problem I would like to solve is to find the convex hull V of ...
17
votes
5answers
495 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 ...
0
votes
0answers
27 views

How do I prove that this function is concave on $f_{ij}(x)$?

I am trying to apply convex optimization to the following problem- ${f^*}(x) = \mathop {\arg \max }\limits_{{f_i}(x)} \sum\limits_i {\ln \left\{ {u_i^* - \sum\limits_j {\frac{1}{{\left( {1 - {\rho _{...
2
votes
2answers
41 views

Interior of a preimage of a continuous function

Let $ f:\mathbb{R}^n\rightarrow \mathbb{R} $ be convex. Let there exist a point $ x_0 $ with $ f(x_0)<0 $. Prove that $$ \operatorname{int}\left\lbrace f(x)\ge 0 \right\rbrace = \left\...
0
votes
1answer
37 views

How to prove the following function is convex?

I was working on a problem and it reduced to show that $$f(a)=log\Big(\sum_{i=1}^{r}a^ix_i\Big)~~a>1, x_i>0$$ is convex. I have $$f^{\prime \prime}(a)=\frac{\partial^2f(a)}{\partial a^2}=\frac{[\...
0
votes
1answer
52 views

Directional Derivative defines Descent Direction

Let $f:\mathbb{R}^m \mapsto \mathbb{R}$ be a proper convex function that is not necessarily differentiable and let $x\in\mathbb{R}^n$ be such that $\mathbf{0} \notin \partial f(x)$. I want to prove ...
1
vote
1answer
18 views

Individually checking constraints for convexity in Optimisation problem valid?

I have a quadratic minimisation problem where both the objective fn and constraints have some quadratic terms. (Such as a throttle variable (continous) * On/Off (integer variable)). My question is: ...
0
votes
0answers
14 views

Uniqueness of projection implies convexity [duplicate]

Prove that for a compact set A in finite dimensional Euclidean space X, A is convex if and only if for any point x in X, the projection of x to A is unique. If we know A is convex, we can show the ...
2
votes
4answers
71 views

Convex integral inequality

I cannot prove that if $f(x)$ is convex on $[a,b]$ then $f\Big(\frac{a+b}2\Big) \le \frac1{b-a}\int_a^b f(x)\,dx \le \frac{f(a)+f(b)}2 .$
0
votes
1answer
24 views

Does function that maps bounded convex sets (minus straight line segments) to bounded convex sets must be continuous everywhere?

This question in the title came to my mind while I was sitting with my granny in front of my house maybe about half an hour ago. Although it looks innocent I do not know at the moment some simple ...
0
votes
0answers
20 views

linearize average success probability constraint

In my optimization problem, I've a constraint to calculate the average success probability of a path. $x_{i,j}$ is binary variable defined as: $$ \begin{align} \label{eq3:1} x_{i,j} = \begin{cases} ...
0
votes
1answer
34 views

Convex or non-convex function

I want to minimize the following function $$\frac{a}{bxy+cd}e^{\frac{a}{bxy+cd}}H+2-\Gamma(1,\frac{eaf}{b(1-x)},\frac{eagf}{bx(1-y)})$$ where $a,b,c,d,e,f,g,H$ are constants and greater than $0$. $\...
0
votes
0answers
47 views

When we can permute between the integral and convex hull?

Is there a relation between the following expressions? $$\operatorname{conv}\left(\int_{0}^{t} f(s,x)ds :x \in A \right) $$ and $$\int_{0}^{t} \operatorname{conv}(f(s,x):x \in A)\ ds $$ where $A$ ...
2
votes
1answer
25 views

Finding minimizer from different order

Let a nonnegative function $f(x,y)$: $\mathbb R^2\to \mathbb R$ be second order continuous differentiable. We also know that $f$ is not convex in its two arguments, but only separately in each of them....
0
votes
0answers
5 views

Invertibility of a polylogarithmic map

Consider a map defined on $\Bbb R\times(0,+\infty)$ and given by $$M:(a,b)\to(\rho,E),$$ $$\rho = \int_{\Bbb R^n}\frac{dx}{1+\exp(a+b|x|^2)}\\E=\int_{\Bbb R^n}\frac{|x|^2dx}{1+\exp(a+b|x|^2)}.$$ I ...
2
votes
1answer
37 views

Can a quasiconvex function be made convex by composition with a diffeomorphism?

Assume we are given a continuous quasiconvex function $f: \mathbb{R}^n \to \mathbb{R}$. Intuitively I feel that quasiconvexity means that there should exist a diffeomorphism $h: \mathbb{R}^n \to \...
0
votes
1answer
25 views

Exact line search in convex optimization

For a convex function $f$ what do we know about convexity of the exact line search problem? $$\min_{\alpha \ge 0} f(x+ \alpha p_k)$$ I think because the function is convex and is linear in variable, ...
0
votes
1answer
21 views

Upper bound for sum of powers

I have a sequence of positive real numbers $\{x_i\}_{i=1}^{N}$ and $k \in \mathbb{N}$. I was wondering if one can find an upper bound of the type $$ \sum_{i=1}^{N}{x_i^k} \leq f\left(\sum_{i=1}^{N}{...
0
votes
0answers
21 views

Inequality for convex functions

Let $a,b:\mathbb{R}\to\mathbb{R}_+$ be two strictly convex and differentiable functions, such that $a\geq b$. Let $x\leq\alpha\leq y\leq\beta$, where $\alpha,\beta\in\mathbb{R}_+$ are two constants. ...
0
votes
1answer
90 views

Why is the dual cone of $l^1$ is $l^\infty$?

I just noticed somewhere in Convex Optimization that the dual cone of $l^1$ is $l^\infty$! (A diamond in $\mathbb{R}^2$ for $l^1$ is a square in $\mathbb{R}^2$ for $l^\infty$.) In fact I cannot ...
1
vote
1answer
26 views

Showing that this set satisfies the closed criterion

Suppose we have the subset $S = \{ \lambda v \mid \lambda \geq 0 \} + K $, where $v$ is a vector in $\mathbb{R^3}$ and $K$ is a convex hull of six other vectors. How do I show that it satisfies the ...
0
votes
0answers
9 views

Is this implicit mapping convex?

I am interested in the convexity properties of the following mapping on the $n\times 1$ vector $x$: $$ x_{j}=y_{j}^{\beta}\left(\sum_{i=1}^{n}B_{ij}x_{i}\right)^{\alpha} $$ where $\beta>0$, $y_j\...
5
votes
2answers
63 views

Convex sets in infinite dimensional Banach spaces

I am reviewing functional analysis and getting stuck in this question. Let $X$ be an infinite dimensional Banach space. Show that there exist convex sets $K_1, K_2$ such that $K_1\cap K_2=\emptyset,...