Optimization is the process of choosing the "best" value among possible values. They are often formulated as questions on the minimization/maximization of functions, with or without constraints.

learn more… | top users | synonyms (5)

2
votes
0answers
21 views

Dual Decomposition with multiple coupling constraints

This is probably a a simple question, but have been stuck on this for a while and unable to figure out my issue from the standard Boyd/Vandhenbergen decomposition references. I am interested in dual ...
1
vote
0answers
15 views

Unique maximizer

I have two functions, $f(x,y)$ and $g(x,y)$. $x\in[0,X]$ while $y\in [0,Y]$. Both functions are non-negative on the domain. Further, $f$ is increasing in $x$ and decreasing in $y$. $g$ is the ...
0
votes
1answer
107 views

An Interesting Resource Allocation Problem

Here is the problem: \begin{array}{ll} \text{minimize} & \sum_{i=1}^N \frac{1}{1 + \textrm{exp}(C_i + x_i)}\\ \text{subject to} & \sum_{i=1}^N x_i \le R \\ & x_i \ge 0, ~ i = 1,2,...,N ...
0
votes
0answers
24 views

How to prove the NP-Completeness or NP-Hardness of this MINLP problem?

I am working on an optimization problem, which is an MINLP (with binary integers). Is this MINLP an NP-Hard problem or NP-Complete problem. And how to prove the hardness or completeness? Here ...
0
votes
1answer
36 views

prove length-like function is convex

I'm trying to prove that $$ F(u)= \int_{0}^{1}\sqrt{(1+u'^2_x)}dx$$ is a convex function of $u=u(x)$ ; however after squaring both side twice of ...
0
votes
0answers
32 views

LP in standard form

I don't know how to properly named this question but here it goes: Let $x, c \in \Bbb{R}^n$, $b \in\Bbb{R}^m$, $A \in \Bbb{R}^{m \times n}$. Consider LP in the form: min $\{c^tx : Ax = b, x \ge 0\}$ ...
2
votes
0answers
26 views

How to solve the constraint nonlinear least-square problem?

I read a paper which says it can be solved by Gauss-Newton type method: I cannot understand why bsin(theta) appears.It seems so starange. Also it is very kind of you to recommend some math books ...
0
votes
1answer
32 views

Linear regression with constrained weights

