Questions tagged [convexity]
For questions related to convex functions and convex sets, especially as they relate to optimization problems.
64 questions
1
vote
0
answers
92
views
Are there examples of sets in 2D which are described implicitely by intersecting half-spaces?
This is a follow up of this question, in which the following set is considered:
$$
\{(x,y,z)\in \mathbb{R}^3, x+y\le 1, y+z\le 1, x+z \le 1, x\ge 0,y\ge 0, z\ge 0\}
$$
Three of its faces (planes) are ...
- 488
2
votes
3
answers
462
views
How to describe this set more explicitly?
Consider the following set of points:
$$
\{(x,y,z)\in \mathbb{R}^3, x+y\le 1, y+z\le 1, x+z \le 1, x\ge 0,y\ge 0, z\ge 0\}
$$
I have a hard time visualizing these points in 3D. What exactly is the ...
- 488
0
votes
0
answers
92
views
Is there a convex (exponential cone?) case of one of the following problem classes?
Let $n\in\mathbb{N}$, $A\in\mathbb{R}^{n\times n}$, $b\in\mathbb{R}^n$, $c>0$, $d_1,\dots,d_{n-1}>0$ and define:
$$S:=\{x\in\mathbb{R}^n\mid Ax\le b, x_1\ge c,\dots,x_n\ge c\}.$$
Do there exist ...
- 289
5
votes
1
answer
271
views
Proof of uniqueness of convex sets using their support functions
For a non-empty set $C \in \mathbb{R}^n$, the support function is $S_c(y)=sup_{x\in C}y^Tx$.
We have two closed convex sets $A$ and $B$.
Using the fact that the support function is an extended-real ...
- 53
1
vote
1
answer
235
views
Why is the convex hull of a integer linear program a polyhedron with same optimum?
Given a MILP with feasible region $P := \left\{ x \in \mathbb{R}^n \times \mathbb{Z}^p \mid Ax = b \right\}$ with $A \in \mathbb{R}^{m \times (p+n)}$, $b \in \mathbb{R}^{m \times 1}$ and objective ...
- 13
1
vote
1
answer
86
views
Why is there a separate area for PSD constraints and PSD variables in the Conic Benchmark Format?
This question pertains to the Conic Benchmark Format (CBF) for specifying a convex optimization problem. Here's a link to the specification.
In the CBF specification, there are separate areas for ...
- 740
2
votes
1
answer
376
views
Convexity of p power of the q norm (0<p<1, q>1)
I encountered a minimization problem involving the following function:
$f(\mathbf{x})=\|\mathbf{x}\|_q^p$
Here, $q>1$ and $0<p<1$. Naturally, each entry of $\mathbf{x}$ is greater than $0$.
I ...
- 23
4
votes
1
answer
222
views
Does minimizing the upper bound due to Jensen's inequality yield an equivalent solution?
$\DeclareMathOperator*{\argmin}{\arg\!\min}$Consider the convex function $f : X \to \mathbb R$, where $X \subseteq \mathbb R^n$ is a convex set. Define the functions $g_\ell : X^m \times \Delta \to \...
- 639
1
vote
2
answers
172
views
Relaxing non-affine equality constraints in convex optimization
Consider the convex function $f$. In section 4.2.1 in these lecture notes, the author writes:
4.2.1 Relaxing non-affine equality constraints
For functions $g_i(x)$, $i \in \{1,\dots,d\}$ that are ...
- 639
3
votes
1
answer
108
views
Is it possible to make a posynomial concave using a change of variables?
Note: this question was already posted on Math.SE but received no answers, so I'm re-posting it here for better reach.
Consider the following posynomial with respect to the variables $x_1,\dots,x_n$:
...
- 639
2
votes
1
answer
110
views
Question About Fritz John Theorem and Slater Constraint Qualification
Background Information
I am studying constraint qualifications. Here are two theorems leading to my question:
Theorem 1$\space\space\space\space$ [Fritz John Theorem] Suppose that $f, g_1, \dots, g_k$...
- 123
3
votes
0
answers
393
views
Changing the order of $\sup$ and $\inf$
I have a problem in the following form
\begin{align}
\begin{array}{cll}
\sup_{\theta \in \mathrm{dom}(f)} & \inf_{z \in \mathbb{R}^n} & \underbrace{f(\theta)}_{\text{concave in $\theta$}} + \...
- 4,050
3
votes
2
answers
232
views
When Biconvex function is Pseudoconvex function?
Is a Biconvex function f(x,y):=yg(x), (where g is a convex function, y>=0), Pseudoconvex function?
2
votes
1
answer
83
views
Does this kind of "partition" have a name?
Consider a convex polyhedron $A$. Assume we have subsets $A_1,\ldots,A_n$ of $A$ that are themselves covex polyhedra and are mutually disjoint except maybe sharing an edge, and that their union gives $...
- 123
5
votes
2
answers
658
views
Is upper incomplete gamma function convex?
Considering the definition of upper incomplete gamma function: $\Gamma(a, x) =$ $\int_{x}^{\infty}t^{a-1}e^{-t} dt$
Given that $a$ is fixed and $0 < x < a$, can we prove the function is convex ...
- 73