Skip to main content

# Questions tagged [convexity]

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

61 questions
Filter by
Sorted by
Tagged with
1 vote
1 answer
88 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
51 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 ...
2 votes
1 answer
190 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 ...
4 votes
1 answer
164 views

• 123
5 votes
2 answers
610 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
3 votes
1 answer
91 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
114 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 ...
• 9,123
2 votes
0 answers
66 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$ ...
• 4,010
2 votes
0 answers
89 views

• 111
1 vote
1 answer
129 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
141 views

• 391
3 votes
1 answer
250 views

10 votes
1 answer
353 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,319
9 votes
2 answers
561 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 ...
• 725
9 votes
3 answers
756 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
611 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 ...
• 12.2k
18 votes
3 answers
7k 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,179