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)

1
vote
0answers
27 views

Two quadratic programming problems always same answer?

Was exploring quadratic programming optimization and for two types of problems the answers seemed to always equal. Is there an intuitive proof? Problem 1: Minimize $\tfrac{1}{2} \mathbf{x}^T ...
0
votes
1answer
19 views

Could someone point me in the right direction for this complex analysis equation?

I'm supposed to show that the maximum value of $|z^2+1|$ on the unit disk $|z|\leq1$ is 2. My teacher's hint was "triangle inequality". I've been racking my brain how to tie the triangle inequality ...
0
votes
0answers
24 views

Search Direction in Conjugate Gradient

Could you help me with a Conjugate Gradient question? In using CG to solve $Ax = b$, why is the search direction $p_{k+1}$ in CG chosen as a linear combination of the residual $r_k$ and previous ...
0
votes
0answers
17 views

Metric Entropy Upper Bounds

In the paper Information-Theoretic Determination of Minimax Rates of Convergence the authors present Theorem 3 as follows: If $M_2(\epsilon)$ is the $\ell_2$ packing entropy of a density class ...
1
vote
0answers
19 views

How do you calculate Up and Down Penalties on a Branch and Bound algorithm of a MILP?

My notes really don't explain this clearly at all, so I have no idea what to do. If I have the following MILP: In which I've been told to solve it using: (a) Rule 1 (choose the variable with the ...
0
votes
1answer
29 views

Labeling constraints in a MILP

A manufacturing company consisting of two plants intends to introduce up to three new products. The production quantity of each product can be any number, integer or non-integer, but there is an upper ...
0
votes
1answer
827 views

How do I construct the Jacobian for use in a Levenberg-Marquardt algorithm.

I am working on a 3D reconstruction system and I am looking to use a Levenberg-marquardt algorithm to do bundle adjustment. I am not too sure about how LM works and what it requires. The model I am ...
2
votes
0answers
20 views

What decides the structure of the dual variables taken in designing min-max type combinatorial optimization algorithms?

There are a bunch of combinatorial optimization problems like min cost flows and min weight perfect matchings that invoke duality and complimentary slackness to improve the primal feasible solution. ...
2
votes
1answer
300 views

Optimization problem, solve for ( )

Some years from now you are working for a book publisher. He asks you to give him a formula that will tell him the length and width of a book page that contains A square inches of printed text, a left ...
0
votes
1answer
60 views

No free lunch theorem

How does the No free lunch theorem apply in linear programming? Given a linear Programm. Calculate the optimal solution. Then you can calculate with the simplex method the solution in finite steps. ...
0
votes
0answers
59 views

Finding the Optimum Point on a Curve

I am trying to find the optimum point on a curve. More specifically the function of the curve I am looking at is: $f(x)=e^{0.3*ln(x+1)}$ and the curve looks like this: As I read in an old ...
0
votes
1answer
23 views

under what conditions the following matrix optimization has a unique solution?

So the problem is simple: Consider the following matrix optimization problem on matrix D. What conditions on the matrix dimensions should apply so that the solution to the minimum is unique. please ...
0
votes
0answers
14 views

Duality of Linear Program

Formulate the dual of the following linear problem: Min $\sum$ $\sum$ $c_{ij}$ $x_{ij}$ s.to $\sum$ $x_{ij}$ - $\sum$ $x_{ji}$ = 0, $\hspace{5mm}$ $x_{ij}$ >= $l_{ij}$ and $x_{ij}$ $\leq$ $u_{ij}$ ...
1
vote
3answers
107 views

Find the minimum of $f(x) = x^2+\sin(x)$

I need to find the minimum of $x^2+\sin(x)$ but I can't get an answer. So far I've done this: The first derivative is $f'(x)=\cos(x) + 2x=0$ and the second derivative $f''(x)=-\sin(x) +2$ From the ...
10
votes
1answer
216 views

Bidding Tic Tac Toe

In regular tic tac toe, both the players get alternate chances. This is a variant of that. Player $A$ has $\$x$ amount and player $B$ has $\$y$ amount as initial balance. Assume that $y>x$. Both ...
0
votes
0answers
20 views

Optimization - economics application, density functions and optimal labour supply

Assume and individuals preferences over consumption (c) and leisure ($l$) are described by the function: $u_i=c_i-a(b-l_i)^2$ The government provides lump-sum transfers to its citizens ($f$) ...
0
votes
0answers
24 views

Optimization (economics application) - Optimal tax rate and levels of education and housing

Every family has a preference over education (E) and housing (H) defined by the function: $U(E,H) = E^\alpha H^{1-\alpha}$ Households differ only with respect to income where household i's income is ...
1
vote
0answers
13 views

Optimal design for constrained Bayesian slope intercept model

Here is a problem I've been stuck on for quite a while. Consider the model \begin{equation} \mathbf{y}=\mathbf{H}\pmb{ \theta }+\pmb{\epsilon }. \end{equation} The design matrix is given by: ...
1
vote
2answers
36 views

Represent if-else or OR condition in a linear equation (optimisation with simplex algorithm)

I would like to write some linear equations and inequations to state that the sum of all possive x - C is smaller than L. As my ...
1
vote
0answers
61 views

When is $D \max G = \max D G$?

All matrices are real. The operator $\max$ on matrices returns the largest value in each row. We are interested in characterizing the set of matrices $D$ of size $n \times m$, $m < n$ such that we ...
2
votes
1answer
17 views

How to set up Lagrangian optimization with matrix constrains

Suppose we have a function $f: \mathbb{R} \to \mathbb{R} $ which we want to optimize subject to some constraint $g(x) \le c$ where $g:\mathbb{R} \to \mathbb{R} $ What we do is that we can set up a ...
2
votes
3answers
568 views

Proving the regular n-gon maximizes area for fixed perimeter.

It is often assumed that, given $n$, the regular $n$-gon will make the most efficient use of perimeter for area. I have never seen this proven. Anyone have something slick? (That is, how can we ...
0
votes
0answers
15 views

Difference between Newton's method and Gauss-Newton method

I know that the Gauss-Newton method is essentially Newton's method with the modification that the Gauss-Newton method it uses the approximation $2J^TJ$ (where $J$ is the Jacobian matrix) for the ...
2
votes
2answers
39 views

Given change in proportions and assuming minimum movement and a direction, calculate minimum proportion moving in that direction

Let $x_1, \dots, x_n$ with $\sum x_i = 1$ be proportions of a discrete distribution. Suppose the distribution changes and let $y_1, \dots, y_n$ be the subsequent proportions (and so $\sum y_i = 1$ ...
2
votes
0answers
38 views

Regularized least squares

In Image Restoration, a true image $f$ (in vector form) can be related to degraded data $y$ through a linear model of the form $$y = Hf + n$$ where $H$ is a 2D blurring matrix and $n$ is a noise ...
2
votes
1answer
272 views

Solving a 3x3 payoff matrix

I need some help solving the value of this payoff matrix and finding the optimal strategy: $$ \begin{matrix} 1 & 2 & 4 \\ -1 & 5 & 3 \\ 3 & 3 & ...
2
votes
0answers
45 views

Lagrange Multipliers for linear functionals

Say I have a Banach-space $X$ and linear (!) functionals $f,g$, and I'm trying to solve the constrained optimization problem $$max~f(x)\quad s.t.~g(x)= 0,~\Vert x\Vert\le 1.$$ Suppose I can show ...
0
votes
0answers
40 views

Maximizing a convex function outside a convex set?

I want to prove the following equality: \begin{equation*} \min_{x: x^2 \ge t - x} x^2 = \max_{0 \le \mu \le 1} \left( \mu t + \frac{\mu^2}{4 (\mu -1)} \right). \end{equation*} The objective function ...
0
votes
0answers
20 views

solver for non-convex matrix optimization with convex constraints

So here is the problem: $\max_{D} ~~ \|A+BD\|$ subject to $\|D\|<1$ (any norm you like) where matrices A and B are given. The cost function is evidently convex as well as the constraint, but ...
0
votes
1answer
18 views

Modified bin packing problem

What is known: There are $b_i$ boxes of type $i$, where $i=1, \ldots, n$. There are $3$ types of truck, each can carry at most $K_1$, $K_2$, and $K_3$ boxes respectively. Each type of truck ...
1
vote
1answer
25 views

Solving linear functions with constraints.

I have a table of data, for maximum available items in a given time period. With a constraint on how many of each items I can take in total. When I have taken the allowed amount of an item I can ...
0
votes
0answers
22 views

Reverse spline interpolation

Say I have a number of sets $(x, y)$ for $x \in \{0, 1, \dots, 255\}$. I want to find the least number of points to reproduce the set with a certain accuracy using linear interpolation. What is the ...
2
votes
0answers
33 views

Why this two SVM problems are equivalent?

Consider the two classification problem, our classifier is a hyperplane $w^T x+b=0$, where $w$ is the weight vector, $x$ is the input vector and $b$ is the bias. we have input $x_i\in ...
3
votes
1answer
383 views

Maximum likelihood estimators, hypergeometric and binomial

I'm trying to solve a two part problem. The set up is as follows: consider a bag with $\theta$ red marbles and $7-\theta$ blue marbles, with $\theta$ being unknown. Let $x$ denote the number of red ...
1
vote
1answer
765 views

primal to dual solution conversion ??

i have an optimization problem $$\text{ maximize } z=3x+4y$$ $$\text{ such that: } x+y ≤ 450 \text{ and } 2x+y ≤ 600$$ the optimal solution to this problems comes to be $x=0$; $y=450$; $p=150$ ...
1
vote
0answers
30 views

How to find the pdf and likelihood function for bernoulli gaussian model

[Paper - A computationally fast approach to maximum-likelihood deconvolution by Chong-Yung Chi, Jerry M. Mendel and Dan Hampson link presents an ...
0
votes
0answers
42 views

Solution of a linearly constrained quadratic programming problem

What is the solution of the following optimization problem: \begin{align} &\min{\mathbf{p}^\mathrm{T} \mathbf{B} \mathbf{p}}\\ &\text{subject to}: \mathbf{0}\leq{\mathbf{p}}\leq \mathbf{1}. ...
1
vote
2answers
51 views

Optimization: maximum area of a triangle under a parabola

Optimization: maximum area of a triangle in a parabola Inside a curve ($x^2-25$ - Parabola) a triangle is drawn with A as the vertex at the origin and the line joining points B and C lie on the ...
4
votes
2answers
59 views

Minimal number of questions

I am trying to solve the following problem : $49$ distinct numbers are written in a $7\times7$ cell board. You are allowed to pick any $3$ cells on the board and find out the set of numbers written in ...
0
votes
1answer
18 views

Does optimal solution always occur at a vertex?

Is it true that if LP $ \text{max} \{c^Tx \ | \ Ax \leq b \}$ has an optimal solution, then $\exists$ a vertex which is simultaneously an optimal solution for LP? I know this works for LP of a ...
0
votes
2answers
38 views

Optimization problem of two variable

Find two numbers $a$ and $b$ with $a \leq b$ such that $\int_a^b (6-x-x^2)dx$ has the largest value.
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
67 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 ...