Skip to main content
20 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, ...
Mark L. Stone's user avatar
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 ...
Mark L. Stone's user avatar
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{...
ErlingMOSEK's user avatar
  • 3,166
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. \...
Kevin Dalmeijer's user avatar
14 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 ...
Nikos Kazazakis's 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)...
Michael Feldmeier's 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 ...
Mark L. Stone's user avatar
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) ...
David Bernal's user avatar
  • 1,075
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 ...
Kevin Dalmeijer's 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}
fpacaud's user avatar
  • 1,511
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 ...
Mark L. Stone's user avatar
8 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 ...
Mark L. Stone's 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 ...
Mark L. Stone's 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): ...
Kevin Dalmeijer's user avatar
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 &...
RobPratt's user avatar
  • 32.3k
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\...
RobPratt's user avatar
  • 32.3k
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 ...
Mark L. Stone's 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 ...
Mark L. Stone's 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}})$.
Johan Löfberg's 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 ...
mohit-mhjn's user avatar
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 ...
RobPratt's user avatar
  • 32.3k
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 \...
Mark L. Stone's user avatar
5 votes

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

Provide the standard citation for YALMIP ...
Mark L. Stone's user avatar
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 ...
ErlingMOSEK's user avatar
  • 3,166
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 ...
prubin's user avatar
  • 39.3k
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}^{...
Johan Löfberg's user avatar
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.
RobPratt's user avatar
  • 32.3k
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 ...
Erwin Kalvelagen's user avatar
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 ...
batwing's user avatar
  • 1,508
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 ...
Kevin Dalmeijer's user avatar

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