Convex Optimization is a special case of mathematical optimization where the feasible region is convex and the objective is to either minimize a convex function or maximize a concave function.

learn more… | top users | synonyms

1
vote
1answer
56 views

Repeated 1d minimization with similar parameters (scipy)

I have a function f(x,k1,k2) and I am trying to minimize it over x for different values of ...
0
votes
1answer
50 views

On Boyd et al.'s convergence analysis of ADMM: Why do we need the convexity assumption?

Please refer to Boyd et al.'s convergence analysis of ADMM (Chapter 3 and Appendix A). My question is: Why do we need $f$ and $g$ to be convex? I don't see the need of this assumption. If the ...
4
votes
2answers
62 views

Subgradients of non-convex functions

In these notes (section 2.3), it is stated that: A point $x^*$ is a minimizer of a function $f$ (not necessarily convex) if and only if $f$ is subdifferentiable at $x^*$ and $0 \in\partial ...
0
votes
0answers
15 views

How to solve a model with a quadratic term in the objective function on CPLEX?

I introduced a model with a quadratic objective function in CPLEX but it takes a long time to solve it, I think there is a way to tell CPLEX that the model has a quadratic objective function, but I ...
0
votes
0answers
48 views

What is the fastest method for solving a quadratic programm repeatedly,( warmstarted)?

I have a quadratic problem, \begin{align} \min_{x\in [0,1]^n} x^T p+ \frac{1}{2\lambda} x^T Q x \end{align} ($Q$ is semidefinite) which I want to solve repeatedly, with the slight change of p and Q, ...
0
votes
2answers
110 views

What method do you suggest to solve this minimax, quadratic in both variables problem?

I have a problem of the form, \begin{align} minimize_{y} maximize_{x}&\quad x^T y - y^T (B\odot x x^T) y\\ s.t. &x\in [l,u]\\ &Ay=b \end{align} How to efficiently solve this problem? ...
0
votes
1answer
72 views

How to understand what's going wrong in a code for solving a problem with augmented lagrangian?

I am very new to optimization. so, sorry If I ask a simple question. I have a problem with a dozen of variables. I want to use Augmented Lagrangian for solving the problem. I write a code based on the ...
1
vote
2answers
96 views

How to solve a constrained optimization problem using minFunc or minConf

