Questions tagged [convexity]

For questions related to convex functions and convex sets, especially as they relate to optimization problems.

Filter by
Sorted by
Tagged with
2 votes
0 answers
44 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$ ...
user avatar
2 votes
0 answers
82 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 \\ &...
user avatar
  • 5,705
4 votes
1 answer
68 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?
user avatar
3 votes
2 answers
235 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}}{{\...
user avatar
2 votes
3 answers
120 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 $\...
user avatar
  • 123
1 vote
1 answer
188 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 ...
user avatar
7 votes
2 answers
136 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 ...
user avatar
3 votes
0 answers
90 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 ...
user avatar
  • 1,229
1 vote
0 answers
71 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 $$ \...
user avatar
  • 111
1 vote
1 answer
71 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 ...
user avatar
  • 395
4 votes
1 answer
98 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 ...
user avatar
3 votes
1 answer
78 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 ...
user avatar
  • 2,105
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 ...
user avatar
  • 179
2 votes
1 answer
75 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 ...
user avatar
  • 179
6 votes
1 answer
153 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 ...
user avatar
4 votes
1 answer
179 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\...
user avatar
1 vote
0 answers
86 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} ...
user avatar
  • 19
4 votes
3 answers
844 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 ...
user avatar
1 vote
1 answer
114 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 &...
user avatar
  • 331
3 votes
1 answer
191 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}{...
user avatar
  • 1,229
8 votes
2 answers
115 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}\ &...
user avatar
  • 542
5 votes
1 answer
108 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....
user avatar
9 votes
1 answer
397 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 $\...
user avatar
  • 487
6 votes
2 answers
387 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 ...
user avatar
3 votes
2 answers
258 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 ...
user avatar
  • 135
5 votes
0 answers
803 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} = ...
user avatar
8 votes
2 answers
209 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 ...
user avatar
4 votes
1 answer
231 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 ...
user avatar
9 votes
1 answer
91 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....
user avatar
  • 193
8 votes
1 answer
253 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{\...
user avatar
10 votes
1 answer
220 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 ...
user avatar
  • 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 ...
user avatar
9 votes
2 answers
376 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 ...
user avatar
9 votes
3 answers
628 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} & ...
user avatar
11 votes
2 answers
496 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 ...
user avatar
18 votes
3 answers
4k 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 ...
user avatar
  • 2,009
15 votes
1 answer
371 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 ...
user avatar
17 votes
5 answers
4k 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 ...
user avatar
  • 2,009
12 votes
2 answers
472 views

Convex vs Strictly Quasiconvex Functions in Optimization

I have read/heard quite a few time that in the old days, it was considered that linear programs constitute the class of optimization problems that can be solved efficiently in practice (as a rule of ...
user avatar
13 votes
1 answer
491 views

How to formulate a problem to prove/disprove convexity?

Given a general non-linear problem: \begin{align}P:\qquad&\min_{x\in X} f(x)\\\text{s.t.}\qquad&g(x)\leq 0\end{align} where $f$ is a non-linear function, $g$ is a vector of non-linear ...
user avatar
9 votes
2 answers
254 views

How to determine the convexity of my problem and categorize it?

My problem is: \begin{align}\min\limits_{x_{ij}}\qquad&{\sum_{i\in N}\sum_{j\in M}\frac{x_{ij}}{C_j-\sum\limits_{i\in N} x_{ij}a_i}}\\\text{s.t.}\qquad&0<C_j-\sum_{i\in N} x_{ij}a_i\\\qquad&...
user avatar
  • 101
12 votes
1 answer
232 views

Recovering primal optimal solutions from dual sub gradient ascent using ergodic primal sequences

My question concerns recovering a primal optimal solution while performing dual sub gradient ascent. Denoting by $y_i$ the dual multiplier in the $i^{\text{th}}$ iteration, let \begin{equation} x_i = ...
user avatar
  • 1,311
7 votes
2 answers
405 views

How can I linearize or convexify this binary quadratic optimization problem?

I have an optimization problem as below. I am having a hard time with the last constraint. $\max \eta$ subject to ${\bf U}(:,m)^T{\bf A}{\bf U}(:,m)=0,m=1,2,\cdots,M$ here $\bf{A}$ is a Binary ...
user avatar
15 votes
2 answers
156 views

Bound on the number of constraints to be generated (lazy constraints)

I am working on a very large optimisation problem. All variables are continuous, the objective is linear and the constraints convex, but I have many such constraints (on the order of $2^n$ — actually, ...
user avatar
  • 938
7 votes
1 answer
419 views

KKT inequality conditions

Let's say I have an objective function $$f(x_1,x_2, \cdots, x_n)$$ and $N$ constraints $$x_i \ge 0. $$ I am trying to solve it with KKT conditions. Now the objective function becomes $$f(x_1,x_2,...
user avatar
  • 1,579
12 votes
2 answers
798 views

Convex Maximization with Linear Constraints

I am doing active research in convex maximization w.r.t. linear constraints. There are many cases which can be efficiently approximately solved, e.g., convex quadratic maximization, log-sum-exp ...
user avatar
20 votes
2 answers
2k views

Reference for "expectation preserves convexity"

It is well known that expectation preserves convexity: If $f(x)$ is convex and $Y$ is a random variable, then $\mathbb E[f(x-Y)]$ is convex. This property arises in, for example, inventory theory. I ...
user avatar