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

0
votes
1answer
43 views

Elastic LP Programming

Say I have an LP that is unfeasible and that I want to find the solution that makes it feasible without strongly violating the current constraints. What is a principled way of solving this problem, ...
4
votes
4answers
86 views

Plane constraints in R3

I have multiple plane constraints in $\mathbb{R}^3$ of the form: $$n_i \cdot x \ge \delta_i$$ Where $n_i$ is the $i$th plane normal (in form (x, y, z)), $x$ is a point in space, and $\delta_i$ is ...
0
votes
1answer
43 views

Custom CVX Functions - Overriding Errors [closed]

I have constructed a function in Matlab that is convex and increasing (qualitatively similar to an exponential function but I am hoping to avoid the successive approximation requirement of exp). In my ...
5
votes
0answers
58 views

Non-linear optimization using approximate gradient

I'm working with non-linear optimization for imaging, such as MRI and CT. Our problem is of the form $\|Ax-b \|_2^2+\lambda \|Wx\|_1$. $A$ is never formed explicitly, so we're limited to approaches ...
5
votes
2answers
98 views

Minimizing 1D convex functions

I have a one dimensional convex function $$f : [a,b] \to \mathbb{R}$$ and want to find the minimum value $$\min_{a \le x \le b} f(x)$$ I know all derivatives of $f$, so the problem could easily be ...
7
votes
4answers
283 views

Linear programming with matrix constraints

I have an optimization problem that looks like the following $$ \begin{array}{rl} \min_{J,B} & \sum_{ij} |J_{ij}|\\ \textrm{s.t.} & MJ + BY =X \end{array} $$ Here, my variables are matrices ...
1
vote
1answer
55 views

Convex objective function of matrix with prescribed determinant and trace

I have real symmetric positive definite matrix $M = \left(\begin{matrix} a & b \\ b & c \end{matrix}\right)$ where $a,b,c \in R,\ a,c>0,\ \left|b\right|<2\sqrt{a c}$. I want to define ...
2
votes
1answer
109 views

Solve Regularized Least Squares problems using Matlab optimization toolbox

I am trying to solve a least squares problem where the objective function has a least squares term along with L1 and L2 norm regularization. I am unable to find which matlab function provides the ...
0
votes
1answer
74 views

Checking the convexity or the concavity of a function