I am trying to solve the following optimization problem: \begin{align} &\min\limits_{s} \rm{tr}\left(S^T S\right) + \mathrm{tr}\left(\left(S^T S\right)^{-2}\right)\\ &\text{subject to ...
0
votes
1answer
28 views

Express the $\gamma_{2}^{\epsilon}$ SemiDefinite program in a form that is acceptable by SDPT3

I'm trying to express the following semidefinite program: for given $A \in R^{m \times n}$ and a scalar $\epsilon \in (0,1)$, \begin{align} &\gamma_{2}^{\epsilon}(A):= \min\,t\\ ...
0
votes
0answers
25 views

Implementation in R of $l_2$ penalized weighted quantile regression

I am struggling with such a minimization problem: $$ min_{\mathbf{w}}~~\left( \lambda ||\mathbf{w}||^2 + \sum_{i=1}^{n}v_i |a_i - \mathbf{x_i}^\top\mathbf{w} - b | \right) $$ Here $v_i$ is weight of ...
3
votes
1answer
60 views

Understanding the conditions for which ADMM can be applied

While reading Boyd's paper on ADMM I encountered an issue. Consider the following problem: Problem. Minimize $f(u) + g(v)$ subject to $Au + Bv = c$, where $f$ and $g$ are closed, proper, convex and ...
5
votes
0answers
54 views

Difference of convex functions optimization problem in R

I am seeking of any already written R package which could help in optimization technique which is called Difference of convex functions. This technique is sketched here and could be very useful for ...
1
vote
1answer
115 views

How to efficently solve: min $\sum_{ij}(a_{ij}x_{ij}^2 + b_{ij}x_{ij})$ s.t

I am trying to solve the following problem, where $a_{ij} \ge 0 \ \forall i,j$: \begin{align} \mbox{minimize}\quad & \sum_{i=1}^m\sum_{j=1}^n (a_{ij}x_{ij}^2 + b_{ij}x_{ij})\\ \mbox{subject ...
3
votes
2answers
86 views

Second-order derivative condition for convexity

It is written in a book I'm reading that $$\nabla f(x) = \left( \frac{\partial f(x)}{\partial x_1}, \frac{\partial f(x)}{\partial x_2},...,\frac{\partial f(x)}{\partial x_n}\right)$$ and $$\nabla^2 ...
0
votes
0answers
60 views

Iterative optimization problem

There is problem which I am stuck in that for nearly a month. I have encountered a problem which is as follows (equation (1)). \begin{align} &\min_x &f(x) &\quad\implies \text{represents ...
6
votes
1answer
129 views

How to minimize ratio of L1 and square root of L2 norms

Here is the function I want to minimize: $$\sum_i\frac{\rho_{\tau}(1-\alpha-\pmb x_i^{\top}\pmb\beta)}{\sqrt{1+\pmb\beta^{\top}\pmb\beta}}$$ where $\alpha\in\mathbb{R}$, $\pmb\beta\in\mathbb{R}^p$ ...
0
votes
0answers
63 views

Iterative Optimization [duplicate]

I have encountered a problem which is as follows \begin{align} &\min_x &f(x)\\ &\operatorname{subject to} &h_i(x) =0\\ & &g_i(x) = 0 \end{align} where $f(x)$ is a quadratic ...
0
votes
0answers
33 views

CPLEX: function convex on search space but not on whole R^n

I have an optimization problem where the function i want to minimize is convex; it's of the form $f = \sum_i - x_i y_i$, all variables have a constraint $x_i \geq 0, y_i \geq 0$, and all other ...
0
votes
0answers
26 views

Algorithm for SDP with repeated structure, diagonal blocks

I wish to solve a semidefinite relaxation of the following problem: $$ \begin{array}{rl} \min_{z_1,\ldots,z_k\in\mathbb R^n}\ & z^\top A z\\ \textrm{s.t.} & z_i^\top B_j z_i+c_j^\top z_i=0\ ...
0
votes
1answer
152 views

Storage complexity of SDP solver SCS

This is a follow up question to this question. Consider the following SDP in standard form: \begin{align} &\min_{X\in S^n, X>0} \operatorname{tr}(AX)\\ &\mbox{subject to}\; ...
3
votes
1answer
94 views

Best platform for complex SDPs with n and m around 5-15K?

I am looking to solve a class of SDPs with complex entries, with the semi-definite cone $S^n$, $n$ around 5000 to 15000. Also, $m$, the number of equality/inequality constraints is close to $n$. I ...
3
votes
1answer
56 views

Maximizing a function over a polytope

I have to maximize $$f(x,y)=-\log(xy)$$ However I need it over the polytope $T=\mathrm{conv}\{(1/2,1/2),(1,2),(2,1)\}$ and this gives me problems: Then I get $$f_x(x,y)=1/x=0$$ $$f_y(x,y)=1/y=0 $$ ...
5
votes
1answer
138 views

Solving $ (A^{-1} + D)^{-1} v $ with low rank Cholesky factors of $A$

I have a large matrix $A \in \mathcal{R}^{N\times N}$ which is supposedly positive-definite, but numerically low rank. Instead of $A$, I have its incomplete Cholesky factor $G$, such that $A \simeq ...
1
vote
2answers
103 views

Mathematical programming formulation of triangle intersection

Given variables $a_1$, $b_1$, $c_1$ and $a_2$, $b_2$, $c_2$ representing the vertices of two plane triangles, how might one specify the requirement for the two triangles to intersect as an objective ...
1
vote
1answer
63 views

Python package for large absolute value optimisation

I have an absolute value optimisation problem $$\min_x \sum |r-Cx|$$ where $x$ is small around 200 dimension. But $C$ has lots of rows, $C_{30000\times200}$ and $r$ is $30000\times1$. So this will ...
3
votes
1answer
65 views

Fast projection onto semidefinite cone

Lots of algorithms for semidefinite programming make use of the Frobenius projection onto the cone of semidefinite matrices: $$\mathcal{P}(A) = \min_{X\succeq0} \|A-X\|_{\mathrm{Fro}}^2.$$ Let's ...
4
votes
2answers
257 views

How to determine whether two cylinders intersect or not?

Considering any two cylinders, defined as: the center of their bottoms $A_i$, the radius of their bottom $R_i$, the unit vector $W_i$ of their axis direction, and the length $L_i$ of the cylinders, ...
0
votes
1answer
45 views

Convex optimization for symmetric (but not positive definite) problems?

Can one employ convex optimization for symmetric but not positive definite problems? I tried using MATLAB's quadprog() function to solve this problem: ...
2
votes
1answer
88 views

Optimization with matrix exponential constraint

Suppose I'm optimizing for an unknown $x\in\mathbb{R}^k.$ I have a linear operator $A(\cdot)$ that maps $x$ to an $n\times n$ symmetric matrix, i.e., $A:\mathbb{R}^k\rightarrow\mathbb{R}^{n\times ...
2
votes
1answer
85 views

How can I solve a nonlinear optimization problem where constraint contains exponential term?

I have the optimization problem as below: $$\begin{align} &\text{maximize } \sum_{k=1}^{M} \alpha_k {R}_k\\ &\text{subject to: } \exp \left[ - (2^{{R}_k } -1) \left(\frac{\tilde{Z} g_{k} ...
2
votes
1answer
156 views

Comparison of convex hulls [closed]

Consider a set of polytopes $P_i : i=1,2,...,k$ each of which has a structure as $P_i:= \{(x_{i1},x_{i2},..., x_{in})\; |\; x_{ij} \in [a_{ij}, b_{ij}] \subseteq [0,1]\}\;\; \text{for all}\;\; ...
2
votes
1answer
132 views

Solve $AX = B$ where $X^T X = C$

Is there a natural way to find the solution to $$AX = B, X^TX = C \enspace \text{?}$$ $X$ is a matrix and has a small number of rows, and $A$ is sparse. An approximate solution would be fine.
4
votes
1answer
51 views

LP and SDP nomenclature

A canonical form of primal linear program is $$ \text{minimize } c^T \cdot x \\ \text{subject to } Ax = b, x \geq 0 $$ The dual is $$ \text{maximize } b^T \cdot y \\ \text{subject to ...
0
votes
1answer
55 views

Converting linear BIP constraints into convex hull

Given a linear BIP $$\text{Minimize}\;\;\;c^Tx$$ $$\hspace{6.5mm}\text{Subject to}\;\;\;Ax\leq b$$ $$\hspace{38mm}x\in\{0,1\}^n$$ We can in theory convert the constraints to the convex hull ...
0
votes
0answers
81 views

Cyclic Coordinate Descent Optimization for Bayes Logistic Regression (Code Problem?)

I am trying to reproduce the CLG algorithm for the Laplace prior given in Genkin et al to find the MAP estimates for a logistic regression model. I am using Python (Anaconda 2.2) with Numpy to ...
0
votes
2answers
124 views

Convex quadratic problem solver gives different answers?

I am pretty sure that the following variance objective function should be a convex quadratic problem. My objective function is as follows: $$ \text{argmin } \text{var }(X*L) \xi \geq 1, \text{ where ...
0
votes
1answer
162 views

Converting smooth $L1$ norm approximation into SOCP

I am approximating the expression $\left\|Ax-b\right\|_1$ by the expression $$\text{minimize}\;\;\sum_i\sqrt{(a_i^Tx-b_i)^2+\varepsilon}$$ where $a_i$ is the $i^{th}$ row of $A$. This function is ...
0
votes
1answer
159 views

What are open source codes for interior point optimization to modify?

I am working on a modified interior point algori thm for semidefinite for my special problem. I don't have enough skills and knowledge about interior point for semidefinite to code it from scratch. ...
1
vote
2answers
117 views

How to nest 2 simple CVX problems? Is it possible at all?

I have the underdetermined outer optimization problem $$\text{min}_{x\geq 0}\quad \|Ax-b_1\|_2^2+\|AT(x)-b_2\|_2^2$$ with $A\in\mathbb{R}^{m\times n}$ and $m<<n=64^2$ or in corresponding CVX ...
0
votes
1answer
64 views

How to write Goemans-Williamson MAX-CUT relaxation as SDP

Let W be a graph Laplacian (symmetric diagonally dominant, and thus PSD), and X the matrix variable. Let $<A,B>=Tr(A^TB)$. $$\text{Maximize}\;\; \displaystyle\sum_{i,j} w_{ij}(x^{(i)}\cdot ...
0
votes
0answers
31 views

comparing different practical convex optimization algorithms

I am trying to implement limited memory bundle method on piece-wise linear convex optimization problem (with dimension=5000) in c++, however, it seems limited memory bundle method code is not ...
0
votes
0answers
19 views

Applying smooth minimization on non smooth problems

Is it possible to apply Nesterov's smooth minimization of non smooth function on a problem of the form $$\mathop {\min }\limits_{\lambda \in {R^m}} \mathop {\max }\limits_{\sigma \in {{\left\{ ...
1
vote
0answers
41 views

Numerical Implementation of “integrates to some values” type constraint in convex solvers?

I am maximizing a linear functional subject to an integrates to one constraint. More explicitly, my problem is $$\begin{align} &\max_{x \in \mathbb{R}^n}\quad c \cdot x\\ &\text{subject to} ...
1
vote
1answer
152 views

Looking for open source numerical solver

I am trying to solve an optimization problem $$\begin{align} &\min f(x)\\ &\text{subject to } Ax\leq b\\ &x \in R^{\sim 10000},\ b \in R^{\sim 10000} \end{align}$$ $A$ is somewhat sparse ...
1
vote
1answer
77 views

beta in Nesterov's first method for piece wise linear convex optimization problem

I am trying to implement Nesterov's first method to solve convex piece-wise linear optimization problem, from this website: ...
0
votes
0answers
33 views

state of art non smooth convex optimization [duplicate]

Basically, I am trying to implement non-smooth convex optimization in c++. I am wondering what is the state of art condition of non-smooth convex optimization. For example, what's the best method ...
0
votes
1answer
69 views

fast gradient method for convex piecewise linear function

What is the state of art gradient based algorithms in convex optimization solving non-smooth piece-wise linear functions? Thank you. EDIT: It is different from one of my previous post in the sense ...
0
votes
1answer
156 views

Doubt regarding stopping criterion for Newton method

I am solving an unconstrained convex optimization problem, which can easily have a million variables. I am trying to get a working system with a toy problem of around 200 variables. I am noticing that ...
4
votes
2answers
215 views

Nearest positive semidefinite matrix to a symmetric matrix in the spectral norm

So I have a symmetric matrix $A$ and I would like to solve the optimization problem: $$\text{Minimize}\;\; ||A-S||_2$$ $$\hspace{-5mm}\text{Subject to}\;\; S\geq0$$ $A$ is given and $S$ is the ...
0
votes
1answer
77 views

Finding the minimum of a convex function with noisy evaluation

I want to find the argument of a function for which it is minimal. The function is expected to be convex but I cannot evaluate it exactly so I have to deal with the fact that there's noise on top. The ...