Convex Optimization is a special case of mathematical optimization. It includes Linear Programming and least-squares.

learn more… | top users | synonyms

0
votes
0answers
11 views

$\max\{c^Tx:Ax\le b,x\ge 0\}=+\infty$ iif it exists $j\in\{1,…,n\}$ such that $\max \{x_j:Ax\le b, x\ge 0\}=+\infty$

Show a vector $\vec c$ exists such that $\max\{c^Tx:Ax\le b,x\ge 0\}=+\infty$ if and only if it exists $j\in\{1,...,n\}$ such that $\max \{x_j:Ax\le b, x\ge 0\}=+\infty$ I'm only asking for a ...
0
votes
0answers
26 views

Positivity of the last component of non negative least squares based on active set method

I have followed the instructions given in Lawson and Hanson book for non-negative least squares using active set method. I am having a trouble in justifying one of the statements they have made about ...
0
votes
0answers
18 views

Can a linear program be optimal if its basis is infeasible?

I want to know thanks to the dual theorem wether the following basis is or isn't optimal. That is to say looking for the slack variables. As far as the third line doesn't respect the constraints: ...
0
votes
0answers
11 views

Which coefficient to start with in the dictionary method?

I used to start with the variable with the biggest coefficient in the goal function (in the case of max). yet I read an article that behaving like this may lead to loop. It is rather preferred to do ...
1
vote
1answer
24 views
+100

Why is the Barycenter operation in Hadamard spaces Lipschitz continuous?

I am looking into exercise 9.2.22 of "A course in metric geometry" by Burago-Burago-Ivanov. For a Hadamard space $H$ (a complete simply connected metric space of nonpositive curvature in the ...
2
votes
0answers
37 views
+100

Optimization of approximate functions using varying objective function

Let $g(\theta;x)$ and $f(\theta;x)$ be two convex functions such that $g$ asymptotically approximates $f$: $g(\theta;x)\approx f(\theta;x)$, specifically: $$ |g(\theta;x)-f(\theta;x)| \leq ...
0
votes
0answers
18 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 ...
1
vote
1answer
29 views

Converting generic linear problems into their dual

I'm revising how to do dual problems in linear algebra. I'm very weak in Linear programing but I struggle to cope with the topic during lectures and assignements. I have to convert the following ...
0
votes
0answers
27 views

How to deal with an $xy\le 1$ constraint?

I have to solve the following optimization problem: $$ \begin{align*} \min_{x,y} &\{-x-y\} \\ \text{such that} \\ y &\ge 3 \\ y &\le 30 \\ x &\ge 0 \\ xy &\le 1 \\ \end{align*} $$ ...
0
votes
1answer
20 views

Convexify $x\le a+by^2$

I have the following non-convex constraint: $$ x\le a+by^2\quad\text{where}\quad a,b>0,\,y\in[0,y_{max}]\text{ and }a\approx by_{max}^2 $$ On a drawing, it looks something like this: The above ...
0
votes
0answers
18 views

Coordinate descent with equality and inequality constraints

I have an intuitive understanding of why the simple method of coordinate descent does not work with linearly coupled constraints such as; $$\min_x\sum_if_i(x_i)$$ $$s.t.$$ $$Ax=b$$ If we try to ...
0
votes
0answers
8 views

How to compute norm bound error in robust approximation

I am reading convex optimization, and I am little confused about the following two prolems in norm bound error of robust approximation. How to compute $\{\|\bar{A}X-b+Ux\| | \|U\|\le a\}$ ? For the ...
0
votes
0answers
10 views

reference for convex function results

Here is a simple property of a concave function from $\mathbb{R}$ to $\mathbb{R}$, Given $x,x'\in \mathbb{R}$ with $x'>x$, if $\exists \kappa'\in (0,1)$ such that ...
0
votes
0answers
9 views

Sequential convex second order cone programming [on hold]

I am trying to solve an optimization problem where the objective function is convex, the inequalities are second order cones but I also have nonlinear equality constraints. The convex energy can be ...
0
votes
1answer
17 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 ...
-1
votes
0answers
6 views

number of constraints is a variable [closed]

I have a mixed integer programming problem. Some of my variables take fixed value (say 0), which is dependent on the integer variable. Are there any references to this kind of problem. The objective ...
-2
votes
0answers
46 views

Please help… is this a convex function?

Kindly help me. What can we say about the function $f$ shown in below? is it convex or non-convex over the variables $x_1, x_2,.., x_{n+1}, y_1,y_2$? \begin{align} f(x_1, x_2,.., x_{n+1}, ...
1
vote
1answer
53 views

Solving a linear program thanks to complementary slackness theorem

Using the complementary slackness theorem, say if the following basis optimal: $$x_1*=0=x_5*,x_2*=4/3,x_3*=2/3,x_4*=5/3$$ \begin{cases} \max & 7x_1 ...
2
votes
1answer
27 views

Use of binary variables in LP problems

I can't figure out how to write the following condition to an LP. I have four nonnegative variables: $X_A$, $X_B$, $X_C$, and $X_D$. The condition which should be satisfied is this: If $X_A$ and ...
0
votes
0answers
13 views

Impact of removing active constraints in convex optimization

In active set methods for non negative least squares, we remove variables from the passive set to active set if the least squares solution gives negative values on those variables. What's the impact ...
1
vote
1answer
14 views

Chebyshev's approximation understanding

I am reading Boyd's book on convex optimization. Could you assisst me in understanding what this expression means: $$\text{minimize} \ \ \text{max}_{i=1,...,k}|a_i^Tx-b_i|$$ This is what I think ...
0
votes
0answers
21 views

Is the minimum point of a strictly convex function stable?

This is a problem I figured out after seeing the definition of minimum stable point and I think the following tense is true: Let $f(x)$ be a strictly convex function whose minimum values is ...
1
vote
0answers
57 views

When does a variable goes out with the revised Simplex method?

Let be the following linear program. \begin{cases} \max & 3x_1& +x_2\\ &x_1&-x_2 &\le -1\\ &-x_1 &-x_2&\le -3\\ &2x_1 &+x_2 &\le4\\ x_1,x_2\ge 0 ...
3
votes
2answers
68 views

Can you prove that this function is convex? $\sqrt{2x_1^2+3x_2^2+x_3^2+4x_1x_2+7} + (x_1^2+x_2^2+x_3^2+1)^2$.

My analysis: The second term can be proven to be convex as follows. It is basically a composition of norm with an affine transformation to the power of four: $(x_1^2+x_2^2+x_3^2+1)^2 = \|(x_1^2, ...
0
votes
0answers
9 views

Pseudo-Boolean functions restricted to integers

The Pseudo-Boolean functions are of the following form. $$ f : \mathbb{B}^n \to \mathbb{R} $$ I would like to know if there is a special sub-category of $$ f : \mathbb{B}^n \to \mathbb{Z} $$ with ...
0
votes
0answers
29 views

Residual norm of active set method in non negative least squares

I am having trouble with understanding one of the statements in active set methods done for non negative least squares given in Book written by Lawson. The quadratic problem can be written as ...
1
vote
0answers
26 views

Find the smallest affine subspace

Find an equation, describing the smallest affine subspace, containing the points: $$(1,2,3,4),(1,1,0,0), (1,0,1,0), (1,0,0,1)$$ I know that a non-empty subset $M\subseteq \mathbb R^d$ is called an ...
1
vote
0answers
10 views

Variant of conjugate function: $V(s) = \underset{x}\max \{\langle s,x-x_0\rangle-\beta f(x)\}$

Consider one variant of conjugate function: $$V(s) = \underset{x}\max \{\langle s,x-x_0\rangle-\beta f(x)\}$$ You can think $s$ as a linear functional. If I do the following steps: ...
0
votes
0answers
24 views

How to form a dual problem in convex optimization (in a broad view)

After reading some papers, this problem confuses me. There are different forms of dual problem to the primal problem: $$\underset{x}\min \ \ f(x)$$ where $f(x)$ is a convex function. By ...
0
votes
1answer
30 views

characteristic cone of polyhedral

Let $$Q=\{x ∶ Ax ≤ b \}≠∅$$ If $Q = P + C$, where $P$ is a polytope and $C$ is a polyhedral cone, prove that $$\{y|Ay ≤ 0\} = \{y|x + y ∈ Q, ∀ x ∈ Q\}$$ The cone $C = \{y|Ay ≤ 0\}$ is ...
0
votes
0answers
51 views

min-max problem

Hello to everybody: I'm trying to prove that : Let $A$ be the incidence matrix of a clutter (simple hypergraph) $C$. Prove that the vertex covering number and the matching number of $C$ satisfy: ...
1
vote
2answers
35 views

$\big\langle\nabla f(x)-\nabla f(y),\,(x-y)\big\rangle\ge m\,\left\| x-y\right\|^2,\;m>0\;$ for strictly and strong convex function

Prove that $\,\big\langle\nabla f(x) - \nabla f(y),\, (x-y)\big\rangle \geq m\,\left\lVert x-y\right\rVert^2, \;\,m > 0\,$ for strong convex function $f: \mathbb R^n \to\mathbb R$. Is it true ...
1
vote
0answers
24 views

Is there a way to determine if the Convex Hull of two polyhedra is going to be huge?

So in this post: Faster Algorithms for Convex Hulls I was interested in determining if a convex hull of two $n$ dimensional polyhedra can be computed quickly, and the answer was in general: no, ...
1
vote
0answers
74 views

Some intuition on the support function of a convex set

I have some doubts on the interpretation and properties of the support function of a convex subset of $\mathbb{R}^d$. (1)Let $K$ be a convex set in $\mathbb{R}^d$. (2) The support function of $K$ is ...
1
vote
2answers
27 views

Is a convex cone a convex polyhedron?

Say that I have a convex cone $C=\{t|Ax = t, x\geq 0\}$. where $x\in R^n$, and $t\in R^m$, $A\in R^m\times R^n$. Can I say that this is a convex polyhedron? and why? EDIT: Just in order to avoid ...
0
votes
0answers
25 views

Is this the correct proximal operator?

I'm supposed implementing certain optimization algorithms (ISTA, FISTA) to minimize: $$\frac12 ||Ax-(Ax_0+z)||_2^2 + \lambda ||x||_1.$$ $A$ is a matrix, $x$ is a vector, $z$ is some noise filled with ...
0
votes
1answer
32 views

Convex optimization: Piece-wise, quadratic objective

This question is about convex optimization with a convex objective function, which is defined piecewise. We have two functions, a concave function A(x) and a strictly convex, increasing function B(x), ...
0
votes
2answers
30 views

$\max 2x_1 +x_2$ unbounded or unfeasible with the constraint $sx_1 +tx_2\le-1$

\begin{cases} \max & 2x_1 &{}+x_2\\ & sx_1 &{}+tx_2&\le-1\\ & x_1,x_2&&\ge 0 \end{cases} Find out when this program is not feasible, bounded Feasibility It ...
0
votes
1answer
25 views

Show convexity of $f(x,y,z)= x^2+y^2+z^2+xyz$

Let $f(x,y,z)= x^2+y^2+z^2+xyz$. Show that $f$ is convex on $\Omega=${$(x,y,z)\in R^3 : x^2+y^2+z^2<\frac{5}{2}$}. To prove it, I want to show that $\nabla^2f(x,y,z)$ is positive definite. I ...
0
votes
0answers
12 views

Is the sum of a bivariate convex function Schur convex?

A well known fact is: Let $f(x)$ be a convex function. Then $g(\vec{x})=\sum_{i=1}^N f(x_i)$ is Schur convex in $\vec{x}$. Supose $f(\vec{z})$ is a convex function of $\vec{z}=(x,y)$. How to ...
1
vote
1answer
30 views

Choosing $\lambda$ to yield sparse solution

I'm supposed implementing certain optimization algorithms (ISTA, FISTA) to minimize: $$\frac12 ||Ax-(Ax_0+z)||_2^2 + \lambda ||x||_1.$$ $A$ is a matrix, $x$ is a vector, $z$ is some noise filled with ...
0
votes
0answers
32 views

Weights in goal programming

I'm not quite convinced about assigning weights in goal programming. Here is an example formulation problem. What I tried: Let $x_j$ be the number of minutes for ad $j = R, T$ We want to ...
-2
votes
0answers
16 views

Where does the duality comes from in linear programing and can we get the optimal basis from it?

$$\begin{cases} \max & c^Tx\\ & Ax\le b\\ & x\ge 0 \end{cases}\Leftrightarrow \begin{cases} \min & y^Tb\\ & y^TA\ge c^T\\ & y^T\ge 0 \end{cases}$$ Then we come to the ...
-1
votes
0answers
44 views

Nonlinear constraints replaced by parameters and estimated iteratively

I have an optimization problem with nonlinear constraints in the following form: $x + y + 0.5(x+y)^2-z = 0$ $s+(x+y)*t\ge M$ I linearize these constraint by replacing the nonlinear terms by ...
0
votes
0answers
8 views

Finding the lower bound of a linear program with the duality method

The issue I have some difficulties understanding the lower bound of a program when applying the duality method. It seems that it comes from $$c^T\underbrace{\le}_{x\ge 0\\y^TA\ge c^T} ...
0
votes
0answers
18 views

Can the constrained optimization problem (1) be transformed into the unconstrained form (2)

(1) \begin{equation}\label{constrained} \begin{array}{cl} \arg \min \limits_{\mathcal{C}_k} & \text{rank}(\mathcal{C}_k)\\ \mathrm{s.t.} & \mathcal{E}(\phi_{j}^{k})\le \epsilon ...
0
votes
0answers
19 views

general framework for proof of convexity in least square problem

Let $f(x_i,\theta) : X \times \Theta \rightarrow Z$ be a parametric function with parameter $\theta$ that we wish to fit to set of samples $S =\{(x_i,z_i)\}_{i=1}^N$, where $(x_i, z_i) \in X \times ...
3
votes
1answer
44 views

Convex set: extreme points and distance to the origin

I'm fairly sure the following is true, although I wouldn't mind being proven wrong. If true, I would like to see an elegant proof, as my attempts are kind of messy. Let $K\subset\mathbb R^2$ be a ...
0
votes
0answers
13 views

Equality constraints into inequalities constraints through elimination

I read here in Section 10.1.2 of this text that a way to eliminate linear equality constraints of the type $$Ax = b$$ in convex optimization problems is to parameterize the related affine space as a ...
0
votes
0answers
24 views

Are the constrained optimization problem equal to the unconstrained one?

(1) \begin{equation}\label{constrained} \begin{array}{cl} \arg \min \limits_{x} & \|Ax-b\|_2\\ \mathrm{s.t.} & \|x\|_1\le \epsilon \end{array} \end{equation} (2) ...