19
votes
Accepted
Trustful Nonlinear Programming
Local nonlinear optimization solvers, such as IPOPT, are not guaranteed to find a feasible point for problems that are feasible. That is certainly the case for problems with non-convex constraints, ...
- 13.2k
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 ...
- 13.2k
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{...
- 3,046
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,063
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
13
votes
Trustful Nonlinear Programming
Oh boy. Adding to Mark's great answer, I'll add some fun facts on what can go wrong with IPOPT and feasibility, and provide us with endless nights of entertainment:
The linear system solver gets ...
- 11.9k
12
votes
Accepted
Solvers and saddle points
While iteratively approximately solving the first order Karush-Kuhn-Tucker conditions, many (nonconvex) nonlinear solvers "roll downhill", i.e., enforce descent (for minimization) of the objective ...
- 13.2k
12
votes
Accepted
IPOPT with HSL vs MUMPS
This question happened to appear only a couple days after Byron Tasseff, Carleton Coffrin, Andreas Wächter, and Carl Laird (the last two are the original authors of IPOPT together with Larry Biegler) ...
- 1,065
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,063
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
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 ...
- 13.2k
8
votes
Maximize correlation subject to nonconvex correlation constraints
You could add the non-convex constraint $z^Tz = 1$. That would make the objective function and other constraints linear. So this would be a Linear Programming problem, but for a single non-convex ...
- 13.2k
7
votes
Does strong duality hold when I dualize only a subset of the constraints?
If strong duality holds, then it also holds when only a subset of the constraints is dualized.
We define the following three problems: the original, the partially dualized, and the dual.
Problem (P1):
...
- 6,063
7
votes
Accepted
Linearizing the square root of two binary summations
For $j\in\{0,1,2\}$, introduce binary variable $w_j$ to indicate whether $x+y=j$, and then impose the following linear constraints:
\begin{align}
\sum_{j=0}^2 w_j &= 1 \\
\sum_{j=0}^2 j\cdot w_j &...
- 30.5k
7
votes
Accepted
how to implement an optimization function with polynomial in Gurobi (Java)
This can be handled by transforming this to a bilinear problem, i.e., a problem only involving products of no more than 2 variables at a time.
This is accomplished by lifting the problem into a higher ...
- 13.2k
6
votes
Accepted
Linearizing the square root of binary summations
Because your objective is minimization and $z_j$ has a nonnegative objective coefficient, you can relax your equality constraint to
$$\displaystyle z_j \ge \sqrt{\sum_{\substack{i\in \mathcal{I},\\k\...
- 30.5k
6
votes
Accepted
Approximation methods for a mixed integer convex optimization problem
Mosek 9.x can natively solve mixed-integer exponential cone problems.
Formulate the problem in YALMIP, specifying the binary variables as binvar, and Mosek as the solver. YALMIP will call Mosek to ...
- 13.2k
6
votes
Find the farthest point in hypercube to an exterior point
This answers a comment by the OP, to explain why the other answers are correct. It is due to the following standard result.
A concave objective subject to compact convex constraints has a global ...
- 13.2k
6
votes
Accepted
How to convexify log(convex) function?
You are maximizing a convex quadratic (the monotonic log is irrelevant) so the maximum is attained at the border, i.e. either $0$ or $\min(1,\sqrt{1-\text{constant}})$.
- 1,702
6
votes
Accepted
What methods are used to solve multi-objective optimization problem with non-linear objective functions and integer decision variables?
Disclaimer: One might want to look for a reformulation or a special structure to apply mathematical tools to find optimal in the feasible set. I am assuming you're already past the possibility that ...
- 394
6
votes
How to maximize sum of cosine squared plus sum of sine squarred?
Allowing $\phi_k\in[-2\pi,2\pi]$ gives you enough freedom to achieve any angle $\theta_k$ as the common argument of $\cos$ and $\sin$. A geometric interpretation of your problem is to find a sequence ...
- 30.5k
5
votes
Accepted
Convexity of the variance of a mixture distribution
In order to find the best upper bound for variance, for given input values of $u_i$ and $\sigma_i^2$, you should globally maximize variance with respect to the $w_i$, subject to the constraints $w_i \...
- 13.2k
5
votes
Maximizing 1-norm: using binary variables to relax non-convexity
Provide the standard citation for YALMIP
...
- 13.2k
5
votes
Convex vs Strictly Quasiconvex Functions in Optimization
My claim is that everything that can be formulated as a conic optimization problem using
Linear cones
Quadratic cones
Power cones
Exponential cones
Semi definite cone (with some qualifications)
can ...
- 3,046
5
votes
Accepted
Dealing with a non-convex problem
You want the two functions to be concave in $h_p$, since you are maximizing (convex would be correct if you were minimizing). As to whether minimizing the sum of the $h_p$ would be equivalent, it ...
- 37.9k
5
votes
Accepted
Non-linear optimization local or global solution
Introduce a binary variable $\delta_t$ to represent which case it is and $z_t$ to represent the modelled product, and your MILP model of the piecewise-affine dynamics would be
${EP}_t\ =\ \sum_{i=1}^{...
- 1,702
5
votes
Find an upper bound for an objective function
Yes, because $\log$ is monotonic, it preserves inequalities. The tightness depends on your other constraints.
- 30.5k
5
votes
Accepted
Endowment of an agent
Endowment is a term from economics. It is the (initial) amount of goods (or factors depending on the type of agent) an agent possesses. In models, this is an exogenous value (constant). Usually, there ...
- 2,586
5
votes
When Biconvex function is Pseudoconvex function?
I am a bit confused by the wording. The title says when biconvex is pseudoconvex, but in the description asks whether a biconvex function is pseudoconvex. I am answering assuming you are asking the ...
- 1,458
4
votes
Examples of problems with non-convex constraint functions but convex feasible region
For any monotonic function $f:\mathbb{R} \rightarrow \mathbb{R}$ your problem is equivalent to
$$
\begin{array}{lll}
\text{minimize} & c^Tx & \\
\text{subject to} & h_i(x) \le ...
- 6,063
Only top scored, non community-wiki answers of a minimum length are eligible