Transcription of R Solution. R - Stanford Engineering Everywhere
{{id}} {{{paragraph}}}
Example: barber
R Solution. R - Stanford Engineering Everywhere
EE364a, Winter 2007-08 Prof. S. BoydEE364a Homework 4 involving 1- and -norms. Formulate the following problems as LPs. Ex-plain in detail the relation between the optimal solution of each problem and thesolution of its equivalent LP.(a) MinimizekAx bk ( -norm approximation).(b) MinimizekAx bk1( 1-norm approximation).(c) MinimizekAx bk1subject tokxk 1.(d) Minimizekxk1subject tokAx bk 1.(e) MinimizekAx bk1+kxk .In each problem,A Rm nandb Rmare given. (See for more problemsinvolving approximation and constrained approximation.)Solution.(a) Equivalent to the LPminimizetsubject toAx b t1Ax b the variablesx Rn,t R. To see the equivalence, assumexis fixed in thisproblem, and we optimize only overt. The constraints say that t aTkx bk tfor eachk, ,t |aTkx bk|, ,t maxk|aTkx bk|=kAx bk .Clearly, ifxis fixed, the optimal value of the LP isp (x) =kAx bk . Thereforeoptimizing overtandxsimultaneously is equivalent to the original problem.
4.29 Maximizing probability of satisfying a linear inequality. Let c be a random variable in Rn, normally distributed with mean ¯c and covariance matrix R. Consider the problem maximize prob(cTx ≥ α) subject to Fx g, Ax = b. Find the conditions under which this is equivalent to a convex or quasiconvex optimiza-
Loading..
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: