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 ...
user avatar
18 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, ...
user avatar
14 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{...
user avatar
  • 2,403
13 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. \...
user avatar
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)...
user avatar
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 ...
user avatar
12 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 ...
user avatar
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 ...
user avatar
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}
user avatar
  • 1,381
10 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) ...
user avatar
  • 1,045
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 ...
user avatar
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 ...
user avatar
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): ...
user avatar
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\...
user avatar
  • 21.8k
6 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 &...
user avatar
  • 21.8k
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 ...
user avatar
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 ...
user avatar
6 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 ...
user avatar
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}})$.
user avatar
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 ...
user avatar
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 \...
user avatar
5 votes

Maximizing 1-norm: using binary variables to relax non-convexity

Provide the standard citation for YALMIP ...
user avatar
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 ...
user avatar
  • 28.9k
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 ...
user avatar
  • 2,403
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.
user avatar
  • 21.8k
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 ...
user avatar
4 votes
Accepted

Find the farthest point in hypercube to an exterior point

As $x_i\in[0,1]$ we just need to compare the values of the endpoints since $(x_i-c_i)^2$ is minimised at $x_i=c_i$. It is easy to see that $x_i=0$ gives the maximum whenever $c_i\ge1/2$ and $x_i=1$ ...
user avatar
  • 5,010
4 votes
Accepted

"Rank 1" type constraint $X=vw^\top$: MILP representation? Convex relaxation? Other tractable approach?

Rank-one constraints are unfortunately not mixed-integer convex representable, as shown in this paper: https://arxiv.org/abs/1706.05135, although they are quadratically-constrained quadratic ...
user avatar
4 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}^{...
user avatar
4 votes

Is it always possible to optimize a multivariate function sequentially?

This is possible to do in a functional form that preserves all relevant information. As mentioned in the Convex Optimization by Boyd (page 133, Optimizing over some variables): We can always minimize ...
user avatar
  • 2,110

Only top scored, non community-wiki answers of a minimum length are eligible