Questions tagged [convexity]
For questions related to convex functions and convex sets, especially as they relate to optimization problems.
22
questions
2
votes
0answers
17 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} = ...
7
votes
2answers
108 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 ...
5
votes
1answer
172 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 ...
8
votes
1answer
79 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....
8
votes
1answer
215 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{\...
9
votes
1answer
119 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 ...
13
votes
2answers
885 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 ...
9
votes
2answers
247 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 ...
9
votes
3answers
431 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} & ...
11
votes
2answers
446 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 ...
13
votes
3answers
975 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 ...
13
votes
1answer
186 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 ...
15
votes
5answers
2k 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 ...
12
votes
2answers
180 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 ...
14
votes
1answer
377 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 ...
10
votes
2answers
206 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&...
11
votes
1answer
168 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 = ...
7
votes
2answers
309 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 ...
15
votes
2answers
128 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, ...
7
votes
1answer
309 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,...
12
votes
2answers
166 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 ...
19
votes
2answers
176 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 ...