I have an optimization problem with the following objective function. $\max_{a^{l}_{n,k} b^l_{n,k}} \sum_{n=1}^{\overline{N_l}} b_{k,n} \frac{C_1}{C_2} \log_2 \bigg(1 +\frac{a_{k,n} h_{k,n}} ...
1
vote
2answers
307 views

Tikhonov regularization in the non-negative least square - NNLS (python:scipy)

I am working on a project that I need to add a regularization into the NNLS algorithm. Is there a way to add the Tikhonov regularization into the NNLS implementation of scipy [1]? [2] talks about it, ...
0
votes
0answers
34 views

polynomiality of a problem

I have a feasibility problem as follows: Does there exist a $p\geq 0$ such that $Ap+Gq=b$ for every non-negative $q\in D$. Here $A,G$ are adjacency matrices and $D$ is a convex set. Is this problem ...
0
votes
0answers
44 views

Minimizing a quadratic form

I would like to minimize the following quadratic form: $$ f(\mathbf{\theta}) = (\mathbf{y} - \mathbf{\mu}(\mathbf{\theta}))^T \mathbf{\Sigma}({\mathbf{\theta}})^{-1} (\mathbf{y} - ...
0
votes
2answers
81 views

Nonconvex Optimization

Consider the following optimization problem: $\text{max}_{p} \quad ||p||^2 \\ s.t: x\geq 0\\ p\in D$ where $D$ is a convex set. Is this problem $\mathcal{NP}$-hard?
1
vote
1answer
40 views

Optimal linear transform in a simplex

I'm looking for a simple method to find a linear transform that minimizes $$ \text{argmin}_T F(T): T \in \mathbb{R}^{m \times n} ,\ T \ge 0 ,\ T \mathbb{1} = c \mathbb{1} ,\ \mathbb{1}^T T = ...
2
votes
2answers
59 views

minimize function with convex constraints

I need to solve the following problem: For a given p=(x0,y0,z0,w0) and arbitrary T. For example , let p=(0.8,0.1,0.06,0.04) and T=-1.2. I need to find a vector q=(x,y,z,w) with the minimum ...
9
votes
2answers
198 views

Computation Effort of Algorithms

Consider the strictly convex unconstrained optimization problem $\mathcal{O} := \min_{x \in \mathbb{R}^n} f(x).$ Let $x_\text{opt}$ denote its unique minima and $x_0$ be a given initial approximation ...
0
votes
1answer
177 views

minimization of a convex piecewise linear function [closed]

Let $$f(x) = \left\{ \begin{array}{l} {a_1}x + {b_1} & if\,0 \le {x_1} \le x \le {x_2}\\ {a_2}x + {b_2} & if\,{x_2} < x \le {x_3}\\ \vdots \\ {a_n}x + {b_n} & if\,{x_{n - 1}} < x ...
0
votes
0answers
35 views

How to choose the subgradient?

I have a threshold linear function as a part of my convex objective function I want to optimize. $f(x) = 0$ for $x < 0$, and $f(x) = x$ for $x \geq 0$. It's not differentiable at 0, but ...
0
votes
0answers
47 views

Issues with CVX package for optimization

I am trying to use the cvx package for optimization. However, I am having some issues with it. I have a variable X which is a matrix but I cannot add $X^{-1}$ in the objective function. What should I ...
7
votes
2answers
231 views

How to deal with norm inequality constraints

I want to solve the (convex) optimisation task: $max_{r,z}\quad r$ subject to the following two constraints $r\|x_i\| - x_i^Tz \leq 0 \qquad \forall i=1,\dots, N $ $\|z\| \leq 1$ $r\geq0$ $r$ is a ...
1
vote
0answers
17 views

Reduction for NP-hardness [duplicate]

Consider the following optimization problem: \begin{align} \text{Min}_{i\neq j\neq s\neq t} |x_i x_j-x_sx_t|\\ s.t: Ax=b\\ x\geq 0; \end{align} This problem can be seen as an instance of non convex ...
2
votes
2answers
160 views

NP-Completeness

Consider the following optimization problem: \begin{align} \text{Min}&&\frac{1}{2}\sum_{(i,j,s,t)\in I, i\neq j\neq s \neq t}|x_ix_j-x_sx_t|^2\\ s.t.: && Ax=b\\ &&x\geq 0 ...
0
votes
0answers
46 views

Proper Algorithm for Image Recovery from Compressed Measurements in Office Spaces

Can anyone please suggest a proper algorithm for image reconstruction from undersampled data for office spaces ? Basis Pursuit (BP) works for sparse images which would not be a correct assumption for ...
5
votes
1answer
96 views

How to transform such an SDP to standard form

I plans to use CSDP to solve the following semi-definite problem: $$\min_{B, \beta}\operatorname{trace}(CB) \\ \text{s.t.} \ \operatorname{trace}(AB)=1 \\ \beta\geqslant 0 \\ \begin{bmatrix} 1 & ...
4
votes
2answers
128 views

Optimization algorithm selection for 3 variable integer

I have a cost function: $f(x,y,z) \rightarrow \mathbb{R}$ it is very expensive to evaluate $x,y,z \in \mathbb{Z}$ 0 < x < 10 0 < y < 30 0 < z < 100 I thought it was convex, not ...
3
votes
2answers
192 views

Quadratic Programming: Quadprog

Given a real-rectangular matrix $S$ and inorder to solve this simple quadratic programming problem: Minimize $w'S'Sw = ||S w||^2$ over $w$ subject to $e^Tw = 1$ and $w \geq 0$ using a solver I ...
3
votes
1answer
322 views

Biconvex optimization problems

Consider minimization of a biconvex function over a biconvex set. Is the biconvex optimization problems polynomially solvable?
3
votes
3answers
203 views

How to prove that a function is convex?

I'm calculating the gradient of a function with a symbolic math library called theano. Then I'm using gradient descent to find the minimum of the function. I'd like to prove that the minimum is a ...
0
votes
2answers
73 views

Analytical form of the minimum of a function with absolute values

I would like to find the analytical form of the point which minimizes the following function: $$ f(x_T) = \frac{1}{T} a_1 (x_T-x_0)^2 + a_2 |x_T-x_0| + T a_3 + \sum_{i=1}^M p_i \left[b_{1i} (x_T - ...
3
votes
2answers
232 views

Finding A and X such that AX = 0, X is positive non-zero, and A is sparse

I apologize if this is a naive question. I'm trying to create some boostrap data for a system of linear, ordinary differential equations at steady state. Since the equations represent the ...
7
votes
2answers
110 views

Why is the Dual problem preferred for Maximal Margin Classification?

The primal problem is $$\min_{w,b}\frac{1}{2}w^Tw$$ $$s.t. f_i(w)=1-y_i(w\cdot x_i+b)\leq0$$ Where $y_i=\pm1$. Instead of using Gradient Descent directly, the dual is usually solved: ...
1
vote
1answer
81 views

Confusion related to convexity of 0-1 loss function

I am a bit confused why the 0-1 loss function is not convex. What's wrong with it?
4
votes
5answers
767 views

MATLAB's CVX Package to minimize $\mathrm{trace}(S)+\mathrm{trace}(S^{-2})$

I would like to minimize in matlab the function $f(S)=\mathrm{trace}(S)+\mathrm{trace}(S^{-2})$ where $S\in \mathcal{M}_{m,m}$ symmetric positive definite which is definitely convex function. So I ...
1
vote
1answer
50 views

Confusion related to interior point method for optimization

I have this little confusion related to interior point method. In this method we use the log barrier function to approximate the real barrier which is not differential Now when we find the optimal ...
2
votes
1answer
49 views

Confusion while proving logdet function to be concave

I was going through this lecture related to convex optimization. It was proved that logdet function is concave. However, I didn't get the derivation at a part I didn't get how the step marked in ...
6
votes
1answer
157 views

Confusion related to convexity and concavity of a function

I was reading this paper http://www.ist.temple.edu/~vucetic/documents/wang11kdd.pdf related to adaptive multi-hyperplane machine for non linear classification In that paper, they have mentioned about ...
0
votes
1answer
125 views

Robust Counterpart of an uncertain LP

Consider the following robust optimization problem: min c'x s.t.: $Ax\geq b \;\;\forall (A,b)\in \mathcal{U}$. Why can the robust counterpart of the problem be written in this form? $min_x{\{ ...
0
votes
1answer
30 views

Polynomial solvability [duplicate]

Consider the following optimization problem: Min$_{x}$ $\qquad \sum_{(i,j,t,s)\in I_r}||x_ix_j-x_tx_s||^2$ S.t.: $\qquad x\in \mathcal{C} ;$ where $x=(x_1,x_2,...x_n)$ and $\quad x_j\geq 0\;\; ...
1
vote
1answer
78 views

Feasibility checking

Consider the following optimization problem: $Min\;\;\; CX$ $AX\geq b$ $x_ix_j= x_s x_t\;\;\; i\neq j \neq s\neq t$ $x_j\geq 0;$ Where $A$ is the adjacency matrix and $C$ is a constant vector. ...
2
votes
2answers
108 views

polynomial time solvability

Consider the following optimization problem: $Min \qquad C^TX$ S.t.: $\qquad AX=0;$ $x_ix_j=x_kx_t$$\quad $for some $i\neq j\neq k\neq t$ $X=(x_1,x_2,...x_n)$ and $\quad x_j\geq 0\;\; ...
2
votes
1answer
70 views

Nonlinear bad constraints

I have an optimization problem with linear objective function. The constraints are in two different groups. The first set of constraints are linear while the second set is nonlinear. The nonlinear ...
4
votes
1answer
139 views

Numerical Methods for minimizing a Non-Differentiable Convex Function of Several Variables

I have a multi-variable convex continuous function which is not differentiable. I am interested to know about different numerical techniques, possibly also references to them, used for this. Read ...
2
votes
1answer
105 views

Extreme points from constraint expression of convex space

I'm looking for the extreme points of the convex set $S\subset [-1,1]^{n\times 3}$ with $r\in S$ such that \begin{equation} r_{i} \ge r_{k} \iff i\ge k, \end{equation} where the first inequality ...
7
votes
2answers
207 views

Max of a convex combination over a convex hull of real variables

I have the following linear program: $$ \begin{array}{cc} \text{Maximize} & a^T x \\ \text{Subject to} & x_{\min} \leq x \leq x_{\max} \\ & \mathbf{1}^T x = 1 ...
1
vote
1answer
65 views

Existence of a solution at a stationary equation for quadratics

Given a convex quadratic function $f(x)$, to obtain a solution for which $f(x)$ has minimal value one sets $\nabla f(x)=0$, and solves for $x$. Suppose that the result of differentiation of convex ...
4
votes
1answer
55 views

Minimal point of a intersection of $n$ convex sets is always the minimal point of the intersection of two convex sets?

I have the intuition that the minimal point (in the sense of having the lowest value in one of the Euclidean space dimensions) of a intersection of $n$ convex sets is always the minimal point of the ...
2
votes
2answers
330 views

Quadratic program With Linear Constraint vs. Eigen Decomposition Time Complexity-Comparison. Which is faster?

Say I had the choice of choosing one out of the following two optimization problems which I could use to solve my problem. Which choice is the fastest? How much of a trade-off would it be-as in - Is ...
8
votes
2answers
1k views

CVXOPT VS. OpenOpt

CVXOPT: http://abel.ee.ucla.edu/cvxopt/index.html OpenOpt: http://openopt.org/Welcome What's the relation between them? What are the advantages/disadvantages of them, respectively? BTW, is there ...
7
votes
2answers
105 views

Is it possible to represent non-linear ranking type constraints as equivalent linear constraints?

I have formulated a linear program with binary indicator variables $z_i(a)$ which is equal to $1$ if the $i^{th}$ document is of rank $a$ and $0$ otherwise. The other variables in the linear ...
8
votes
3answers
170 views

How to intellligently attempt to rule out convexity?

I want to minimize a complicated objective function, and I'm not sure if it is convex. Is there a nice algorithm that attempts to prove that it is not convex? Of course the algorithm could fail to ...