I have a set of $n$ linear combinations, each with $m$ parameters and desired value $b$. I want to find the set of weights $w$ which minimizes the total equations distances (e.g. the sum of distances ...
2
votes
1answer
68 views

Three people want to personally meet each other as fast as possible: optimization problem.

Problem: Three people want to be all gathered at the same place, and they want it to happen as soon as possible. Where should they head to? P.S. Assume they all travel with the same speed. Think of ...
0
votes
1answer
33 views

What does $(y-c)^{*\beta}$ mean

I recently came across an equation which says: $$\alpha_0+\alpha_1y^{*\beta_1}+\alpha_2\left(y-c\right)^{*\beta_2}+\alpha_3\left(y-1\right)^{*\beta_3}$$ ...
0
votes
1answer
20 views

Proximal operators on Balls (Projection)

I was following this tutorial, In section 21 it is given Proximal operator over a ball $B_\epsilon$ of radius $\epsilon$ as $$\text{Proj}_{B_\epsilon(y)}(u) = y + (u-y) \max({1 , ...
2
votes
1answer
656 views

Notation: what is “arg min”

there is a function that says $j = \text{argmin}\{ f(x),g(y) \}$ What does that mean? As noted by the comment, $\text{argmin} f(x)$ is the $x$ that gives smallest $f$. But what happens when ...
1
vote
2answers
106 views

Absolute extrema of $\sin x+\cos y+\sin (xy)$ on a square

I want to find the absolute extrema of the function $f(x,y)=\sin x+\cos y+\sin (xy)$ on $\{ (x,y) \mid 0\le x\le 2\pi,~0\le y \le 2\pi \}$. I tried by finding the gradient of the function $f$, but it ...
0
votes
1answer
286 views

De Jong's Fifth Function's Minimum?

What is the minimum solution to De Jong's fifth function, in the range $-65.536\leqslant x_1\leqslant 65.536, -65.536\leqslant x_2\leqslant 65.536$?
1
vote
0answers
31 views

Sign of the Lagrange multiplier associated with an equality constraint

I am trying to determine conditions under which the Lagrange multiplier(s) associated with an equality constraint is(are) positive. In general, the multiplier of an equality constraint is not ...
1
vote
1answer
185 views

Baseball Roster Optimization

I'm trying to programmatically optimize a Fantasy Baseball Roster that requires a fixed number of players at position (2 Catchers, 5 Outfielders, etc.) and has a salary constraint (total draft price ...
0
votes
0answers
15 views

Monte Carlo simulations, accuracy of mean vs variance of answers

I am working on a Monte Carlo simulation where two inputs are being used, $N$ is the amount of simulations I use, and $M$ controls the detail of each simulation (specifically the amount of time step ...
0
votes
0answers
12 views

Combinatorial Optimization and Relaxation

There are a number of NP-hard optimization problems that may be formulated as either binary linear or quadratic programs, i.e. $\min_x c^tx $ s.t. $x \in K, x_i \in \{0,1\}$ or $\min_x x^t Q x $ s.t. ...
1
vote
1answer
297 views

Linear Programming with One Quadratic Equality Constraint

I have a problem which can be formulated as a Linear Programming with One Quadratic Equality Constraint: where variable x is n-dimensional vector and H is a Semi-Positive Definite n-by-n matrix. I ...
0
votes
2answers
51 views

How to solve the function $\max \sum_{i=1}^n \log(x_i \cdot \mu)$ with $\sum _{j=1}^b \mu_j = 1$

$$ \max_{\mu} \sum_{i=1}^n \log(x_i \cdot \mu)\qquad\text{with}\qquad \sum _{j=1}^b \mu_j = 1,\qquad \mu_i \ge 0,\qquad x_{ij} \ge 0 $$ The function is shown as above, where $x_i$ and $\mu$ are ...
0
votes
0answers
20 views

Simplex minimum ratio test fails on bounded problem

Consider the linear program $\max 3x_1 + x_2 \ @ \\ 3x_1+2x_2 -s_1 = 1 \\ 2x_1+x_2 +s_2 = 2 \\ x_1 \geq 0$ Leting $x_2 = x_2^+ + x_2^-$, introducing slack and solving phase 1 gives $\textbf{x}_b ...
0
votes
0answers
8 views

The set of extreme points

I need help to describe the set of extreme points for transport polyhedral ${x_{ij}}, \quad (i,j=1...n), \quad \sum\limits_{i=1}^{n}x_{ij}=1, \quad \sum\limits_{j=1}^{n}x_{ij}=1, \quad x_{ij} ≥ 0$
0
votes
0answers
13 views

Allocating students to advisors

I'm looking for an algorithm that will allocate advising slots to students. Suppose we have $n$ students and $m$ faculty members. Each of the students expresses an interest in talking to some ...
8
votes
2answers
1k views

Why are additional constraint and penalty term equivalent in ridge regression?

Tikhonov regularization (or ridge regression) adds a constraint that $\|\beta\|^2$, the $L^2$-norm of the parameter vector, is not greater than a given value (say $c$). Equivalently, it may solve ...
0
votes
0answers
12 views

Minimising the expected value

Given a Gaussian distribution, I sample a value, say $\alpha$ from the the normal distribution and then i use it as an input to a complex neural network-like function. Based on each $\alpha$, I get an ...
0
votes
0answers
21 views

Nonlinear non-convex semi-infinite programming with norm equality constraint

In optimization theory, semi-infinite programming (SIP) is an optimization problem with a finite number of variables and an infinite number of constraints, or an infinite number of variables and a ...
1
vote
1answer
27 views

Does point's neighborhood have no local extremum?

I have polynomial of some limited degree: $f(x,y) = a_1 + a_2x + a_3y + a_4xy + a_5x^2 + a_6y^2 + a_7x^2y + \ldots$ There is a point $p_0=(x_0,y_0)$, which is NOT a local extreme NOR inflection ...
0
votes
1answer
15 views

Optimization relaxtion quesiton

I have the following LP relaxation of an integer programme (the programme formed from the set cover problem) minimize $\sum_{j=1}^{m} w_{j}x_{j}$ subject to $\sum_{j:e_{i} \in S_{j}} x_{j} \geq 1$ ...
-1
votes
0answers
24 views

How do I give an example of a vector which minimises the following quantity?

I've been working through some past papers and have come across this part of a question I'm not sure if I'm answering correctly.. In previous parts we have to work out the eigenvalues of a vector, ...
1
vote
1answer
51 views

Partial derivative with matrices

I have reforumulated my problem of computing some quantities $\mathbf{a}\in R^{m}$ from $\mathbf{b}\in R^{n}$ in a matricial form: $$\mathbf{b} = (C\odot(\mathbf{1}_{n}\cdot \mathbf{a}^{T}))\cdot ...
0
votes
1answer
45 views

Matrix Derivative of this Equation

I'm trying to solve this minimization problem: $$ \min_{\Theta} \frac{C_1}{2} \sum_{j=1}^{N-1} \|\vec{\theta_{j+1}} - \vec{\theta_j}\|^2 ,$$ where $\Theta = (\vec{\theta_1}, \vec{\theta_2}, \ldots, ...
0
votes
1answer
20 views

Maximal Permutations of numbers with monotonic objective function

I felt confident in the validity of the following statement, but now that I've played with the proof more I'm starting to have a few minor doubts. Any thoughts? Suppose you have two partitions of ...
1
vote
0answers
14 views

Is optimal solution to dual not unique if optimal solution to the primal is degenerate?

If optimal solution to the primal is degenerate, does it necessarily follow that optimal solution to dual not unique? That is, is uniqueness an unnecessary assumption? Spin-off from here. In my ...
0
votes
1answer
31 views

Looking for Method to evaluate the optimal node rate vs number of simulation rate in a Monte Carlo simulation

I am currently working on evaluating an American Option using a Monte Carlo simulation, and I am getting answers but they vary quite a bit. The two variables that I can alter are number of simulations ...
0
votes
0answers
16 views

For convex $f:\mathbb{R}^n \to \mathbb{R}$, d is of minumum norm in $\partial f(x)$ if and only if $-d/||d||$ minimizes $f'(x:d)$ over $||d||\leq 1$.

Okay, so I am having some problems with convex analysis review before my optimization exam. I want to prove that For convex $f:\mathbb{R}^n \to \mathbb{R}$, d is of minimum norm in $\partial f(x)$ if ...
2
votes
3answers
74 views

Augmented Lagrangian

Consider the following equality constraint minimization problem: minimize $\text{ }f(x)$ subject to $Ax=b$ Its Lagrangian is then: $L(x,y) = f(x) + y^T(Ax-b)$ We can use then gradient ascent to ...
2
votes
0answers
34 views

Online stochastic convex optimization.

I need to find/approximate the argument that minimizes a stochastic convex function $F(\theta, Z)$: $$ {\arg\min_{\theta}} E_{Z}[ F(\theta, Z) ]$$ Where $Z$ is some random variable (we could assume ...
2
votes
1answer
39 views

Minimum Distance between a Triangle and a Distance Field 3D

I am looking for (possibly numerical) solution to this geometric problem: Given a filled 3D triangle $T = \text{conv}(p_1, p_2, p_3) \subseteq R^3$, and a distance field $D(x) : R^3 \to R$, what ...
0
votes
2answers
585 views

Optimal Basic Feasible Solutions

In linear programming, is it true that you can only have at most 2 optimal basic feasible solutions? If so, why?
2
votes
2answers
36 views

Optimization—Finding the Area of the Largest Isoceles Triangle

I managed to solve $(a)$. Since the area of a triangle is determined by $\frac{1}{2}$ base $\times$ height, and we already know the height, we just have to solve for the base. Using Pythagorean ...
0
votes
2answers
38 views

Applying mathematics to design

I need help on this and i am also curious to know what looks better, applying mathematics or using designer eye I asked a graphic designer to design my company logo. The width of the logo is ...
0
votes
2answers
16 views

What does the matrix derivative of this equation look like?

I'm trying to solve this minimization problem: $$ \min_{\Theta} \frac{C_1}{2} \sum_j^N ||\vec{\theta_j}||^2 $$ where $\Theta = (\vec{\theta_1}, \vec{\theta_2}, ..., \vec{\theta_N})$. (FYI, it's ...
2
votes
2answers
71 views

Conditional inequalities

Let a,b,c be positive real numbers such that $abc=1$. Prove that $$\frac 1{a^3(b+c)}+\frac 1{b^3(c+a)}+\frac 1{c^3(a+b)} \ge \frac 32$$ We can derive the following inequalities from the given equality ...
0
votes
1answer
16 views

Find the largest lower bound that covers p percent of the data

Suppose that you have a finite set $X\subseteq \mathbb R$, and you want to solve the following constrained optimization problem Find $\max a$ such that $\frac{|\{ x \in X: x>a \}|}{|X|}\ge ...
0
votes
0answers
23 views

Writing dual of LP gives infeasible optimal solution

I'm given the following optimization problem: $ \begin{array}{cccccccccc} \text{max } z & = & & & -4x_2 & + & 3x_3 & + & 2x_4 & - & 8x_5\\ && 3x_1 & ...
0
votes
1answer
33 views

Optimization problem with an added quadratic inequality constraint

Consider the following (non-convex) optimization problem on the real variables $\lambda_\ell^\pm$ with $\ell=1,\ldots,n$ \begin{align} \mbox{maximize}&\quad ...
1
vote
1answer
72 views

Scale ellipsoid maximally within polyhedron

Given an ellipsoid around the origin with scaling parameter $e$ in the form $x^T E x \leq e$ and a polyhedron $P$ given by $A x \leq b$, how can we define an optimization problem that maximizes e such ...
0
votes
0answers
11 views

Bicritiera combinatorial/linear optimization problem with an exponential number of non-dominated extreme point

In [Ruhe 1988] an instance of a bicriterial combinatorial optimization problem is constructed such that the number of non-dominated extreme points is exponential in the input size. Are there any ...
1
vote
0answers
29 views

Maximization question [duplicate]

I'm trying to find the maximum value of the function $f(x,y)=(ax+by)^p+x^p$ subject to the constraint $x^p+y^p=1$. Here, $a,b$ and $p$ are constants with $a,b>0$ and $p>1$, and $x,y>0$. I ...
0
votes
1answer
35 views

How do I see that every point inside the corresponding convex region in $\mathbb R^2$ belong to this set?

Convex set in $\mathbb R^2$. Suppose I use the convex operator $\text {conv}$ to create the convex set of $X = \{x_1, ... , x_n\} \subset \mathbb R^2$, that is $\text {conv}(X) = \{(1-\lambda)x_i + ...