Questions tagged [convexity]
For questions related to convex functions and convex sets, especially as they relate to optimization problems.
59
questions
2
votes
1
answer
98
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
127
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 \...
- 467
1
vote
2
answers
64
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 ...
- 467
3
votes
1
answer
81
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$:
...
- 467
0
votes
0
answers
39
views
Is a posynomial concave under the following conditions?
Update
In case anyone is interested, this question has been answered here.
Consider the following posynomial with respect to the variables $x_1,\dots,x_n$:
\begin{align}
f(x_1,\dots,x_n) &= \sum_{...
- 467
2
votes
1
answer
70
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
77
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$}} + \...
- 3,980
3
votes
2
answers
172
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
64
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
598
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 ...
- 63
3
votes
1
answer
90
views
On a clarification on usage of inequalities in convex programming
The inequality $x^3\leq y$ is not convex. But $0<x$ added to the above provides a convex region.
My question is whether in convex programming it is allowed to use both inequalities together and use ...
- 131
2
votes
1
answer
110
views
Convex not strictly convex!
Update:
Linear programming problems (LP) have a convex space, precisely vector space, such as a convex feasible region as pointed out by @prubin. Also, they may have either unique or multiple ...
- 8,505
2
votes
0
answers
63
views
FOC point vs Stationary point in local optimization
In this SIAM Review paper the authors are giving the following necessary condition for a point being a local maximum of a convex function:
Let $F: \mathbb{R}^n \mapsto \mathbb{R}$ be convex. If $x$ ...
- 3,980
2
votes
0
answers
88
views
How to figure out integer variables in the relaxation set?
Suppose, there is mixed-integer programming as follows:
$(1)$
$$\begin{aligned}
\min&\quad c^{\top} x\\
\text{s.t.}& \quad A x \geq b \\
&\quad B x \geq d \\
&\quad x \geq 0 \\
&...
- 8,505
4
votes
1
answer
112
views
How to know if a combinatorial optimization problem is linear or not?
I want to know if a combinatorial problem like the knapsack problem is linear or not. And how do we know if a given problem is convex or not?
- 335
3
votes
2
answers
338
views
How to make following constraint a convex one?
I would like to write a constraint as follows, where $x,y>0$ are optimization variables, and $a,b,c,d,A$ are positive constants. How to make it a convex constraint?
\begin{equation}
\frac{{ax}}{{\...
- 177
2
votes
3
answers
224
views
Convex optimization on the unit hypercube with gradients and a bounded minimum
I'd like to find the minimum of a smooth, continuous function inside the unit hypercube (the dimensionality of which could go into the hundreds or even thousands). The function is convex (Hessian $\...
- 123
1
vote
1
answer
339
views
How to convexify log(convex) function?
I have the following optimization problem: \begin{align}\max_x&\quad\log_2(1+|a+bx|^2+cx^2)\\\text{s.t.}&\quad0\le x\le1\\&\quad(1-x^2)\ge\text{constant}\end{align} where $a$ and $b$ are ...
8
votes
2
answers
238
views
Is $\min \ x^3 \ \mathrm{s.t.}\ x \geq 0$ a convex problem?
The problem $$\min \ x^3 \ \mathrm{s.t.} \ x \geq 0$$
is sometimes said to be a convex optimization problem. $f(x) = x^3$ is not a convex function. However, in the domain of $x\geq 0$ it is convex. So ...
- 3,980
3
votes
0
answers
133
views
Proving convexity for a function with summation and integer variable
I would like to show that the function $f$ is convex in $\rho\in [0,1)$ under $s\in \mathbb{Z}^+$. When I use Sympy packages of Python to find $\displaystyle\frac{\partial^2 f(\rho)}{d\rho^2}$. I get ...
- 1,249
1
vote
0
answers
78
views
Decomposition of Polyhedra
There is no doubt that clear examples consolidate the understanding of concepts being learnt. I am new to finding the structure and decomposition of a polyhedra. Suppose that we have the system
$$ \...
- 111
1
vote
1
answer
113
views
Find a dual problem with one dual decision variable to the problem of finding the orthogonal projection of a given vector
Given the set $T_{\alpha}=\{x\in\mathbb{R}^n:\sum x_i=1,0\leq x_i\leq \alpha\}$
For which $\alpha$ the set is non-empty?
Find a dual problem with one dual decision variable to the problem of finding
...
- 405
4
votes
1
answer
130
views
Optimization of strongly convex functions with approximate evaluations of gradient and Hessian
Suppose I want to find the minimum of a differentiable, strongly convex function $f:\mathbb{R}^n\to\mathbb{R}$ with constant $\mu>0$. That is, for all $x,y\in\mathbb{R}^n$, I have that:
$$f(y) \geq ...
- 89
3
votes
1
answer
102
views
How to evaluate the convexity of an optimal control problem?
Can we consider an optimal control problem, a convex optimization problem like static optimization problems? If it is possible, under what conditions, will this problem be a convex problem? For ...
- 2,150
1
vote
0
answers
54
views
$\nabla_y\nabla_vf(x^*)\geq0$ for any concave $f$ if and only if $y=-v$
$f:\mathbb R^3\to\mathbb R$ is an arbitrary concave function.
$H$ is a plane. $v$ is a given vector on $H$.
$x^*=\max_{x\in H} f(x)$
Prove that $\nabla_y\nabla_vf(x^*)\geq 0$ if and only if $y=-v$.
I ...
- 179
2
votes
1
answer
95
views
Quasi-convex function must be "partially monotonic"?
$f(x)$ is quasi-convex,
$$x^*\in\arg\min_{x\in C}f(x).$$
How to prove that, for any $a\in C$, $f(x) $ is weakly monotonic in the direction of $(x^*-a)$?
Is this simple result a part of an ancient ...
- 179
6
votes
1
answer
202
views
Convexity of the variance of a mixture distribution
$X$ is a random variable that is sampled from the mixture of uniform distributions. In other words:
$$X \sim \sum_{i=1}^N w_i \cdot \mathbb{U}(x_i, x_{i+1}),$$
where $\mathbb{U}(x_i, x_{i+1})$ denotes ...
- 3,980
4
votes
1
answer
183
views
Can we get closed form solution for such a problem?
\begin{align}\min&\quad\sum_{i=1}^N\frac{A_i}{x_i}\\\text{s.t.}&\quad\sum x_i \le X\\&\quad x_i \ge 0\end{align}
wherein $A_i>0, (i\in\{1,\dots,N\})$ is constant, $x_i, (i\in\{1,\dots,N\...
- 177
1
vote
0
answers
93
views
Question on quadratically constrained quadratic program
If the constrained optimization problem is a quadratically constrained quadratic program of the form \begin{align}\min&\quad x^HQx-a(x+x^H)+b|z^Hx|^2\\\text{s.t.}&\quad\|x\|^2\le1\end{align} ...
- 19
5
votes
3
answers
2k
views
Linear programming convexity
Is it possible for a linear programming model to be non-convex ? If it is, please, provide a simple 2 variables example and explain why it is non-convex.
EDIT 1:
I have been wondering, maybe the ...
- 185
1
vote
1
answer
159
views
Simple nonlinear programming using convexity analysis and KKT
I want to solve the following two-variate nonlinear programming using KKT conditions:
$$ \begin{align} \begin{split}
\max \quad & 15 \sqrt{x_{1}} + 16 \sqrt{x_{2}} \\
\text{s.t.} \quad &...
- 381
3
votes
1
answer
232
views
Convexity Analysis
For the following function, I am testing the convexity in $\lambda$. All parameters are in $\mathbb{R}^+$.
$$\frac{\left(- \lambda \left(b + \frac{p}{\beta}\right) + 1\right) \left(\left(1 + \frac{p}{...
- 1,249
8
votes
2
answers
196
views
how to penalize a shortfall of a sum of absolute values
I have a model where there is a constraint on the sum of absolute values, and I would like to add a penalty on the shortfall from the constraint. More specifically:
\begin{align*}
\text{maximize}\ &...
- 542
5
votes
1
answer
113
views
Concavity: Definition similar to sub-modularity
We know that for $b \geq a$, and some $s \geq 0$, a concave function $f$ satisfies:
$f(a+s) - f(a) \geq f(b+s) - f(b)$.
This is not a frequent definition of concavity, but can be found, e.g., here....
- 3,980
9
votes
1
answer
520
views
Compute the distance from a point inside a convex set to the boundary of the set
Problem
Let $\mathcal C = \{ X \in \mathbb{R}^n \mid g(X) \leq 0\}$ where $g$ is convex, and let $X_c \in \mathcal{C}$. Is there any algorithm to compute the distance from $X_c$ to the boundary of $\...
- 507
6
votes
2
answers
769
views
Existence of Optimal Solution
Assume we are solving $\min\{f(x) \ | \ x \in S \}$.
If $f: \mathbb{R}^n \mapsto \mathbb{R}$ is a proper closed convex function, and $S$ is a non-empty closed convex set, does this imply that the ...
- 3,980
3
votes
2
answers
273
views
Convexity of a function
I would like to show that this function
$$2x^2 + 8y^2$$
is convex or concave by using the definition
$$f(θx+(1−θ)y) \le θf(x)+(1−θ)f(y)$$
From my understanding, using the Hessian matrix, I believe ...
- 135
5
votes
0
answers
1k
views
Convexity of the projection of a convex set
Question:
A set $S \subset \mathbb{R}^m \times \mathbb{R}^n$ is convex. Using the fact that affine maps preserves convexity prove that $S(y) = \{x \in \mathbb{R}^m\mid (x,y)\in S \}$ and $\hat{S} = ...
- 3,980
8
votes
2
answers
390
views
Convex Optimization: Separation of Cones
I am trying to solve Exercise 2.39 at Boyd and Vandenberghe's Convex Optimization book. In one source, the answer is given as:
2.39 Separation of cones. Let $K$ and $\tilde K$ be two convex cones ...
- 3,980
4
votes
1
answer
304
views
How to express this constraint?
I have the constraint \begin{align}\max&\quad\gamma\\\text{s.t.}&\quad a\ge\gamma b\\&\quad\gamma\le 1\end{align} where $\gamma$ is an optimization variable and $a$ is a function of some ...
- 2,211
9
votes
1
answer
98
views
Problem solvable $\Rightarrow$ subproblems solvable if feasible region closed, convex?
Let $c \in \mathbb{R}^n$, $M \subseteq \mathbb{R}^n$ such that the problem
\begin{align}P:\quad\min_{x \in \mathbb{R}^n}&\quad c^\intercal x\\\textrm{s.t.}&\quad x \in M\end{align} is solvable....
- 213
8
votes
1
answer
267
views
Convexity/Concavity of Average Number of Jobs in M/M/1 Queue?
I am working on a problem involving the average number of jobs $L$ in an M/M/1 queue with arrival rate $\lambda$, service rate $\mu$. For traffic intensity $\rho = \frac{\lambda}{\mu}$,
$$
L = \frac{\...
- 333
10
votes
1
answer
330
views
Solving convex programs defined by separation oracles?
General question: What software can solve convex programs defined by a separation oracle?
The objective function is concave, and the feasible set is a polytope. By a separation oracle I mean that I ...
- 203
13
votes
2
answers
1k
views
Is This Constraint Convex?
I have a constraint that I believe to be convex and not affine which I think means that I can implement a relaxation. I will first define the full constraint, and then build up my (informal) reasoning ...
- 2,299
9
votes
2
answers
503
views
Convexity of a QP
In quadratic programming (QP), you encounter an objective of the following form:
$$x^TQx + c^Tx$$
and often it's desirable to know if the QP is convex. One method to check for convexity is by ...
- 715
9
votes
3
answers
734
views
Examples of problems with non-convex constraint functions but convex feasible region
I'm looking for examples of (classes of) problems with a non-convex, non-linear formulation, but convex feasible region.
That is, a problem of the sort:
$$
\begin{array}{lll}
\text{minimize} & ...
- 2,316
12
votes
2
answers
596
views
Dedicated solver for convex problems
Are you aware of a fast solver (open source or commercial) for convex NLPs that is faster than IPOPT? I'm interested in problems in the 50K+ variable range, both dense and sparse. Ideally, it would be ...
- 11.9k
18
votes
3
answers
6k
views
Can an integer optimization problem be convex?
I'm trying to wrap my head around an apparent paradox that I've come across while trying to learn more about optimization algorithms:
On one hand several sources state that convex optimization is ...
- 2,129
16
votes
1
answer
474
views
Convexity of Variance Minimization
$X$ is a discrete random variable taking value $x_n$ with probability $1/N$ for $n=1,
\ldots,N$. I would like to set the $x_n$ values in an optimization problem. My objective is to minimize the ...
- 3,980
17
votes
5
answers
5k
views
Linear Programming with additional "if-then"/"Default to zero" constraints?
What approaches can I use for a Linear Programming problem with the additional constraint that if a decision variable falls below a certain threshold, then it should just be forced to 0.
I'm ...
- 2,129