# Tag Info

18

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 the RHS were convex, an inequality, {affine expression} $\le$ {convex RHS}, is going the wrong direction to be convex. I suggest you study sections 2.3 and ...

18

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, and I believe may even occur sometimes for problems having convex nonlinear constraints. The starting (initial) point is often important in determining whether or ...

13

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{(e^\top x)^2}N\right) \\ & = & \dfrac{x^\top x}{N} - \dfrac{(e^\top x)^2}{N^2}. \end{array}$$ So you are minimizing the $\ell^2$-norm of an ...

13

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. \begin{align} \max\qquad& g\left(\lambda x + (1-\lambda) y\right) && \small\textrm{(maximize constraint violation of convex combination)}\\ \text{s.t.}\...

13

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) = \frac{x^4}{x}$ is not. Argument 4: Let $f(x) = x$, and $y \in \mathbb{R}$. $f$ is convex, but $g(x, y) = yf(x) = xy$ is not.

12

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 function for algorithms which attain and maintain primal feasibility, or improvement in a merit function (or similarly with filter methods) for algorithms which ...

12

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 stuck. A timeless classic, especially for MUMPS. It will suddenly slow down to a crawl for no apparent reason. It can also fail outright, which can cascade to ...

10

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 Burer shows that every mixed integer quadratic program is equivalent to some convex program that is not significantly bigger. Because mixed integer programming ...

10

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}

10

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) uploaded the following paper in arXiV. The paper compares the different Linear Solvers (and potential parallelization schemes) performance within IPOPT. They ...

8

+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 simplicity, I'll show the formulation for 3-D. \begin{align}x^2 &\le yz\\y &\ge 0\\z &\ge 0\end{align} Moving everything to the Left-Hand Side (LHS), ...

7

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): \begin{align}\min_x&\quad f(x)\\\text{s.t.}&\quad g_i(x)\leq 0, i \in C\end{align} Problem (P2): \begin{align}\max_{\lambda\ge0} \min_x&\quad f(x) +...

6

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\in \mathcal{K}}}\lambda_k\left(x_{ijk}+y_{jik}\right)}\qquad j\in\mathcal{J}$$ and this constraint will naturally be satisfied with equality for an optimal ...

6

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 &= x+y \\ \sqrt{\lambda}\sum_{j=0}^2 \sqrt{j}\cdot w_j &= z \end{align}

6

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 exploit its native mixed-integer exponential cone capability. Here is a mixed-integer example (mixture of binary and continuous): x = binvar(3,1); % binary y =...

6

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 minimum at an extreme of the constraints. You're maximizing a convex objective, which is equivalent to minimizing the negative of the objective, which is concave. ...

6

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 dimension, i.e., by introducing new variables and corresponding constraints. For instance, the term $x^3$ can be made bilinear (quadratic), by introducing a ...

6

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}})$.

5

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 \ge 0, \Sigma w_i = 1$. This can be formulated as a convex QP (Quadratic Programming problem), i.e., maximizing a concave quadratic subject to linear constraints....

5

Provide the standard citation for YALMIP @inproceedings{Lofberg2004, address = {Taipei, Taiwan}, author = {L{\"{o}}fberg, J.}, booktitle = {In Proceedings of the CACSD Conference}, title = {YALMIP : A Toolbox for Modeling and Optimization in MATLAB}, year = {2004} } which is shown at https://yalmip.github.io/reference/lofberg2004/ Then perhaps you can ...

5

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 would not (in general ... I suppose that the two problems could accidentally have the same solution for a specific set of parameters). Any immediate problem with ...

5

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 be solved efficiently in practice. First of all there are surprisingly few convex optimization problems that fall outside this class of problems and secondly ...

5

Yes, because $\log$ is monotonic, it preserves inequalities. The tightness depends on your other constraints.

4

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 f(0) & (i \in I) \end{array}$$ with $h_i(x) = f(g(x_i))$. In this case, $h_i(x)$ need not be convex. You can see this by taking $f(x) = x^3$ for example.

4

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$ otherwise. Thus we can treat $x_i$ as binary variables for the purpose of maximisation (see In an integer program, how I can force a binary variable to equal 1 if ...

4

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 representable. If the problem size is not too large, you can try solving it using Gurobi, either directly (for n<=10) or via branch-and-cut (for say n<=50; see ...

4

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}^{n}{x_ic_i^t}\ -L_t + z_t\\ {EP}_{t-1}\leq (1-\delta_t)M, -(1-\delta_t)M \leq z_t - s_t{EP}_{t-1}\leq (1-\delta_t)M\\ ~{EP}_{t-1}\geq -\delta_t M, -\delta_tM \... 3 You are trying to minimize a convex function outside (including on) a sphere. That is a non-convex constraint region, and hence a non-convex optimization problem. The statement Hence a sufficient condition for$X^T\cdot X \geq r^2$is$\begin{bmatrix} r^2 &X^T\\ X &\mathcal{I}\end{bmatrix} \preceq 0$, which is convex in$X\$ is obtained: is ...

3

Glover and Sörensen (2015) Metaheuristics have been demonstrated by the scientific community to be a viable, and often superior, alternative to more traditional (exact) methods of mixed-integer optimization such as branch and bound and dynamic programming. Especially for complicated problems or large problem instances, metaheuristics are often able to offer ...

3

In addition to the references already given in the comments, this paper (DOI link) demonstrates that exact solutions to some non-convex quadratic programs are given by semi-definite programming, and whenever the SDP relaxation is tight we can actually solve the SDP via SOCP! In general the SDP relaxation will of course not be tight, but as shown by ...

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