Questions tagged [convexity]

For questions related to convex functions and convex sets, especially as they relate to optimization problems.

46 questions
Filter by
Sorted by
Tagged with
74 views

52 views

Find a dual problem with one dual decision variable to the problem of finding the orthogonal projection of a given vector

Given the set $T_{\alpha}=\{x\in\mathbb{R}^n:\sum x_i=1,0\leq x_i\leq \alpha\}$ For which $\alpha$ the set is non-empty? Find a dual problem with one dual decision variable to the problem of finding ...
92 views

185 views

187 views

Solving convex programs defined by separation oracles?

General question: What software can solve convex programs defined by a separation oracle? The objective function is concave, and the feasible set is a polytope. By a separation oracle I mean that I ...
1k views

Is This Constraint Convex?

I have a constraint that I believe to be convex and not affine which I think means that I can implement a relaxation. I will first define the full constraint, and then build up my (informal) reasoning ...
346 views

Convexity of a QP

In quadratic programming (QP), you encounter an objective of the following form: $$x^TQx + c^Tx$$ and often it's desirable to know if the QP is convex. One method to check for convexity is by ...
604 views

I'm looking for examples of (classes of) problems with a non-convex, non-linear formulation, but convex feasible region. That is, a problem of the sort: \begin{array}{lll} \text{minimize} & ... 2answers 487 views Dedicated solver for convex problems Are you aware of a fast solver (open source or commercial) for convex NLPs that is faster than IPOPT? I'm interested in problems in the 50K+ variable range, both dense and sparse. Ideally, it would be ... 3answers 3k views Can an integer optimization problem be convex? I'm trying to wrap my head around an apparent paradox that I've come across while trying to learn more about optimization algorithms: On one hand several sources state that convex optimization is ... 1answer 356 views Convexity of Variance Minimization X is a discrete random variable taking value x_n with probability 1/N for n=1, \ldots,N. I would like to set the x_n values in an optimization problem. My objective is to minimize the ... 5answers 4k views Linear Programming with additional "if-then"/"Default to zero" constraints? What approaches can I use for a Linear Programming problem with the additional constraint that if a decision variable falls below a certain threshold, then it should just be forced to 0. I'm ... 2answers 353 views Convex vs Strictly Quasiconvex Functions in Optimization I have read/heard quite a few time that in the old days, it was considered that linear programs constitute the class of optimization problems that can be solved efficiently in practice (as a rule of ... 1answer 477 views How to formulate a problem to prove/disprove convexity? Given a general non-linear problem: \begin{align}P:\qquad&\min_{x\in X} f(x)\\\text{s.t.}\qquad&g(x)\leq 0\end{align} where f is a non-linear function, g is a vector of non-linear ... 2answers 251 views How to determine the convexity of my problem and categorize it? My problem is: \begin{align}\min\limits_{x_{ij}}\qquad&{\sum_{i\in N}\sum_{j\in M}\frac{x_{ij}}{C_j-\sum\limits_{i\in N} x_{ij}a_i}}\\\text{s.t.}\qquad&0<C_j-\sum_{i\in N} x_{ij}a_i\\\qquad&... 1answer 219 views Recovering primal optimal solutions from dual sub gradient ascent using ergodic primal sequences My question concerns recovering a primal optimal solution while performing dual sub gradient ascent. Denoting by y_i the dual multiplier in the i^{\text{th}} iteration, let \begin{equation} x_i = ... 2answers 386 views How can I linearize or convexify this binary quadratic optimization problem? I have an optimization problem as below. I am having a hard time with the last constraint. \max \eta subject to {\bf U}(:,m)^T{\bf A}{\bf U}(:,m)=0,m=1,2,\cdots,M here \bf{A} is a Binary ... 2answers 150 views Bound on the number of constraints to be generated (lazy constraints) I am working on a very large optimisation problem. All variables are continuous, the objective is linear and the constraints convex, but I have many such constraints (on the order of 2^n — actually, ... 1answer 382 views KKT inequality conditions Let's say I have an objective functionf(x_1,x_2, \cdots, x_n)$$and N constraints$$x_i \ge 0. $$I am trying to solve it with KKT conditions. Now the objective function becomes$$f(x_1,x_2,...
It is well known that expectation preserves convexity: If $f(x)$ is convex and $Y$ is a random variable, then $\mathbb E[f(x-Y)]$ is convex. This property arises in, for example, inventory theory. I ...