# 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 ...

16

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, y)$ is convex in $x$ for each $y\in A$, and $w(y) \ge 0$ for each $y\in A$, then the function $g$ defined as $$g(x) = \int_A w(y)f(x, y)\, dy$$ is convex ...

14

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 ...

14

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 can think of as a layman in the field that are convex, are (probably) tractable to solve. That's why you would be told that in an introductory course on convex ...

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

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 that case, some solvers might be able to exploit that! Disciplined geometric programming is another way to teach solvers how to exploit convexity in nonlinear ...

10

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 programming), you can find the solution in polynomial time using interior-point methods. The reason the optimization community is going against the pure "...

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

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

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 the KKT's are the first-order necessary conditions for optimality. For convex nonlinear optimization, you are better off using sequential quadratic ...

10

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 $L_i \le 0 \le U_i$. Create variables $y_i\ge 0$ and $z_i\in \lbrace 0, 1\rbrace$. For each $i$, add the constraints $$0 \le y_i - x_i \le -2L_i (1-z_i)$$and ... 9 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 following two feasible solutions: Value of the product at its minimum feasible value (Ordering quantity at its given threshold). Value of the product at zero (... 9 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 Vandenberghe 9 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 constraints. If any lazy constraints are violated, add some of the violated constraints and solve again. Stop when the solution satisfies all lazy constraints. ... 9 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 9 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 Hessian of L with respect to \lambda and \mu. I used MAPLE to compute the Hessian, and then evaluate its eigenvalues at the point \lambda = 0.5, \mu = 1. ... 8 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/don't buy" variables and the related bounds are order sizes are handled internally by the solver rather than explicitly in your model. Some citations (shamelessly ... 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), ... 8 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 typical equation with the simpler notation x^T A x = 0 (mostly to save typing). A square matrix A may have a square root B, such that BB=A. In some cases, ... 8 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,m)U(j,m) terms as explained here. 8 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 \in M.\end{align} The following example shows that the answer to your question is no. Let n = 2 and take c = (0,1)^\top. Furthermore, letM = \{x \in \...

8

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 convex (and not concave). Check out this link, it is well explained, or this one for an algeabraic proof. Your example has only one feasible point (assuming $... 8 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 at the simple case of$a = b = c = 1$. The Hessian of$\frac{{ax}}{{\ln (b + cy)}}$at$x = y = 1$has one positive and one negative eigenvalue. Hence$\frac{{ax}...

7

$\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,1]$ \begin{align} \phi(\alpha x + (1-\alpha)x') {}={}& \E[f(\alpha x + (1-\alpha)x'-Y)] \\ {}={}& \E\left[f\left(\alpha x + (1-\alpha)x'- \alpha Y - (1-...

7

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.

7

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. Therefore, practical criteria are developed and implemented whereby the algorithm is terminated and optimality declared when the optimality conditions (or convergence)...

7

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 of two variables; e.g. How to linearize the product of two continuous variables? How to linearize the product of two binary variables? How to linearize the ...

7

No, linear programming is convex, which you can prove directly from the definition. If $A x \le b$ and $A y \le b$, then for arbitrary $\alpha\in[0,1]$, we have $$A (\alpha x+(1-\alpha)y) = \alpha A x+(1-\alpha)Ay \le \alpha b+(1-\alpha)b = b.$$

6

You can use Singular Value Decomposition or Cholesky Decomposition. I recommend you read this Verification of Positive Definiteness. On page 9 there is an algorithm in MATLAB.

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