18
votes
Accepted
Is This Constraint Convex?
Arguments 3 and 4 are incorrect. The Right-Hand Side (RHS) is not convex. Even if it were, setting a nonlinear equality with either side non-affine is non-convex. As the final coup de grace, even if ...
- 12.8k
16
votes
Accepted
Reference for "expectation preserves convexity"
Reference "Convex Optimization" by Boyd and Vandenberghe https://web.stanford.edu/~boyd/cvxbook/, section 3.2.1, p. 79.
These properties extend to infinite sums and integrals. For example if
$f(x,...
- 12.8k
15
votes
Accepted
Convexity of Variance Minimization
It holds
$$
\begin{array}{rcl}
\operatorname V(x) &= &\dfrac1N\left\| x-\dfrac{e^\top x}{N} e \right\|^2 \\
& = & \dfrac1N\left(x^\top x+\dfrac{(e^\top x)^2 e^\top e}{N^2}-2\dfrac{...
- 2,946
15
votes
Can an integer optimization problem be convex?
Feels like you are asking two things, tractability of convex problems and convexity of integer problems.
A first order approximation is that convex programs are tractable, .i.e., most problems you ...
- 1,682
14
votes
Accepted
How to formulate a problem to prove/disprove convexity?
Based on the comment by Ryan Cory-Wright, you could formulate it like this.
Verify convexity of the domain $\{x \in X : g(x) \le 0\}$
Solve the following problem, and check the optimal value.
\...
- 6,033
13
votes
Dedicated solver for convex problems
Are you formulating your model with nonlinear expressions that just happen to be convex?
Or can you provide conic normal forms, maybe using a modeling tool based on displicined convex programming? In ...
- 2,306
13
votes
Is This Constraint Convex?
Counterexamples to your arguments:
Argument 1:
Only affine equality constraints are convex, $x = y^2$ is not convex.
Argument 3:
Take $f(x) = x^4$ and $g(x) = x$. Both are convex, but the ratio $h(x)...
- 2,856
12
votes
Can an integer optimization problem be convex?
Mathematically, mixed-integer programs (MIPs) are non-convex, for the very reason you stated: the set $x \in \{0,1\}$ is inherently non-convex. In fact, for a convex optimization problem (e.g. linear ...
- 3,449
10
votes
Accepted
Examples of problems with non-convex constraint functions but convex feasible region
Couldn't we use a combination of trigonometric functions ? E.g.
\begin{cases}
x \in [0, 2\pi] \\
y \le \sin x \\
y \ge -\sin x
\end{cases}
- 1,471
10
votes
Convex vs Strictly Quasiconvex Functions in Optimization
Even though I consider "convex is easy" to be a good rule of thumb, there are some important details to consider. Maybe surprisingly:
Convex programming is NP-hard in general
In this paper, Samuel ...
- 6,033
10
votes
Dedicated solver for convex problems
You may want to try out the NLP solver Knitro, which, despite being commercial, is faster than Ipopt:
http://plato.asu.edu/ftp/ampl-nlp.html
- 1,471
10
votes
Accepted
KKT inequality conditions
If you want to use the KKT conditions for the solution, you need to test all possible combinations. This is why in most cases, we use the KKT's to validate that something is an optimal solution, since ...
- 3,449
10
votes
Accepted
how to penalize a shortfall of a sum of absolute values
If the $x$ variables are bounded, you can do this by introducing some binary variables (one for each $x$). Assume that $L_i \le x_i \le U_i$ for all $i$, where $L_i$ and $U_i$ are constants such that $...
- 37.5k
10
votes
Is upper incomplete gamma function convex?
The incomplete gamma function is not convex with respect to x for fixed a for 0 < x < a, as evidenced by the following counterexample.
Counterexample for a = 10, and x = 1, 5, 9:
...
- 12.8k
10
votes
Accepted
Is upper incomplete gamma function convex?
No, you cannot prove it is convex in $x$ because it is not, as Mark's counterexample indicates. For fixed $a$, $\Gamma$ is concave for $x\in (0, a-1)$ and convex for $x\in (a-1, a).$ Differentiating ...
- 37.5k
9
votes
Linear Programming with additional "if-then"/"Default to zero" constraints?
You asked several questions at once but these should be answered all at once too. The problem that you describe is no longer convex. An easy way of seeing this is that the linear combination of the ...
- 1,065
9
votes
Accepted
How to determine the convexity of my problem and categorize it?
This is a Linear-Fractional Programming problem.
It can be transformed to a Linear Programming problem as shown in section 4.3.2 "Linear-fractional programming" of "Convex Optimization" by Boyd and ...
- 12.8k
9
votes
Accepted
Bound on the number of constraints to be generated (lazy constraints)
The number of lazy constraints that have to be used, depends on the algorithm that is used. I will discuss two algorithms:
The cutting-plane method: solve the problem to optimality for a subset of ...
- 6,033
9
votes
Linear Programming with additional "if-then"/"Default to zero" constraints?
An alternative to using binary variables is to use semicontinuous variables, supported by some solvers. You still wind up with a discrete optimization problem (integer program), but the binary "buy/...
- 37.5k
9
votes
Accepted
Convexity/Concavity of Average Number of Jobs in M/M/1 Queue?
Your calculations (factoring and simplification) are incorrect. $L$ is neither convex nor concave as a function of $\lambda$ and $\mu$.
This can be concluded by examining the eigenvalues of the ...
- 12.8k
9
votes
Accepted
Linear programming convexity
A linear problem is always convex, because anything linear is convex.
As pointed out by @Marco Lübbecke, any linear function is also concave. But polygons (feasible sets of linear programs) are only ...
- 12.8k
8
votes
Examples of problems with non-convex constraint functions but convex feasible region
+1 for answer by @fpacaud .
Here are two non-contrived examples, which commonly arise in modern O.R. optimization.
Rotated Second Order Cone, which arises in Second Order Cone Programming.
For ...
- 12.8k
8
votes
How can I linearize or convexify this binary quadratic optimization problem?
Kevin Dalmeijer's answer is correct for the general case. Since $A$ is symmetric, there may be a method that involves fewer constraints. As suggested by Kevin's comment, I'm going to represent a ...
- 37.5k
8
votes
Accepted
How can I linearize or convexify this binary quadratic optimization problem?
The constraints
$${\bf U}(:,m)^T{\bf A}{\bf U}(:,m)=0,m=1,2,\cdots,M$$
can be rewritten as
$$\sum_{i=1}^N \sum_{j=1}^N A(i,j) U(i,m)U(j,m)=0,m=1,2,\cdots,M.$$
Next, you can linearize each of the $U(i,...
- 6,033
8
votes
Accepted
Problem solvable $\Rightarrow$ subproblems solvable if feasible region closed, convex?
In your question, you call a problem 'solvable' if there exists an $\hat{x} \in M$ such that
\begin{align}c^\top\hat{x} = \inf_{x \in \mathbb{R}^n}&\quad c^\intercal x\\\textrm{s.t.}&\quad x \...
- 6,033
8
votes
How to make following constraint a convex one?
The constraint is not convex, and is not transformable to a convex constraint without substantively changing it.
The additive linear term $dx$ is irrelevant to convexity. So let's ignore it and look ...
- 12.8k
7
votes
Reference for "expectation preserves convexity"
$\newcommand{\E}{\mathbb{E}}\newcommand{\R}{\mathbb{R}}$Define $\phi(x) = \E[f(x-Y)]$ and assume that for all $x\in\R$, $f(x-Y)$ is measurable and integrable. Then, for $x,x'\in\R$ and $\alpha \in [0,...
7
votes
Convex Maximization with Linear Constraints
The location-inventory problem by Shen, et al. and Daskin, et al. has a concave minimization objective. It's related to economies of scale (which you list in your PS 2) but not exactly the same.
- 13k
7
votes
Recovering primal optimal solutions from dual sub gradient ascent using ergodic primal sequences
In general, nonlinear optimization algorithms implemented in finite precision floating point software don't converge exactly to an optimal solution exactly satisfying the optimality conditions. ...
- 12.8k
7
votes
How to express this constraint?
No. The constraint $a\ge\gamma b$ sets no upper bound on $a$ so it cannot be bounded above by $b$ as your second formulation suggests.
There are a few posts here on the linearisation of the product ...
- 5,341
Only top scored, non community-wiki answers of a minimum length are eligible